In the chapter on grammars, we have seen how to use grammars for very effective and efficient testing. In this chapter, we refine the previous string-based algorithm into a tree-based algorithm, which is much faster and allows for much more control over the production of fuzz inputs.
To use the code provided in this chapter, write
>>> from fuzzingbook.GrammarFuzzer import <identifier>
and then make use of the following features.
This chapter introduces GrammarFuzzer
, an efficient grammar fuzzer that takes a grammar to produce syntactically valid input strings. Here's a typical usage:
>>> from Grammars import US_PHONE_GRAMMAR
>>> phone_fuzzer = GrammarFuzzer(US_PHONE_GRAMMAR)
>>> phone_fuzzer.fuzz()
'(807)581-3463'
The GrammarFuzzer
constructor takes a number of keyword arguments to control its behavior. start_symbol
, for instance, allows to set the symbol that expansion starts with (instead of <start>
):
>>> area_fuzzer = GrammarFuzzer(US_PHONE_GRAMMAR, start_symbol='<area>')
>>> area_fuzzer.fuzz()
'547'
>>> import inspect
>>> print(inspect.getdoc(GrammarFuzzer.__init__))
Produce strings from `grammar`, starting with `start_symbol`.
If `min_nonterminals` or `max_nonterminals` is given, use them as limits
for the number of nonterminals produced.
If `disp` is set, display the intermediate derivation trees.
If `log` is set, show intermediate steps as text on standard output.
Internally, GrammarFuzzer
makes use of derivation trees, which it expands step by step. After producing a string, the tree produced can be accessed in the derivation_tree
attribute.
>>> display_tree(phone_fuzzer.derivation_tree)
In the internal representation of a derivation tree, a node is a pair (symbol
, children
). For nonterminals, symbol
is the symbol that is being expanded, and children
is a list of further nodes. For terminals, symbol
is the terminal string, and children
is empty.
>>> phone_fuzzer.derivation_tree
('<start>',
[('<phone-number>',
[('(', []),
('<area>',
[('<lead-digit>', [('8', [])]),
('<digit>', [('0', [])]),
('<digit>', [('7', [])])]),
(')', []),
('<exchange>',
[('<lead-digit>', [('5', [])]),
('<digit>', [('8', [])]),
('<digit>', [('1', [])])]),
('-', []),
('<line>',
[('<digit>', [('3', [])]),
('<digit>', [('4', [])]),
('<digit>', [('6', [])]),
('<digit>', [('3', [])])])])])
The chapter contains various helpers to work with derivation trees, including visualization tools.
In the previous chapter, we have introduced the simple_grammar_fuzzer()
function which takes a grammar and automatically produces a syntactically valid string from it. However, simple_grammar_fuzzer()
is just what its name suggests – simple. To illustrate the problem, let us get back to the expr_grammar
we created from EXPR_GRAMMAR_BNF
in the chapter on grammars:
expr_grammar = convert_ebnf_grammar(EXPR_EBNF_GRAMMAR)
expr_grammar
{'<start>': ['<expr>'], '<expr>': ['<term> + <expr>', '<term> - <expr>', '<term>'], '<term>': ['<factor> * <term>', '<factor> / <term>', '<factor>'], '<factor>': ['<sign-1><factor>', '(<expr>)', '<integer><symbol-1>'], '<sign>': ['+', '-'], '<integer>': ['<digit-1>'], '<digit>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], '<symbol>': ['.<integer>'], '<sign-1>': ['', '<sign>'], '<symbol-1>': ['', '<symbol>'], '<digit-1>': ['<digit>', '<digit><digit-1>']}
expr_grammar
has an interesting property. If we feed it into simple_grammar_fuzzer()
, the function gets stuck in an infinite expansion:
with ExpectTimeout(1):
simple_grammar_fuzzer(grammar=expr_grammar, max_nonterminals=3)
Traceback (most recent call last): File "<ipython-input-6-fbcda5f486bb>", line 2, in <module> simple_grammar_fuzzer(grammar=expr_grammar, max_nonterminals=3) File "Grammars.ipynb", line 69, in simple_grammar_fuzzer term = new_term File "Grammars.ipynb", line 47, in nonterminals File "Grammars.ipynb", line 47, in nonterminals File "ExpectError.ipynb", line 59, in check_time TimeoutError (expected)
Why is that so? The problem is in this rule:
expr_grammar['<factor>']
['<sign-1><factor>', '(<expr>)', '<integer><symbol-1>']
Here, any choice except for (expr)
increases the number of symbols, even if only temporary. Since we place a hard limit on the number of symbols to expand, the only choice left for expanding <factor>
is (<expr>)
, which leads to an infinite addition of parentheses.
The problem of potentially infinite expansion is only one of the problems with simple_grammar_fuzzer()
. More problems include:
It is inefficient. With each iteration, this fuzzer would go search the string produced so far for symbols to expand. This becomes inefficient as the production string grows.
It is hard to control. Even while limiting the number of symbols, it is still possible to obtain very long strings – and even infinitely long ones, as discussed above.
Let us illustrate both problems by plotting the time required for strings of different lengths.
trials = 50
xs = []
ys = []
for i in range(trials):
with Timer() as t:
s = simple_grammar_fuzzer(EXPR_GRAMMAR, max_nonterminals=15)
xs.append(len(s))
ys.append(t.elapsed_time())
print(i, end=" ")
print()
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
average_time = sum(ys) / trials
print("Average time:", average_time)
Average time: 0.17431333863904
%matplotlib inline
import matplotlib.pyplot as plt
plt.scatter(xs, ys)
plt.title('Time required for generating an output')
Text(0.5,1,'Time required for generating an output')
We see that (1) the time needed to generate an output increases quadratically with the length of that ouptut, and that (2) a large portion of the produced outputs are tens of thousands of characters long.
To address these problems, we need a smarter algorithm – one that is more efficient, that gets us better control over expansions, and that is able to foresee in expr_grammar
that the (expr)
alternative yields a potentially infinite expansion, in contrast to the other two.
To both obtain a more efficient algorithm and exercise better control over expansions, we will use a special representation for the strings that our grammar produces. The general idea is to use a tree structure that will be subsequently expanded – a so-called derivation tree. This representation allows us to always keep track of our expansion status – answering questions such as which elements have been expanded into which others, and which symbols still need to be expanded. Furthermore, adding new elements to a tree is far more efficient than replacing strings again and again.
Like other trees used in programming, a derivation tree (also known as parse tree or concrete syntax tree) consists of nodes which have other nodes (called child nodes) as their children. The tree starts with one node that has no parent; this is called the root node; a node without children is called a leaf.
The grammar expansion process with derivation trees is illustrated in the following steps, using the arithmetic grammar from
the chapter on grammars. We start with a single node as root of the tree, representing the start symbol – in our case <start>
.
tree
To expand the tree, we traverse it, searching for a nonterminal symbol $S$ without children. $S$ thus is a symbol that still has to be expanded. We then chose an expansion for $S$ from the grammar. Then, we add the expansion as a new child of $S$. For our start symbol <start>
, the only expansion is <expr>
, so we add it as a child.
tree
To construct the produced string from a derivation tree, we traverse the tree in order and collect the symbols at the leaves of the tree. In the case above, we obtain the string "<expr>"
.
To further expand the tree, we choose another symbol to expand, and add its expansion as new children. This would get us the <expr>
symbol, which gets expanded into <expr> + <term>
, adding three children.
tree
We repeat the expansion until there are no symbols left to expand:
tree
We now have a representation for the string 2 + 2
. In contrast to the string alone, though, the derivation tree records the entire structure (and production history, or derivation history) of the produced string. It also allows for simple comparison and manipulation – say, replacing one subtree (substructure) against another.
To represent a derivation tree in Python, we use the following format. A node is a pair
(SYMBOL_NAME, CHILDREN)
where SYMBOL_NAME
is a string representing the node (i.e. "<start>"
or "+"
) and CHILDREN
is a list of children nodes.
CHILDREN
can take some special values:
None
as a placeholder for future expansion. This means that the node is a nonterminal symbol that should be expanded further.[]
(i.e., the empty list) to indicate no children. This means that the node is a terminal symbol that can no longer be expanded.Let us take a very simple derivation tree, representing the intermediate step <expr> + <term>
, above.
derivation_tree = ("<start>",
[("<expr>",
[("<expr>", None),
(" + ", []),
("<term>", None)]
)])
To better understand the structure of this tree, let us introduce a function that visualizes this tree. We use the dot
drawing program from the graphviz
package algorithmically, traversing the above structure. (Unless you're deeply interested in tree visualization, you can directly skip to the example below.)
While we are interested at present in visualizing a derivation_tree
, it is in our interest to generalize the visualization procedure. In particular, it would be helpful if our method display_tree()
can display any tree like data structure. To enable this, we define a helper method extract_node()
that extract the current symbol and children from a given data structure. The default implementation simply extracts the symbol, children, and annotation from any derivation_tree
node.
def extract_node(node, id):
symbol, children, *annotation = node
return symbol, children, ''.join(str(a) for a in annotation)
While visualizing a tree, it is often useful to display certain nodes differently. For example, it is sometimes useful to distinguish between non-processed nodes and processed nodes. We define a helper procedure default_node_attr()
that provides the basic display, which can be customized by the user.
def default_node_attr(dot, nid, symbol, ann):
dot.node(repr(nid), dot_escape(unicode_escape(symbol)))
Similar to nodes, the edges may also require modifications. We define default_edge_attr()
as a helper procedure that can be customized by the user.
def default_edge_attr(dot, start_node, stop_node):
dot.edge(repr(start_node), repr(stop_node))
While visualizing a tree, one may sometimes wish to change the appearance of the tree. For example, it is sometimes easier to view the tree if it was laid out left to right rather than top to bottom. We define another helper procedure default_graph_attr()
for that.
def default_graph_attr(dot):
dot.attr('node', shape='plain')
Finally, we define a method display_tree()
that accepts these four functions extract_node()
, default_edge_attr()
, default_node_attr()
and default_graph_attr()
and uses them to display the tree.
def display_tree(derivation_tree,
log=False,
extract_node=extract_node,
node_attr=default_node_attr,
edge_attr=default_edge_attr,
graph_attr=default_graph_attr):
# If we import display_tree, we also have to import its functions
from graphviz import Digraph
counter = 0
def traverse_tree(dot, tree, id=0):
(symbol, children, annotation) = extract_node(tree, id)
node_attr(dot, id, symbol, annotation)
if children:
for child in children:
nonlocal counter
counter += 1
child_id = counter
edge_attr(dot, id, child_id)
traverse_tree(dot, child, child_id)
dot = Digraph(comment="Derivation Tree")
graph_attr(dot)
traverse_tree(dot, derivation_tree)
if log:
print(dot)
return dot
This is what our tree visualizes into:
display_tree(derivation_tree)
Say we want to customize our output, where we want to annotate certain nodes and edges. Here is a method display_annotated_tree()
that displays an annotated tree structure, and lays the graph out left to right.
def display_annotated_tree(tree, a_nodes, a_edges, log=False):
def graph_attr(dot):
dot.attr('node', shape='plain')
dot.graph_attr['rankdir'] = 'LR'
def annotate_node(dot, nid, symbol, ann):
if nid in a_nodes:
dot.node(repr(nid), "%s (%s)" % (dot_escape(unicode_escape(symbol)), a_nodes[nid]))
else:
dot.node(repr(nid), dot_escape(unicode_escape(symbol)))
def annotate_edge(dot, start_node, stop_node):
if (start_node, stop_node) in a_edges:
dot.edge(repr(start_node), repr(stop_node),
a_edges[(start_node, stop_node)])
else:
dot.edge(repr(start_node), repr(stop_node))
return display_tree(tree, log=log,
node_attr=annotate_node,
edge_attr=annotate_edge,
graph_attr=graph_attr)
display_annotated_tree(derivation_tree, {3: 'plus'}, {(1, 3): 'op'}, log=False)
If we want to see all the leaf nodes in a tree, the following all_terminals()
function comes in handy:
def all_terminals(tree):
(symbol, children) = tree
if children is None:
# This is a nonterminal symbol not expanded yet
return symbol
if len(children) == 0:
# This is a terminal symbol
return symbol
# This is an expanded symbol:
# Concatenate all terminal symbols from all children
return ''.join([all_terminals(c) for c in children])
all_terminals(derivation_tree)
'<expr> + <term>'
The all_terminals()
function returns the string representation of all leaf nodes. However, some of these leaf nodes may be due to nonterminals deriving empty strings. For these, we want to return the empty string. Hence, we define a new function tree_to_string()
to retrieve the original string back from a tree like structure.
def tree_to_string(tree):
symbol, children, *_ = tree
if children:
return ''.join(tree_to_string(c) for c in children)
else:
return '' if is_nonterminal(symbol) else symbol
tree_to_string(derivation_tree)
' + '
Let us now develop an algorithm that takes a tree with unexpanded symbols (say, derivation_tree
, above), and expands all these symbols one after the other. As with earlier fuzzers, we create a special subclass of Fuzzer
– in this case, GrammarFuzzer
. A GrammarFuzzer
gets a grammar and a start symbol; the other parameters will be used later to further control creation and to support debugging.
class GrammarFuzzer(Fuzzer):
def __init__(self, grammar, start_symbol=START_SYMBOL,
min_nonterminals=0, max_nonterminals=10, disp=False, log=False):
"""Produce strings from `grammar`, starting with `start_symbol`.
If `min_nonterminals` or `max_nonterminals` is given, use them as limits
for the number of nonterminals produced.
If `disp` is set, display the intermediate derivation trees.
If `log` is set, show intermediate steps as text on standard output."""
self.grammar = grammar
self.start_symbol = start_symbol
self.min_nonterminals = min_nonterminals
self.max_nonterminals = max_nonterminals
self.disp = disp
self.log = log
self.check_grammar()
In the following, we will add further methods to GrammarFuzzer
, using the hack already introduced for the MutationFuzzer
class. The construct
class GrammarFuzzer(GrammarFuzzer):
def new_method(self, args):
pass
allows us to add a new method new_method()
to the GrammarFuzzer
class. (Actually, we get a new GrammarFuzzer
class that extends the old one, but for all our purposes, this does not matter.)
Using this hack, let us define a helper method check_grammar()
that checks the given grammar for consistency:
class GrammarFuzzer(GrammarFuzzer):
def check_grammar(self):
assert self.start_symbol in self.grammar
assert is_valid_grammar(
self.grammar,
start_symbol=self.start_symbol,
supported_opts=self.supported_opts())
def supported_opts(self):
return set()
Let us now define a helper method init_tree()
that constructs a tree with just the start symbol:
class GrammarFuzzer(GrammarFuzzer):
def init_tree(self):
return (self.start_symbol, None)
f = GrammarFuzzer(EXPR_GRAMMAR)
display_tree(f.init_tree())
Next, we will need a helper function expansion_to_children()
that takes an expansion string and decomposes it into a list of derivation trees – one for each symbol (terminal or nonterminal) in the string. It uses the re.split()
method to split an expansion string into a list of children nodes:
def expansion_to_children(expansion):
# print("Converting " + repr(expansion))
# strings contains all substrings -- both terminals and nonterminals such
# that ''.join(strings) == expansion
expansion = exp_string(expansion)
assert isinstance(expansion, str)
if expansion == "": # Special case: epsilon expansion
return [("", [])]
strings = re.split(RE_NONTERMINAL, expansion)
return [(s, None) if is_nonterminal(s) else (s, [])
for s in strings if len(s) > 0]
expansion_to_children("<term> + <expr>")
[('<term>', None), (' + ', []), ('<expr>', None)]
The case of an epsilon expansion, i.e. expanding into an empty string as in <symbol> ::=
needs special treatment:
expansion_to_children("")
[('', [])]
Just like nonterminals()
in the chapter on Grammars, we provide for future extensions, allowing the expansion to be a tuple with extra data (which will be ignored).
expansion_to_children(("+<term>", ["extra_data"]))
[('+', []), ('<term>', None)]
We realize this helper as a method in GrammarFuzzer
such that it can be overloaded by subclasses:
class GrammarFuzzer(GrammarFuzzer):
def expansion_to_children(self, expansion):
return expansion_to_children(expansion)
With this, we can now take some unexpanded node in the tree, choose a random expansion, and return the new tree. This is what the method expand_node_randomly()
does, using a helper function choose_node_expansion()
to randomly pick an index from an array of possible children. (choose_node_expansion()
can be overloaded in subclasses.)
class GrammarFuzzer(GrammarFuzzer):
def choose_node_expansion(self, node, possible_children):
"""Return index of expansion in `possible_children` to be selected. Defaults to random."""
return random.randrange(0, len(possible_children))
def expand_node_randomly(self, node):
(symbol, children) = node
assert children is None
if self.log:
print("Expanding", all_terminals(node), "randomly")
# Fetch the possible expansions from grammar...
expansions = self.grammar[symbol]
possible_children = [self.expansion_to_children(
expansion) for expansion in expansions]
# ... and select a random expansion
index = self.choose_node_expansion(node, possible_children)
chosen_children = possible_children[index]
# Process children (for subclasses)
chosen_children = self.process_chosen_children(chosen_children,
expansions[index])
# Return with new children
return (symbol, chosen_children)
The generic expand_node()
method can later be used to select different expansion strategies; as of now, it only uses expand_node_randomly()
.
class GrammarFuzzer(GrammarFuzzer):
def expand_node(self, node):
return self.expand_node_randomly(node)
The helper function process_chosen_children()
does nothing; it can be overloaded by subclasses to process the children once chosen.
class GrammarFuzzer(GrammarFuzzer):
def process_chosen_children(self, chosen_children, expansion):
"""Process children after selection. By default, does nothing."""
return chosen_children
This is how expand_node_randomly()
works:
f = GrammarFuzzer(EXPR_GRAMMAR, log=True)
print("Before:")
tree = ("<integer>", None)
display_tree(tree)
Before:
print("After:")
tree = f.expand_node_randomly(tree)
display_tree(tree)
After: Expanding <integer> randomly
Let us now apply the above node expansion to some node in the tree. To this end, we first need to search the tree for unexpanded nodes. possible_expansions()
counts how many unexpanded symbols there are in a tree:
class GrammarFuzzer(GrammarFuzzer):
def possible_expansions(self, node):
(symbol, children) = node
if children is None:
return 1
return sum(self.possible_expansions(c) for c in children)
f = GrammarFuzzer(EXPR_GRAMMAR)
print(f.possible_expansions(derivation_tree))
2
The method any_possible_expansions()
returns True if the tree has any unexpanded nodes.
class GrammarFuzzer(GrammarFuzzer):
def any_possible_expansions(self, node):
(symbol, children) = node
if children is None:
return True
return any(self.any_possible_expansions(c) for c in children)
f = GrammarFuzzer(EXPR_GRAMMAR)
f.any_possible_expansions(derivation_tree)
True
Here comes expand_tree_once()
, the core method of our tree expansion algorithm. It first checks whether it is currently being applied on a nonterminal symbol without expansion; if so, it invokes expand_node()
on it, as discussed above.
If the node is already expanded (i.e. has children), it checks the subset of children which still have unexpanded symbols, randomly selects one of them, and applies itself recursively on that child.
The expand_tree_once()
method replaces the child in place, meaning that it actually mutates the tree being passed as an argument rather than returning a new tree. This in-place mutation is what makes this function particularly efficient. Again, we use a helper method (choose_tree_expansion()
) to return the chosen index from a list of children that can be expanded.
class GrammarFuzzer(GrammarFuzzer):
def choose_tree_expansion(self, tree, children):
"""Return index of subtree in `children` to be selected for expansion. Defaults to random."""
return random.randrange(0, len(children))
def expand_tree_once(self, tree):
"""Choose an unexpanded symbol in tree; expand it. Can be overloaded in subclasses."""
(symbol, children) = tree
if children is None:
# Expand this node
return self.expand_node(tree)
# Find all children with possible expansions
expandable_children = [
c for c in children if self.any_possible_expansions(c)]
# `index_map` translates an index in `expandable_children`
# back into the original index in `children`
index_map = [i for (i, c) in enumerate(children)
if c in expandable_children]
# Select a random child
child_to_be_expanded = \
self.choose_tree_expansion(tree, expandable_children)
# Expand in place
children[index_map[child_to_be_expanded]] = \
self.expand_tree_once(expandable_children[child_to_be_expanded])
return tree
Let's put it to use, expanding our derivation tree from above twice.
derivation_tree = ("<start>",
[("<expr>",
[("<expr>", None),
(" + ", []),
("<term>", None)]
)])
display_tree(derivation_tree)
f = GrammarFuzzer(EXPR_GRAMMAR, log=True)
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <expr> randomly
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <term> randomly
We see that with each step, one more symbol is expanded. Now all it takes is to apply this again and again, expanding the tree further and further.
With expand_tree_once()
, we can keep on expanding the tree – but how do we actually stop? The key idea here, introduced by Luke in \cite{Luke2000}, is that after inflating the derivation tree to some maximum size, we only want to apply expansions that increase the size of the tree by a minimum. For <factor>
, for instance, we would prefer an expansion into <integer>
, as this will not introduce further recursion (and potential size inflation); for <integer>
, likewise, an expansion into <digit>
is preferred, as it will less increase tree size than <digit><integer>
.
To identify the cost of expanding a symbol, we introduce two functions that mutually rely on each other:
symbol_cost()
returns the minimum cost of all expansions of a symbol, using expansion_cost()
to compute the cost for each expansion.expansion_cost()
returns the sum of all expansions in expansions
. If a nonterminal is encountered again during traversal, the cost of the expansion is $\infty$, indicating (potentially infinite) recursion.class GrammarFuzzer(GrammarFuzzer):
def symbol_cost(self, symbol, seen=set()):
expansions = self.grammar[symbol]
return min(self.expansion_cost(e, seen | {symbol}) for e in expansions)
def expansion_cost(self, expansion, seen=set()):
symbols = nonterminals(expansion)
if len(symbols) == 0:
return 1 # no symbol
if any(s in seen for s in symbols):
return float('inf')
# the value of a expansion is the sum of all expandable variables
# inside + 1
return sum(self.symbol_cost(s, seen) for s in symbols) + 1
Here's two examples: The minimum cost of expanding a digit is 1, since we have to choose from one of its expansions.
f = GrammarFuzzer(EXPR_GRAMMAR)
assert f.symbol_cost("<digit>") == 1
The minimum cost of expanding <expr>
, though, is five, as this is the minimum number of expansions required. (<expr>
$\rightarrow$ <term>
$\rightarrow$ <factor>
$\rightarrow$ <integer>
$\rightarrow$ <digit>
$\rightarrow$ 1)
assert f.symbol_cost("<expr>") == 5
Here's now a variant of expand_node()
that takes the above cost into account. It determines the minimum cost cost
across all children and then chooses a child from the list using the choose
function, which by default is the minimum cost. If multiple children all have the same minimum cost, it chooses randomly between these.
class GrammarFuzzer(GrammarFuzzer):
def expand_node_by_cost(self, node, choose=min):
(symbol, children) = node
assert children is None
# Fetch the possible expansions from grammar...
expansions = self.grammar[symbol]
possible_children_with_cost = [(self.expansion_to_children(expansion),
self.expansion_cost(
expansion, {symbol}),
expansion)
for expansion in expansions]
costs = [cost for (child, cost, expansion)
in possible_children_with_cost]
chosen_cost = choose(costs)
children_with_chosen_cost = [child for (child, child_cost, _) in possible_children_with_cost
if child_cost == chosen_cost]
expansion_with_chosen_cost = [expansion for (_, child_cost, expansion) in possible_children_with_cost
if child_cost == chosen_cost]
index = self.choose_node_expansion(node, children_with_chosen_cost)
chosen_children = children_with_chosen_cost[index]
chosen_expansion = expansion_with_chosen_cost[index]
chosen_children = self.process_chosen_children(
chosen_children, chosen_expansion)
# Return with a new list
return (symbol, chosen_children)
The shortcut expand_node_min_cost()
passes min()
as the choose
function, which makes it expand nodes at minimum cost.
class GrammarFuzzer(GrammarFuzzer):
def expand_node_min_cost(self, node):
if self.log:
print("Expanding", all_terminals(node), "at minimum cost")
return self.expand_node_by_cost(node, min)
We can now apply this function to close the expansion of our derivation tree, using expand_tree_once()
with the above expand_node_min_cost()
as expansion function.
class GrammarFuzzer(GrammarFuzzer):
def expand_node(self, node):
return self.expand_node_min_cost(node)
f = GrammarFuzzer(EXPR_GRAMMAR, log=True)
display_tree(derivation_tree)
if f.any_possible_expansions(derivation_tree):
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <term> at minimum cost
if f.any_possible_expansions(derivation_tree):
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <factor> at minimum cost
if f.any_possible_expansions(derivation_tree):
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <integer> at minimum cost
We keep on expanding until all nonterminals are expanded.
while f.any_possible_expansions(derivation_tree):
derivation_tree = f.expand_tree_once(derivation_tree)
Expanding <factor> at minimum cost Expanding <term> at minimum cost Expanding <factor> at minimum cost Expanding <integer> at minimum cost Expanding <integer> at minimum cost Expanding <digit> at minimum cost Expanding <digit> at minimum cost Expanding <digit> at minimum cost
Here is the final tree:
display_tree(derivation_tree)
We see that in each step, expand_node_min_cost()
chooses an expansion that does not increase the number of symbols, eventually closing all open expansions.
Especially at the beginning of an expansion, we may be interested in getting as many nodes as possible – that is, we'd like to prefer expansions that give us more nonterminals to expand. This is actually the exact opposite of what expand_node_min_cost()
gives us, and we can implement a method expand_node_max_cost()
that will always choose among the nodes with the highest cost:
class GrammarFuzzer(GrammarFuzzer):
def expand_node_max_cost(self, node):
if self.log:
print("Expanding", all_terminals(node), "at maximum cost")
return self.expand_node_by_cost(node, max)
To illustrate expand_node_max_cost()
, we can again redefine expand_node()
to use it, and then use expand_tree_once()
to show a few expansion steps:
class GrammarFuzzer(GrammarFuzzer):
def expand_node(self, node):
return self.expand_node_max_cost(node)
derivation_tree = ("<start>",
[("<expr>",
[("<expr>", None),
(" + ", []),
("<term>", None)]
)])
f = GrammarFuzzer(EXPR_GRAMMAR, log=True)
display_tree(derivation_tree)
if f.any_possible_expansions(derivation_tree):
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <term> at maximum cost
if f.any_possible_expansions(derivation_tree):
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <term> at maximum cost
if f.any_possible_expansions(derivation_tree):
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <expr> at maximum cost
We see that with each step, the number of nonterminals increases. Obviously, we have to put a limit on this number.
We can now put all three phases together in a single function expand_tree()
which will work as follows:
min_nonterminals
nonterminals. This phase can be easily skipped by setting min_nonterminals
to zero.max_nonterminals
nonterminals.We implement these three phases by having expand_node
reference the expansion method to apply. This is controlled by setting expand_node
(the method reference) to first expand_node_max_cost
(i.e., calling expand_node()
invokes expand_node_max_cost()
), then expand_node_randomly
, and finally expand_node_min_cost
. In the first two phases, we also set a maximum limit of min_nonterminals
and max_nonterminals
, respectively.
class GrammarFuzzer(GrammarFuzzer):
def log_tree(self, tree):
"""Output a tree if self.log is set; if self.display is also set, show the tree structure"""
if self.log:
print("Tree:", all_terminals(tree))
if self.disp:
display(display_tree(tree))
# print(self.possible_expansions(tree), "possible expansion(s) left")
def expand_tree_with_strategy(self, tree, expand_node_method, limit=None):
"""Expand tree using `expand_node_method` as node expansion function
until the number of possible expansions reaches `limit`."""
self.expand_node = expand_node_method
while ((limit is None
or self.possible_expansions(tree) < limit)
and self.any_possible_expansions(tree)):
tree = self.expand_tree_once(tree)
self.log_tree(tree)
return tree
def expand_tree(self, tree):
"""Expand `tree` in a three-phase strategy until all expansions are complete."""
self.log_tree(tree)
tree = self.expand_tree_with_strategy(
tree, self.expand_node_max_cost, self.min_nonterminals)
tree = self.expand_tree_with_strategy(
tree, self.expand_node_randomly, self.max_nonterminals)
tree = self.expand_tree_with_strategy(
tree, self.expand_node_min_cost)
assert self.possible_expansions(tree) == 0
return tree
Let us try this out on our example.
derivation_tree = ("<start>",
[("<expr>",
[("<expr>", None),
(" + ", []),
("<term>", None)]
)])
f = GrammarFuzzer(
EXPR_GRAMMAR,
min_nonterminals=3,
max_nonterminals=5,
log=True)
derivation_tree = f.expand_tree(derivation_tree)
Tree: <expr> + <term> Expanding <term> at maximum cost Tree: <expr> + <factor> / <term> Expanding <expr> randomly Tree: <term> + <factor> / <term> Expanding <term> randomly Tree: <factor> + <factor> / <term> Expanding <term> randomly Tree: <factor> + <factor> / <factor> / <term> Expanding <term> randomly Tree: <factor> + <factor> / <factor> / <factor> * <term> Expanding <factor> at minimum cost Tree: <factor> + <integer> / <factor> / <factor> * <term> Expanding <integer> at minimum cost Tree: <factor> + <digit> / <factor> / <factor> * <term> Expanding <factor> at minimum cost Tree: <integer> + <digit> / <factor> / <factor> * <term> Expanding <integer> at minimum cost Tree: <digit> + <digit> / <factor> / <factor> * <term> Expanding <factor> at minimum cost Tree: <digit> + <digit> / <integer> / <factor> * <term> Expanding <digit> at minimum cost Tree: <digit> + 9 / <integer> / <factor> * <term> Expanding <digit> at minimum cost Tree: 1 + 9 / <integer> / <factor> * <term> Expanding <term> at minimum cost Tree: 1 + 9 / <integer> / <factor> * <factor> Expanding <integer> at minimum cost Tree: 1 + 9 / <digit> / <factor> * <factor> Expanding <digit> at minimum cost Tree: 1 + 9 / 2 / <factor> * <factor> Expanding <factor> at minimum cost Tree: 1 + 9 / 2 / <factor> * <integer> Expanding <factor> at minimum cost Tree: 1 + 9 / 2 / <integer> * <integer> Expanding <integer> at minimum cost Tree: 1 + 9 / 2 / <integer> * <digit> Expanding <integer> at minimum cost Tree: 1 + 9 / 2 / <digit> * <digit> Expanding <digit> at minimum cost Tree: 1 + 9 / 2 / <digit> * 0 Expanding <digit> at minimum cost Tree: 1 + 9 / 2 / 3 * 0
display_tree(derivation_tree)
all_terminals(derivation_tree)
'1 + 9 / 2 / 3 * 0'
Based on this, we can now define a function fuzz()
that – like simple_grammar_fuzzer()
– simply takes a grammar and produces a string from it. It thus no longer exposes the complexity of derivation trees.
class GrammarFuzzer(GrammarFuzzer):
def fuzz_tree(self):
# Create an initial derivation tree
tree = self.init_tree()
# print(tree)
# Expand all nonterminals
tree = self.expand_tree(tree)
if self.log:
print(repr(all_terminals(tree)))
if self.disp:
display(display_tree(tree))
return tree
def fuzz(self):
self.derivation_tree = self.fuzz_tree()
return all_terminals(self.derivation_tree)
We can now apply this on all our defined grammars (and visualize the derivation tree along)
f = GrammarFuzzer(EXPR_GRAMMAR)
f.fuzz()
'(2 * 8 - 5 / 0) * 3 * 5 - (1 + 6) * 1 * 9 * 2'
After calling fuzz()
, the produced derivation tree is accessible in the derivation_tree
attribute:
display_tree(f.derivation_tree)
Let us try out the grammar fuzzer (and its trees) on other grammar formats.
f = GrammarFuzzer(URL_GRAMMAR)
f.fuzz()
'ftps://user:password@fuzzingbook.com/'
display_tree(f.derivation_tree)
f = GrammarFuzzer(CGI_GRAMMAR, min_nonterminals=3, max_nonterminals=5)
f.fuzz()
'+_+'
display_tree(f.derivation_tree)
How do we stack up against simple_grammar_fuzzer()
?
trials = 50
xs = []
ys = []
f = GrammarFuzzer(EXPR_GRAMMAR, max_nonterminals=20)
for i in range(trials):
with Timer() as t:
s = f.fuzz()
xs.append(len(s))
ys.append(t.elapsed_time())
print(i, end=" ")
print()
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
average_time = sum(ys) / trials
print("Average time:", average_time)
Average time: 0.0265340686799027
%matplotlib inline
import matplotlib.pyplot as plt
plt.scatter(xs, ys)
plt.title('Time required for generating an output')
Text(0.5,1,'Time required for generating an output')
Our test generation is much faster, but also our inputs are much smaller. We see that with derivation trees, we can get much better control over grammar production.
Finally, how does GrammarFuzzer
work with expr_grammar
, where simple_grammar_fuzzer()
failed? It works without any issue:
f = GrammarFuzzer(expr_grammar, max_nonterminals=10)
f.fuzz()
'(2 - 6 * 4 - 6 - 1 - 7) * 2 * 3'
With GrammarFuzzer
, we now have a solid foundation on which to build further fuzzers and illustrate more exciting concepts from the world of generating software tests. Many of these do not even require writing a grammar – instead, they infer a grammar from the domain at hand, and thus allow to use grammar-based fuzzing even without writing a grammar. Stay tuned!
This chapter introduces GrammarFuzzer
, an efficient grammar fuzzer that takes a grammar to produce syntactically valid input strings. Here's a typical usage:
phone_fuzzer = GrammarFuzzer(US_PHONE_GRAMMAR)
phone_fuzzer.fuzz()
'(807)581-3463'
The GrammarFuzzer
constructor takes a number of keyword arguments to control its behavior. start_symbol
, for instance, allows to set the symbol that expansion starts with (instead of <start>
):
area_fuzzer = GrammarFuzzer(US_PHONE_GRAMMAR, start_symbol='<area>')
area_fuzzer.fuzz()
'547'
print(inspect.getdoc(GrammarFuzzer.__init__))
Produce strings from `grammar`, starting with `start_symbol`. If `min_nonterminals` or `max_nonterminals` is given, use them as limits for the number of nonterminals produced. If `disp` is set, display the intermediate derivation trees. If `log` is set, show intermediate steps as text on standard output.
Internally, GrammarFuzzer
makes use of derivation trees, which it expands step by step. After producing a string, the tree produced can be accessed in the derivation_tree
attribute.
display_tree(phone_fuzzer.derivation_tree)
In the internal representation of a derivation tree, a node is a pair (symbol
, children
). For nonterminals, symbol
is the symbol that is being expanded, and children
is a list of further nodes. For terminals, symbol
is the terminal string, and children
is empty.
phone_fuzzer.derivation_tree
('<start>', [('<phone-number>', [('(', []), ('<area>', [('<lead-digit>', [('8', [])]), ('<digit>', [('0', [])]), ('<digit>', [('7', [])])]), (')', []), ('<exchange>', [('<lead-digit>', [('5', [])]), ('<digit>', [('8', [])]), ('<digit>', [('1', [])])]), ('-', []), ('<line>', [('<digit>', [('3', [])]), ('<digit>', [('4', [])]), ('<digit>', [('6', [])]), ('<digit>', [('3', [])])])])])
The chapter contains various helpers to work with derivation trees, including visualization tools.
Derivation trees (then frequently called parse trees) are a standard data structure into which parsers decompose inputs. The Dragon Book (also known as Compilers: Principles, Techniques, and Tools) \cite{Aho2006} discusses parsing into derivation trees as part of compiling programs. We also use derivation trees when parsing and recombining inputs.
The key idea in this chapter, namely expanding until a limit of symbols is reached, and then always choosing the shortest path, stems from Luke \cite{Luke2000}.
Tracking GrammarFuzzer
reveals that some methods are called again and again, always with the same values.
Set up a class FasterGrammarFuzzer
with a cache that checks whether the method has been called before, and if so, return the previously computed "memoized" value. Do this for expansion_to_children()
. Compare the number of invocations before and after the optimization.
Important: For expansion_to_children()
, make sure that each list returned is an individual copy. If you return the same (cached) list, this will interfere with the in-place modification of GrammarFuzzer
. Use the Python copy.deepcopy()
function for this purpose.
Some methods such as symbol_cost()
or expansion_cost()
return a value that is dependent on the grammar only. Set up a class EvenFasterGrammarFuzzer()
that pre-computes these values once upon initialization, such that later invocations of symbol_cost()
or expansion_cost()
need only look up these values.
In expand_tree_once()
, the algorithm traverses the tree again and again to find nonterminals that still can be extended. Speed up the process by keeping a list of nonterminal symbols in the tree that still can be expanded.
We could define expand_node_randomly()
such that it simply invokes expand_node_by_cost(node, random.choice)
:
class ExerciseGrammarFuzzer(GrammarFuzzer):
def expand_node_randomly(self, node):
if self.log:
print("Expanding", all_terminals(node), "randomly by cost")
return self.expand_node_by_cost(node, random.choice)
What is the difference between the original implementation and this alternative?