3 ms·
I’ve seen it suggested before, when I was looking into the bijectivity of parsing, that generating lexical-program L-systems (i.e. ASTs where the leaf symbols a
by derefr 7y ago
I’ve seen it suggested before, when I was looking into the bijectivity of parsing, that generating lexical-program L-systems (i.e. ASTs where the leaf symbols are a compiler’s lexemes) is a good way of turning a compiler’s BNF-grammar spec into a fuzzer for said compiler’s parser, and possibly, through it, the rest of the compiler.
I expect you could get pretty far by teaching AFL (http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/) to generate inputs “through” a BNF-grammar L-system—since AFL already has the ability to explore the execution-path-space of the program-under-test.
Personally, I’m intrigued about whether L-systems can be generalized into generators for Directed Acyclic Graphs, rather than just trees. Then you could directly generate (branch-and-label-containing) machine-code, and—hooked up to a tool like AFL—fuzz processors/emulators with it.
- feanaro 7y agoI've had this same idea before and used this process successfully for fuzzing interpreters, though it was partly manual, partly a hodge podge of shell scripts. There are already fuzzers based on this idea, for instance tavor (https://github.com/zimmski/tavor https://github.com/zimmski/tavor). On the purely generative side (no execution), there's blab (https://github.com/aoh/blab https://github.com/aoh/blab). What these lack is probability parameters for each rule so that the probability distribution isn't necessarily uniform.