3 ms·

That's interesting. I was aware of formal grammars and was toying with using stochastic parametric grammars to make generative programs, unknowingly a form of L

That's interesting. I was aware of formal grammars and was toying with using stochastic parametric grammars to make generative programs, unknowingly a form of L-system. I did one thing that goes beyond the grammars mentioned in the article and in wikipedia. You can assign an address to each leaf symbols. If you have binary rules of the form Ax->AxAx, this is easy as you are generating a binary tree and a path to that tree is just a binary number. If you are generating a programming language and each leaf node is a program statement, the return value of that statement can be assigned to that address. Then it is not difficult for each parameters in a parametric grammar to have a reference or reference offset back to these address. These address offsets can be stocastic parameters in the grammar. To me it's more like generating a full programming language since each statement has a return value and later statements can reference these value by address, a bit like putting the value in a variable and accessing it later. I then have a scheme to try to learn the stochastic parameters from output examples to try to produce programs that learn to generate specific output (I have had very limited success). The learning scheme includes trying to cluster together rules that generate similar subprograms. I have a longer description here: https://www.quora.com/What-deep-learning-ideas-have-you-tried-that-didnt-work/answer/Benoit-Essiambre https://www.quora.com/What-deep-learning-ideas-have-you-trie...

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 ago
  I'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.

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 ago
I'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.