Evolutionary Grammar Fuzzing#
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.
Prerequisites
You should have read the chapter on search-based test generation.
You should have read the chapter on recombining inputs.
import fuzzingbook_utils
import SearchBasedFuzzer
import LangFuzzer
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")
display_tree(tree)
Pick any node in the tree
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):
LangFuzzer
– a chapter onMutating trees (randomly)
Mutating trees from a given population (the LangFuzz approach)
Tree recombination (and crossover)
EvoGrammarFuzzer
– a chapter onGenetic improvement (using coverage only)
Genetic improvement (using a fitness function from search-based fuzzing)
def mutate_tree(tree, grammar):
pass
Grammar-Based Crossover#
Lessons Learned#
Lesson one
Lesson two
Lesson three
Next Steps#
Link to subsequent chapters (notebooks) here, as in:
Background#
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 \cite{Burkhardt1967}, to be later rediscovered by Paul Purdom \cite{Purdom1972}.
Exercises#
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
**Solution.**
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
pass
Some more text for the exercise
Solution. Some text for the solution
# Some code for the solution
2 + 2
4
Some more text for the solution
Exercise 2: Title#
Text of the exercise
Solution. Solution for the exercise