Source-linked AI summary
Learn&Fuzz: Machine Learning for Input Fuzzing
Patrice Godefroid, Hila Peleg, Rishabh Singh
TL;DR
The paper addresses the laborious problem of obtaining grammars for grammar-based fuzzing of complex structured inputs. It learns generative input models from sample inputs with neural networks and introduces learn&fuzz to guide mutations using learned probabilities. In PDF experiments with Microsoft Edge’s parser, the learned models generated well-formed objects and increased parser coverage, while results may vary across applications.
Problem
Grammar-based fuzzing of complex structured inputs requires comprehensive grammars that are typically laborious, time consuming, and error-prone to write by hand.
Method
The paper uses unsupervised recurrent neural-network statistical learning to generate input grammars from sample inputs and uses learned probabilities to guide fuzzing.
Results
The learned models generated many new well-formed PDF objects and increased coverage of the PDF parser used in the experiments.
Takeaways & Limitations
Learned input distributions can support the learn&fuzz challenge by combining statistically well-formed generation with targeted fuzzing.
Takeaways & Limitations
The reported results may vary for other applications, and the current work does not learn the higher-level hierarchical structure of complete PDF documents.
Abstract
from arXiv · showhide
Fuzzing consists of repeatedly testing an application with modified, or fuzzed, inputs with the goal of finding security vulnerabilities in input-parsing code. In this paper, we show how to automate the generation of an input grammar suitable for input fuzzing using sample inputs and neural-network-based statistical machine-learning techniques. We present a detailed case study with a complex input format, namely PDF, and a large complex security-critical parser for this format, namely, the PDF parser embedded in Microsoft's new Edge browser. We discuss (and measure) the tension between conflicting learning and fuzzing goals: learning wants to capture the structure of well-formed inputs, while fuzzing wants to break that structure in order to cover unexpected code paths and find bugs. We also present a new algorithm for this learn&fuzz challenge which uses a learnt input probability distribution to intelligently guide where to fuzz inputs.
1 Introduction
The paper targets the laborious, error-prone task of manually writing grammars for grammar-based fuzzing by learning input grammars automatically from sample inputs. It introduces neural statistical learning and a learn&fuzz algorithm, evaluated on PDF parsing in Microsoft Edge.
- Grammar-based fuzzing is effective for complex structured inputs but requires a comprehensive, manually written grammar.Writing this grammar is laborious, time consuming, and error-prone.
- The paper investigates automatically generating input grammars for grammar-based fuzzing using machine-learning techniques.
- Recurrent neural networks learn a generative statistical input model from sample inputs without format-specific customization.The approach uses unsupervised learning and generates new inputs from the learned probability distribution.
- The case study targets PDF and Microsoft Edge’s large, security-critical PDF parser.The PDF specification is described as a 1,300-page document, and the experiments examine generating diverse well-formed inputs while injecting ill-formed parts.
- The learn&fuzz algorithm uses a learned input probability distribution to guide where to fuzz statistically well-formed inputs.The paper reports that it can outperform the other learning-based and random fuzzing algorithms considered.
2 The Structure of PDF Documents
PDF documents use a textual structure organized into bodies containing objects, cross-reference tables, and trailers. The paper focuses on learning grammars for non-binary PDF data objects, while higher-level document structure involves additional relationships and invariants.
- The PDF specification exceeds 1,300 pages, with roughly 70% describing data objects and their relationships.
- A PDF document contains at least one body, and each body has objects, a cross-reference table, and a trailer.
- Objects: Objects are basic units with a shared outer structure containing an identifier, generation number, obj marker, and endobj terminator.
- Objects: PDF objects include arrays, string literals, numeric objects, and multi-type arrays that can compose larger objects.
- Cross-reference tables and trailers: Cross-reference tables map referenced objects to byte addresses, while trailers store body information and the cross-reference table’s startxref address.These structures support parsing from the document’s end and loading objects as needed.
- Updating a document: Incremental updates append a new PDF body containing revised objects and a new cross-reference table to the previous document.Updated objects receive a higher generation number than their earlier versions.
- Scope of this work: This work learns grammars for non-binary PDF data objects rather than the higher-level cross-reference structure.The higher-level structure involves relationships and complex invariants among document sections.
3 Statistical Learning of Object Contents
The paper uses seq2seq recurrent neural networks to learn generative models of PDF-object character sequences, then samples those models to generate objects for fuzzing. It compares generation strategies and introduces SampleFuzz to balance well-formedness with anomaly injection.
- Sequence-to-Sequence Neural Network Models: Seq2seq models learn arbitrary-length character contexts and generate PDF objects from a learned probability distribution.The model is trained unsupervised to predict subsequent characters in PDF-object sequences.
- Sequence-to-Sequence Neural Network Models: Training concatenates PDF-object files, splits the resulting character sequence into fixed-size inputs, and uses one-position-shifted outputs for end-to-end learning.Each training instance is a subsequence of length d, with the corresponding output shifted by one character.
- Generating new PDF objects: Generation starts with the prefix “obj ” and continues sampling characters until “endobj” terminates the PDF object.The generation procedure queries the model repeatedly for output characters.
- Generating new PDF objects: NoSample greedily produces likely, consistent objects but repeats the same object, whereas Sample produces diverse objects that may be ill-formed.The latter property is useful for fuzzing because malformed parts can exercise parser behavior.
- Generating new PDF objects: SampleSpace samples only after whitespace and otherwise selects the best character, aiming for more well-formed objects than unrestricted Sample.The strategy combines sampling and greedy prediction by restricting randomness to token boundaries.
- SampleFuzz: Sampling with Fuzzing: SampleFuzz uses the learned distribution while introducing anomalies during generation to exercise error-handling code.Its controls include a fuzzing probability and a threshold determining when a predicted character may be modified.
4 Experimental Evaluation
The experiments evaluate neural-network-generated PDF objects against baselines using Edge’s PDF parser, measuring coverage, pass rate, and runtime-detected bugs. A baseline study shows host-dependent coverage while appended objects remain parser-accepted.
- Training data and baseline: About 63,000 non-binary PDF objects from 534 files formed the training corpus, while 1,000 randomly selected objects provided the baseline.The 534 files had previously undergone seed minimization for Edge-parser fuzzing.
- Baseline coverage: Host coverage ranged from 353,327 unique instructions for host1 to 457,464 for host2, while host123 covered 494,652.The union exceeded each individual host because each host covered some unique instructions.
- Baseline coverage: Baseline123 reached 553,873 instructions, only 59,221 above host123, meaning 90% of instructions were already included in host coverage.Each test typically covered on the order of half a million unique instructions.
- Runtime and validity: Regardless of host, recombined PDF files were always perceived as well-formed by the Edge PDF parser.Coverage nevertheless varied across hosts because appended objects could interact differently with each host.
4.4 Learning PDF Objects
The study compares Sample and SampleSpace generation across training durations from 10 to 50 epochs. SampleSpace consistently achieves higher pass rates, with validity improving as models train longer.
- Pass rate: At 10 epochs, Sample already achieved a pass rate above 70%, indicating good learning quality.Pass rate measures the proportion of generated files accepted as well-formed by the parser.
- Pass rate: Pass rates increased with more epochs as the learned models became more precise, although training required more time.The paper reports this trend for both generation modes.
- Pass rate: The best pass rate was 97%, obtained with SampleSpace after 50 epochs.This result represents the strongest validity outcome among the reported epoch and strategy combinations.
- Host effects: Pass rate varied by at most 0.1% across host PDF files.The host-insensitivity result was reported for the experiments in this section.
4.5 Coverage with Learned PDF Objects
Coverage depended strongly on the host and differed from pass-rate behavior. Sample achieved the best overall coverage at 40 epochs, while SampleSpace generally traded coverage for higher validity.
- Host effects: Unlike pass rate, host choice significantly affected coverage, and coverage curves had different shapes across hosts.The four host conditions were host1, host2, host3, and host123.
- Comparison with baseline: For host1 and host2, Sample and SampleSpace exceeded baseline coverage for most epoch settings.The learned generators performed differently on host3 and host123.
- Comparison with baseline: For host3 and host123, Sample and SampleSpace were mostly below baseline coverage.This reverses the predominant relationship observed for host1 and host2.
- Best coverage: The best overall coverage came from Sample trained for 40 epochs.SampleSpace also achieved its best coverage at 40 epochs, while baseline123 ranked second overall.
4.6 Comparing Coverage Sets
Sample-40e nearly subsumes the other measured coverage sets, while SampleSpace-40e and baseline123 retain distinct instruction coverage.
- Sample-40e misses only 1,680 instructions relative to SampleSpace-40e and a few hundred relative to baseline123 and host123.
- Figure 7 compares unique instructions in each coverage-set row against each column.
- SampleSpace-40e has 3,393 instructions absent from baseline123 but misses 6,514 instructions covered by baseline123.
- Sample-40e is almost a superset of all other coverage sets.
4.7 Combining Learning and Fuzzing
The experiments combine learned PDF generation with random or distribution-guided fuzzing, showing that learning-based methods are competitive with baseline+Random.
- Random fuzzing is applied to objects from Sample-40e, SampleSpace-40e, and baseline, producing three sets of 30,000 PDF files.
- Figure 8 reports overall coverage and pass rate for each 30,000-file set, whose processing takes about 45 hours.
- SampleFuzz achieves the best overall coverage, with a 68.24% pass rate.
- The absolute coverage difference between SampleFuzz and Sample+Random is only 670 instructions.
- SampleFuzz exceeds Sample+Random by 2,622 instructions but misses 1,952 instructions covered by Sample+Random.
- All learning-based algorithms are competitive with baseline+Random, and three outperform that baseline in coverage.
4.8 Main Takeaway: Tension between Coverage and Pass Rate
The experiments reveal a coverage–pass-rate tension: more malformed inputs can expand parser coverage, while SampleFuzz targets an intermediate trade-off. A longer run found a confirmed stack-overflow bug.
- Coverage and pass rate exhibit a tension across the experiments.
- SampleSpace has better pass rate than Sample, whereas Sample has better overall coverage.
- Random fuzzing increases coverage while reducing pass rates below 50% for the fuzzed sets.
- SampleFuzz targets a pass-rate sweet spot around 65%–70%, combining diverse well-formed objects with error-handling coverage.
- Instruction coverage is a better indicator of fuzzing effectiveness than pass rate, which measures learning quality.
- A 300,000-file Sample+Random experiment found a 33Kb PDF triggering unexpected recursion and a stack overflow later confirmed and fixed by Microsoft Edge developers.
5 Related Work
Prior work learns grammars through synthesis or program observation, whereas Learn&Fuzz uses sequence-to-sequence neural models for statistical generation and fuzzing guidance.
- Grammar-based fuzzing commonly represents input structure with grammars and generates tests randomly or exhaustively.
- Bastani et al. synthesize context-free grammars from input examples using generalization steps such as repetition, alternation, and nonterminal merging.
- Learn&Fuzz instead uses sequence-to-sequence neural-network models to learn statistical generative models of flat formats.
- The learned statistical model also guides additional fuzzing of generated inputs.
- AUTOGRAM and Tupni reverse-engineer input formats using dynamic taint tracking and program-processing observations.
- Neural program-analysis work includes models for simple algorithms, input-output-to-program synthesis, and program repair.
6 Conclusion and Future Work
The paper concludes that neural-network-learned models generate well-formed PDF objects and improve parser coverage over random fuzzing, while highlighting the tension between learning structure and breaking it. Future work targets higher-level PDF structure and application-guided learning.
- Conclusion: Learnt neural-network models generate many new well-formed PDF objects and increase coverage of the evaluated PDF parser compared with random fuzzing.
- Conclusion: Learning must capture well-formed input structure, whereas fuzzing must break that structure to reach unexpected code paths and find bugs.
- Future Work: Future work would learn PDF documents’ higher-level hierarchical structure, including cross-reference tables, object bodies, trailer sections, and their invariants.
- Future Work: The authors also propose reinforcement learning with application coverage feedback to guide seq2seq models toward increased coverage.