  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.
