Source-linked AI summary
Not all bytes are equal: Neural byte sieve for fuzzing
Mohit Rajpal, William Blum, Rishabh Singh
TL;DR
Fuzzing complex input formats can require millions of mutations, making it difficult to find inputs that increase coverage or expose crashes. This paper uses neural networks trained on prior fuzzing and coverage data to guide mutation locations in AFL. Results vary across formats and measures, with PDF coverage gains constrained by prediction time on large files.
Problem
Finding mutations that increase coverage or expose crashes is a difficult search problem, and complex formats may require millions of mutations.
Source: §I · p. 1Method
Neural networks learn from prior fuzzing inputs and coverage to predict promising mutation locations and guide AFL's future mutations.
Source: §I · pp. 1–2Results
Neural-augmented AFL improved coverage for ELF and PNG, explored more unique paths for ELF, PNG, and XML, and found more crashes for ELF and XML; coverage was comparable for PDF and XML.
Source: §I · p. 2Takeaways & Limitations
The authors conclude that targeting useful locations in seed files may help explore novel execution behavior, particularly in small sections that affect execution.
Source: §VII · p. 10For large PDF inputs, model prediction time limited coverage improvement, though the authors believe performance engineering could improve it.
Source: §I · p. 2
Abstract
from arXiv · showhide
Fuzzing is a popular dynamic program analysis technique used to find vulnerabilities in complex software. Fuzzing involves presenting a target program with crafted malicious input designed to cause crashes, buffer overflows, memory errors, and exceptions. Crafting malicious inputs in an efficient manner is a difficult open problem and often the best approach to generating such inputs is through applying uniform random mutations to pre-existing valid inputs (seed files). We present a learning technique that uses neural networks to learn patterns in the input files from past fuzzing explorations to guide future fuzzing explorations. In particular, the neural models learn a function to predict good (and bad) locations in input files to perform fuzzing mutations based on the past mutations and corresponding code coverage information. We implement several neural models including LSTMs and sequence-to-sequence models that can encode variable length input files. We incorporate our models in the state-of-the-art AFL (American Fuzzy Lop) fuzzer and show significant improvements in terms of code coverage, unique code paths, and crashes for various input formats including ELF, PNG, PDF, and XML.
I. INTRODUCTION
The introduction frames fuzzing as a search for mutations that increase coverage and find crashes, then proposes using neural networks and prior coverage feedback to guide mutation locations. It reports gains that vary by input format and outcome.
I. INTRODUCTION
- The introduction situates the work among blackbox, whitebox, and greybox fuzzing, noting AFL's lightweight coverage instrumentation and efficient implementation.Fuzzers generate inputs through random mutations, constraint solving, or manually defined heuristics, while complex formats can require millions of mutations.Source: §I · p. 1
- The proposed strategy learns from prior fuzzing inputs and coverage to predict promising mutation locations and guide future input modifications.The paper instantiates the approach in AFL, whose input queue retains promising files that reach new code paths.Source: §I · p. 1
- LSTMs and attention-based sequence-to-sequence models encode variable-length inputs and predict a heat map for prioritizing mutation locations.Training begins with a limited AFL run on a subset of seed files to collect mutation and coverage data.Source: §I · p. 1
- Neural-augmented AFL increased code coverage for ELF and PNG, explored more unique paths for ELF, PNG, and XML, and found more crashes for ELF and XML.Coverage was comparable for PDF and XML; PDF coverage gains were smaller because model predictions took additional time on large files.Source: §I · p. 2
- The stated contributions are neural models for locating promising bytes, an efficient training and fuzzing technique, and integration with AFL.The authors report improved coverage, unique paths, and crashes across multiple input formats, with outcomes varying by format.Source: §I · p. 2
II. AFL BACKGROUND
AFL evolves seeds through coverage-guided mutations, but useful byte locations vary by format and are difficult to identify manually. The framework learns a per-byte usefulness heat map to guide mutation selection.
II. AFL BACKGROUND
- AFL applies localized and stacked mutations, retaining inputs that produce new code execution or change execution frequency as seeds for further mutation.The seed pool is periodically culled to choose which inputs to mutate.Source: §II · p. 2
- Mutation usefulness varies across file formats: critical sections such as headers may yield input gain, while raw-data regions are less likely to do so.Manually identifying useful locations in complex formats requires substantial domain expertise.Source: §II · p. 2
- The paper investigates neural networks to identify useful input-file locations automatically using code-coverage feedback.This addresses the difficulty of manually locating promising mutation targets.Source: §II · pp. 2–3
III. OVERVIEW OF THE FRAMEWORK
- The model maps each input file to a heat map of mutation usefulness, which Augmented-AFL queries before mutation and uses to veto mutations below a cutoff.The heat map is computed once per seed, and α controls how many useful bytes a mutation must target.Source: §III · p. 3
- Training examples pair seed files and mutations with code-coverage information, then filter pairs using a score of the coverage change.The training data includes the seed, its coverage bitmap, the mutated seed, and the mutated seed’s coverage bitmap.Source: §III · p. 3
- The bitwise strictly-less-than score rewards coverage increases, approximating mutation usefulness despite its dependence on prior fuzzing history.The score highlights code sections executed for the mutated input but not the original.Source: §III · p. 3
IV. LEARNING FOR AUGMENTED FUZZING
The design combines AFL modifications with a neural network that predicts promising mutation locations.
IV. LEARNING FOR AUGMENTED FUZZING
- The design pairs modifications to AFL with a neural network for predicting optimal locations to fuzz.Source: §IV · p. 4
A. Augmented-AFL
Augmented-AFL uses a neural model to identify useful byte regions and vetoes mutations that target none of them. Its permissive veto is intended to improve the hit rate while avoiding unlikely-to-help executions.
A. Augmented-AFL
- Augmented-AFL queries the neural model for each seed, classifies byte locations as useful or useless, and vetoes mutations that target no useful locations.Source: A. Augmented-AFL · p. 4
- AFL’s mutation set includes bit and byte flips, arithmetic changes, interesting-value and dictionary substitutions, and random byte assignment.It also deletes, clones, or overwrites byte sections and stacks multiple changes.Source: A. Augmented-AFL · p. 4
- The veto aims to improve mutation hit rate by avoiding executions of mutations considered unlikely to yield input gain.The stated veto is permissive: it rejects mutations targeting no useful locations.Source: A. Augmented-AFL · p. 4
B. Neural network architectures
The paper represents byte-level inputs for neural coverage-heatmap prediction and compares recurrent and sequence-to-sequence architectures. It explores model depth and input chunk size, with architecture parameter counts tabulated.
B. Neural network architectures
- The learned function maps a length-k byte sequence to k per-position scores in [0,1] for the coverage-heatmap prediction task.The section introduces this family of functions as the target for the neural architectures.Source: B. Neural network architectures · p. 4
- Bytes are encoded as sequences of bits because byte values may represent states or bitmasks rather than numerical magnitudes.The alternative is to feed byte values directly as floating-point numbers from 0 to 255.Source: B. Neural network architectures · p. 5
- Recurrent networks suit sequential, variable-length inputs, while LSTMs address the difficulty recurrent networks have with longer sequences.The paper also notes that recurrent networks can count, which can help annotate formats with fixed-offset headers.Source: B. Neural network architectures · p. 5
- Table II enumerates the architectures and trainable-parameter counts; blank entries indicate untested combinations.One-layer bidirectional LSTMs use sum merging, while models with two or more layers use concatenation.Source: Table II · p. 6, B. Neural network architectures · p. 6
- The evaluated architectures include unidirectional and bidirectional LSTMs, Seq2Seq, and Seq2Seq with attention.Seq2Seq variants use a bidirectional encoder and unidirectional decoder; unidirectional Seq2Seq variants were not explored.Source: B. Neural network architectures · p. 6
- Experiments varied LSTM layer count and input chunk size, using 64-bit or 128-bit chunks per timestep.These variations tested whether more complex models outperform simpler ones.Source: B. Neural network architectures · p. 6
V. EVALUATION
The evaluation compares Augmented-AFL with AFL on four target programs using code coverage, input gain, and crashes. It gathers training pairs from AFL runs and evaluates the learned models on held-out seeds.
V. EVALUATION
- The evaluation covers readpng, readelf, mupdf, and libxml, measuring code coverage, input gain, and crashes.Input gain counts inputs that cause new coverage behavior over the fuzzer's runtime.Source: §V · p. 6
- For each program, 180 randomly chosen seeds were split evenly into training and test sets; AFL ran for 24 hours with input-coverage pairs sampled uniformly at 1%.The resulting data was filtered to construct the training set.Source: §V · p. 6
- Table III reports average code coverage after 24 hours for each program and architecture, with the top three strategies bolded per program.Source: Table III · p. 7
- Evaluation restarted AFL and Augmented-AFL on test seeds for 24 hours, averaging results across multiple instances.AFL used 16 instances on 16 cores; Augmented-AFL used eight instances, reserving eight cores for model queries.Source: §V · p. 7
A. Code Coverage
Code-coverage gains vary by target: readelf and readpng improve, whereas mupdf and libxml show no significant overall improvement.
A. Code Coverage
- Readelf and readpng show significant coverage gains; most mupdf models underperform except Seq2Seq+Attn's small gain, while libxml models cluster around 2.10% within error.Almost all models outperform baseline AFL on readelf and readpng, often with the simplest unidirectional models.Source: A. Code Coverage · p. 7
B. Input Gain
Input gain improves significantly on evaluated programs other than PDF, but mupdf shows no significant gain. The paper links this limitation to model-query time on large PDF inputs.
B. Input Gain
- Input gain improves significantly for all programs except PDF; Figure 6 plots unique paths over time for readelf, readpng, mupdf, and libxml.Input gain counts paths showing new behavior, such as executing a new block or changing an existing block's execution frequency.Source: B. Input Gain · p. 7, Figure 6 · p. 8
- Libxml shows input-gain improvement despite no coverage increase, which the authors suggest reflects changed execution frequencies in already exercised code.Source: B. Input Gain · p. 8
- Mupdf shows no significant coverage or input-gain improvement; large PDF files can take several seconds to query, blocking fuzzing execution.The authors expect faster model querying to improve efficacy on lengthy formats such as PDF.Source: B. Input Gain · p. 8
C. Crashes
The augmented fuzzer found more unique crashes than AFL in both readelf and libxml. By the 24-hour mark, the reported counts were over 20 versus none for readelf, and about 110 versus about 80 for libxml.
C. Crashes
- Unique crashes were the study’s measure of malicious-input discovery; crashes were observed only for readelf and libxml.The paper omits crash plots for readpng and mupdf.Source: C. Crashes · p. 8
- More than 20 readelf crashes versus none, and about 110 libxml crashes versus about 80 for AFL, were reported by 24 hours.Figure 7 plots unique crashes against time for readelf and libxml.Source: C. Crashes · pp. 8–9, Figure 7 · p. 9
- The authors characterize these results as improvements over AFL across a variety of target programs and file formats.They describe AFL as a state-of-the-art genetic-algorithm greybox fuzzer.Source: C. Crashes · p. 9
VI. RELATED WORK
Related work spans learned input grammars, bandit-based fuzzing, evolutionary feedback, and neural program analysis. This paper instead learns promising mutation locations in input files and presents neural guidance as an easily integrated feedback-driven approach.
Machine Learning for Grammar-based Fuzzing
- Learn&Fuzz learns a PDF-object grammar for generating inputs, whereas this work predicts promising locations for mutations in seed files and may complement grammar-based fuzzing.The authors note that manually writing grammars for complex formats can be tedious and error-prone.Source: §VI · p. 9
Bandit formulation for Fuzzing
- Prior bandit work modeled fuzzer configuration scheduling, while this paper frames byte-location selection as a discrete optimization problem for multi-armed bandits.The authors call the framing “bytes-as-bandits” and say it deserves further study.Source: §VI · p. 9
Evolutionary Fuzzing
- Evolutionary and taint-guided approaches use execution feedback, while this work favors neural models to guide future fuzzing actions.The authors describe the neural approach as quick to develop, easy to integrate, and low-overhead for simple models.Source: §VI · pp. 9–10
Neural Networks for Program Analysis
- Unlike neural program-analysis work that represents programs, this paper trains neural models to represent input files and identify promising fuzzing locations.The authors present this as the first application of neural networks to learning promising fuzzing locations in input files.Source: §VI · p. 10
VII. FUTURE WORK AND CONCLUSION
The paper presents neural augmentation for greybox fuzzing that identifies useful seed-file locations, using code-coverage feedback to train models. It reports gains over AFL on all evaluated targets except PDF, while identifying offline learning and mutation vetoes as areas for future work.
VII. FUTURE WORK AND CONCLUSION
- The augmentation targets small seed-file sections thought to affect execution behavior, focusing fuzzing there to seek novel execution behavior.The authors frame this as a neural-based augmentation to greybox fuzzing.Source: §VII · p. 10
- Code-coverage feedback from greybox fuzzers trains the model to identify promising fuzzing locations, and the approach is described as easy to integrate.The authors identify AFL-like greybox fuzzers as the primary target because they provide coverage feedback for each execution.Source: §VII · p. 10
- The neural model significantly outperformed AFL on every evaluated target except PDF; simpler models typically outperformed more complex ones.The authors suggest PDF results reflect a cost-benefit tradeoff in querying models on large input files and say performance engineering may help.Source: §VII · p. 10
- Current models use offline supervised learning and veto AFL-proposed mutations; online reinforcement learning and generating mutations directly remain future directions.The authors identify both as possible extensions.Source: §VII · p. 10