Source-linked AI summary
FairFuzz: Targeting Rare Branches to Rapidly Increase Greybox Fuzz Testing Coverage
Caroline Lemieux, Koushik Sen
TL;DR
AFL’s content-agnostic mutations limit deep coverage when specific input regions must remain intact. FairFuzz prioritizes rare branches and modifies mutations to preserve the input structure needed to reach them; across repeated real-world evaluations, it improves coverage on some benchmarks and reaches high coverage faster on others.
Problem
AFL remains limited in deep program coverage because it does not account for input parts that must remain unmutated to satisfy deeper constraints.
Method
FairFuzz prioritizes inputs exercising rare program parts and adjusts byte-level mutations so mutated inputs are more likely to exercise those same parts.
Results
FairFuzz produces significant 24-hour coverage increases on certain benchmarks and reaches high coverage faster on others than state-of-the-art AFL versions.
Takeaways & Limitations
Targeting rare branches while preserving branch-enabling input regions can improve greybox fuzzing coverage speed or extent on some real-world benchmarks.
Takeaways & Limitations
FairFuzz cannot target branches never hit by any AFL input and offers little benefit for progress toward a single multi-byte magic-number comparison without new coverage.
Abstract
from arXiv · showhide
In recent years, fuzz testing has proven itself to be one of the most effective techniques for finding correctness bugs and security vulnerabilities in practice. One particular fuzz testing tool, American Fuzzy Lop or AFL, has become popular thanks to its ease-of-use and bug-finding power. However, AFL remains limited in the depth of program coverage it achieves, in particular because it does not consider which parts of program inputs should not be mutated in order to maintain deep program coverage. We propose an approach, FairFuzz, that helps alleviate this limitation in two key steps. First, FairFuzz automatically prioritizes inputs exercising rare parts of the program under test. Second, it automatically adjusts the mutation of inputs so that the mutated inputs are more likely to exercise these same rare parts of the program. We conduct evaluation on real-world programs against state-of-the-art versions of AFL, thoroughly repeating experiments to get good measures of variability. We find that on certain benchmarks FairFuzz shows significant coverage increases after 24 hours compared to state-of-the-art versions of AFL, while on others it achieves high program coverage at a significantly faster rate.
1 INTRODUCTION
FairFuzz targets a key AFL limitation: shallow exploration caused by mutations that destroy input structure needed for deeper paths. It prioritizes rare branches, preserves branch-enabling input regions during mutation, and evaluates these changes across repeated real-world experiments.
- Motivation: AFL is popular for its simple setup and mutation-based process, which retains inputs that discover new coverage.It mutates user-provided inputs with byte-level operations, executes them, collects low-overhead coverage, and saves interesting inputs.
- Motivation: AFL often fails to explore deeply guarded program regions because it does not identify input parts needed to satisfy deeper constraints.Inputs may require specific headers and byte sequences that ordinary mutation can destroy.
- Approach: FairFuzz prioritizes inputs exercising rare program parts and adjusts byte-level mutations to preserve conditions for exercising those parts.The mutation strategy can also target other program characteristics, such as a recently patched function.
- Evaluation: FairFuzz is implemented open-source on AFL and evaluated against AFL, FidgetyAFL, and AFLFast.new on nine real-world benchmarks.The evaluation examines coverage speed, 24-hour coverage, targeted-branch inputs, and crash finding.
- Evaluation: The study repeats AFL comparisons 20 times and reports variability because AFL-based techniques are highly nondeterministic.The paper presents confidence intervals and argues that repeated measurements are necessary for correct comparisons.
2 OVERVIEW
AFL uses lightweight coverage feedback to guide mutations, but its content-agnostic byte mutations can destroy structure needed to pass nested conditions. FairFuzz identifies rare branches and preserves input positions whose mutation would prevent those branches from being exercised.
- AFL overview: AFL is a greybox mutation-based fuzzer that uses limited program feedback without source-code analysis.It is built around a queue of seed inputs that are repeatedly selected, mutated, executed, and replaced when they produce new coverage.
- Coverage model: AFL represents coverage as branch ID and bucketized hit-count pairs, calling an input’s set of pairs its path.A new-coverage input is one that hits a new branch or produces a relevant coverage distinction.
- AFL limitation: AFL’s deterministic and havoc stages apply byte-oriented mutations without considering input contents, so they can destroy structure required for deeper execution.Nested comparisons in libxml require ordered strings such as <!ATTLIST, a valid attribute type, and #FIXED.
- FairFuzz approach: FairFuzz identifies rare branches by tracking how many generated inputs hit each branch and selecting branches below a dynamic rarity cutoff.The cutoff is defined using the smallest power of two bounding the number of inputs hitting the rarest branch.
- FairFuzz approach: FairFuzz computes a branch mask during deterministic mutation to mark input positions that remain overwritable, deletable, or insertable while preserving the target branch.Later mutation stages avoid changing crucial positions identified by this mask.
- Related work: Prior AFL extensions target rare paths or magic-number branches, but AFLFast does not effectively address nested byte comparisons like those in the libxml example.FairFuzz is evaluated against AFLFast because both emphasize rare execution regions, despite targeting different structures.
3 FAIRFUZZ ALGORITHM
FairFuzz targets rare branches by selecting inputs that exercise them and constraining subsequent mutations to preserve those targets. Its design includes dynamic rarity thresholds, branch-specific mutation masks, and adaptations to prevent selection from becoming stuck while maintaining efficiency.
- Selecting and targeting rare branches: FairFuzz modifies AFL in two ways: it selects inputs hitting rare branches and biases their mutations toward those branches.The target is to increase the frequency of hitting the selected rare branch while still exploring different program paths.
- Selecting and targeting rare branches: A branch is rare when its input-hit count is no greater than a dynamically chosen cutoff based on the rarest branch.The cutoff is the smallest power of two that bounds the rarest branch’s input-hit count, avoiding fixed thresholds across benchmarks.
- Selecting and targeting rare branches: FairFuzz tracks branch hit counts, selects queue inputs that hit rare branches, and targets the rarest such branch when an input hits several.The selected target branch guides subsequent mutation.
- Handling selection and efficiency: Because strict rare-branch selection can repeatedly choose the same input, FairFuzz excludes a target branch when none of its seed’s mutations hits it.Excluded branches are ignored when identifying rare branches and recalculating the rarity cutoff.
- Mutating inputs: The branch mask marks input positions as overwritable, deletable, or insertable when modifying them can preserve the target branch.FairFuzz computes the mask during deterministic mutation stages and uses it to restrict later deterministic and havoc mutations.
- Handling selection and efficiency: FairFuzz keeps branch-mask computation practical by shortening inputs and relaxing trimming to preserve only the original input’s target branch.Mask computation is linear in selected-input length, so shorter queue inputs are important for efficiency.
4 IMPLEMENTATION AND EVALUATION
FairFuzz evaluates rare-branch targeting against AFL variants using coverage, targeting, and crash-finding analyses. It generally accelerates coverage and improves structural input discovery, while showing benchmark-specific limitations and high crash-finding variability.
- Evaluation design: Basic block transitions are the primary coverage metric because it is robust to input-discovery order.The evaluation reports averages and variability across repeated runs.
- Coverage compared to prior techniques: FairFuzz generally increases coverage most rapidly early in execution and leads or reaches the upper bound on most benchmarks.It shows rapid gains on objdump, readelf, readpng, tcpdump, and xmllint; AFLFast.new has the edge on c++filt, while techniques tie on mutool and djpeg.
- Coverage compared to prior techniques: 6,896 branches versus 6,541 for AFLFast.new after 24 hours: FairFuzz retains higher average xmllint coverage even without three outlier runs.One FairFuzz run covered 6,160 branches, while two covered 7,969 and 10,990 branches; the reported averages excluding these runs remain 6,896 and 6,541.
- Input structure and coverage: FairFuzz’s coverage gains reflect more frequent discovery of structured constraints, keywords, packet lengths, organization codes, and valid protocol fields.Examples include XML keywords, legal ForCES packet lengths, RFC 2684 OUIs, and valid SNMP fields.
- Input structure and coverage: FairFuzz covered 39 cases in xmllint’s 57-case error-message statement, compared with 33 for AFL and 22 for both FidgetyAFL and AFLFast.new.The generated inputs were not necessarily well-formed, but they enabled broader exploration of parser faults.
5 DISCUSSION
FairFuzz cannot target branches that no AFL input reaches, and its branch-focused strategy can struggle with long inputs and repeated loop iterations. Input-format transformations such as comparison unrolling may help expose additional coverage opportunities.
- FairFuzz cannot target branches that are never hit by any AFL input.
- FairFuzz’s success on xmllint depended on byte-by-byte comparisons exposing new coverage as progress was made.A single multi-byte comparison would not provide the same coverage feedback for intermediate progress.
- LLVM comparison-unrolling passes can transform multi-byte comparisons into byte-by-byte comparisons and may therefore complement FairFuzz’s approach.
6 OTHER RELATED WORK
Related fuzzing approaches trade generality, automation, or scalability against specialized input modeling, targeted analysis, symbolic precision, or search-based optimization. FairFuzz differs by using a fully automatic, lower-specificity strategy for targeting rare branches.
- Symbolic execution directly satisfies unexplored path constraints but can face scalability problems from path explosion.
- Traditional blackbox fuzzing optimizes a mutation ratio, but these optimizations do not apply to AFL-type generational fuzzers.
- Specialized fuzzers for network protocols and source code can outperform FairFuzz on those formats, while FairFuzz requires neither user inputs nor extensive tuning.
- Input-format learning systems infer structures or grammars, whereas FairFuzz uses a branch mask to preserve important input regions during mutation.
- Taint- and symbolic-analysis tools target likely crash locations or vulnerable branches using program-data relationships, unlike FairFuzz’s coverage-guided mutation strategy.
- VUzzer combines static and dynamic analysis with a Markov Chain to identify rare program parts, whereas FairFuzz uses an empirical approach.
- Randoop and EvoSuite generate method-call sequences, unlike FairFuzz’s input-generation form of fuzzing.
- Search-based testing optimizes observable fitness functions but works less well when coverage changes are not smooth with respect to input mutations.