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

### Overview Coverage-guided fuzzing is a premier software testing technique used to discover vulnerabilities across modern applications. Typical coverage-guided fuzzers execute test cases against a target application and record coverage metrics to identify inputs that explore new execution paths. However, conventional implementations trace code coverage for every executed test case. Stefan Nagy, presenting joint research with Dr. Matthew Hicks from Virginia Tech, shows that over 90% of fuzzer execution time is spent on tracing and executing test cases, even though over 99.99% of generated inputs fail to discover new coverage and are discarded. To address this inefficiency, the authors introduce coverage-guided tracing through a framework called UnTracer, which filters out non-coverage-increasing inputs at native execution speed and restricts expensive tracing strictly to inputs that discover new coverage.

### Key Topics - **Overhead Analysis in Fuzzing:** Profiling popular tools like AFL and Driller across diverse benchmarks reveals that tracing adds severe performance costs, while the rate of coverage-increasing inputs decays exponentially to fewer than 1 in 10,000 test cases over a 24-hour run. - **Coverage-Guided Tracing Concept:** Instead of indiscriminately inspecting every test case, the execution framework places lightweight detection mechanisms on untaken basic blocks to detect coverage increases without continuous tracing. - **UnTracer Architecture:** Utilizing software interrupts (e.g., modifying the first byte of basic blocks) in an instrumented binary, the framework identifies new block visits. Once hit, the input is traced via a separate binary (using Dyninst), and the triggered interrupts are removed dynamically so future executions run with zero overhead. - **Complementary Optimization:** The approach isolates tracing performance and works orthogonally alongside test case generation and mutation engines such as Angora and VUzzer.

### Technical Details Standard coverage-guided fuzzers hook every basic block to update shared tracking structures (such as AFL's coverage bitmap), introducing instruction overhead across long execution paths and tight loops. UnTracer instead statically rewrites the target binary by inserting interrupt instructions at the beginning of basic blocks. When a test case executes, the common case—inputs that do not increase coverage—encounters no interrupts and runs at native speed with zero tracing overhead.

When a novel test case triggers an interrupt, UnTracer identifies it as coverage-increasing, runs that specific test case on a separate tracing binary built with Dyninst to extract full coverage information, and clears the corresponding interrupts in the interrupt binary so subsequent executions do not fire them again. Over time, as coverage saturates, the interrupt binary sheds interrupts and runs at native execution speed.

In experimental evaluations across eight diverse benchmarks over five days worth of test cases and 24-hour trials, UnTracer reduced tracing overhead to approximately 0.3%. It achieved a 36% overhead reduction compared to AFL Clang assembly-time white-box tracing, and boosted total fuzzer throughput by 70% to 616% when evaluated with QSYM.

### Takeaways - Tracing every generated test case represents an enormous resource waste in coverage-guided fuzzing because the vast majority of test cases yield no new coverage. - Filtering out redundant executions with dynamic interrupt removal permits the common execution path to run at native speed, cutting overhead to near zero. - Coverage-guided tracing provides massive throughput speedups (70%–616%) while maintaining modularity and compatibility with existing test case generators and modern hybrid fuzzers.