PaperlayerView exact revision on arXiv

Source-linked AI summary

NEUZZ: Efficient Fuzzing with Neural Program Smoothing

Dongdong She, Kexin Pei, Dave Epstein, Junfeng Yang, Baishakhi Ray, Suman Jana

arXiv:1807.05620v4cs.CRcs.LG

TL;DR

Fuzzers often struggle with hard-to-trigger bugs because evolutionary mutation cannot exploit gradients, while real programs have discontinuous branching behavior. NEUZZ trains neural surrogate models to smooth those behaviors and uses their gradients for input generation, outperforming 10 state-of-the-art fuzzers and finding 31 previously unknown bugs.

  • Problem

    Evolutionary fuzzers can get stuck in random mutations, while discontinuous real-world program behavior prevents direct use of gradient-guided optimization.

  • Method

    NEUZZ incrementally trains surrogate neural networks to approximate program branching behavior and uses their gradients to guide input mutations.

  • Results

    NEUZZ significantly outperformed 10 state-of-the-art fuzzers across evaluated real-world programs and datasets, finding 31 previously unknown bugs that other fuzzers missed.

  • Takeaways & Limitations

    Neural program smoothing combined with gradient-guided input generation can improve fuzzing effectiveness in the evaluated settings.

Abstract

from arXiv · show

Fuzzing has become the de facto standard technique for finding software vulnerabilities. However, even state-of-the-art fuzzers are not very efficient at finding hard-to-trigger software bugs. Most popular fuzzers use evolutionary guidance to generate inputs that can trigger different bugs. Such evolutionary algorithms, while fast and simple to implement, often get stuck in fruitless sequences of random mutations. Gradient-guided optimization presents a promising alternative to evolutionary guidance. Gradient-guided techniques have been shown to significantly outperform evolutionary algorithms at solving high-dimensional structured optimization problems in domains like machine learning by efficiently utilizing gradients or higher-order derivatives of the underlying function. However, gradient-guided approaches are not directly applicable to fuzzing as real-world program behaviors contain many discontinuities, plateaus, and ridges where the gradient-based methods often get stuck. We observe that this problem can be addressed by creating a smooth surrogate function approximating the discrete branching behavior of target program. In this paper, we propose a novel program smoothing technique using surrogate neural network models that can incrementally learn smooth approximations of a complex, real-world program's branching behaviors. We further demonstrate that such neural network models can be used together with gradient-guided input generation schemes to significantly improve the fuzzing efficiency. Our extensive evaluations demonstrate that NEUZZ significantly outperforms 10 state-of-the-art graybox fuzzers on 10 real-world programs both at finding new bugs and achieving higher edge coverage. NEUZZ found 31 unknown bugs that other fuzzers failed to find in 10 real world programs and achieved 3X more edge coverage than all of the tested graybox fuzzers for 24 hours running.

I. INTRODUCTION

NEUZZ addresses the difficulty of fuzzing hard-to-trigger bugs by smoothing discontinuous program behavior with neural networks and using gradients to guide input generation. Evaluations report improved bug finding and edge coverage over state-of-the-art fuzzers.

  • I. INTRODUCTION: Popular evolutionary fuzzers often get stuck in redundant random mutations and cannot leverage gradients or higher-order derivatives.Fuzzing seeks inputs that maximize vulnerability discovery or code coverage, but real-world vulnerabilities are sparse and erratically distributed.
  • I. INTRODUCTION: Gradient-guided optimization is promising, but discontinuous branching behavior prevents its direct application to real-world fuzzing.A smooth surrogate function can approximate target-program branching behavior with respect to program inputs.
  • I. INTRODUCTION: NEUZZ uses scalable surrogate neural networks to learn smooth approximations of target-program branching behavior and incrementally refine them with additional training data.The neural model predicts exercised control-flow edges and supports efficient gradient computation.
  • I. INTRODUCTION: 31 previously unknown bugs were found in tested real-world programs, including CVE-2018-19931 and CVE-2018-19932, which other fuzzers failed to find.NEUZZ was evaluated against 10 state-of-the-art fuzzers on 10 real-world programs, LAVA-M, and CGC.
  • I. INTRODUCTION: NEUZZ significantly outperformed 10 state-of-the-art fuzzers in detected bugs and edge coverage across the evaluated programs.The paper frames this result as evidence that neural smoothing can improve gradient-guided fuzzing effectiveness.
  • I. INTRODUCTION: NEUZZ uses surrogate-model gradients to generate inputs and identify mutation locations that can maximize detected bugs.The approach combines gradient-guided search with incremental retraining on mispredicted program behaviors.

III. OVERVIEW OF OUR APPROACH

NEUZZ combines neural program smoothing with gradient-guided mutations to navigate branching behaviors that evolutionary fuzzers may miss. The surrogate model is trained and incrementally refined as new behaviors appear.

  • Neural program smoothing: NEUZZ trains a neural network to smoothly approximate complex program branching behaviors and incrementally refines it with new training data.The model predicts exercised control-flow edges and is refined until desired behavior is found.
  • Gradient-guided optimization: Gradient-guided optimization uses the smoothed model to search for input values that reach difficult target branches.In the motivating example, AFL explores other branches but random mutation rarely finds the values triggering the buggy branch.
  • Incremental learning: Incremental learning updates the surrogate as new program behaviors are observed during fuzzing.This allows the approach to bootstrap from existing test inputs while progressively expanding modeled behavior.
  • Motivating example: The motivating example computes pow(3,a+b) and contains a buggy branch exercised when the output lies in the range (1,2).The original function has a sharp jump, whereas neural smoothing exposes a surface that gradient-guided mutations can exploit.

IV. METHODOLOGY

Program smoothing replaces discontinuous program behavior with a differentiable approximation so gradient-guided optimization can operate on real-world programs. NEUZZ learns this approximation from observed edge-coverage data in a graybox manner.

  • Program smoothing: Smoothing makes gradient-guided optimization more effective by reducing discontinuities and plateaus in program behavior.Without smoothing, gradient-guided methods can get stuck when optimizing non-smooth functions.
  • Program smoothing: Program smoothing is formulated as convolving a discontinuous function with a smooth mask to produce a differentiable output.Gaussian and Sigmoid functions are examples of smoothing masks.
  • Program smoothing: Analytical convolution is impractical when the target program lacks a closed-form representation, so numerical or learned approximations are needed.For programs, the corresponding convolution cannot be computed analytically.
  • Graybox smoothing: NEUZZ uses neural networks to learn smooth program approximations from edge-coverage data in a graybox setting.This avoids relying solely on blackbox sampling or whitebox symbolic analysis.

B. Neural program smoothing

NEUZZ models target-program branching with surrogate feed-forward neural networks trained on input bytes and edge-coverage labels. The networks provide smooth predictions and efficiently computable derivatives for fuzzing.

  • Why neural networks: Feed-forward neural networks fit the approach because they model nonlinear, non-convex behaviors while supporting efficient gradients and higher-order derivatives.They can also generalize program behavior to unseen inputs based on similar observed inputs.
  • Model formulation: NEUZZ’s surrogate neural network maps byte-sequence inputs of size m to edge bitmaps of size n.The model parameters are trained from input samples paired with corresponding edge-coverage bitmaps.
  • Model training: The network is trained by minimizing binary cross-entropy between predicted and ground-truth coverage bitmaps.The loss compares each predicted bitmap bit with its corresponding label.
  • Training data: The smoothing technique can use edge-coverage data from existing input corpora, including corpora generated by AFL.The prototype uses evolutionary-fuzzer inputs for initial model training.
  • Training data preprocessing: Training-data preprocessing addresses biased edge labels and correlations that can prevent the model from converging to a small loss.Such correlations are described as multicollinearity in machine learning.

C. Gradient-guided optimization

NEUZZ uses surrogate-network gradients to select and directionally mutate important input bytes, then incrementally retrains the model when predictions diverge from observed behavior. Coverage-based filtering limits retraining growth and helps preserve previously learned behavior.

  • Gradient-guided optimization: Smooth neural networks provide gradients and higher-order derivatives that can guide faster-converging fuzzing input generation.NEUZZ specifically designs a gradient-guided search scheme robust to minor prediction errors.
  • Gradient computation: The gradient dimension matches the input byte sequence, allowing each byte’s influence on a selected output neuron to be estimated.The gradient indicates how changing an input byte affects predicted edge coverage.
  • Gradient-guided mutation: Algorithm 1 ranks input locations by gradient magnitude, mutates them in both gradient-sign directions, and clips byte values to 0–255.The procedure tests mutation magnitudes from 1 through 255.
  • Gradient-guided mutation: The mutation process starts with a small target-byte set and exponentially increases it to cover the large input space.This controls the number of bytes changed during input generation.
  • Incremental learning: NEUZZ incrementally refines its surrogate when observed program behavior diverges from predictions or new edges are triggered.Retraining incorporates new data while addressing the risk of forgetting previously learned behavior.
  • Incremental learning: Edge-coverage filtering retains old samples that triggered newly covered branches, limiting training-set growth across retraining iterations.The authors report that the scheme supports up to 50 retraining iterations.

V. IMPLEMENTATION

NEUZZ uses a three-layer fully connected neural network and tunes mutation and architecture parameters to improve edge coverage. Experiments favor smaller mutations and a single hidden layer over deeper alternatives.

  • NN architecture: NEUZZ implements its neural model with three fully connected layers, using ReLU in the hidden layer.The implementation uses Keras-2.1.3 with TensorFlow-1.4.1.
  • Training Data Collection: Around 2K training inputs per program are collected with AFL, then split into training and testing data at a 5:1 ratio.Inputs are selected using a 10KB threshold file size.
  • Parameter tuning: Smaller mutations with fewer changed bytes may achieve higher code coverage than larger mutations across all four evaluated programs.The comparison uses k = 2 and 1M mutations per iteration across three iterations.
  • NN model selection: A single hidden layer performs better than three hidden layers across all four evaluated programs.The models vary between 4096 and 8192 neurons per hidden layer and are tested with 1M mutations.

VI. EVALUATION

The evaluation examines whether NEUZZ finds more bugs, achieves higher edge coverage, outperforms RNN-based fuzzers, and is affected by model choices. It begins by describing the study subjects and experimental setting.

  • Evaluation goals: The evaluation compares NEUZZ’s bug-finding performance and edge coverage with other state-of-the-art fuzzers.The evaluation is organized around four research questions.
  • Evaluation goals: RQ1 asks whether NEUZZ can find more bugs than existing fuzzers.
  • Evaluation goals: RQ2 asks whether NEUZZ can achieve higher edge coverage than existing fuzzers.
  • Evaluation goals: RQ3 asks whether NEUZZ performs better than existing RNN-based fuzzers.
  • Evaluation goals: RQ4 examines how different model choices affect NEUZZ’s performance.

A. Study Subjects

NEUZZ is evaluated on three dataset types: 10 real-world programs, LAVA-M, and the DARPA CGC dataset. Its edge coverage and detected bugs are compared with 10 state-of-the-art fuzzers.

  • Study subjects: NEUZZ is evaluated on 10 real-world programs, LAVA-M, and the DARPA CGC dataset.
  • Study subjects: The evaluation compares NEUZZ with 10 state-of-the-art fuzzers using edge coverage and number of bugs detected.

B. Experimental Setup

The experiments use a shared AFL-generated seed corpus and fixed fuzzing budgets, with dataset-specific handling for learning-based, hybrid, and RNN-based fuzzers.

  • Common setup: AFL runs for one hour to generate the initial seed corpus before each fuzzer runs under a fixed time budget.
  • Common setup: The fuzzing budgets are 24 hours for real-world programs, 5 hours for LAVA-M, and 6 hours for CGC datasets.
  • Corpus handling: The same seed corpus initializes evolutionary fuzzers and generates training data for NEUZZ and RNN-based fuzzers.
  • Corpus handling: KleeFL receives an additional hour of Klee-generated seeds before its 24-hour fuzzing process.
  • RNN comparison: RNN-based fuzzers are evaluated at a fixed number of mutations to exclude disparities in training time, which can reach 20× NEUZZ’s training time.

C. Results

NEUZZ consistently outperforms comparison fuzzers across real-world, LAVA-M, and CGC evaluations, both in bug discovery and edge coverage. Its gradient-guided neural smoothing approach is especially effective for difficult magic-number and branching conditions.

  • Detecting real-world bugs: NEUZZ finds all five bug types across six real-world programs and discovers twice as many bugs as the second-best fuzzer.Two uniquely found bugs received CVE-2018-19931 and CVE-2018-19932 assignments.
  • Detecting injected bugs in LAVA-M: NEUZZ finds all listed LAVA-M bugs in base64, md5sum, and uniq, and the highest number in who.The dataset contains four programs whose bugs are guarded by four-byte magic-number comparisons.
  • Detecting CGC bugs: 31 of 50 CGC buggy binaries are uncovered by NEUZZ, compared with 21 by AFL and 25 by Driller.NEUZZ includes every buggy binary found by either baseline and additionally finds six binaries missed by both.
  • Edge coverage: NEUZZ’s gradient-guided mutation explores diverse edges with minimal neural-network overhead, whereas heavyweight analysis can limit scalability.The paper attributes the contrast to evolutionary fuzzers repeatedly checking branches and advanced analyses incurring higher execution overhead.
  • Edge coverage: NEUZZ achieves up to 4× better edge coverage than AFL and 2.5× better coverage than the second-best fuzzer over 24 hours.Across nine of ten programs, NEUZZ exceeds AFL by 1.3× to 10×; zlib reaches similar coverage because of saturation.
  • Comparison with RNN fuzzing: NEUZZ achieves 3.7× to 8.4× more edge coverage than an RNN-based fuzzer across four projects.The RNN fuzzer also incurs, on average, 20× more training overhead because its models are more complicated.

VII. CASE STUDIES OF BUGS

NEUZZ discovered integer-overflow, out-of-memory, and crash-inducing bugs by exploring extreme input values and malformed file metadata. The cases include bugs in strip, libjpeg, and readelf.

  • Integer overflow and out-of-memory: NEUZZ enumerates critical bytes across 0x00–0xff, enabling discovery of bugs caused by mishandled extreme variable values.The paper reports out-of-memory bugs in libjpeg, objdump, nm, and strip, plus an integer-overflow bug in strip.
  • Integer overflow and out-of-memory: A strip integer overflow can induce an infinite loop when NEUZZ sets input bytes to extreme values.
  • Integer overflow and out-of-memory: A large JPEG sampling factor causes excessive image-memory allocation and an out-of-memory error.The JPEG standard requires the sampling factor to be between 1 and 4, while NEUZZ sets a large value.
  • Crash-inducing bugs: Setting readelf’s section count to zero returns a NULL pointer that subsequent code dereferences, triggering a crash.The section count is specified by the ELF header’s e_shnum field.

VIII. RELATED WORK

Related work includes program smoothing, learning-based fuzzing, taint-based fuzzing, symbolic execution, and neural programs. NEUZZ differs by smoothing branching behavior and then applying gradient-guided input generation.

  • Program smoothing: Prior program-smoothing algorithms use abstract interpretation and symbolic execution but incur prohibitive overhead, especially for large programs.
  • Learning-based fuzzing: Existing learning-based fuzzers directly predict input patterns for higher code coverage, whereas NEUZZ first approximates branching behavior smoothly.NEUZZ then uses gradient-guided input generation.
  • Taint-based fuzzing: Taint-based fuzzers identify promising mutation locations, but dynamic taint analysis has high overhead and static analysis has many false positives.The paper reports that NEUZZ outperforms existing state-of-the-art taint-based fuzzers using neural networks to identify mutation locations.
  • Symbolic/concolic execution: Symbolic and concolic execution solve path constraints with SMT solvers but struggle with path explosion, incomplete environment modeling, and overheads.
  • Neural programs: Neural programs learn latent representations of program logic, whereas NEUZZ learns smooth approximations of branching behaviors.

IX. CONCLUSION

NEUZZ combines surrogate neural-network smoothing of target-program branch behavior with gradient-guided test-input generation. Evaluations report improved bug detection and edge coverage across real-world programs.

  • NEUZZ significantly outperforms 10 state-of-the-art fuzzers in detected bugs and achieved edge coverage.
Loading 1807.05620v4…