Grammars for Mutation Testing
Andreas Zeller
CISPA Helmholtz Center for Information Security

www.fuzzingbook.org@AndreasZeller

Saarbrücken

@FuzzingBook

─┐ CISPA | Center for IT-Security, Privacy and Accountability └─Scientific excellence in fundamental research
50,000,000 €/year • 500+ researchers─┐ CISPA | Center for IT-Security, Privacy and Accountability └─Fuzzing
Random Testing at the System Level[;x1-GPZ+wcckc];,N9J+?#6^6\e?]9lu2_%'4GX"0VUB[E/r~fApu6b8<{%siq8Zh.6{V,hr?;{Ti.r3PIxMMMv6{xS^+'Hq!AxB"YXRS@!
Kd6;wtAMefFWM(`|J_<1~o}z3K(CCzRH JIIvHz>_*.\>JrlU32~eGP?
lR=bF3+;y$3lodQ<B89!5"W2fK*vE7v{')KC-i,c{<[~m!]o;{.'}Gj\(X}EtYetrpbY@aGZ1{P!AZU7x#4(Rtn!q4nCwqol^y6}0|
Ko=*JK~;zMKV=9Nai:wxu{J&UV#HaU)*BiC<),`+t*gka<W=Z.
%T5WGHZpI30D<Pq>&]BS6R&j?#tP7iaV}-}`\?[_[Z^LBMPGFKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2D|vBy!^zkhdf3C5PAkR?V hn|
3='i2Qx]D$qs4O`1@fevnG'2\11Vf3piU37@55ap\zIyl"'f,$ee,J4Gw:cgNKLie3nx9(`efSlg6#[K"@WjhZ}r[Scun&sBCS,T[/
vY'pduwgzDlVNy7'rnzxNwI)(ynBa>%|b`;`9fG]P_0hdG~$@63]KAeEnQ7lU)3Pn,0)G/6N-wyzj/MTd#A;r@FuzzingBook

Bart Miller
University of Wisconsin-Madison@FuzzingBook

Fuzzing
Random Testing at the System Level

FuzzerUNIX utilities“ab’d&gfdfggg”

grep • sh • sed …

25%–33%@FuzzingBook

Grammar Fuzzing• Suppose you want to test a parser –to compile and execute a program• To get deep into the program, you needsyntactically correct inputs

Parser@FuzzingBook

LangFuzz (2012)• Fuzz tester for JavaScript
and other languages• Uses a full-fledged grammar
to generate inputs@FuzzingBook

JavaScript Grammar
If Statement
IfStatementfull ⇒if ParenthesizedExpression Statementfull| if ParenthesizedExpression StatementnoShortIf else Statementfull
IfStatementnoShortIf ⇒ if ParenthesizedExpression StatementnoShortIf else StatementnoShortIf

Switch Statement
SwitchStatement ⇒switch ParenthesizedExpression { }| switch ParenthesizedExpression { CaseGroups LastCaseGroup }CaseGroups ⇒«empty»| CaseGroups CaseGroup
CaseGroup ⇒ CaseGuards BlockStatementsPrefix@FuzzingBookhase IIIest case into
ter, check forand assertions

Fuzzing JavaScript
var haystack = "foo";
2 var re text = "^foo";
3 haystack += "x";4 re text += "(x)";JavaScript
5 var re = new RegExp(re text);
Parser6 re. test (haystack);
7 RegExp.input = Number();
30
Chromium+
MozillaSecurity
Rewards
8 print(RegExp.$1);
153,000 US$ in Bug Bounties

Figure 2: Test case generated by LangFuzz, crashing the
C. Holler
JavaScript interpreter when executing Line 8. The static
Holler,of
Herzig,Zeller:is"Fuzzing
with CodeUSENIX 2012
accessRegExpdeprecatedbut Fragments",
valid. Reportedas@FuzzingBook

LangFuzz (2012)• Fuzz tester for JavaScript and otherlanguages• Uses a full-fledged grammar to
generate inputs• Uses grammar

to parse and mutate existing inputs@FuzzingBookMutating with Grammars
To use a grammar for mutating code and data,
1. Parse an input into a derivation tree
2. Mutate the derivation tree
3. Write the tree out again
You need a grammar, a parser, and an unparser@FuzzingBook

A Grammar Framework in Python
We have implemented a full-fledged Python framework to
1. Specify grammars
2. Parse inputs into derivation trees
3. Mutate derivation trees
4. Write the tree out again

plus much much more;e.g. testingThis framework comes implemented as Jupyter notebooks@FuzzingBook

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

A Grammar in Python
EXPR_GRAMMAR = {"<start>": ["<expr>"],"<expr>":["<term> + <expr>", "<term> - <expr>", "<term>"],"<term>":["<factor> * <term>", "<factor> / <term>", "<factor>"],"<factor>": ["+<factor>", "-<factor>", "(<expr>)","<integer>.<integer>", "<integer>"],"<integer>": ["<digit><integer>", "<digit>"],"<digit>": ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]}@FuzzingBook

Parsing with Grammars
expr_input = "2 + -2"
expr_parser = EarleyParser(EXPR_GRAMMAR)
expr_trees = expr_parser.parse(expr_input)@FuzzingBookMutating with Grammars
def swap_plus_minus(tree):node, children = tree
if node == " + ":node = " - "elif node == " - ":node = " + "return node, children
def apply_mutator(tree, mutator):node, children = mutator(tree)
return node, [apply_mutator(c, mutator) for c in children]
mutated_tree = apply_mutator(expr_tree, swap_plus_minus)@FuzzingBook

Demo@FuzzingBook

Jupyter Notebooks• Very fast prototyping• Literate programmingwith examples (and tests!)• Data visualizations
Prototype for Python first; then go for a "serious" language like C@FuzzingBook

Learning Grammars
http://user:password@www.google.com:80/command?foo=bar&lorem=ipsum#fragment
http://www.guardian.co.uk/sports/worldcup#results
ftp://bob:12345@ftp.example.com/oss/debian7.iso

URL ::= PROTOCOL '://' AUTHORITY PATH ['?' QUERY] ['#' REF]
AUTHORITY ::= [USERINFO '@'] HOST [':' PORT]PROTOCOL ::= 'http' | 'ftp'
USERINFO ::= /[a-z]+:[a-z]+/
HOST ::= /[a-z.]+/PORT ::= '80'
PATH ::= /\/[a-z0-9.\/]*/QUERY ::= 'foo=bar&lorem=ipsum'
REF ::= /[a-z]+/
Höschele, Zeller: "Mining Input Grammars from Dynamic Taints", ASE 2016 @FuzzingBookhich is on our list of challenges to address (Section 7).
nal and pragmatic answer is that a “better” techniqueow exists is better than an “even better” technique
oes not yet exist—in particular if it can pave the way
ds this “even better” technique.

Parser-Directed Fuzzing

n

#

1
2
3
4
5
6
7
8
9
0

27
24
13
10
9
7
3
3
2
1

We track and satisfy comparisons in parsers to find language elements
Examples{ [ ( + & ? identi�er number . . .
+= == ++ /= &= |= != if in string . . .
=== !== <<= >>> for try let . . .
>>>= true null void with else . . .
false throw while break catch . . .
return delete typeof Object . . .
default finally indexOf
continue function debugger
undefined stringify
instanceof

JS tokens of length 3+ discovered
AFL

KLEE

pFuzzer

5,0 %

7,5 %

52,5 %

le 5. ��� tokens and their number for each length.

Mathis, Gopinath, Mera, Kampmann, Höschele, Zeller: Parser-Directed Fuzzing, PLDI 2019

@AndreasZellerDeep Fuzzing without Samples
PYGMALION prototype for Python programs
ꋶProgram

Test Inputs

ɢFuzzerUnder Test
Tests

Comparisonsɠ Parser-Directed
Test Generator

GrammarDynamic Taints

Inputs +Equivalence Classes

ɡGrammar
Learner

Perfect coverage, much faster than AFL, much better structure than KLEE
Gopinath, Mathis, Höschele, Kampmann, Zeller: "Sample-Free Learning of Input Grammars"@FuzzingBook

@FuzzingBook

A Grammar Framework in Python

A Grammar in Python

We have implemented a full-fledged Python framework to

EXPR_GRAMMAR = {"<start>": ["<expr>"],"<expr>":["<term> + <expr>", "<term> - <expr>", "<term>"],"<term>":["<factor> * <term>", "<factor> / <term>", "<factor>"],"<factor>": ["+<factor>", "-<factor>", "(<expr>)","<integer>.<integer>", "<integer>"],"<integer>": ["<digit><integer>", "<digit>"],"<digit>": ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]}1. Specify grammars
2. Parse inputs into derivation trees
3. Mutate derivation trees
4. Write the tree out again

plus much much more;e.g. testing

Grammars for Mutation TestingThis framework comes implemented as Jupyter notebooks@FuzzingBook

Jupyter Notebooks@FuzzingBook

Andreas Zeller• Very fast prototyping CISPA Helmholtz Center for Information Security• Literate programmingwith examples (and tests!)• Data visualizations
Prototype for Python first; then go for a "serious" language like C@FuzzingBook

www.fuzzingbook.org@FuzzingBook@AndreasZeller@FuzzingBookMutations with Grammars
A Chapter of “Generating Software Tests”

Author:Andreas Zeller,
Rahul Gopinath,
Marcel Böhme,Gordon Fraser, andChristian Holler

April 22, 2019

Contents
Mutations with Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Defining Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Fuzzing with Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Parsing with Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Mutating a Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Unparsing the Mutated Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6 Lots of mutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 Another Example: JSON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
5
6
8
9
9
10

2 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

1

List of Figures
List of Tables
List of Codes

A chapter of Generating Software Tests, by Andreas Zeller, Rahul Gopinath, Marcel Böhme,Gordon Fraser, and Christian Holler.
Copyright © 2018 by the authors; all rights reserved.

2

1 Mutations with Grammars
In this notebook, we make a very short and simple introduction on how to use thefuzzingbook framework for grammar-based mutation – both for data and for code.
Prerequisites• This chapter is meant to be self-contained.

1.1 Defining Grammars
We define a grammar using standard Python data structures. Suppose we want to encode thisgrammar:<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 | 911

import fuzzingbook_utils
from Grammars import syntax_diagram, is_valid_grammar,!→ convert_ebnf_grammar, srange, crange

In Python, we encode this as a mapping (a dictionary) from nonterminal symbols to a list of
possible expansions:
1
EXPR_GRAMMAR = {2”<start>”:3[”<expr>”],4
5
6”<expr>”:[”<term> + <expr>”, ”<term> - <expr>”, ”<term>”],7
8
9”<term>”:[”<factor> * <term>”, ”<factor> / <term>”, ”<factor>”],

10
11
12
13
14
15
16

”<factor>”:[”+<factor>”,”-<factor>”,”(<expr>)”,”<integer>.<integer>”,”<integer>”],

17
18
19

”<integer>”:[”<digit><integer>”, ”<digit>”],20

1 Mutations with Grammars

3

21
22

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

23

}

1

assert is_valid_grammar(EXPR_GRAMMAR)

1syntax_diagram(EXPR_GRAMMAR)

start

expr

expr

term

+

expr

term

-

expr

term

term

factor*term

factor/term

factorfactor

1 Mutations with Grammars

4+factor-factor(expr

integer.

)
integer

integer

integer

digit

integer
digit

digit

0

2

4

6

8

1

3

5

7

9

1.2 Fuzzing with Grammars
We mostly use grammars for fuzzing, as in here:
1
from GrammarFuzzer import GrammarFuzzer
1
2
3

expr_fuzzer = GrammarFuzzer(EXPR_GRAMMAR)
for i in range(10):print(expr_fuzzer.fuzz())

3.8 + --62.912 - ++4 - +5 * 3.0 * 4
7 * (75.5 - -6 + 5 - 4) + -(8 - 1) / 5 * 2(-(9) * +6 + 9 / 3 * 8 - 9 * 8 / 7) / -+-65(9 + 8) * 2 * (6 + 6 + 9) * 0 * 1.9 * 0(1 * 7 - 9 + 5) * 5 / 0 * 5 + 7 * 5 * 7
1 Mutations with Grammars5

-(6 / 9 - 5 - 3 - 1) - -1 / +1 + (9) / (8) * 6(+-(0 - (1) * 7 / 3)) / ((1 * 3 + 8) + 9 - +1 / --0) - 5 *(-+939.491)+2.9 * 0 / 501.19814 / --+--(6.05002)+-8.8 / (1) * -+1 + -8 + 9 - 3 / 8 * 6 + 4 * 3 * 5(+(8 / 9 - 1 - 7)) + ---06.30 / +4.39

1.3 Parsing with Grammars
We can parse a given input using a grammar:1

expr_input = ”2 + -2”

1

from Parser import EarleyParser, display_tree, tree_to_string1

expr_parser = EarleyParser(EXPR_GRAMMAR)

1expr_tree = list(expr_parser.parse(expr_input))[0]1display_tree(expr_tree)

1 Mutations with Grammars

6<start><expr><term>+<expr><factor><term><integer><factor><digit>-2<factor><integer><digit>2

Internally, each subtree is a pair of a node and a list of children (subtrees)
1

expr_tree('<start>',[('<expr>',[('<term>', [('<factor>', [('<integer>', [('<digit>', [('2', [])])])])]),(' + ', []),('<expr>',[('<term>',[('<factor>',[('-', []),

1 Mutations with Grammars7])])])])])('<factor>', [('<integer>', [('<digit>', [('2', [])])])])

1.4 Mutating a TreeWe define a simple mutator that traverses an AST to mutate it.
1
2
3
4
5
6
7

def swap_plus_minus(tree):node, children = tree
if node == ” + ”:
node = ” - ”
elif node == ” - ”:
node = ” + ”
return node, children3

def apply_mutator(tree, mutator):node, children = mutator(tree)
return node, [apply_mutator(c, mutator) for c in children]1

mutated_tree = apply_mutator(expr_tree, swap_plus_minus)

1

display_tree(mutated_tree)

12

1 Mutations with Grammars

8<start><expr><term>-<expr><factor><term><integer><factor><digit>-2<factor><integer><digit>2

1.5 Unparsing the Mutated Tree
To unparse, we traverse the tree and look at all terminal symbols:
1tree_to_string(mutated_tree)'2 - -2'

1.6 Lots of mutations
1
2
3
4

for i in range(10):s = expr_fuzzer.fuzz()
s_tree = list(expr_parser.parse(s))[0]s_mutated_tree = apply_mutator(s_tree, swap_plus_minus)

1 Mutations with Grammars

9

5
6

->

s_mutated = tree_to_string(s_mutated_tree)
print('' + s + '\n-> ' + s_mutated + '\n')8786.82 - +01.170 / 9.2 - +(7) + 1 * 9 - 0
8786.82 + +01.170 / 9.2 + +(7) - 1 * 9 + 0+-6 * 0 / 5 * (-(1.7 * +(-1 / +4.9 * 5 * 1 * 2) + -4.2 + (6 +-5) / (4 * 3 + 4)))-> +-6 * 0 / 5 * (-(1.7 * +(-1 / +4.9 * 5 * 1 * 2) - -4.2 - (6 -5) / (4 * 3 - 4)))->(6 * 2 + 5) * -(5) / (0 + 7) / 7 - -075 / 2(6 * 2 - 5) * -(5) / (0 - 7) / 7 + -075 / 2->

6 + 9 * 3 * 7 - 6 / 0 * 5 - 7 * 5 + 3 - 0
6 - 9 * 3 * 7 + 6 / 0 * 5 + 7 * 5 - 3 + 0->

93 * +-(0 / 0 - 0 - 4) / (2) / 1 - 2.49 - (7.0 / 9.1)
93 * +-(0 / 0 + 0 + 4) / (2) / 1 + 2.49 + (7.0 / 9.1)->

+0.6 * 1.62 * 3 / 7 * 5 - 645 / (3 * 4 - 2) / 7+0.6 * 1.62 * 3 / 7 * 5 + 645 / (3 * 4 + 2) / 7->(1 * 8 * 4 + 1) - +-+(2 - 8) / 0.76 * 3(1 * 8 * 4 - 1) + +-+(2 + 8) / 0.76 * 3->-+-+-(0 - 0) / 1 / 3 / 5 * 9 * 2 + +5.0 / (+(5) * 8 * 7)-+-+-(0 + 0) / 1 / 3 / 5 * 9 * 2 - +5.0 / (+(5) * 8 * 7)->

1 * ++6 - -(5 + 7 + 5 - 6 - 4) - 5.4 / 2 - +5 / 9
1 * ++6 + -(5 - 7 - 5 + 6 + 4) + 5.4 / 2 + +5 / 9->(1.5 * 1 + 9 - 3 + 3) - 6 / 6 + 1 + 0(1.5 * 1 - 9 + 3 - 3) + 6 / 6 - 1 - 0

1.7 Another Example: JSON
1

1
2
3

4

1
2
3

import string
CHARACTERS_WITHOUT_QUOTE = (string.digits+ string.ascii_letters+ string.punctuation.replace('”', '')!→ .replace('\\', '')+ ' ')
JSON_EBNF_GRAMMAR = {”<start>”: [”<json>”],”<json>”: [”<element>”],1 Mutations with Grammars

10

4
5

6
7
8
9
10
11
12
13
14
15
16

17
18
19
20
21
22
23
24

}

”<element>”: [”<ws><value><ws>”],”<value>”: [”<object>”, ”<array>”, ”<string>”, ”<number>”, ”!→ true”, ”false”, ”null”],”<object>”: [”{<ws>}”, ”{<members>}”],”<members>”: [”<member>(,<members>)*”],”<member>”: [”<ws><string><ws>:<element>”],”<array>”: [”[<ws>]”, ”[<elements>]”],”<elements>”: [”<element>(,<elements>)*”],”<element>”: [”<ws><value><ws>”],”<string>”: ['”' + ”<characters>” + '”'],”<characters>”: [”<character>*”],”<character>”: srange(CHARACTERS_WITHOUT_QUOTE),”<number>”: [”<int><frac><exp>”],”<int>”: [”<digit>”, ”<onenine><digits>”, ”-<digits>”, ”-<!→ onenine><digits>”],”<digits>”: [”<digit>+”],”<digit>”: ['0', ”<onenine>”],”<onenine>”: crange('1', '9'),”<frac>”: [””, ”.<digits>”],”<exp>”: [””, ”E<sign><digits>”, ”e<sign><digits>”],”<sign>”: [””, '+', '-'],”<ws>”: [”( )*”]

25
26

assert is_valid_grammar(JSON_EBNF_GRAMMAR)

1

JSON_GRAMMAR = convert_ebnf_grammar(JSON_EBNF_GRAMMAR)

1syntax_diagram(JSON_GRAMMAR)

start

json

json

element

1 Mutations with Grammars

11element

ws

value

ws

value

objectarray

stringnumber

true

false

null

object{{ws}

members}

members

membersymbol-3

memberws

string

ws

:

[

ws

]

elementarray[

1 Mutations with Grammars

elements]

12

elements

element

symbol-1-1

string"characters"characterscharacter-1

character

1 Mutations with Grammars

13

0

i

A

S

,

1

j

B

T

-

2

k

C

U

.

3

l

D

V

/

4

m

E

W

:

5

n

F

X

;

6

o

G

Y

<

7

p

H

Z

=

8

q

I

!

>

}

9

r

J

#

?

~

a

s

K

$

@

b

t

L

%

[

c

u

M

&

]

d

v

N

'

^

e

w

O

(

_

f

x

P

)

`

g

y

Q

*

{

h

z

R

+

|

number

int

frac

exp

int

1 Mutations with Grammars

14

digitonenine-digitsdigitsoneninedigitsdigitsdigit-1

digit

0
onenineonenine

1

2

3

4

5

6

.

digits

7

8

9

frac

1 Mutations with Grammars

15

exp

E

sign

digitse

signdigits

sign

+
-

ws

symbol-2-1

symbol,members,

elements

symbol-1

1 Mutations with Grammars

16

symbol-2

symbol-3

symbolsymbol-3

symbol-1

symbol-1-1

charactercharacter-1

symbol-1-1

character-1

digit-1

digit
digit

1 Mutations with Grammars

digit-1

17

symbol-2-1

symbol-2

symbol-2-1

1json_input = '{”conference”: ”ICSE”}'

1

json_parser = EarleyParser(JSON_GRAMMAR)1json_tree = list(json_parser.parse(json_input))[0]1display_tree(json_tree)

1 Mutations with Grammars

18

<start><json><element><ws><value><symbol-2-1><object><symbol-2-1>{<members>}<member><ws><symbol-2-1><string>"<characters>

<ws>

"

<symbol-3>:c<character-1><character>o<element><symbol-2-1><character-1><character>

<ws>

<ws>

<value><symbol-2-1><string><symbol-2><symbol-2-1>"<character-1><character>nf<symbol-2-1><characters>"<character-1><character-1><character><ws><character><character-1><character>eI<character-1><character><character-1><character>rC<character-1><character><character-1><character>eS<character-1><character><character-1><character>n<character-1>

E<character-1><character>c<character-1><character><character-1>

e4

def swap_venue(tree):
if tree_to_string(tree) == '”ICSE”':
tree = list(json_parser.parse('”ICST”'))[0]return tree

1

mutated_tree = apply_mutator(json_tree, swap_venue)

12
3

1 Mutations with Grammars

19

1

tree_to_string(mutated_tree)'{”conference”: ”ICST”}'

1 Mutations with Grammars

20

2 References

2 References21