Contents

  1. Iterative fuzzer
  2. Artifacts

Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.

Fuzzing is one of the key tools in a security researcher’s tool box. It is simple to write a random fuzzer.




















Unfortunately, random fuzzing is not very effective for programs that accept complex
input languages such as those that expect JSON or any other structure in their input.
For these programs, the fuzzing can be much more effective if one has a model of their
input structure. A number of such tools exist
(1, 2, 3, 4).
But how difficult is it to write your own grammar based fuzzer?
The interesting thing is that, a grammar fuzzer is essentially a parser turned inside
out. Rather than consuming, we simply output what gets compared. With that idea in mind,
let us use one of the simplest parsers – (A PEG parser).














Now, all one needs is a grammar.














The driver is as follows:














This grammar fuzzer can be implemented in pretty much any programming language
that supports basic data structures.
What if you want the derivation tree instead? The following modified fuzzer
will get you the derivation tree which
can be used with fuzzingbook.GrammarFuzzer.tree_to_string














Using it














We now want a way to display this tree. We can do that as follows
We first define a simple option holder class.














We can now define our default drawing options for displaying a tree.
The default options include the vertical (|), the horizontal (–)
and the how the last line is represented (+)














We want to display the tree. This is simply display_tree.














The display_tree calls format_tree which is defined as follows














We can now show the tree














The corresponding string is














One problem with the above fuzzer is that it can fail to terminate the
recursion. So, what we want to do is to limit unbounded recursion to a fixed
depth. Beyond that fixed depth, we want to only expand those rules that are
guaranteed to terminate.



For that, we define the cost of expansion for each symbol in a grammar.
A symbol costs as much as the cost of the least cost rule expansion.














A rule costs as much as the cost of expansion of the most costliest symbol
in that rule + 1.














Here is an implementation that uses random expansions until
a configurable depth (max_depth) is reached, and beyond that, uses
purely non-recursive cheap expansions.














Using it:














Iterative fuzzer


One of the problems with the above fuzzer is that we use the Python stack to
keep track of the expansion tree. Unfortunately, Python is really limited in
terms of the usable stack depth. This can make it hard to generate deeply
nested trees. One alternative solution is to handle the stack management
ourselves as we show next.
First, we define an iterative version of the tree_to_string function called iter_tree_to_str() as below.














You can use it as follows:














Next, we add the iter_gen_key() to LimitFuzzer














Finally, we ensure that the iterative gen_key can be called by defining iter_fuzz().














Using it














The runnable Python source for this notebook is available here









Artifacts



The runnable Python source for this notebook is available here.



The installable python wheel simplefuzzer is available here.