1 of 56

Grammar-Based Fuzzing

Using Input Features

Nikolas Havrikov

March 4, 2022

2 of 56

Grammar-Based Fuzzing Using Input Features

2

Outline

  1. Grammar-based fuzz testing
    1. Features / properties of inputs
    2. Modeling context of input elements
  2. Mapping input features to code
    • Predicting behavior
    • Targeting behavior

3 of 56

System Testing

3

Program under Test

Set of Test Inputs

4 of 56

Fuzzing

4

Program under Test

Test Input Generator

5 of 56

Grammar-Based Fuzzing

5

Program under Test

Test Input Generator

6 of 56

Grammar-Based Fuzzing

6

Program under Test

Test Input Generator

(𝑥 + 2) ∗ 5

(𝑥 ∗ 2) + 5

1337 - 2 ∗ 21

“foobar”

7 of 56

Grammars and Derivation Trees

7

(𝑥 + 2) ∗ 5

AddExpr

DecDigits

MultExpr

UnaryExpr

DecDigits

MultExpr

*

UnaryExpr

AddExpr

(

)

DecDigit

AddExpr

MultExpr

+

MultExpr

UnaryExpr

UnaryExpr

Identifier

DecDigit

x

2

5

Expr := AddExpr;

​

AddExpr := MultExpr

| AddExpr ("+" | "-") MultExpr;

​

MultExpr := UnaryExpr

| MultExpr ("∗" | "/" | "%") UnaryExpr;

​

UnaryExpr := Identifier

| "+" UnaryExpr

| "-" UnaryExpr

| "(" AddExpr ")"

| DecDigits;

​

DecDigits := DecDigit+;

DecDigit := "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9";

​

Identifier := "x" | "y" | "z";

MultExpr ("∗" | "/" | "%") UnaryExpr

DecDigits := DecDigit+

DecDigit :=

"(" AddExpr ")"

DecDigits

"5"

UnaryExpr :=

Expr := AddExpr

AddExpr :=

MultExpr :=

MultExpr

"2"

UnaryExpr

Identifier

Identifier := "x"

AddExpr ("+" | "-") MultExpr

AddExpr

MultExpr

MultExpr

*

UnaryExpr

UnaryExpr

AddExpr

(

)

AddExpr

MultExpr

+

MultExpr

UnaryExpr

Identifier

x

DecDigits

DecDigit

5

DecDigits

UnaryExpr

DecDigit

2

8 of 56

Grammars and Derivation Trees

8

AddExpr

MultExpr

MultExpr

UnaryExpr

DecDigits

DecDigit

UnaryExpr

AddExpr

AddExpr

MultExpr

UnaryExpr

DecDigits

DecDigit

MultExpr

UnaryExpr

Identifier

*

5

(

)

+

x

2

(𝑥 + 2) ∗ 5

9 of 56

Measuring Input Diversity

9

5𝑥 + 10

(𝑥 ∗ 2) + 5

(𝑥 + 2) ∗ 5

(𝑥 ∗ 2) + 5

10 of 56

Measuring Input Diversity

10

(𝑥 + 2) ∗ 5

(𝑥 ∗ 2) + 5

+

AddExpr

MultExpr

UnaryExpr

AddExpr

MultExpr

UnaryExpr

DecDigits

DecDigit

MultExpr

UnaryExpr

*

+

*

5

5

AddExpr

AddExpr

MultExpr

MultExpr

UnaryExpr

UnaryExpr

DecDigits

DecDigits

DecDigit

DecDigit

(

(

)

)

2

2

Identifier

Identifier

x

x

MultExpr

UnaryExpr

AddExpr

AddExpr

MultExpr

UnaryExpr

DecDigits

DecDigit

MultExpr

UnaryExpr

11 of 56

Grammar Graphs

11

Expr := AddExpr;

​

AddExpr := MultExpr

| AddExpr ("+" | "-") MultExpr;

​

MultExpr := UnaryExpr

| MultExpr ("∗" | "/" | "%") UnaryExpr;

​

UnaryExpr := Identifier

| "+" UnaryExpr

| "-" UnaryExpr

| "(" AddExpr ")"

| DecDigits;

​

DecDigits := DecDigit+;

DecDigit := "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9";

​

Identifier := "x" | "y" | "z";

AddExpr

|

~

MultExpr

|

UnaryExpr

~

AddExpr

|

MultExpr

+

-

|

Identifier

|

x

y

z

~

UnaryExpr

+

DecDigits

MultExpr

|

UnaryExpr

*

/

%

+

DecDigit

|

0

1

2

3

4

5

6

7

8

9

...

12 of 56

Grammar Graphs

12

AddExpr

AddExpr

MultExpr

|

|

~

UnaryExpr

MultExpr

|

UnaryExpr

*

/

%

|

~

|

MultExpr

+

-

Identifier

|

x

y

z

~

UnaryExpr

+

DecDigits

+

DecDigit

|

0

1

2

3

4

5

6

7

8

9

Expr := AddExpr;

​

AddExpr := MultExpr

| AddExpr ("+" | "-") MultExpr;

​

MultExpr := UnaryExpr

| MultExpr ("∗" | "/" | "%") UnaryExpr;

​

UnaryExpr := Identifier

| "+" UnaryExpr

| "-" UnaryExpr

| "(" AddExpr ")"

| DecDigits;

​

DecDigits := DecDigit+;

DecDigit := "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9";

​

Identifier := "x" | "y" | "z";

...

0

2

5

7

8

44

10

11

13

15

23

24

25

16

27

28

22

42

39

40

41

45

46

47

48

49

50

51

52

53

1

3

4

13 of 56

Grammar Graphs

13

Expr := AddExpr;

​

AddExpr := MultExpr

| AddExpr ("+" | "-") MultExpr;

​

MultExpr := UnaryExpr

| MultExpr ("∗" | "/" | "%") UnaryExpr;

​

UnaryExpr := Identifier

| "+" UnaryExpr

| "-" UnaryExpr

| "(" AddExpr ")"

| DecDigits;

​

DecDigits := DecDigit+;

DecDigit := "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9";

​

Identifier := "x" | "y" | "z";

|

~

|

~

|

|

~

+

|

2

...

AddExpr

0

MultExpr

2

AddExpr

5

0

44

-

11

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

UnaryExpr

28

DecDigits

22

DecDigit

42

x

39

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

|

|

MultExpr

7

UnaryExpr

8

Identifier

16

+

10

+

27

"+"

"+"

14 of 56

Grammar Graphs

14

MultExpr

2

+

10

+

27

Expr := AddExpr;

​

AddExpr := MultExpr

| AddExpr ("+" | "-") MultExpr;

​

MultExpr := UnaryExpr

| MultExpr ("∗" | "/" | "%") UnaryExpr;

​

UnaryExpr := Identifier

| "+" UnaryExpr

| "-" UnaryExpr

| "(" AddExpr ")"

| DecDigits;

​

DecDigits := DecDigit+;

DecDigit := "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9";

​

Identifier := "x" | "y" | "z";

|

~

|

~

|

|

~

+

|

2

...

AddExpr

0

AddExpr

5

0

44

-

11

UnaryExpr

15

*

23

/

24

%

25

UnaryExpr

28

DecDigits

22

DecDigit

42

x

39

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

|

|

UnaryExpr

8

Identifier

16

MultExpr

MultExpr

MultExpr

7

MultExpr

13

15 of 56

k-paths

15

|

|

~

|

|

~

|

|

~

+

|

2

...

AddExpr

0

MultExpr

2

AddExpr

5

MultExpr

7

UnaryExpr

8

0

44

+

10

-

11

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

Identifier

16

+

27

UnaryExpr

28

DecDigits

22

DecDigit

42

x

39

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

16 of 56

k-paths

16

~

|

~

|

~

+

|

2

...

AddExpr

5

0

44

+

10

-

11

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

+

27

UnaryExpr

28

DecDigits

22

DecDigit

42

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

MultExpr

7

|

|

AddExpr

0

MultExpr

2

x

39

|

|

UnaryExpr

8

Identifier

16

𝑥

17 of 56

k-paths

17

|

MultExpr

2

AddExpr

5

MultExpr

7

~

|

~

|

~

+

|

2

...

AddExpr

0

0

44

+

10

-

11

UnaryExpr

15

*

23

/

24

%

25

+

27

UnaryExpr

28

DecDigits

22

DecDigit

42

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

|

|

UnaryExpr

8

Identifier

16

|

x

39

MultExpr

13

𝑥 ∗ ?

𝑥 / ?

𝑥 % ?

18 of 56

k-paths

18

MultExpr

7

~

|

~

|

~

+

|

2

...

AddExpr

0

0

44

+

10

-

11

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

+

27

UnaryExpr

28

DecDigits

22

DecDigit

42

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

|

|

UnaryExpr

8

Identifier

16

|

x

39

|

MultExpr

2

AddExpr

5

AddExpr

MultExpr

UnaryExpr

Identifier

x

5

39

2

8

16

𝑥 + ?

𝑥 - ?

19 of 56

Measuring Input Diversity

19

MultExpr

UnaryExpr

Identifier

x

13

8

16

(𝑥 + 2) ∗ 5

(𝑥 ∗ 2) + 5

AddExpr

+

AddExpr

MultExpr

UnaryExpr

DecDigits

DecDigit

5

MultExpr

UnaryExpr

AddExpr

(

)

MultExpr

*

UnaryExpr

DecDigits

DecDigit

2

AddExpr

MultExpr

MultExpr

*

UnaryExpr

DecDigits

DecDigit

5

UnaryExpr

AddExpr

MultExpr

(

)

+

UnaryExpr

DecDigits

DecDigit

2

0

0

2

23

13

15

22

42

49

8

35

37

36

10

7

8

22

42

46

10

5

7

8

22

42

49

39

2

8

35

37

36

2

23

15

22

42

46

AddExpr

MultExpr

UnaryExpr

Identifier

x

5

39

2

8

16

AddExpr

MultExpr

UnaryExpr

Identifier

x

5

39

2

8

16

20 of 56

Generating Inputs

20

|

|

~

|

|

~

|

|

~

+

|

2

...

AddExpr

0

MultExpr

2

AddExpr

5

MultExpr

7

UnaryExpr

8

0

44

+

10

-

11

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

Identifier

16

+

27

UnaryExpr

28

DecDigits

22

DecDigit

42

x

39

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

AddExpr

MultExpr

UnaryExpr

Identifier

x

5

39

2

8

16

21 of 56

Generating Inputs

21

MultExpr

7

~

|

~

|

~

+

|

2

...

AddExpr

0

0

44

+

10

-

11

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

+

27

UnaryExpr

28

DecDigits

22

DecDigit

42

y

40

z

41

1

45

46

3

47

4

48

5

49

6

50

7

51

8

52

9

53

|

|

UnaryExpr

8

Identifier

16

|

x

39

|

MultExpr

2

AddExpr

5

AddExpr

MultExpr

UnaryExpr

Identifier

x

5

39

2

8

16

|

AddExpr

0

|

~

AddExpr

5

|

AddExpr

5

|

MultExpr

2

|

MultExpr

2

UnaryExpr

8

|

UnaryExpr

8

Identifier

16

|

Identifier

16

x

39

~

|

MultExpr

7

|

+

10

|

|

+

|

2

MultExpr

7

UnaryExpr

8

DecDigits

22

DecDigit

42

46

AddExpr

5

MultExpr

2

UnaryExpr

8

Identifier

16

x

39

𝑥 + 2

22 of 56

K-path Coverage

22

5

39

2

8

16

5

39

2

8

16

AddExpr

MultExpr

UnaryExpr

Identifier

x

5

39

2

8

16

23 of 56

Experimental Setup

23

k-path

(tribble)

n-random

(grammarinator)

%

%

> ? <

k

n

24 of 56

Evaluating k-path Generation

24

​

Subject

Function

SLOC

Version

Source

JSON

argo

parser

9650

5.4

http://argo.sourceforge.net/

fastjson

marshaller

208461

1.2.51

https://github.com/alibaba/fastjson

genson

marshaller

24761

1.4

https://github.com/owlike/genson

gson

marshaller

27732

2.8.5

https://github.com/google/gson

jackson-databind

marshaller

134547

2.9.8

https://github.com/FasterXML/jackson-databind

json-flattener

parser

2673

0.6.0

https://github.com/wnameless/json-flattener

json-java

parser

13240

20180813

https://github.com/stleary/JSON-java

json-simple

parser

2695

1.1.1

https://github.com/fangyidong/json-simple

json-cliftonlabs

parser

3307

3.0.2

https://github.com/cliftonlabs/json-simple

minimal-json

parser

9246

0.9.5

https://github.com/ralfstx/minimal-json

pojo

parser

25773

1.0.0

https://github.com/joelittlejohn/jsonschema2pojo

CSV

commons-csv

marshaller

6840

1.6

https://commons.apache.org/proper/commons-csv

jackson-csv

marshaller

11756

2.9.8

https://github.com/FasterXML/jackson-dataformats-text

jcsv

marshaller

870

1.4.0

https://code.google.com/archive/p/jcsv

sfm-csv

marshaller

100284

6.1.1

https://github.com/arnaudroger/SimpleFlatMapper

simplecsv

marshaller

13051

2.1

https://github.com/quux00/simplecsv

super-csv

marshaller

18299

2.4.0

https://github.com/super-csv/super-csv

URL

autolink

parser + detector

2078

0.9.0

https://github.com/robinst/autolink-java

galimatias

parser

5406

0.2.1

https://github.com/smola/galimatias

jurl

parser

2940

v0.3.0

https://github.com/anthonynsimon/jurl

url-detector

parser + detector

2945

0.1.17

https://github.com/linkedin/URL-Detector

MD

commonmark

transpiler

16377

0.11.0

https://github.com/atlassian/commonmark-java

markdown4j

transpiler

5371

2.2-cj-1.1

https://github.com/jdcasey/markdown4j

txtmark

transpiler

6270

0.13

https://github.com/rjeschke/txtmark

25 of 56

Evaluating k-path Generation

25

​

Subject

1-path

1-random

2-path

2-random

3-path

3-random

5-path

5-random

JSON

argo

0.4116

0.4000

0.4187

0.3963

0.4197

0.4092

0.4242

0.4187

fastjson

0.0364

0.0376

0.0404

0.0374

0.0413

0.0388

0.0431

0.0414

genson

0.0842

0.0866

0.0886

0.0864

0.0902

0.0883

0.0916

0.0905

gson

0.2080

0.2215

0.2264

0.2213

0.2294

0.2266

0.2352

0.2371

jackson-databind

0.0886

0.0926

0.0932

0.0924

0.0938

0.0935

0.0940

0.0952

json-flattener

0.5039

0.6246

0.6828

0.6235

0.7127

0.6609

0.7809

0.7475

json-java

0.1093

0.1377

0.1457

0.1310

0.1661

0.1441

0.1890

0.1733

json-simple

0.4427

0.4695

0.4870

0.4662

0.4931

0.4836

0.5093

0.5062

json-cliftonlabs

0.3355

0.3325

0.3445

0.3301

0.3446

0.3410

0.3478

0.3546

minimal-json

0.4158

0.3970

0.4267

0.3936

0.4163

0.4054

0.4174

0.4166

pojo

0.1246

0.1414

0.1428

0.1423

0.1597

0.1433

0.2112

0.1462

CSV

commons-csv

0.3828

0.3773

0.3903

0.3772

0.3984

0.3770

0.4034

0.3799

jackson-csv

0.1665

0.1527

0.1666

0.1523

0.1700

0.1532

0.1777

0.1573

jcsv

0.3287

0.3167

0.3337

0.3152

0.3374

0.3201

0.3400

0.3270

sfm-csv

0.0628

0.0686

0.0664

0.0686

0.0675

0.0686

0.0682

0.0686

simplecsv

0.3472

0.3377

0.3482

0.3368

0.3481

0.3395

0.3489

0.3439

super-csv

0.1560

0.1433

0.1589

0.1423

0.1646

0.1439

0.1646

0.1471

URL

autolink

0.4514

0.2861

0.4673

0.2861

0.5716

0.2859

0.6265

0.2889

galimatias

0.0879

0.0343

0.0897

0.0341

0.0875

0.0346

0.0873

0.0356

jurl

0.6790

0.6854

0.6807

0.6872

0.6933

0.6904

0.7095

0.7012

url-detector

0.4057

0.3273

0.4083

0.3244

0.4188

0.3342

0.4352

0.3458

MD

commonmark

0.6678

0.6253

0.6991

0.6322

0.7183

0.6419

0.7335

0.6634

markdown4j

0.6772

0.6817

0.7094

0.6851

0.7162

0.6931

0.7313

0.7129

txtmark

0.6017

0.6144

0.6291

0.6174

0.6348

0.6237

0.6498

0.6413

26 of 56

Evaluating k-path Generation

26

​

Subject

1-path

1-random

2-path

2-random

3-path

3-random

5-path

5-random

JSON

​

>

>

>

>

​

​

<

​

​

​

​

​

<

​

​

=

=

​

=

CSV

​

>

>

>

>

​

​

​

​

​

<

<

<

<

URL

​

>

>

>

>

​

​

​

<

<

=

MD

​

>

>

>

>

​

<

​

27 of 56

27

Outline

  • Grammar-based fuzz testing
    • Features / properties of inputs
    • Modeling context of input elements
  • Mapping input features to code
    • Predicting behavior
    • Targeting behavior

k-paths

}

28 of 56

Mapping Input Features to Code Locations

28

29 of 56

Mapping Input Features to Code Locations

29

5 ∗ (𝑥 + 2)

5 ∗ (𝑥 ∗ 2)

5𝑥 + 10

10𝑥

if (matches_dist_pattern(expr)) {

state.apply {

distributive_rule()

}

}

30 of 56

Mapping Input Features to Code Locations

30

Program

Fuzzer

Learner

31 of 56

Decision Trees

31

∃?

∃?

MultExpr

UnaryExpr

AddExpr

2

36

15

yes

no

yes

no

UnaryExpr

AddExpr

36

15

✗

✓

✗

32 of 56

Predicting with Decision Trees

32

✓

yes

yes

no

no

∃?

MultExpr

UnaryExpr

AddExpr

2

36

15

UnaryExpr

AddExpr

36

15

∃?

*

2

Identifier

x

UnaryExpr

DecDigits

DecDigit

MultExpr

UnaryExpr

46

13

MultExpr

2

23

16

39

8

15

22

42

✗

AddExpr

MultExpr

MultExpr

*

DecDigits

DecDigit

5

(

)

0

49

35

AddExpr

36

37

13

2

23

UnaryExpr

15

22

42

UnaryExpr

8

AddExpr

36

UnaryExpr

15

MultExpr

2

AddExpr

36

UnaryExpr

15

5 ∗ (𝑥 ∗ 2)

✗

33 of 56

Predicting with Decision Trees

33

AddExpr

MultExpr

MultExpr

*

DecDigits

DecDigit

5

AddExpr

MultExpr

(

)

+

UnaryExpr

DecDigits

DecDigit

2

MultExpr

UnaryExpr

Identifier

x

yes

yes

no

no

0

10

46

49

35

AddExpr

36

37

5

13

2

23

16

39

8

22

42

UnaryExpr

15

22

42

7

2

15

UnaryExpr

8

∃?

MultExpr

UnaryExpr

AddExpr

2

36

15

∃?

UnaryExpr

AddExpr

36

15

AddExpr

36

UnaryExpr

15

✓

✗

5 ∗ (𝑥 + 2)

✗

34 of 56

Experimental Setup: Prediction

34

∃?

✗

✓

∃?

✗

✓

∃?

✗

✓

35 of 56

Evaluating Prediction

35

​

Subject

Association Quality

​

Accuracy

Precision

Recall

JSON

argo

0.983

0.959

0.971

fastjson

0.984

0.966

0.976

genson

0.986

0.964

0.969

gson

0.987

0.964

0.962

json-flattener

0.970

0.978

0.936

json-java

0.982

0.944

0.937

json-simple

0.997

0.988

0.994

json-cliftonlabs

0.987

0.989

0.988

minimal-json

0.974

0.946

0.928

pojo

0.988

0.953

0.934

URL

autolink

0.946

0.948

0.952

jurl

0.941

0.956

0.977

url-detector

0.952

0.966

0.970

JS

rhino

0.954

0.846

0.825

✓

✓

✓

✓

✓

✓

✓

✓

✓

✓

✓

✗

✗

✗

✗

✗

✗

✗

✗

✗

✗

✗

Accuracy =

Precision =

Recall =

36 of 56

Generating with Decision Trees

36

5 ∗ (𝑥 + 2)

3 ∗ (z - 7)

5𝑥 + 10

3z - 21

if (matches_dist_pattern(expr)) {

state.apply {

distributive_rule()

}

}

37 of 56

Generating with Decision Trees

37

✗

✓

✗

∃?

∃?

MultExpr

UnaryExpr

AddExpr

2

36

15

yes

no

yes

no

UnaryExpr

AddExpr

36

15

MultExpr

UnaryExpr

AddExpr

2

36

15

AddExpr

36

UnaryExpr

15

∧

∄

∃

38 of 56

Generating with Decision Trees

38

|

~

AddExpr

36

~

|

...

AddExpr

0

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

(

35

...

)

37

~

|

+

10

-

11

|

|

MultExpr

2

AddExpr

5

UnaryExpr

8

MultExpr

UnaryExpr

AddExpr

2

36

15

AddExpr

36

UnaryExpr

15

AddExpr

0

AddExpr

36

(

35

)

37

MultExpr

2

*

23

UnaryExpr

15

MultExpr

DecDigits

DecDigit

5

49

UnaryExpr

8

13

22

42

MultExpr

+

10

2

46

AddExpr

5

Identifier

16

x

39

UnaryExpr

8

DecDigits

22

DecDigit

42

MultExpr

7

2

UnaryExpr

15

AddExpr

0

|

|

MultExpr

2

~

|

MultExpr

2

~

UnaryExpr

15

|

UnaryExpr

15

|

~

AddExpr

36

AddExpr

36

|

~

|

∧

∄

∃

5 ∗ (𝑥 + 2)

39 of 56

Experimental Setup: Generation

39

?

✗

✓

?

✗

✓

✗

✓

?

Codeine

Grammarinator

40 of 56

Relative Coverage Fraction

40

✓

yes

no

✓

∃?

∃?

∃?

∃?

✗

✗

✓

✓

✗

✗

41 of 56

Absolute Coverage Fraction

41

distributive_rule()

fold_constants()

operator_substitution()

reduce_fractions()

zero_multiplication()

known_equation_subst()

42 of 56

Evaluating Generation

42

​

Subject

Median

Relative Coverage Fraction

​

Absolute Coverage Fraction

​

Codeine

Random

​

Codeine

Random

JSON

argo

0.800

0.111

​

1.000

0.606

fastjson

0.857

0.286

​

0.960

0.713

genson

0.700

0.300

​

0.956

0.717

gson

1.000

0.000

​

0.966

0.486

json-flattener

1.000

0.000

​

1.000

0.463

json-java

1.000

0.000

​

1.000

0.250

json-simple

1.000

0.000

​

1.000

0.471

json-cliftonlabs

1.000

0.857

​

1.000

0.941

minimal-json

1.000

0.125

​

0.980

0.560

pojo

0.500

0.000

​

0.680

0.240

URL

autolink

0.886

0.500

​

1.000

1.000

jurl

1.000

0.948

​

1.000

1.000

url-detector

0.852

0.833

​

1.000

0.949

JS

rhino

0.692

0.000

​

0.928

0.392

43 of 56

43

Outline

  • Grammar-based fuzz testing
    • Features / properties of inputs
    • Modeling context of input elements
  • Mapping input features to code
    • Predicting behavior
    • Targeting behavior

k-paths

}

k-paths

}

44 of 56

44

45 of 56

Grammar-Based Fuzzing: Challenging Grammars

45

DecDigit := S0;

S0 := "0" | S1;

S1 := "1" | S2;

S2 := "2" | S3;

⋯

S8 := "8" | S9;

S9 := "9";

DecDigit := "0"

| "1" | "2" | "3"

| "4" | "5" | "6"

| "7" | "8" | "9";

Identifier := Character

| Character Identifier;

​

Character := ASCIICharacter

| UnicodeCharacter;

​

ASCIICharacter := ASCIIUpper

| ASCIILower

| "_";

46 of 56

Systematically Generating k-paths

46

1: function GenerateKPaths(grammar graph 𝐺, positive natural number 𝑘)

2: forest ← {}

3: 𝑟 ← 𝑟𝑜𝑜𝑡(𝐺)

4: 𝑃 ← 𝑘𝑝𝑎𝑡ℎ𝑠(𝐺) // Enumerate all 𝑘-paths in G

5: while 𝑃 ≠ {} do

6: 𝑡 ← 𝑡𝑟𝑒𝑒(𝑟) // Start new derivation tree rooted at 𝑟

7: 𝑠 ← child slot of 𝑟

8: 𝑝 ← remove next 𝑘-path from 𝑃 // Select next 𝑘-path to pursue

9: if ℎ𝑒𝑎𝑑(𝑝) = 𝑟 then

10: 𝑝 ← 𝑡𝑎𝑖𝑙(𝑝)

11: while 𝑝 is not empty do

12: 𝑛 ← expansion of 𝑠

13: Add 𝑛 to 𝑡 by filling slot 𝑠

14: if 𝑛 = ℎ𝑒𝑎𝑑(𝑝) then

15: 𝑝 ← 𝑡𝑎𝑖𝑙(𝑝)

16: if 𝑝 is not empty then

17: 𝑠 ← child slot of 𝑛 with shortest derivation path to ℎ𝑒𝑎𝑑(𝑝)

18: 𝑡 ← CloseOff(𝐺, 𝑡) // Finalize 𝑡 by expanding all unfilled slots

19: forest ← forest ∪ {𝑡}

20: Remove from 𝑃 all 𝑘-paths found in 𝑡

21: return forest

47 of 56

Generating from Constraints

47

1: function OuterSearch(grammar graph 𝐺, constraint 𝐶)

2: 𝑄 ← a priority queue

3: 𝑠 ← the start symbol of 𝐺

4: 𝑟 ← expansion of 𝑠

5: add 𝑟 to 𝑄 with priority 𝑀𝐴𝑋

6: while 𝑄 ≠ {} do

7: 𝑛 ← a partial derivation tree removed from 𝑄

8: if 𝑛 is a complete tree and fulfils the constraint 𝐶 then

9: return 𝑛

10: 𝑂 ← all open slots in 𝑛

11: for 𝑑 in 𝑂 do

12: for 𝑒 in all candidate fillings of slot 𝑑 do

13: 𝑡1 ← a new tree created from 𝑛 by filling 𝑑 with 𝑒

14: 𝑡2 ← a new tree, created by the inner search as a completion of 𝑡1

15: 𝑝 ← the number of subclauses of 𝐶 not fulfilled by 𝑡2

16: if 𝑡2 is a complete tree and fulfils the constraint 𝐶 then

17: return 𝑡2

18: add 𝑑 to 𝑄 with priority 𝑝

19: return unsolvable

48 of 56

Correlating Coverage

48

High code coverage

Low code coverage

Low k-path coverage

High k-path coverage

49 of 56

Correlating Coverage

49

Low k-path coverage

High k-path coverage

50 of 56

Correlating Coverage

50

0

0.2

0.8

1

0.4

0.6

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

k-path coverage

branch coverage

Subject: argo JSON parser

51 of 56

Correlating Coverage

51

​

​

Spearman’s 𝜌

​

Subject

1-path

2-path

3-path

4-path

5-path

JSON

argo

0.978

0.979

0.977

0.978

0.978

fastjson

0.890

0.892

0.892

0.894

0.894

genson

0.719

0.718

0.716

0.716

0.716

gson

0.785

0.786

0.784

0.784

0.784

jackson-databind

0.671

0.668

0.667

0.667

0.667

json-flattener

0.834

0.832

0.832

0.833

0.833

json-java

0.855

0.855

0.854

0.856

0.857

json-simple

0.936

0.931

0.926

0.926

0.926

json-cliftonlabs

0.923

0.918

0.913

0.914

0.914

minimal-json

0.869

0.864

0.860

0.861

0.861

pojo

0.921

0.918

0.915

0.916

0.917

CSV

commons-csv

0.860

0.848

0.885

0.884

0.890

jackson-csv

0.844

0.856

0.818

0.817

0.802

jcsv

0.873

0.822

0.858

0.858

0.880

sfm-csv

0.516

0.481

0.462

0.462

0.464

simplecsv

0.862

0.811

0.821

0.820

0.828

super-csv

0.918

0.863

0.881

0.882

0.888

URL

autolink

0.692

0.791

0.796

0.796

0.797

galimatias

0.681

0.757

0.774

0.770

0.769

jurl

0.579

0.573

0.578

0.578

0.578

url-detector

0.680

0.771

0.775

0.776

0.776

MD

commonmark

0.878

0.886

0.887

0.887

0.887

markdown4j

0.875

0.885

0.886

0.886

0.886

txtmark

0.880

0.891

0.893

0.893

0.893

52 of 56

Predicting with Associations

52

✓

…

yes

yes

no

no

∃?

MultExpr

UnaryExpr

AddExpr

2

36

15

UnaryExpr

AddExpr

36

15

∃?

AddExpr

MultExpr

0

2

(

)

35

37

AddExpr

36

UnaryExpr

8

*

2

Identifier

x

MultExpr

UnaryExpr

DecDigits

DecDigit

MultExpr

UnaryExpr

46

13

2

23

16

39

8

15

22

42

✗

53 of 56

Grammars

53

Expr := AddExpr;

​

AddExpr := MultExpr

| AddExpr ("+" | "-") MultExpr;

​

MultExpr := UnaryExpr

| MultExpr ("∗" | "/" | "%") UnaryExpr;

​

UnaryExpr := Identifier

| "+" UnaryExpr

| "-" UnaryExpr

| "(" AddExpr ")"

| DecDigits;

​

DecDigits := DecDigit+;

DecDigit := "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9";

​

Identifier := "x" | "y" | "z";

(𝑥 + 2) ∗ 5

(𝑥 ∗ 2) + 5

1337 - 2 ∗ 21

54 of 56

Associating Input Features with Code Locations

54

|

~

AddExpr

36

~

|

...

AddExpr

0

MultExpr

13

UnaryExpr

15

*

23

/

24

%

25

(

35

...

)

37

~

|

+

10

-

11

∃?

∃?

MultExpr

UnaryExpr

AddExpr

2

36

15

yes

no

yes

no

|

|

MultExpr

2

AddExpr

5

UnaryExpr

8

UnaryExpr

AddExpr

36

15

|

~

AddExpr

36

UnaryExpr

15

AddExpr

36

|

MultExpr

2

✗

✓

✗

55 of 56

Generating with Decision Trees

55

(𝑥 + 2) ∗ 5

(𝑥 ∗ 2) + 5

5𝑥 + 10

(𝑥 ∗ 2) + 5

if (matches_dist_pattern(expr)) {

state.apply {

distributive_rule()

}

}

if (expr.is_distributive()) {

expr = expr.with {

distributive_rule()

}

}

56 of 56

Grammars and Derivation Trees

56

Expr := AddExpr;

​

AddExpr := MultExpr

| AddExpr ("+" | "-") MultExpr;

​

MultExpr := UnaryExpr

| MultExpr ("∗" | "/" | "%") UnaryExpr;

​

UnaryExpr := Identifier

| "+" UnaryExpr

| "-" UnaryExpr

| "(" AddExpr ")"

| DecDigits;

​

DecDigits := DecDigit+;

DecDigit := "0" | "1" | "2" | "3" | "4"

| "5" | "6" | "7" | "8" | "9";

​

Identifier := "x" | "y" | "z";

(𝑥 + 2) ∗ 5

MultExpr ("∗" | "/" | "%") UnaryExpr

DecDigits := DecDigit+

DecDigit :=

"(" AddExpr ")"

AddExpr

DecDigits

MultExpr

UnaryExpr

DecDigits

MultExpr

*

UnaryExpr

AddExpr

(

)

DecDigit

AddExpr

MultExpr

+

MultExpr

UnaryExpr

UnaryExpr

Identifier

DecDigit

x

2

5

DecDigits

"5"

UnaryExpr :=

Expr := AddExpr

AddExpr :=

MultExpr :=

MultExpr

"2"

UnaryExpr

Identifier

Identifier := "x"

AddExpr ("+" | "-") MultExpr