Grammar-Based Fuzzing
Using Input Features
Nikolas Havrikov
March 4, 2022
Grammar-Based Fuzzing Using Input Features
2
Outline
System Testing
3
Program under Test
Set of Test Inputs
Fuzzing
4
Program under Test
Test Input Generator
Grammar-Based Fuzzing
5
Program under Test
Test Input Generator
Grammar-Based Fuzzing
6
Program under Test
Test Input Generator
(𝑥 + 2) ∗ 5
(𝑥 ∗ 2) + 5
1337 - 2 ∗ 21
“foobar”
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
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
Measuring Input Diversity
9
5𝑥 + 10
(𝑥 ∗ 2) + 5
(𝑥 + 2) ∗ 5
(𝑥 ∗ 2) + 5
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
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
...
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
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
"+"
"+"
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
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
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
𝑥
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
𝑥 ∗ ?
𝑥 / ?
𝑥 % ?
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
𝑥 + ?
𝑥 - ?
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
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
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
K-path Coverage
22
5
39
2
8
16
5
39
2
8
16
AddExpr
MultExpr
UnaryExpr
Identifier
x
5
39
2
8
16
Experimental Setup
23
k-path
(tribble)
n-random
(grammarinator)
%
%
> ? <
k
n
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 |
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 |
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
Outline
k-paths
}
Mapping Input Features to Code Locations
28
Mapping Input Features to Code Locations
29
5 ∗ (𝑥 + 2)
5 ∗ (𝑥 ∗ 2)
5𝑥 + 10
10𝑥
if (matches_dist_pattern(expr)) {
state.apply {
distributive_rule()
}
}
Mapping Input Features to Code Locations
30
Program
Fuzzer
Learner
Decision Trees
31
∃?
∃?
MultExpr
UnaryExpr
AddExpr
2
36
15
yes
no
yes
no
UnaryExpr
AddExpr
36
15
✗
✓
✗
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)
✗
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)
✗
Experimental Setup: Prediction
34
∃?
✗
✓
∃?
✗
✓
∃?
✗
✓
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 =
Generating with Decision Trees
36
5 ∗ (𝑥 + 2)
3 ∗ (z - 7)
5𝑥 + 10
3z - 21
if (matches_dist_pattern(expr)) {
state.apply {
distributive_rule()
}
}
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
∧
∄
∃
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)
Experimental Setup: Generation
39
?
✗
✓
?
✗
✓
✗
✓
?
Codeine
Grammarinator
Relative Coverage Fraction
40
✓
yes
no
✓
∃?
∃?
∃?
∃?
✗
✗
✓
✓
✗
✗
Absolute Coverage Fraction
41
distributive_rule()
fold_constants()
operator_substitution()
reduce_fractions()
zero_multiplication()
known_equation_subst()
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
Outline
k-paths
}
k-paths
}
44
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
| "_";
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
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
Correlating Coverage
48
High code coverage
Low code coverage
Low k-path coverage
High k-path coverage
Correlating Coverage
49
Low k-path coverage
High k-path coverage
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
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 | |
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
✗
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
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
✗
✓
✗
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()
}
}
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