PaperlayerView exact revision on arXiv

Source-linked AI summary

Full-speed Fuzzing: Reducing Fuzzing Overhead through Coverage-guided Tracing

Stefan Nagy, Matthew Hicks

arXiv:1812.11875v2cs.CRcs.SE

TL;DR

Coverage-guided fuzzers spend most of their time tracing test cases even though only a small fraction increase coverage. The paper introduces coverage-guided tracing, which uses modified binaries to identify coverage-increasing cases before conventional tracing, reducing overhead and increasing executions.

  • Problem

    Coverage-guided fuzzers trace all generated test cases, although only a small percentage increase coverage and tracing dominates runtime.

  • Method

    Coverage-guided tracing modifies target binaries to self-report new coverage, using this interest-oracle signal to restrict conventional tracing to coverage-increasing test cases.

  • Results

    Coverage-guided tracing reduces overhead by as much as 1300% for black-box binaries and 70% for white-box binaries.

  • Takeaways & Limitations

    The results support exploiting the rarity of coverage-increasing test cases to execute most fuzzing inputs at native speed and improve fuzzing throughput.

Abstract

from arXiv · show

Of coverage-guided fuzzing's three main components: (1) testcase generation, (2) code coverage tracing, and (3) crash triage, code coverage tracing is a dominant source of overhead. Coverage-guided fuzzers trace every testcase's code coverage through either static or dynamic binary instrumentation, or more recently, using hardware support. Unfortunately, tracing all testcases incurs significant performance penalties---even when the overwhelming majority of testcases and their coverage information are discarded because they do not increase code coverage. To eliminate needless tracing by coverage-guided fuzzers, we introduce the notion of coverage-guided tracing. Coverage-guided tracing leverages two observations: (1) only a fraction of generated testcases increase coverage, and thus require tracing; and (2) coverage-increasing testcases become less frequent over time. Coverage-guided tracing works by encoding the current frontier of code coverage in the target binary so that it self-reports when a testcase produces new coverage---without tracing. This acts as a filter for tracing; restricting the expense of tracing to only coverage-increasing testcases. Thus, coverage-guided tracing chooses to tradeoff increased coverage-increasing-testcase handling time for the ability to execute testcases initially at native speed. To show the potential of coverage-guided tracing, we create an implementation based on the static binary instrumentor Dyninst called UnTracer. We evaluate UnTracer using eight real-world binaries commonly used by the fuzzing community. Experiments show that after only an hour of fuzzing, UnTracer's average overhead is below 1%, and after 24-hours of fuzzing, UnTracer approaches 0% overhead, while tracing every testcase with popular white- and black-box-binary tracers AFL-Clang, AFL-QEMU, and AFL-Dyninst incurs overheads of 36%, 612%, and 518%, respectively.

I. INTRODUCTION

Fuzzing is widely used for vulnerability discovery, but coverage tracing imposes substantial overhead because most generated test cases do not increase coverage. The paper introduces coverage-guided tracing and evaluates UnTracer as a way to restrict tracing to coverage-increasing cases.

  • Fuzzing automates vulnerability discovery by generating test cases, monitoring execution, and triaging bug- and crash-producing inputs.
  • Coverage tracing is costly because most test cases do not increase coverage, even though fuzzers trace every generated test case.The paper identifies tracing as a dominant source of fuzzing time.
  • Coverage-guided tracing transforms the target binary into an interest oracle that self-reports new coverage before conventional tracing collects detailed coverage information.Non-increasing cases can execute without tracing, while increasing cases trigger conventional tracing.
  • Coverage-guided tracing trades higher handling cost for coverage-increasing cases against initially native-speed execution of other cases.The additional handling cost is reported as about twice the cost of tracing alone.
  • UnTracer implements coverage-guided tracing with Dyninst and is evaluated on eight real-world programs against AFL-Clang, AFL-QEMU, and AFL-Dyninst.The evaluation includes white-box and black-box tracing approaches and programs from domains including cryptography and image processing.

B. Coverage-Guided Fuzzing

Coverage-guided fuzzers repeatedly mutate seeds, execute test cases, trace coverage, and retain only inputs that reach new code. The paper focuses on reducing the cost of tracing discarded cases while supporting block- and edge-based coverage workflows.

  • Coverage-Guided Fuzzing: Coverage-guided fuzzing mutates queued seeds, traces every generated test case, retains coverage-increasing cases, and discards the rest.Crashing test cases are separately reported during the execution-monitoring loop.
  • Coverage-Guided Fuzzing: Coverage-guided fuzzers measure coverage using basic blocks, basic-block edges, or basic-block paths through instrumentation, emulation, or hardware-assisted tracing.Basic blocks are straight-line code sequences ending in control-flow transfers.
  • Coverage-Guided Fuzzing: Edge coverage can be represented as source–destination basic-block pairs, allowing edge coverage to be inferred from block coverage after critical-edge elimination.
  • Coverage-Guided Fuzzing: Coverage-guided tracing targets fuzzers that trace block or edge coverage, while path-granularity tracing remains an envisioned use of Intel Processor Trace.
  • Focus of this Paper: The paper presents coverage-guided tracing as an Amdahl’s-Law-inspired response to the common case of tracing non-coverage-increasing test cases.UnTracer is the paper’s framework for applying this approach to coverage-guided fuzzers.

III. IMPACT OF DISCARDED TEST CASES

The study examines whether discarded test cases consume substantial fuzzing time in both blind and smart fuzzers. Across eight one-hour trials, execution and tracing dominate runtime while coverage-increasing cases remain extremely rare.

  • The experiments measure execution/tracing time and coverage-increasing-testcase rates for AFL and Driller across eight binaries using one-hour trials.Coverage-increasing cases are counted from AFL queue entries marked +cov.
  • AFL uses random mutation, whereas Driller augments mutation with selective concolic execution to produce coverage-increasing test cases.AFL-Clang and AFL-QEMU represent white-box and black-box AFL tracing, while Driller-AFL uses QEMU tracing.
  • 91.8% and 97.3% of each hour are spent on execution and coverage tracing by AFL-Clang and AFL-QEMU, respectively.These are average runtime percentages across the benchmarks.
  • 95.9% of each hour is spent on execution and coverage tracing by Driller-AFL.This average is reported across the evaluated benchmarks.
  • .0062%, .0257%, and .00653% of generated test cases are coverage-increasing for AFL-Clang, AFL-QEMU, and Driller-AFL, respectively.These averages show that both blind and smart fuzzers mostly execute and trace non-coverage-increasing cases.

IV. COVERAGE-GUIDED TRACING

Coverage-guided tracing filters test cases before full coverage tracing by using an interest oracle that identifies previously uncovered basic blocks. As coverage accumulates, fewer test cases trigger the oracle, so overall overhead approaches zero.

  • Coverage-Guided Tracing: Coverage-guided tracing inserts an interest-oracle filtering step between test-case generation and full coverage tracing.The oracle marks only test cases that trigger interrupts in previously uncovered basic blocks as coverage-increasing.
  • Coverage-Guided Tracing: Coverage-increasing test cases are fully traced, after which interrupts are removed from their newly visited basic blocks.The workflow repeats oracle execution, tracing, unmodification, and oracle execution for subsequent test cases.
  • Coverage-Guided Tracing: Coverage-guided tracing supports block coverage and, when critical edges are mitigated, edge coverage through a separate tracing-only target version.This design remains compatible with most existing tracing approaches.
  • Theoretical Performance Impact: As more basic blocks are unmodified, the oracle increasingly resembles the target, making coverage-increasing test cases less likely and reducing overall overhead toward 0%.The approach trades additional handling for coverage-increasing test cases against faster execution of ordinary test cases.

V. IMPLEMENTATION: UNTRACER

UnTracer implements coverage-guided tracing within AFL using separate interest-oracle and tracer binaries. Its workflow uses forkservers and static analysis to identify, trace, and process coverage-increasing test cases.

  • UnTracer Overview: UnTracer is an implementation of coverage-guided tracing integrated with the modified AFL 2.52b grey-box fuzzer.It instruments separate oracle and tracer binaries for filtering and coverage identification.
  • UnTracer Overview: UnTracer instruments an interest oracle and a tracer, giving both forkservers while adding basic-block coverage instrumentation to the tracer.Static analysis identifies the oracle’s basic blocks before interrupts are inserted.
  • UnTracer Overview: During fuzzing, the oracle executes all test cases, while the tracer executes only those identified as coverage-increasing.This separates inexpensive filtering from full coverage extraction.
  • UnTracer Overview: UnTracer uses forkservers to avoid repetitive process initialization and improve execution speed for both oracle and tracer binaries.The oracle uses AFL’s assembly-time instrumentation after Dyninst-based instrumentation showed performance problems.

C. Interest Oracle Binary

The interest oracle is a modified target binary that self-reports coverage-increasing test cases through interrupts placed at uncovered basic blocks. Its construction depends on basic-block discovery and interrupt compatibility constraints.

  • Interest Oracle Binary: The interest oracle adds software interrupts at the start of uncovered basic blocks to identify test cases that exercise new coverage.A triggered interrupt marks the test case as coverage-increasing.
  • Interest Oracle Binary: Dyninst-related performance problems led UnTracer to use AFL’s assembly-time instrumentation for the oracle forkserver.The reported issue involved excessive function calls after forkserver exit, and it was unresolved before publication.
  • Interest Oracle Binary: Oracle construction requires prior knowledge of basic-block addresses obtained through static control-flow analysis.UnTracer uses Dyninst to enumerate blocks and binary file I/O to insert interrupts.

D. Tracer Binary

UnTracer extracts full coverage for oracle-positive test cases with a separate instrumented tracer. Its evaluation compares this design with three conventional tracers across eight real-world benchmarks using controlled repeated trials.

  • Tracer Binary: The tracer binary extracts new coverage only after the oracle identifies a coverage-increasing test case.Dyninst inserts a forkserver and callbacks in each basic block, with callbacks recording block addresses.
  • Tracer Binary: UnTracer records uniquely covered basic blocks to reduce logging, reading, and processing overhead from repeated execution.This optimization targets loops and other traces containing repeatedly executed blocks.
  • Tracer Binary: UnTracer removes interrupts from newly covered blocks, while a global-coverage hashmap avoids repeatedly unmodifying blocks already seen in prior traces.These operations update the oracle’s frontier as fuzzing proceeds.
  • Evaluation: The evaluation compares UnTracer with AFL-Clang, AFL-QEMU, and AFL-Dyninst on eight real-world benchmarks covering white-box and black-box tracing approaches.The comparison spans static and dynamic binary rewriting under the same AFL fuzzer.
  • Evaluation: Each benchmark uses five 24-hour datasets, eight trials per dataset, and trimmed-mean denoising for per-test-case tracing-time measurements.The experiments examine overall performance, overhead sources, and the effect of coverage-increasing-test-case rate.

B. Experiment Infrastructure

The evaluation uses pre-generated test-case datasets and a tracing-focused infrastructure to compare UnTracer with established tracers across varied real-world benchmarks. Baseline execution is defined using forkserver-based execution without coverage tracing.

  • Evaluation design: Evaluations use five pre-generated test-case datasets per benchmark, with all tracers run on the same datasets for fairness.QEMU generates the datasets, while the analysis records only time spent executing and tracing test cases.
  • Measurement infrastructure: TestTrace replays each dataset’s test cases, measures tracing time, and logs per-test-case trace times for each tracing mode.UnTracer measurements include both initial full-speed execution and handling time for coverage-increasing test cases.
  • Benchmark selection: The benchmark set spans eight software categories, including cryptography, image processing, data archiving, and web development.Candidates were selected from popular fuzzers’ trophy cases and public benchmark repositories, then partitioned by program type.
  • Compilation: The evaluation compiles benchmarks with Clang/LLVM using benchmark-specific default compiler options.AFL-Clang is used because AFL-GCC compilation failed for some binaries after GCC changes.
  • Baseline: The ground-truth baseline uses statically instrumented forkserver execution without coverage tracing to represent the fastest known execution speed.All evaluated tracers use forkserver-based execution, making the baseline comparable to their execution model.

3) AFL-QEMU:

UnTracer substantially lowers black-box tracing overhead relative to AFL-QEMU and AFL-Dyninst across the evaluated benchmarks. Its average overhead is 0.3%, compared with 612% for AFL-QEMU and 518% for AFL-Dyninst, with statistically large execution-time differences.

  • Timeouts: Missed coverage from prematurely timed-out test cases can cause coverage-increasing inputs to be misidentified as non-coverage-increasing.Because fuzzers mutate coverage-increasing inputs, this misidentification can slow coverage indefinitely.
  • Timeouts: Small execution timeouts can distort tracer overhead comparisons by making slower and faster tracers appear more similar.A 100ms timeout caused frequent timeouts and was found too restrictive because baseline executions had substantially fewer timeouts.
  • Per-test-case behavior: Coverage-increasing test cases in the cjson dataset incur double the overhead of AFL-Dyninst tracing alone.Figure 9 separates these cases from non-coverage-increasing cases using red dots, relative to the average baseline execution speed.
  • Black-box tracer comparison: 0.3% overhead is UnTracer’s average across all benchmarks, versus 612% for AFL-QEMU and 518% for AFL-Dyninst.The corresponding average relative execution times are 1.003, 7.12, and 6.18, respectively.
  • Statistical analysis: UnTracer’s execution time is statistically smaller than both AFL-QEMU’s and AFL-Dyninst’s across the benchmark trials.The Vargha–Delaney A-hat statistic is 1.0 for all comparisons, exceeding the conventionally large effect-size threshold of 0.71.

2) White-box binary tracing:

UnTracer substantially reduces white-box tracing overhead by tracing only coverage-increasing test cases, though handling those cases adds concentrated costs. Its overhead declines as coverage-increasing cases become rarer, approaching native performance over time.

  • 0.3% overhead: UnTracer averages relative execution time 1.003 across eight benchmarks, versus AFL-Clang’s 36% overhead.AFL-Clang averages relative execution time 1.36; the comparison excludes sfconvert from statistical evaluations because timeouts make tracer overheads similar.
  • UnTracer’s coverage-increasing test cases incur double the overhead of tracing with AFL-Dyninst alone, while non-coverage-increasing cases remain clearly separable.
  • By 1000 test cases, UnTracer reaches 90% of native-binary performance as the impact of individual coverage-increasing cases diminishes.The authors identify this trend as an opportunity for a hybrid model that traces initial cases until UnTracer becomes beneficial.
  • Overhead components: Coverage-increasing test cases trigger oracle handling, tracing, and forkserver operations, whereas the overwhelming majority exit the oracle without interrupts.
  • Overhead components: Coverage tracing contributes almost 80% of UnTracer’s overhead across benchmarks, making faster tracing implementations a potential optimization.The implementation uses Dyninst-based static binary rewriting for black-box tracing; the authors note compatibility with alternative tracers such as AFL-Clang.
  • Overhead components: Forkserver restarting is the second-highest overhead component, especially for binaries with shorter test-case execution times.Restarting relies on process creation and inter-process communication, while stopping the forkserver is constant-time.

G. Overhead versus Rate of Coverage-increasing test cases

Coverage-guided tracing becomes increasingly advantageous as coverage-increasing test cases decline, and a rate-based crossover can determine when to switch tracing strategies. The modeled thresholds favor UnTracer below 2% versus AFL-Clang and below 50% versus AFL-QEMU and AFL-Dyninst.

  • Coverage-increasing test-case rates decrease over time for all benchmarks, enabling UnTracer to approach near-zero overhead by tracing only those cases.
  • A hybrid fuzzer can switch between coverage-guided and coverage-agnostic tracing according to the observed coverage-increasing test-case rate.The switch is based on a crossover threshold where coverage-guided tracing becomes less costly per test case.
  • The crossover model averages coverage-increasing-case overheads across tracer-benchmark trials to estimate thresholds for competing tracers.
  • Below 2%, UnTracer’s overhead per test case is less than AFL-Clang’s; below 50%, it is less than AFL-QEMU’s and AFL-Dyninst’s.
  • QSYM-UnTracer integrates coverage-guided tracing into a hybrid fuzzer, with performance compared against QSYM-Clang and QSYM-QEMU.The evaluation covers seven benchmarks and excludes sfconvert because the QEMU-based QSYM variant crashes in all eight trials.
  • QSYM-UnTracer uses the tracer rather than the interest oracle for trimming and calibration because those procedures must detect changes in a priori coverage.
  • Timeout and hang coverage tracking is configured to avoid adding overhead in binaries with many timeouts, such as djpeg.

A. Evaluation Overview

The evaluation examines UnTracer in hybrid fuzzing, hardware-assisted tracing, and edge-coverage settings. Results indicate that coverage-guided tracing retains its advantage across these settings, though black-box edge-coverage support remains constrained.

  • Hybrid fuzzing: The hybrid-fuzzing advantage outweighed the overhead of using the slow tracer for test-case trimming and calibration.Interest-oracle execution formed the common case in the evaluated implementation.
  • Hardware-assisted tracing: Hardware-assisted IPT tracing is orthogonal to coverage-guided tracing, so an IPT-based UnTracer could approach 0% overhead sooner.This expectation follows from IPT's lower tracing overhead relative to the Dyninst-based implementation.
  • Edge coverage: Critical edges are handled by inserting an intermediate dummy basic block, enabling edge identification from basic-block tracing.The inserted block transfers control directly to the original destination block.
  • Edge coverage: Moving from basic-block to edge coverage increases the rate of coverage-increasing test cases because edge coverage is a superset of basic-block coverage.The paper argues that seven of eight benchmarks had rates below 1 in 100,000, while UnTracer benefited below 1 in 50.
  • Edge coverage: A 4-orders-of-magnitude increase in coverage-increasing-testcase rates would be needed to undermine UnTracer's value under the reported thresholds.The paper considers such an increase unlikely because edge-coverage fuzzers show rates aligned with the evaluation.

C. Comprehensive Black-Box Binary Support

The paper frames comprehensive black-box support as an implementation boundary while relating UnTracer to broader efforts that improve fuzzing through generation and system scalability. Its central result is that reducing tracing overhead improves fuzzing performance overall.

  • Black-box support: UnTracer's comprehensive black-box support remains a niche implementation goal rather than a fully established capability.The implementation currently relies on a mix of black- and white-box binary instrumentation.
  • Related optimization areas: Coverage-guided tracing complements test-case-generation improvements because generated test cases still require tracing to identify coverage increases.The paper characterizes discarded test cases as common despite efforts to reduce them.
  • System-level impact: Tracing reductions carry over to fuzzing as a whole because tracing consumes over 90% of total fuzzing time.This conclusion applies even to fuzzers that focus on test-case generation.
  • Broader implications: The paper identifies fuzzing asymmetries as opportunities for further optimization, including skipping common code that is uninteresting but necessary to reach interesting code.This extends the coverage-guided-tracing idea beyond coverage-increasing test cases.
Loading 1812.11875v2…