PaperlayerView exact revision on arXiv

Source-linked AI summary

Evaluating Fuzz Testing

George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, Michael Hicks

arXiv:1808.09700v2cs.CR

TL;DR

Fuzzing algorithms are mainly evaluated experimentally, raising the question of how to obtain trustworthy evidence. The paper surveys 32 fuzzing evaluations and conducts extensive AFL/AFLFast experiments, finding that incomplete methodology can weaken or mislead conclusions and motivating concrete evaluation guidelines.

  • Problem

    Because fuzzing algorithms are primarily evaluated experimentally, the paper asks what setup is needed to produce trustworthy comparisons.

  • Method

    The authors survey 32 recent papers and experimentally compare AFLFast with AFL across seeds, timeouts, targets, trials, and bug-measurement methods.

  • Results

    No surveyed paper fully followed the proposed methodology, and the authors’ experiments showed that omitted safeguards can produce misleading or weakened conclusions.

  • Takeaways & Limitations

    Trustworthy fuzzing evaluations should use repeated statistically tested trials, diverse targets, varied documented seeds, long or justified timeouts, and known bugs rather than crash heuristics.

  • Takeaways & Limitations

    Synthetic benchmarks may not generalize to actual programs because their program sizes, protocols, and injected bugs may differ from real-world software.

Abstract

from arXiv · show

Fuzz testing has enjoyed great success at discovering security critical bugs in real software. Recently, researchers have devoted significant effort to devising new fuzzing techniques, strategies, and algorithms. Such new ideas are primarily evaluated experimentally so an important question is: What experimental setup is needed to produce trustworthy results? We surveyed the recent research literature and assessed the experimental evaluations carried out by 32 fuzzing papers. We found problems in every evaluation we considered. We then performed our own extensive experimental evaluation using an existing fuzzer. Our results showed that the general problems we found in existing experimental evaluations can indeed translate to actual wrong or misleading assessments. We conclude with some guidelines that we hope will help improve experimental evaluations of fuzz testing algorithms, making reported results more robust.

1 INTRODUCTION

Because fuzzing algorithms are primarily evaluated experimentally, trustworthy comparisons require careful choices of baselines, benchmarks, metrics, parameters, trials, and statistical analysis. The authors’ survey and experiments show that common evaluation practices can produce misleading conclusions.

  • Motivation: Fuzzers are effective security tools, but new fuzzing algorithms are primarily assessed through experiments.AFL found 68 bugs versus angr’s 16 in the same corpus over 24 hours.
  • Evaluation requirements: Evaluations must specify a baseline, representative target programs, a meaningful performance metric, and configuration parameters such as seeds and timeouts.Because fuzzing is random, evaluations also need enough trials and statistical tests to distinguish real improvements from chance.
  • Study design: 32 surveyed papers all had important shortcomings in their experimental evaluations, and the authors’ 50,000-plus CPU-hour study examined their practical consequences.The study compared AFLFast with AFL as an advanced algorithm and baseline.
  • Empirical threats: Run-to-run performance, elapsed time, and seed choice can reverse apparent comparisons between fuzzers.On nm, AFL outperformed AFLFast at six hours with non-empty seeds, but the trend reversed after 24 hours; seed changes also shifted AFLFast from over 1,000 crashes to 24.
  • Measurement and benchmarks: Coverage and crash-deduplication heuristics can misrepresent bug-finding performance, while diverse benchmarks are needed because results vary by target program.Coverage profiles labeled 57,142 cxxfilt crashes as unique even though nine patches accounted for them.
  • Recommendations: The paper recommends multiple trials with statistical tests, varied seeds, longer timeouts, ground-truth bug measures, and an agreed-upon diverse benchmark.These guidelines are intended to make reported evaluations more robust.

2 BACKGROUND

Fuzzers iteratively mutate concrete seed inputs, execute the target program, retain interesting inputs, and stop when a goal or timeout is reached. Different fuzzers vary in the observations, mutations, selection policies, and analyses used throughout this loop.

  • Core fuzzing loop: Fuzzers operate on concrete inputs and repeatedly generate, mutate, evaluate, and retain inputs based on observed program behavior.The loop starts from an initialized seed corpus and ends when progress or a timeout satisfies the stopping condition.
  • Core fuzzing loop: The fuzzing procedure is parameterized by seed initialization, stopping, candidate selection, mutation, evaluation, and interestingness functions.These functions determine what inputs enter the queue and which observations are preserved.
  • Observation models: Black-box fuzzers observe crashes, gray-box fuzzers also use execution information such as branches, and white-box fuzzers exploit program semantics.The observation model distinguishes major classes of fuzzing techniques.
  • Goals and outputs: Fuzzers may stop after a crash or continue collecting distinct crashes and other behaviors such as unusually long execution times.The stopping rule depends on the fuzzer configuration and its goal.
  • Research landscape: Modern techniques alter seed selection, mutation, evaluation, observations, or candidate selection using grammars, symbolic execution, taint, dynamic slicing, instrumentation, and other analyses.These changes address different stages of the common fuzzing loop.

3 OVERVIEW AND EXPERIMENTAL SETUP

The paper evaluates how fuzzing studies choose benchmarks, baselines, metrics, trials, seeds, and timeouts, then uses AFL and AFLFast to demonstrate why these choices matter. Its setup treats existing evaluation practice as systematically incomplete rather than proposing a new fuzzer.

  • Evaluation framework: The study assesses baseline selection, representative targets, performance measurement, and parameters such as seeds and timeouts across prior fuzzing evaluations.Table 1 records these methodological choices for 32 papers.
  • Evaluation framework: No surveyed evaluation fully carried out all recommended steps, and the authors argue that some omissions can yield misleading or incorrect conclusions.They distinguish open questions about best practice from naive approaches that should be avoided.
  • Fuzzers: The experiments use AFL 2.43b as baseline B and AFLFast as advanced algorithm A, with AFLNaive occasionally representing a black-box configuration.The tested AFLFast version was based on AFL 2.43b and was selected as a representative advanced fuzzer.
  • Benchmarks: The benchmark consists of nm, objdump, cxxfilt, gif2png, and FFmpeg drawn from prior fuzzing evaluations.The authors explicitly do not claim this is a complete benchmark suite; they use it to show how targets can change conclusions.
  • Metrics: The primary experimental crash metric counts AFL coverage-profile “unique” crashes, although the paper identifies this measure as problematic.The study also includes ground-truth analysis for bug assessment.
  • Platform: Experiments control machine assignment across fuzzer combinations to account for possible system variation.Each benchmark program was tested on the same machine for all compared configurations.

4 STATISTICALLY SOUND COMPARISONS

Trustworthy fuzzing comparisons require repeated trials, variance-aware reporting, and statistical tests because randomness can make single runs or average differences misleading. Confidence intervals help, but visual inspection alone is less conclusive than statistical comparison.

  • Fuzzers should be run for many trials because randomness can produce substantially different outcomes across runs.A single run may support opposite conclusions depending on whether it is unusually favorable or unfavorable.
  • 30 runs of AFL and AFLFast showed that observed performance can vary dramatically even on the same target.Figure 2 summarizes medians, confidence intervals, and extrema over repeated runs.
  • 12 of the 15 papers using multiple trials did not characterize performance variance and instead compared average performance.Ignoring variance can make apparent differences difficult to interpret.
  • A median difference need not be statistically significant: gif2png showed 51 crashes for AFLFast versus 39 for AFL, but the Mann–Whitney test gave p > 0.05.Statistical testing assesses whether a measured difference is likely to reflect more than chance variation.
  • Confidence intervals are useful, but evaluations should statistically compare the proposed fuzzer with its baseline rather than relying only on visual judgment.The paper notes that permutation and bootstrap-based tests are viable alternatives, while the preferred test remains debatable.

5 SEED SELECTION

Seed choice can substantially alter fuzzing results and interact with algorithm choice. Evaluations should report seed construction, test varied seeds, and include empty seeds as a useful baseline.

  • 30 of 32 surveyed papers used non-empty seed corpora, but many did not describe their contents or collection process.The paper recommends specifying seed construction and, preferably, releasing the actual seeds.
  • Seed effects can interact with algorithm choice, so a single seed configuration cannot establish that one fuzzer is generally superior to another.The paper argues that varied seeds, including the empty seed, reduce uncertainty about this interaction.
  • Different valid seeds produced sharply different FFmpeg results: one single-seed setup found around 100 crashes, while another found fewer than 5 after 24 hours.This variation occurred for both AFL and AFLFast.
  • For AFL and AFLFast, empty seeds produced hundreds of crashing inputs, whereas AFLNaive produced none; with 1-made or 3-made seeds, AFLNaive found 5000 versus 102/129.Table 2 reports medians at the 24-hour timeout and statistical tests against AFL.
  • AFLFast was superior to AFL with an empty seed but no longer outperformed AFL on nm when using 1-made seeds.Both AFL and AFLFast generally found fewer crashes with the 1-made seeds.

6 TIMEOUTS

Timeout selection affects the conclusions drawn from fuzzing evaluations because relative performance can change over time. The paper recommends examining performance trajectories and using sufficiently long runs.

  • Prior fuzzing evaluations used timeouts ranging from 1 hour to days or weeks, with 24 hours and 5–6 hours among the most common choices.Most papers reported their timeout without explaining why it was selected.
  • Relative performance can change over time, so terminating an experiment too quickly may produce an incomplete result.The paper gives the example that AFL found no objdump bugs after six hours, while longer runs produced a different picture.
  • Figure 4 reports that AFLFast was superior to AFL at 6 hours with p < 10^-13, whereas AFL was superior at 24 hours with p = 0.000105.The comparison uses three sampled seeds on nm.
  • Evaluations should plot performance over time and use at least a 24-hour timeout, since shorter-time results can be extracted from longer runs.Longer runs can reveal algorithms that start slowly but improve later.
  • Area under the curve can complement crash counts at selected times by measuring how quickly crashes are found throughout the run.The paper illustrates this with contrasting crash-per-second timing patterns.

7 PERFORMANCE MEASURES

Crashing inputs are an unreliable proxy for distinct bugs because many inputs can trigger the same bug and automated deduplication heuristics can misclassify root causes. Ground-truth analysis shows that coverage profiles and stack hashes can substantially distort bug counts, so evaluations should prioritize verified bugs and treat coverage as secondary.

  • Performance Measures: Many crashing inputs can trigger the same bug, so counting crashes may rank fuzzers differently from counting actual bugs.A fuzzer can find more crashes than another while finding the same or fewer bugs.
  • Performance Measures: Coverage profiles and stack hashes are popular crash-deduplication heuristics, but experiments found them poor at clustering inputs by root cause.Coverage-based deduplication was used by 7 papers, and stack hashes by 7 papers.
  • 7.1 Ground Truth: Bugs Found: 57,142 coverage-profile-“unique” crashing inputs for cxxfilt corresponded to 9 distinct patches, demonstrating dramatic overcounting of bugs.The ground-truth procedure grouped inputs by the patch that made them gracefully exit.
  • 7.2 AFL Coverage Profile: AFLFast found significantly more crashes than AFL, but the difference in bugs was not statistically significant: p=10^-10 for crashes versus p=0.066 for bugs.The comparison also showed at best a weak correlation between crashing-input counts and bugs found per run.
  • 7.3 Stack hashes: Stack hashing reduced overcounting relative to coverage profiles but still produced an inflated estimate and discarded bugs because about 16% of hashes were non-unique.For one label, no unique hash existed; the hashes only falsely matched other crashing inputs.
  • 7.4 Code Coverage: Coverage should be a secondary measure, while ground truth based on discovered bugs should be primary.Maximizing coverage is not fundamentally connected to finding bugs, and the correlation may be weak.

8 TARGET PROGRAMS

The choice of target programs strongly affects fuzzing conclusions: small or mismatched suites can make advantages appear broader than they are. The paper argues for larger, diverse, independently defined benchmarks with known ground truth while recognizing limits of both real and synthetic programs.

  • Real programs: Most papers used only a median of seven real programs without clearly justifying their representativeness for larger target populations.FuzzSim was an exception, using more than 100 programs and explaining how they were collected.
  • Real programs: Small, insufficiently representative target sets can make AFLFast appear uniformly superior to AFL, whereas adding FFmpeg and gif2png removed a statistically significant difference.The first comparison used nm, objdump, and cxxfilt; the broader comparison found no statistical difference on FFmpeg and gif2png.
  • Real programs: Using different target versions across papers makes even informal comparisons difficult, as binutils evaluations used versions 2.26, 2.28, and 2.29.Several evaluations overlapped in target names but not in exact versions.
  • Suites of artificial programs (or bugs): CGC contains 296 buggy programs, while LAVA-M contains four bug-injected coreutils programs with bug counts ranging from a few dozen to more than 2000.Both suites provide telltale signs identifying triggered bugs, supporting direct counting of bugs found.
  • Suites of artificial programs (or bugs): Synthetic suites may not generalize to real software: CGC programs are small and often text-protocol based, while LAVA-M bugs may follow simple patterns unlike bugs found in the wild.The paper notes that no independent study had established how representative or general these suites are.
  • Toward a Fuzzing Benchmark Suite: The paper calls for a large, independently defined fuzzing benchmark suite with clear bug indicators, representative program coverage, and defenses against benchmark overfitting.It favors real programs with known bugs for ecological validity but leaves the appropriate suite size open, suggesting that 25 may be closer than seven.

9 CONCLUSIONS AND FUTURE WORK

The paper argues that trustworthy fuzz-testing research requires rigorous, reproducible experimental methodology. Its recommendations address randomness, benchmark diversity, bug measurement, seed choices, and runtime, while motivating further work on benchmarks and crash deduplication.

  • Recommended evaluation methodology: Fuzz-testing evaluations should compare a baseline and new algorithm on representative targets, using meaningful parameters and enough repeated trials for statistical testing.The methodology includes target programs, performance measures, seed choices, timeouts, and statistical treatment of randomness.
  • Observed evaluation problems: Many prior evaluations omitted multiple trials or statistical tests, used heuristic crash counts instead of distinct bugs, selected short timeouts, or overlooked seed effects.These omissions can weaken or mislead conclusions about algorithmic improvements.
  • Conclusion: The authors conclude that the fuzzing community needs more rigorous experiments to draw reliable conclusions about claimed technical advances.The conclusion follows the survey of 32 papers and the authors’ empirical demonstration that evaluation choices can weaken evidence.
  • Recommended evaluation methodology: The study recommends multiple trials with statistical tests, diverse benchmarks containing known bugs, bug-based performance measures, documented seed choices, and at least 24-hour timeouts unless shorter runs are justified.Performance should be plotted over time, with coverage retained only as a secondary measure.
  • Future work: Future work includes developing well-assessed benchmark suites, studying crash-deduplication methods on realistic fuzzing runs, and exploring algorithmic enhancements informed by the absence of a universally best fuzzing strategy.The paper identifies benchmark construction and deduplication as open research needs.
Loading 1808.09700v2…