Fuzzing Grammars in Python: gramfuzz

Grammar-based fuzzing is not new, nor is my grammar-based fuzzer; however, this is my fifth, best, and favorite rewrite of it. My grammar fuzzer started with the original version in ruby, and then over the years was rewritten once more in ruby and twice in Python. This version is the third Python rewrite.

Readers and friends, meet gramfuzz (https://github.com/d0c-s4vage/gramfuzz, docs), my fifth-generation grammar-based fuzzer.

Installation

gramfuzz can be downloaded from github, or can be installed via pip:

pip install gramfuzz

Intro

gramfuzz doesn’t rely on a separate language or grammars defined in *BNF (although they will be importable in the future). Instead, grammars are defined directly in Python. Take, for example, the grammar below that describes roman numerals:

       <roman> ::= <hundreds> <tens> <units>
    <hundreds> ::= <low hundreds> | CD | D <low hundreds> | CM
<low hundreds> ::= e | <low hundreds> C
        <tens> ::= <low tens> | XL | L <low tens> | XC
    <low tens> ::= e | <low tens> X
       <units> ::= <low units> | IV | V <low units> | IX
   <low units> ::= e | <low units> I

The BNF grammar above can be implemented in Python with gramfuzz like so:

class RDef(Def): cat="roman-numeral-def"
class RRef(Ref): cat="roman-numeral-def"

# top-level rule
Def("roman-numeral",
    RRef("hundreds"), RRef("tens"), RRef("units"),
cat="roman-numeral")

# helper rules
RDef("hundreds",
    RRef("low-hundreds") | "CD" | And("D", RRef("low-hundreds")) | "CM"
)
RDef("low-hundreds",
    And(RRef("low-hundreds"), "C") | ""
)
RDef("tens",
    RRef("low-tens") | "XL" | And("L", RRef("low-tens")) | "XC"
)
RDef("low-tens",
    And(RRef("low-tens"), "X") | ""
)
RDef("units",
    RRef("low-units") | "IV" | And("V", RRef("low-units") | "IX")
)
RDef("low-units",
    And(RRef("low-units"), "I") | ""
)

To use a defined grammar, one must create a GramFuzzer instance, load the desired grammar(s), and then tell the GramFuzzer object how many random rules to generate and from which category the rules should randomly be chosen:

import gramfuzz

fuzzer = gramfuzz.GramFuzzer()
fuzzer.load_grammar("roman_numeral.py")

for roman_numeral in fuzzer.gen(cat="roman-numeral", num=10):
    print(roman_numeral)

Which would yield output like this:

python example.py
CDI
CMXCVII
CLXIV
DCIV
DCCXLIV
CDLV
CMIV
CMLIV
CXCI
CLXVII

Benefits of Defining Grammars in Python

Having the grammar defined in Python allows one to do things that typically wouldn’t be doable in a normal (E)BNF grammar, unless near-scripting abilities were added into the grammar language itself; however, at that point I think I would rather use Python directly.

As an example of where having the grammar defined in Python is useful, I implemented the python 2.7 ~EBNF grammar in gramfuzz.

The “suite” rule in the Python 2.7 grammar is the rule that defines a new block of code (and thus a new indentation level). Notice how two special rules are defined to track the indentation level of the code (the “INDENT” and “DEDENT” rules):

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

Below is the implementation of the “suite” rule in gramfuzz. Notice how the INDENT/DEDENT logic are defined in new gramfuzz.Field subclasses that can be used by other rules:

INDENT_LEVEL = 0
class INDENT(Field):
    def build(self, pre=None, shortest=False):
        global INDENT_LEVEL
        INDENT_LEVEL += 1
        # indent one extra time
        return "    "
class DEDENT(Field):
    def build(self, pre=None, shortest=False):
        global INDENT_LEVEL
        INDENT_LEVEL -= 1
        return NEWLINE().build(pre, shortest=shortest)
class NEWLINE(Field):
    def build(self, pre=None, shortest=False):
        return "\n" + ("    " * INDENT_LEVEL)


PyDef("suite", Or(
    PyRef("simple_stmt"),
    And(
        NEWLINE, INDENT, PLUS(PyRef("stmt")), DEDENT
    )
))

Running the example script found in the source code:

python example.py -g python27 -n 1 -s 13337 --max-recursion 7

Yields the randomly-generated python code below:

print  >> (  )  if -56  else (  ) ; continue; global NkwRAqm, tOULPPwSf, kkWiy, Gvk, KBcgMqrk, QOb, Kibpj, vkDYRM; exec "V"  | edwpvwkC  | (  )  | {  }  | [  ]   | [  ]   | "BAnfxFleGs" in nnvYJhOE  if (  )  else [  ]  ; print  >> [  ]  ; global tXUwFWr, tIDHIA; break
from .......... import JmjgP
def TgdQjLJ(cuDiSCoYd="tDe" , DNhf=(  ) , NhtErVF, BNZUubHZ=0 , MDitNMRp=30 , ItUdL=jKx , oiJaAxm, QpMrAWoSk={  } , *IFjKBQ):
    pass
    try:pass
    except :pass
    pass
    pass
    
if lambda : nMgyB :pass;
else:
    def hko():pass
    pass
    pass
    def cdq():pass
    class UJobDb:pass
    try:pass
    finally:pass

Gotchas

You may notice that the code generated isn’t exactly valid Python. In fact, running it yields the following error:

  File "/tmp/test.py", line 3
 def TgdQjLJ(cuDiSCoYd="tDe" , DNhf=(  ) , NhtErVF, BNZUubHZ=0 , MDitNMRp=30 , ItUdL=jKx , oiJaAxm, QpMrAWoSk={  } , *IFjKBQ):
SyntaxError: non-default argument follows default argument

The error above occurs due to the fact that additional post-processing occurs after Python lexes the generated code into tokens. The post-processing that Python’s parser performs enforces rules that are not expressed in its grammar (such as requiring all non-default arguments to come before default arguments). For those interested, this is the function in the CPython source that raises the SyntaxError above while creating an AST node for an arguments list.

Keep in mind that not all grammars that are used for parsing can be directly used to generate valid data, since additional rules may be contained in that data format’s parser that aren’t expressed in its grammar.

Happy fuzzing!

-James Johnson (@d0c_s4vage)