Part III: Syntactic Fuzzing

This part introduces test generation at the syntactical level, that is, composing inputs from language structures.

• Grammars provide a specification of legal inputs to a program. Specifying inputs via a grammar allows for very systematic and efficient test generation, in particular for complex input formats.

• Efficient Grammar Fuzzing introduces tree-based grammar fuzzing algorithms, which are much faster and allow for much more control over the production of fuzz inputs.

• Grammar Coverage allows systematically covering elements of a grammar such that we maximize variety and do not miss out individual elements.

• Parsing Inputs shows how to use grammars to parse and decompose a given set of valid seed inputs into their corresponding derivation trees.

• Probabilistic Grammar Fuzzing gives grammars even more power by assigning probabilities to individual expansions.

• Fuzzing with Generators shows how to extend grammars with functions – pieces of code that get executed during grammar expansion, and that can generate, check, or change elements produced.

• Greybox Grammar Fuzzing makes use of the structural representation allows us to mutate, crossover, and recombine their parts in order to generate new valid, slightly changed inputs.

• Reducing Failure-Inducing Inputs presents techniques that automatically reduce and simplify failure-inducing inputs to a minimum in order to ease debugging.