Part III: Syntactical 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 to systematically cover 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.