Evolutionary Grammar Fuzzing

 This chapter is work in progress ("beta"). It is incomplete and may change at any time.

In this chapter, we introduce how to implement search-based test generation on grammars, using genetic improvement operators such as mutation and cross-over on derivation trees.


Grammar-Based Mutation

General idea: Take a derivation tree and a matching grammar; apply a random mutation.

from Grammars import EXPR_GRAMMAR
from GrammarFuzzer import display_tree
from Parser import EarleyParser
parser = EarleyParser(EXPR_GRAMMAR)
tree, *_ = parser.parse("1 + 2 * 3")
%3 0 <start> 1 <expr> 0->1 2 <term> 1->2 7 + 1->7 8 <expr> 1->8 3 <factor> 2->3 4 <integer> 3->4 5 <digit> 4->5 6 1 5->6 9 <term> 8->9 10 <factor> 9->10 14 * 9->14 15 <term> 9->15 11 <integer> 10->11 12 <digit> 11->12 13 2 12->13 16 <factor> 15->16 17 <integer> 16->17 18 <digit> 17->18 19 3 18->19
  1. Pick any node in the tree
  2. Produce a new expansion.

We have seen this for LangFuzzer already, right?

How about we factor this out (from the Parser notebook), and have two notebook on mutational (and genetic fuzzing):

  1. LangFuzzer – a chapter on

    • Mutating trees (randomly)
    • Mutating trees from a given population (the LangFuzz approach)
    • Tree recombination (and crossover)
  2. EvoGrammarFuzzer – a chapter on

    • Genetic improvement (using coverage only)
    • Genetic improvement (using a fitness function from search-based fuzzing)
def mutate_tree(tree, grammar):

Grammar-Based Crossover

Lessons Learned

  • Lesson one
  • Lesson two
  • Lesson three


Cite relevant works in the literature and put them into context, as in:

The idea of ensuring that each expansion in the grammar is used at least once goes back to Burkhardt [Burkhardt et al, 1967.], to be later rediscovered by Paul Purdom [Purdom et al, 1972.].


Close the chapter with a few exercises such that people have things to do. To make the solutions hidden (to be revealed by the user), have them start with


Your solution can then extend up to the next title (i.e., any markdown cell starting with #).

Running make metadata will automatically add metadata to the cells such that the cells will be hidden by default, and can be uncovered by the user. The button will be introduced above the solution.

Exercise 1: Title

Text of the exercise

# Some code that is part of the exercise

Some more text for the exercise

Exercise 2: Title

Text of the exercise

Creative Commons License The content of this project is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. The source code that is part of the content, as well as the source code used to format and display that content is licensed under the MIT License. Last change: 2019-03-25 02:48:44+13:00CiteImprint