Efficient Grammar Fuzzing

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.

The algorithm in this chapter serves as a foundation for several more techniques; this chapter thus is a "hub" in the book.

Prerequisites

An Insufficient Algorithm

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:

import fuzzingbook_utils
from Grammars import EXPR_EBNF_GRAMMAR, convert_ebnf_grammar, simple_grammar_fuzzer, is_valid_grammar, exp_string, exp_opts
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:

from ExpectError import ExpectTimeout
with ExpectTimeout(1):
    simple_grammar_fuzzer(grammar=expr_grammar, max_nonterminals=3)
Traceback (most recent call last):
  File "<ipython-input-5-fbcda5f486bb>", line 2, in <module>
    simple_grammar_fuzzer(grammar=expr_grammar, max_nonterminals=3)
  File "<string>", line 7, in simple_grammar_fuzzer
  File "<string>", line 7, in simple_grammar_fuzzer
  File "<string>", line 16, 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:

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

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

from Grammars import simple_grammar_fuzzer
from Grammars import START_SYMBOL, EXPR_GRAMMAR, URL_GRAMMAR, CGI_GRAMMAR
from Grammars import RE_NONTERMINAL, nonterminals, is_nonterminal
from Timer import Timer
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.16051781930029393
%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 effort increases quadratically over time, and (2) we can easily produce outputs that 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.

Derivation Trees

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
root \<start\> <start>

To expand the tree, we traverse it, searching for a symbol $S$ without children to expand, and 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
root \<start\> <start> \<expr\> <expr> \<start\>->\<expr\>

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
root \<start\> <start> \<expr\> <expr> \<start\>->\<expr\> \<expr\> <expr> \<expr\>->\<expr\> + + \<expr\>->+ \<term\> <term> \<expr\>->\<term\>

We repeat the expansion until there are no symbols left to expand:

tree
root \<start\> <start> \<expr\> <expr> \<start\>->\<expr\> \<expr\> <expr> \<expr\>->\<expr\> + + \<expr\>->+ \<term\> <term> \<expr\>->\<term\> \<term\> <term> \<expr\> ->\<term\> \<factor\> <factor> \<term\>->\<factor\> \<factor\> <factor> \<term\> ->\<factor\> \<integer\> <integer> \<factor\> ->\<integer\> \<digit\> <digit> \<integer\> ->\<digit\> 2 2 \<digit\> ->2 \<integer\> <integer> \<factor\>->\<integer\> \<digit\> <digit> \<integer\>->\<digit\> 2 2 \<digit\>->2

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.

Representing Derivation Trees

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:

  1. None as a placeholder for future expansion. This means that the node is a nonterminal symbol that should be expanded further.
  2. [] (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.)

from graphviz import Digraph
from IPython.display import display
import re
def dot_escape(s):
    """Return s in a form suitable for dot"""
    # s = s.replace("\\", "\\\\")
    s = re.sub(r'([^a-zA-Z0-9" ])', r"\\\1", s)
    return s
assert dot_escape("hello") == "hello"
assert dot_escape("<hello>, world") == "\\<hello\\>\\, world"
assert dot_escape("\\n") == "\\\\n"

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(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):
    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)
    display(dot)

This is what our tree visualizes into:

display_tree(derivation_tree)
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 + 1->3 4 <term> 1->4

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(symbol), a_nodes[nid]))
        else:
            dot.node(repr(nid), dot_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))

    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)
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 +  (plus) 1->3 op 4 <term> 1->4

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)
' + '

Expanding a Node

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.

from Fuzzer import Fuzzer
class GrammarFuzzer(Fuzzer):
    def __init__(self, grammar, start_symbol=START_SYMBOL,
                 min_nonterminals=0, max_nonterminals=10, disp=False, log=False):
        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())
%3 0 <start>

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

import random
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)

print("After:")
tree = f.expand_node_randomly(tree)
display_tree(tree)
Before:
%3 0 <integer>
After:
Expanding <integer> randomly
%3 0 <integer> 1 <digit> 0->1

Expanding a Tree

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)
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 + 1->3 4 <term> 1->4
f = GrammarFuzzer(EXPR_GRAMMAR, log=True)
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <term> randomly
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 + 1->3 4 <term> 1->4 5 <factor> 4->5
derivation_tree = f.expand_tree_once(derivation_tree)
display_tree(derivation_tree)
Expanding <factor> randomly
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 + 1->3 4 <term> 1->4 5 <factor> 4->5 6 <integer> 5->6

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.

Closing the Expansion

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 [Luke et al, 2000.], 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)
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 + 1->3 4 <term> 1->4 5 <factor> 4->5 6 <integer> 5->6
if f.any_possible_expansions(derivation_tree):
    derivation_tree = f.expand_tree_once(derivation_tree)
    display_tree(derivation_tree)
Expanding <integer> at minimum cost
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 + 1->3 4 <term> 1->4 5 <factor> 4->5 6 <integer> 5->6 7 <digit> 6->7
if f.any_possible_expansions(derivation_tree):
    derivation_tree = f.expand_tree_once(derivation_tree)
    display_tree(derivation_tree)
Expanding <expr> at minimum cost
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 4 + 1->4 5 <term> 1->5 3 <term> 2->3 6 <factor> 5->6 7 <integer> 6->7 8 <digit> 7->8
if f.any_possible_expansions(derivation_tree):
    derivation_tree = f.expand_tree_once(derivation_tree)
    display_tree(derivation_tree)
Expanding <digit> at minimum cost
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 4 + 1->4 5 <term> 1->5 3 <term> 2->3 6 <factor> 5->6 7 <integer> 6->7 8 <digit> 7->8 9 6 8->9

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 <term> at minimum cost
Expanding <factor> at minimum cost
Expanding <integer> at minimum cost
Expanding <digit> at minimum cost

Here is the final tree:

display_tree(derivation_tree)
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 8 + 1->8 9 <term> 1->9 3 <term> 2->3 4 <factor> 3->4 5 <integer> 4->5 6 <digit> 5->6 7 2 6->7 10 <factor> 9->10 11 <integer> 10->11 12 <digit> 11->12 13 6 12->13

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.

Node Inflation

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)
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 3 + 1->3 4 <term> 1->4
if f.any_possible_expansions(derivation_tree):
    derivation_tree = f.expand_tree_once(derivation_tree)
    display_tree(derivation_tree)
Expanding <expr> at maximum cost
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 6 + 1->6 7 <term> 1->7 3 <term> 2->3 4 + 2->4 5 <expr> 2->5
if f.any_possible_expansions(derivation_tree):
    derivation_tree = f.expand_tree_once(derivation_tree)
    display_tree(derivation_tree)
Expanding <expr> at maximum cost
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 9 + 1->9 10 <term> 1->10 3 <term> 2->3 4 + 2->4 5 <expr> 2->5 6 <term> 5->6 7 + 5->7 8 <expr> 5->8
if f.any_possible_expansions(derivation_tree):
    derivation_tree = f.expand_tree_once(derivation_tree)
    display_tree(derivation_tree)
Expanding <term> at maximum cost
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 12 + 1->12 13 <term> 1->13 3 <term> 2->3 4 + 2->4 5 <expr> 2->5 6 <term> 5->6 10 + 5->10 11 <expr> 5->11 7 <factor> 6->7 8 * 6->8 9 <term> 6->9

We see that with each step, the number of nonterminals increases. Obviously, we have to put a limit on this number.

Three Expansion Phases

We can now put all three phases together in a single function expand_tree() which will work as follows:

  1. Max cost expansion. Expand the tree using expansions with maximum cost until we have at least min_nonterminals nonterminals. This phase can be easily skipped by setting min_nonterminals to zero.
  2. Random expansion. Keep on expanding the tree randomly until we reach max_nonterminals nonterminals.
  3. Min cost expansion. Close the expansion with minimum cost.

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_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 <expr> at maximum cost
Tree: <term> + <expr> + <term>
Expanding <term> randomly
Tree: <factor> / <term> + <expr> + <term>
Expanding <term> randomly
Tree: <factor> / <term> + <expr> + <factor> * <term>
Expanding <expr> at minimum cost
Tree: <factor> / <term> + <term> + <factor> * <term>
Expanding <term> at minimum cost
Tree: <factor> / <term> + <factor> + <factor> * <term>
Expanding <factor> at minimum cost
Tree: <factor> / <term> + <integer> + <factor> * <term>
Expanding <factor> at minimum cost
Tree: <factor> / <term> + <integer> + <integer> * <term>
Expanding <term> at minimum cost
Tree: <factor> / <term> + <integer> + <integer> * <factor>
Expanding <integer> at minimum cost
Tree: <factor> / <term> + <integer> + <digit> * <factor>
Expanding <factor> at minimum cost
Tree: <factor> / <term> + <integer> + <digit> * <integer>
Expanding <term> at minimum cost
Tree: <factor> / <factor> + <integer> + <digit> * <integer>
Expanding <factor> at minimum cost
Tree: <factor> / <integer> + <integer> + <digit> * <integer>
Expanding <integer> at minimum cost
Tree: <factor> / <integer> + <digit> + <digit> * <integer>
Expanding <digit> at minimum cost
Tree: <factor> / <integer> + 4 + <digit> * <integer>
Expanding <digit> at minimum cost
Tree: <factor> / <integer> + 4 + 0 * <integer>
Expanding <factor> at minimum cost
Tree: <integer> / <integer> + 4 + 0 * <integer>
Expanding <integer> at minimum cost
Tree: <digit> / <integer> + 4 + 0 * <integer>
Expanding <integer> at minimum cost
Tree: <digit> / <integer> + 4 + 0 * <digit>
Expanding <integer> at minimum cost
Tree: <digit> / <digit> + 4 + 0 * <digit>
Expanding <digit> at minimum cost
Tree: 7 / <digit> + 4 + 0 * <digit>
Expanding <digit> at minimum cost
Tree: 7 / 0 + 4 + 0 * <digit>
Expanding <digit> at minimum cost
Tree: 7 / 0 + 4 + 0 * 4
display_tree(derivation_tree)
%3 0 <start> 1 <expr> 0->1 2 <expr> 1->2 21 + 1->21 22 <term> 1->22 3 <term> 2->3 14 + 2->14 15 <expr> 2->15 4 <factor> 3->4 8 / 3->8 9 <term> 3->9 5 <integer> 4->5 6 <digit> 5->6 7 7 6->7 10 <factor> 9->10 11 <integer> 10->11 12 <digit> 11->12 13 0 12->13 16 <term> 15->16 17 <factor> 16->17 18 <integer> 17->18 19 <digit> 18->19 20 4 19->20 23 <factor> 22->23 27 * 22->27 28 <term> 22->28 24 <integer> 23->24 25 <digit> 24->25 26 0 25->26 29 <factor> 28->29 30 <integer> 29->30 31 <digit> 30->31 32 4 31->32
all_terminals(derivation_tree)
'7 / 0 + 4 + 0 * 4'

Putting it all Together

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_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()
'+76 - +8 / 4 * (4 - 2) + (8 * 2 + 4 + 6)'

After calling fuzz(), the produced derivation tree is accessible in the derivation_tree attribute:

display_tree(f.derivation_tree)
%3 0 <start> 1 <expr> 0->1 2 <term> 1->2 12 - 1->12 13 <expr> 1->13 3 <factor> 2->3 4 + 3->4 5 <factor> 3->5 6 <integer> 5->6 7 <digit> 6->7 9 <integer> 6->9 8 7 7->8 10 <digit> 9->10 11 6 10->11 14 <term> 13->14 45 + 13->45 46 <expr> 13->46 15 <factor> 14->15 21 / 14->21 22 <term> 14->22 16 + 15->16 17 <factor> 15->17 18 <integer> 17->18 19 <digit> 18->19 20 8 19->20 23 <factor> 22->23 27 * 22->27 28 <term> 22->28 24 <integer> 23->24 25 <digit> 24->25 26 4 25->26 29 <factor> 28->29 30 ( 29->30 31 <expr> 29->31 44 ) 29->44 32 <term> 31->32 37 - 31->37 38 <expr> 31->38 33 <factor> 32->33 34 <integer> 33->34 35 <digit> 34->35 36 4 35->36 39 <term> 38->39 40 <factor> 39->40 41 <integer> 40->41 42 <digit> 41->42 43 2 42->43 47 <term> 46->47 48 <factor> 47->48 49 ( 48->49 50 <expr> 48->50 76 ) 48->76 51 <term> 50->51 62 + 50->62 63 <expr> 50->63 52 <factor> 51->52 56 * 51->56 57 <term> 51->57 53 <integer> 52->53 54 <digit> 53->54 55 8 54->55 58 <factor> 57->58 59 <integer> 58->59 60 <digit> 59->60 61 2 60->61 64 <term> 63->64 69 + 63->69 70 <expr> 63->70 65 <factor> 64->65 66 <integer> 65->66 67 <digit> 66->67 68 4 67->68 71 <term> 70->71 72 <factor> 71->72 73 <integer> 72->73 74 <digit> 73->74 75 6 74->75

Let us try out the grammar fuzzer (and its trees) on other grammar formats.

f = GrammarFuzzer(URL_GRAMMAR)
f.fuzz()
'ftp://user:password@fuzzingbook.com:80/'
display_tree(f.derivation_tree)
%3 0 <start> 1 <url> 0->1 2 <scheme> 1->2 4 :// 1->4 5 <authority> 1->5 14 <path> 1->14 16 <query> 1->16 3 ftp 2->3 6 <userinfo> 5->6 8 @ 5->8 9 <host> 5->9 11 : 5->11 12 <port> 5->12 7 user:password 6->7 10 fuzzingbook.com 9->10 13 80 12->13 15 / 14->15 17 16->17
f = GrammarFuzzer(CGI_GRAMMAR, min_nonterminals=3, max_nonterminals=5)
f.fuzz()
'%9a+a'
display_tree(f.derivation_tree)
%3 0 <start> 1 <string> 0->1 2 <letter> 1->2 9 <string> 1->9 3 <percent> 2->3 4 % 3->4 5 <hexdigit> 3->5 7 <hexdigit> 3->7 6 9 5->6 8 a 7->8 10 <letter> 9->10 13 <string> 9->13 11 <plus> 10->11 12 + 11->12 14 <letter> 13->14 15 <other> 14->15 16 a 15->16

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.02814632705412805
%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()
'(3 / 1 * 3 * 5) - (2 * 0 - 4 + 4)'

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!

Lessons Learned

  • Derivation trees are important for expressing input structure
  • Grammar fuzzing based on derivation trees
    1. is much more efficient than string-based grammar fuzzing,
    2. gives much better control over input generation, and
    3. effectively avoids running into infinite expansions.

Next Steps

Congratulations! You have reached one of the central "hubs" of the book. From here, there is a wide range of techniques that build on grammar fuzzing.

Extending Grammars

First, we have a number of techniques that all extend grammars in some form:

Applying Grammars

Second, we can apply grammars in a variety of contexts that all involve some form of learning it automatically:

Keep on expanding!

Background

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) [Aho et al, 2006.] 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 [Luke et al, 2000.].

Exercises

Exercise 1: Caching Method Results

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.

Exercise 2: Grammar Pre-Compilation

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.

Exercise 3: Maintaining Trees to be Expanded

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.

Exercise 4: Alternate Random Expansions

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?

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: 2018-12-10 15:56:40+01:00CiteImprint