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.

  • 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.

  • Parsing and Recombining Inputs shows how to use grammars to parse and decompose a given set of valid seed inputs into their corresponding derivation trees. This 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.