Parsing Inputs

Parsing Inputs

We have seen how grammars can be used to generate strings from a language. They can also be used to break strings down to tell the parts of grammar they were made from. A derivation tree would show a broken down string and its hierarchical organization. You can use the derivation tree to recreate the string, or you can swap put branches to create new strings. This is how parsing can be used for fuzzing; get the parts of a valid input by parsing, and make a few changes, while following the grammar, and you’ll have new valid inputs to use.

Why Parsing for Fuzzing?

The book provides an example where parsing inputs for fuzzing could be useful. A program takes in a CSV file of vehicle details and processes each line, behaving differently with a van versus a car. Using a grammar for generating comma separated values, 1000 inputs are created. None of them work, however, as the vehicle types car and van aren’t included. The grammar is updated to include car and van as options, but many invalid inputs are still generated, having either the wrong amount of comma separated values or incorrect types of one or more of the values. The book suggests that instead the solution could be to get the “template” for valid inputs by parsing valid samples and using them for fuzzing.

def process_van(year, company, model):
    res = ["We have a %s %s van from %s vintage." % (company, model, year)]
    iyear = int(year)
    if iyear > 2010:
        res.append("It is a recent model!")
    else:
        res.append("It is an old but reliable model!")
    return res

def process_car(year, company, model):
    res = ["We have a %s %s car from %s vintage." % (company, model, year)]
    iyear = int(year)
    if iyear > 2016:
        res.append("It is a recent model!")
    else:
        res.append("It is an old but reliable model!")
    return res

CSV_GRAMMAR: Grammar = {
    '<start>': ['<csvline>'],
    '<csvline>': ['<items>'],
    '<items>': ['<item>,<items>', '<item>'],
    '<item>': ['<letters>'],
    '<letters>': ['<letter><letters>', '<letter>'],
    '<letter>': list(string.ascii_letters + string.digits + string.punctuation + ' \t\n')
}

'9w9J\'/,LU<"l,|,Y,Zv)Amvx,c\n'     Invalid entry
'(n8].H7,qolS'     not enough values to unpack (expected at least 4, got 2)
'\nQoLWQ,jSa'     not enough values to unpack (expected at least 4, got 2)
'K1,\n,RE,fq,%,,sT+aAb'     Invalid entry
"m,d,,8j4'),-yQ,B7"     Invalid entry
'g4,s1\t[}{.,M,<,\nzd,.am'     Invalid entry
',Z[,z,c,#x1,gc.F'     Invalid entry
'pWs,rT`,R'     not enough values to unpack (expected at least 4, got 3)
'iN,br%,Q,R'     Invalid entry
'ol,\nH<\tn,^#,=A'     Invalid entry

',h,van,|'     Invalid entry
'M,w:K,car,car,van'     Invalid entry
'J,?Y,van,van,car,J,~D+'     Invalid entry
'S4,car,car,o'     invalid literal for int() with base 10: 'S4'
'2*-,van'     not enough values to unpack (expected at least 4, got 2)
'van,%,5,]'     Invalid entry
'van,G3{y,j,h:'     Invalid entry
'$0;o,M,car,car'     Invalid entry
'2d,f,e'     not enough values to unpack (expected at least 4, got 3)
'/~NE,car,car'     not enough values to unpack (expected at least 4, got 3)

Using a Parser

A parser is “the part of a program that processes (structured) input”. It takes in an input string and outputs a derivation tree. Current parsers usually require two steps: initialize the parser and give it some input to parse.

An Ad Hoc Parser

The book creates a simple parser for demonstration. It takes the input and breaks it down by line into records, and then by comma separated value.Display_tree() is used to show a visual of an example derivation tree. More complicated examples are then given, such as handling commas in quoted values and handling embedded quotes. More and more changes would need to be made to this parser, and it would be difficult to ensure you’ve gotten everything. This is where formal parsers come in. Rather than trying to figure out every parsing rule needed on your own, a formal parser is created directly from a formal grammar (this includes context-free grammars).

def simple_parse_csv(mystring: str) -> DerivationTree:
    children: List[DerivationTree] = []
    tree = (START_SYMBOL, children)
    for i, line in enumerate(mystring.split('\n')):
        children.append(("record %d" % i, [(cell, [])
                                           for cell in line.split(',')]))
    return tree

Grammars in Parsing

A Parser Class

The Fuzzing Book describes two approaches for parsing:

• Lexer: Lexing breaks its source down into its smallest meaningful parts. Then, these “parts,” or “tokens,” are fed to the parser to be organized into a derivation tree.

• Tree Pruner: Use “a grammar that incorporates complete details of the syntax.” After parsing, “prune” the tree by replacing nodes that correspond to tokens with their corresponding strings as leaf nodes.

The parser class the book defines uses the Tree Pruner option, and includes a parse method which returns a list of derivation trees if the parse was successful.

Parsing Expression Grammars

A Parsing Expression Grammar (PEG) is a type of formal grammar that specifies the sequence of steps to take to parse a given string. Both PEGs and Context-Free Grammars use nonterminals and corresponding alternatives representing how to match each. PEGs, however, use ordered choice and will stop at the first match that succeeds. One technique for parsing PEGs is Packrat parsing, which is so named because it caches results to avoid recomputation.

PEG1 = {
    '<start>': ['a', 'b']
}

PEG2 = {
    '<start>': ['ab', 'abc']
}

Parsing Context-Free Grammars

Lessons Learned

• Grammars can be used to generate derivation trees for a given string.
• PEGs are intuitive, and easy to implement, but require care to write.
• Earley Parsers can parse arbitrary Context Free Grammars.

Return to Blog Post Listing