Source-linked AI summary
The Art, Science, and Engineering of Fuzzing: A Survey
Valentin J. M. Manes, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, Maverick Woo
TL;DR
Fuzzing’s rapid growth has made its literature difficult to organize coherently and its terminology and design choices difficult to compare. This paper responds with a unified model and taxonomy, surveys the model’s stages and trade-offs, and concludes with a comprehensive view of modern fuzzing literature.
Problem
The surge of fuzzing research and practice has fragmented terminology and obscured design decisions, making the literature difficult to consolidate and compare.
Method
The paper presents a general-purpose fuzzing model, develops a taxonomy, and surveys design decisions, trade-offs, and engineering efforts across its stages.
Results
The paper provides a comprehensive and coherent view of modern fuzzing literature through its model, taxonomy, and stage-by-stage survey.
Takeaways & Limitations
The unified model is intended to accommodate black-, grey-, and white-box fuzzing and organize the field’s diverse techniques and design choices.
Takeaways & Limitations
In-memory API fuzzing can produce unsound, non-reproducible results when valid calling contexts or cross-call side effects are not captured.
Abstract
from arXiv · showhide
Among the many software vulnerability discovery techniques available today, fuzzing has remained highly popular due to its conceptual simplicity, its low barrier to deployment, and its vast amount of empirical evidence in discovering real-world software vulnerabilities. At a high level, fuzzing refers to a process of repeatedly running a program with generated inputs that may be syntactically or semantically malformed. While researchers and practitioners alike have invested a large and diverse effort towards improving fuzzing in recent years, this surge of work has also made it difficult to gain a comprehensive and coherent view of fuzzing. To help preserve and bring coherence to the vast literature of fuzzing, this paper presents a unified, general-purpose model of fuzzing together with a taxonomy of the current fuzzing literature. We methodically explore the design decisions at every stage of our model fuzzer by surveying the related literature and innovations in the art, science, and engineering that make modern-day fuzzers effective.
1 INTRODUCTION
Fuzzing is widely used to discover software vulnerabilities, but rapid growth has fragmented its terminology and obscured design decisions. The paper addresses this by consolidating the field through a unified model, taxonomy, and literature survey.
- Fuzzing repeatedly runs a program with generated inputs that may be syntactically or semantically malformed.
- Researchers, attackers, vendors, auditors, and open-source developers use fuzzing for vulnerability discovery, exploit generation, penetration testing, and security assurance.
- The expanding fuzzing literature makes it difficult to track design decisions, preserve important implementation tweaks, and compare results across tools.
- Terminological fragmentation can give similar techniques different names or identical names different meanings, complicating comparisons between fuzzers.
- The paper presents unified fuzzing terminology and a general-purpose model designed to accommodate many fuzzing tasks.
- It surveys each model stage, discusses design trade-offs, and summarizes major fuzzers in a taxonomy and comparison table.
2 SYSTEMIZATION, TAXONOMY, AND TEST PRO-
This section systematizes fuzzing terminology by defining fuzzing, fuzz testing, fuzzers, campaigns, bug oracles, and configurations, while situating fuzzing across diverse contexts.
- The paper traces “fuzz” to Miller et al.’s 1990 program that generates random characters for a target program.
- Fuzzing is defined as executing the PUT with inputs sampled from a space that extends beyond the PUT’s expected input space.
- Fuzz testing uses fuzzing to test whether a PUT violates a security policy, including policies that detect crashes or other execution-observable violations.
- A fuzzer performs fuzz testing on a PUT, while a fuzz campaign is a specific fuzzer execution against a PUT under a specific security policy.
- A bug oracle determines whether a PUT execution violates a specified security policy.
- A fuzz configuration consists of parameter values controlling the fuzz algorithm, with configuration spaces ranging from simple PUT-only settings to evolving sets.
2.2 Paper Selection Criteria
The survey defines a bounded publication corpus from major security and software engineering conferences between January 2008 and February 2019, supplemented by relevance-based inclusion from other venues.
- The core corpus includes publications from four major security conferences and three major software engineering conferences.
- The main selection period runs from January 2008 through February 2019.
- Publications from other venues or mediums are included based on the authors’ judgment of relevance.
- The paper distinguishes fuzzers from conventional testing tools partly through differing assumptions about source-code access and knowledge of the PUT.
- The authors use the presence of the word “fuzz” as a simple rule of thumb for inclusion.
2.3 Fuzz Testing Algorithm
The paper models fuzz testing as a campaign pipeline that preprocesses configurations, repeatedly schedules configurations, generates and evaluates inputs, updates configurations, and decides whether to continue.
- Algorithm 1 accepts fuzz configurations C and a timeout tlimit, then outputs a finite set of discovered bugs B.
- The model begins with PREPROCESS, which may modify configurations through actions such as instrumentation or seed-speed measurement.
- SCHEDULE selects the configuration for each fuzz iteration using the current configurations, elapsed time, and timeout.
- INPUTGEN converts a selected configuration into concrete test cases using parameters such as seeds, models, or grammars.
- INPUTEVAL executes the PUT on generated test cases, applies a bug oracle, and returns discovered bugs plus execution information.
- CONFUPDATE may revise the configuration set from execution information, while CONTINUE determines whether another iteration occurs.
2.4 Taxonomy of Fuzzers
The paper classifies fuzzers by how much semantic information they observe from each fuzz run: black-box, grey-box, or white-box. These categories trade analytical depth against execution speed and input throughput.
- Black-box Fuzzer: Black-box fuzzers observe only the PUT’s input/output behavior without inspecting its internals.
- White-box Fuzzer: White-box fuzzers analyze PUT internals and execution information to explore its state space systematically.Dynamic symbolic execution is a prominent white-box approach, often combining symbolic and concrete execution.
- Grey-box Fuzzer: Grey-box fuzzers gather partial internal or execution information, such as code coverage, without reasoning about the PUT’s full semantics.They use approximated information to gain speed and test more inputs than white-box approaches.
- Grey-box Fuzzer: Grey-box fuzzing includes coverage-guided evolutionary systems such as EFS, AFL, and VUzzer.
2.5 Fuzzer Genealogy and Overview
The paper organizes notable fuzzers chronologically and categorizes them by instrumentation granularity and the input types they use. It also summarizes each fuzzer through the five functions of the unified model fuzzer.
- Fuzzer Genealogy: Figure 1 presents selected popular fuzzers in chronological order, beginning with Miller et al.’s seminal work, and connects related techniques through a graph.Selection was based on appearance at a major conference or more than 100 GitHub stars.
- Fuzzer Genealogy: The genealogy separates black-box fuzzers on the left from grey-box and white-box fuzzers on the right.
- Fuzzer Genealogy: Fuzzers are further subdivided by the PUT’s input type, including file, network, UI, web, kernel I/O, and threads.
- Fuzzer Overview: Table 1 summarizes notable fuzzers according to their implementation of the model fuzzer’s five functions plus miscellaneous details.Some fuzzers shown in Figure 1 were omitted because of space constraints.
3 PREPROCESS
The PREPROCESS stage prepares fuzzing configurations and the PUT before iterative testing. It can instrument programs, select or trim seeds, generate drivers, and prepare models for future input generation.
- Preprocessing: PREPROCESS modifies the initial fuzz configurations before the first fuzzing iteration.
- Preprocessing: Preprocessing commonly instruments the PUT, removes redundant configurations through seed selection, trims seeds, and generates driver applications.
- Instrumentation: Static instrumentation occurs before execution and generally has lower runtime overhead, whereas dynamic instrumentation operates at runtime and can instrument dynamically linked libraries.
- Instrumentation: AFL supports source-level static instrumentation and binary-level dynamic instrumentation through QEMU.
- In-Memory Fuzzing: In-memory API fuzzing repeatedly invokes a function without restoring the PUT’s state, improving efficiency but ignoring potential repeated-call side effects.
- In-Memory Fuzzing: In-memory API fuzzing can produce non-reproducible bugs because valid calling contexts may be unavailable and cross-call side effects may be missed.Its soundness mainly depends on selecting an appropriate entry-point function, which is challenging.
- Seed Management: Seed selection reduces a potentially unbounded initial seed space by choosing a minimal set that maximizes a coverage metric.This process is called computing a minset.
- Seed Management: Seed trimming reduces input size before or during fuzzing, potentially increasing throughput because smaller seeds consume less memory.
4 SCHEDULING
Scheduling selects the next fuzz configuration using available information while balancing exploration against exploitation. Black-box methods use fuzz outcomes, while grey-box methods can also use execution feedback such as coverage.
- Scheduling: Scheduling chooses a configuration for the next iteration based on information expected to improve bug discovery or coverage.The central decision is the exploration-versus-exploitation trade-off.
- Model Fuzzer: In the model fuzzer, SCHEDULE uses the configuration set, elapsed time, and total time budget to select the next configuration.PREPROCESS and CONFUPDATE acquire the information used by this decision.
- Black-box FCS Algorithms: 85% more unique crashes were observed after replacing uniform sampling in CERT BFF with scheduling based on observed success rates.The result was measured over 5 million ffmpeg runs.
- Black-box FCS Algorithms: Woo et al. modeled black-box mutational fuzzing with WCCP/UW and designed multi-armed-bandit algorithms to handle decaying configuration success probabilities.They also normalized success probability by time spent, favoring faster configurations.
- Black-box FCS Algorithms: 1.5× more unique bugs were found with Woo et al.’s approach using the same time as the existing BFF.
- Grey-box FCS Algorithms: Grey-box FCS algorithms can use richer information, such as coverage, and AFL applies an evolutionary algorithm to select and transform configurations.
- Grey-box FCS Algorithms: AFLFast modifies AFL’s fitness, selection, and use of configurations to increase exploration and prioritize less frequently chosen inputs.
- Directed Scheduling: AFLGo, Hawkeye, FairFuzz, and QTEP extend scheduling or generation to target locations, static-analysis priorities, rare branches, or inferred faulty regions.
5 INPUT GENERATION
Input generation is a central fuzzer design decision because test-case content directly affects bug triggering. The paper organizes techniques around model-based generation, mutation-based generation, and model inference.
- Mutation-based generation: Mutation-based fuzzers generate test cases by modifying seed inputs, which are examples rather than complete descriptions of the PUT’s input space.Seeds are typically well-structured files, packets, or UI-event sequences, so mutations can remain mostly valid while introducing anomalies.
- Model-based generation: Model-based fuzzers generate test cases from models describing inputs or executions accepted by the PUT.Models may precisely specify formats with grammars or use less precise constraints such as magic values.
- Model-based generation: User-configured and built-in models support generation for general formats, specific languages, and network protocols.Examples include user-provided specifications in Peach, PROTOS, and Dharma, built-in JavaScript grammars in jsfunfuzz, and TLS models in protocol fuzzers.
- Model inference: Model inference can occur during preprocessing or fuzzing, allowing fuzzers to learn grammars, API models, or protocol state machines.Skyfire infers probabilistic context-sensitive grammars, IMF learns kernel API models, and PULSAR infers network protocol models from captured packets.
- Mutation-based generation: Common mutation operations include bit flipping, arithmetic replacement, block insertion or deletion, block replacement, permutation, and resizing.AFL, honggfuzz, and LibFuzzer also use semantically significant values such as 0, -1, and 1.
- Mutation-based generation: Mutation performance depends on the mutation ratio, and SymFuzz reports that no single ratio works well for all PUTs.BFF and FOE allocate iterations across exponentially scaled ratios, while SymFuzz infers a ratio for each seed using white-box analysis.
6 INPUT EVALUATION
Input evaluation executes the PUT on generated inputs and determines how resulting executions violate security policies. The section covers bug oracles, sanitizers, differential testing, execution optimizations, and triage.
- Evaluation pipeline: Input evaluation executes the PUT on a generated input and decides how to handle the resulting execution.Although execution is conceptually simple, its optimizations and design decisions affect fuzzer performance and effectiveness.
- Bug oracles: The canonical crash policy treats executions terminated by fatal signals as security-policy violations, efficiently detecting many memory vulnerabilities.Operating systems allow the fuzzer to trap exceptional situations without instrumentation.
- Bug oracles: Crash detection misses vulnerabilities that produce invalid results without crashing, motivating sanitizers that abort on unsafe or unwanted behavior.A stack overflow can overwrite a pointer with a valid address and let execution continue despite corrupted behavior.
- Sanitizers: AddressSanitizer detects spatial and temporal memory errors with an average slowdown of 73%, while SoftBound/CETS theoretically detects all such errors with 116% overhead.ASan uses shadow memory; SoftBound/CETS associates bounds and temporal information with each pointer.
- Bug oracles: Differential testing compares similar programs or multiple inputs to identify behavioral discrepancies and information leaks.Black-box differential fuzzing can map mutations from a PUT’s input to its output.
- Triage: Triage analyzes policy-violating test cases through deduplication, prioritization, and test-case minimization.Deduplication removes cases triggering the same bug, reducing storage and helping users estimate distinct bugs and inspect one example of each.
7 CONFIGURATION UPDATING
Configuration updating lets fuzzers use information from current executions to modify future fuzzing configurations. Black-box fuzzers leave configurations unchanged, while grey- and white-box fuzzers add, remove, or reprioritize them.
- Configuration updating: The CONFIGUPDATE function can modify the configuration set using information collected during the current fuzzing run.In its simplest form, it returns the configuration set unchanged, as in black-box fuzzers.
- Configuration updating: Grey- and white-box fuzzers use CONFIGUPDATE to incorporate new configurations or remove superseded ones for future iterations.This carries information from one fuzzing iteration into all subsequent iterations.
- Evolutionary algorithms: Evolutionary-algorithm fuzzers maintain seed pools that evolve as new promising individuals are discovered.These fuzzers form the basis of many grey-box fuzzers.
- Evolutionary algorithms: Most evolutionary fuzzers use node or branch coverage as a fitness function and add inputs discovering new coverage to the seed pool.The pool is intended to provide a diverse subselection of reachable paths.
- Fitness functions: Fitness functions can be refined with branch-hit counts, statistical estimates, intermediate comparison progress, or weighted basic blocks.Examples include AFL, STADS, LAF-INTEL, and VUzzer.
- Configuration management: Minsets limit configuration growth by retaining a minimal set of test cases that maximizes a coverage metric.AFL instead marks minset configurations as favorable and gives them a higher chance of selection.
8 RELATED WORK
Earlier fuzzing literature emphasized practical tools and techniques, while later surveys and evaluation work addressed coverage, comprehensiveness, and methodological coherence. This paper positions itself as a broad survey of the field rather than an evaluation study.
- Earlier surveys: Three fuzzing trade books published in 2007–2008 provided practical coverage of available tools, techniques, and target usages.One book distinguished black-, white-, and grey-box fuzzers without formal definitions, and its later edition added modern tools.
- Concurrent surveys: Concurrent surveys reviewed recent fuzzing advances but had narrower goals than this paper’s comprehensive study of the entire area.One focused on coverage-based fuzzing, while another was more similar in scope but informal in presentation.
- Evaluation literature: Klees et al. found no coherent way to evaluate fuzzing techniques and proposed guidelines for comparing their effectiveness.The paper treats that evaluation work as orthogonal because evaluating fuzzing algorithms is outside its scope.
9 CONCLUDING REMARKS
The paper distills modern fuzzing literature into a comprehensive, coherent view by presenting a general-purpose model fuzzer and a taxonomy. It examines each model stage’s design decisions while highlighting community achievements.
- The paper presents a general-purpose model fuzzer to explain the many forms of fuzzing currently in use.
- It organizes current fuzzers into a rich taxonomy using Figure 1 and Table 1.
- It explores every model stage’s design decisions and showcases achievements by the fuzzing community.