NEUZZ: Efficient Fuzzing with Neural Program Smoothing
Dongdong She, Kexin Pei, Dave Epstein, Junfeng Yang, Baishakhi Ray, and Suman Jana
Columbia University
1
Fuzzing: a popular way to uncover bugs
2
[Liang et al. 2019]
Existing fuzzers
3
Evolutionary Fuzzing
Advantage: easy to implement
Disadvantage: inefficient
4
Mutation
Hard to find scalable and adaptive heuristics for guided mutation
Seed
Children
Grandchildren
A new approach to fuzzing-> ML
5
ML models learns knowledge from training data(seen, past ) and predicts on testing data(unseen, future).
6
Fuzzing is actually an repeating process which executes a tested program for million/billion times.
7
ML needs to define a loss function, then uses training data to optimize towards specific objective.
8
Fuzzing: An Optimization Problem
9
a program input
# of bugs found by input
generate K inputs from input space
Maximize
is discrete and hard to optimize
Find C(X) that can maximize total no. of bugs
Fuzzing: An Optimization Problem
10
: # of bugs
Input
Hard to find inputs like and
among flat plateaus
Fuzzing: An Optimization Problem
11
a program input
edge coverage of input
generate K inputs from input space
Maximize
Find C(X) that can maximize total number of edges
Fuzzing: An Optimization Problem
12
Input
: # of edges
Evolutionary optimization
13
Input
1
2
3
4
5
Random mutation is not efficient
: # of edges
Gradient-guided Optimization
14
Input
: # of edges
Smooth Approximation + Gradient-guided Mutation
: smooth approximation of
Gradient-guided Optimization
15
: smooth approximation of
Input
Smooth Approximation + Gradient-guided Mutation
1
2
3
4
5
Smooth Approximation
16
Problem:
How to smoothly approximate G(x)?
Neuzz Solution:
Use a NN to learn a smooth H(x)
Universal Approximation Theorem:
A NN can approximate any continuous function
Gradient-guided Mutation
17
Why gradient guidance?
Gradient indicates critical parts of input
What are critical parts of the input?
Critical parts of input affect program branches
How gradient-guided mutation works?
Focus mutations on the critical parts of the input
Main Idea behind Neuzz
18
Input
Branching Behaviors
Program
NN
Gradient-guided mutation
Smooth
Surrogate
Input
Branching
Behaviors
A Peek Into NN Model
19
Generalization to Unseen branches
Observations:
Neuzz Solution:
20
Design of NEUZZ
21
Evaluation
22
Evaluations: Edge Coverage �NEUZZ vs. state-of-the-art fuzzers�
10 real world applications for 24 hours
23
NEUZZ achieves on average 3x more edge coverage than other fuzzers
Evaluations: Bug Finding �NEUZZ vs. state-of-the-art fuzzers�
24
NEUZZ finds the most number of bugs and all 5 bug types including two new CVEs
Evaluations: Lava-M and CGC
25
NEUZZ outperforms state-of-the-art fuzzers on LAVA-M and CGC
Lava-M dataset
DARPA CGC dataset
Evaluations: NEUZZ vs. RNN-based Fuzzer
26
NEUZZ achieves 6x more edge coverage and 20x less training time
Evaluations: Effect of Different NNs
27
NEUZZ achieves best performance with
NN+Incremetal learning
Edge coverage for 1M mutations
Key Takeaways of NEUZZ
28
Github Repo
NEUZZ is available at https://github.com/Dongdongshe/neuzz
29