Fuzzing with Grammars

Synopsis

The fuzzing book describes a grammar as “a mapping of nonterminal symbols to lists of alternative expansions.” In the book, nonterminal symbols are notated with angle brackets, like <nonterminal>. Each nonterminal will have a list of expansions to be made, eventually all leading to terminal symbols, the actual characters used in the input. For example, <digit>, a nonterminal, leads to the expansions ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]. Any of those numbers can be chosen to replace any space where <digit> appears in the grammar.

Input Languages

According to the fuzzing book, “all possible behaviors of a program can be triggered by input,” meaning that input is what changes how the code can behave. “Input” can be data from files, network connections, user input, etc. The set of all valid inputs to a program is called a language. For example, the Python language contains the set of all valid Python programs. Another example the book uses is how a regular expression like [a-z]* represents all sequences of lowercase letters.

Grammars

Grammars are the systems for specifying how input languages are generated. They are formulas used for expressing the syntax, or rules for how characters and symbols can be arranged. The grammars the book uses are context-free grammars which are one of the types of formal grammars that can be used to describe the syntax of programming languages. Context-free grammars are given their name because nonterminals can always be replaced with their expansions regardless of what surrounds them; they don’t need context to be replaced.

<start>  ::= <integer>
<integer> ::= <digit> | <digit><integer>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<start>   ::= <expr>
<expr>    ::= <term> + <expr> | <term> - <expr> | <term>
<term>    ::= <term> * <factor> | <term> / <factor> | <factor>
<factor>  ::= +<factor> | -<factor> | (<expr>) | <integer> | <integer>.<integer>
<integer> ::= <digit><integer> | <digit>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Representing Grammars in Python

The first step of representing grammars in Python is figuring out the format to display it with. The easiest way is to do this with a dictionary, where the keys are the nonterminals and the values are lists of expansions.

    DIGIT_GRAMMAR = {
    "<start>":
        ["<integer>"],

    "<integer>":
        ["<digit><integer>", "<digit>"],

    "<digit>":
        ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
}

Each key is a single nonterminal, which is what makes this a context-free grammar. Each item in a value list is what could possibly replace that nonterminal.

Some Definitions

The book then defines two functions: nonterminals and is_nonterminal. The former uses regular expressions to find all nonterminals to be replaced, and the latter checks if the nonterminals that are found are actually options in the grammar.

import re

RE_NONTERMINAL = re.compile(r'(<[^<> ]*>)')

def nonterminals(expansion):
    # In later chapters, we allow expansions to be tuples,
    # with the expansion being the first element
    if isinstance(expansion, tuple):
        expansion = expansion[0]

    return RE_NONTERMINAL.findall(expansion)

def is_nonterminal(s):
    return RE_NONTERMINAL.match(s)

A Simple Grammar Fuzzer

The book then builds a simple grammar fuzzer, using a while loop to keep replacing nonterminals with expansions until there are no more nonterminals left. The fuzzer also defines max_nonterminals and max_expansions to avoid infinite loops in case of recursion. Lastly, it has a logging option to show the process of the input being build from the grammar.

Visualizing Grammars

The fuzzing book provides an option to visualize grammars: Railroad Diagrams (also called Syntax Diagrams). These diagrams follow possible paths left to right to simulate the generation of an input.

Some Grammars

The book provides three example grammars: one for cgi_decode (a function introduced in the coverage chapter), one for generating URLs, and one that uses English to create actual sentences. These all show the uses that grammars can have.

Grammars as Mutation Seeds

A grammar is made to produce valid inputs. This can be useful for testing with valid inputs, of course, but it can also be useful in combination with mutation testing. Using grammars to generate valid inputs first gives the mutation testing a wider range of seeds to mutate from. This can help to find more bugs in the program being tested.

A Grammar Toolbox

The book also mentions a couple smaller pieces of information that can be useful when working with grammars.

• Escapes: When using < and > to denote nonterminals, it can be useful to have a way to escape them if they are needed in the input.
• Extending Grammars: How to add new nonterminals and expansions to an existing grammar using copy.
• Character Classes: Sometimes there are quicker ways to create a list with a lot of expansions, like using a function to generate a list from string.ascii_letters, rather than typing out every single letter.
• Grammar Shortcuts: Rather than requiring recursion to give any repetition, symbols like * and + can be used to denote zero or more, and one or more repetitions, respectively. Another shortcut is to use parentheses to symbolize that what is inside is optional.
• Grammar Extensions: Expansions can be included in a tuple, where the first element is the expansion and the second can be additional information if there are any constraints you may want, such as the minimum or maximum depth.

Checking Grammars

As with all code, testing is important. The book uses assert statements and runs is_valid_grammar to check that all symbols that occur are actually defined and that all symbols are actually reachable from the start symbol. For example, {"<start>": ["<x>"], "<y>": ["1"]} would not pass as <y> can never be reached.

Lessons Learned

• Grammars are the systems for specifying how input languages are generated.
• The set of all valid inputs to a program is called a language.
• Each nonterminal will have a list of expansions to be made, eventually all leading to terminal symbols.
• Fuzzing with grammars can be used in combination with mutation testing as a provider of valid seeds from which to mutate.

Return to Blog Post Listing