2018/12/31 by Stefan Nagy, Nagy, Stefan, Matthew Hicks +1 · 1 voice · 2 citations
Computer Science · #Advanced Malware Detection Techniques #Software System Performance and Reliability #Software Testing and Debugging Techniques #cs.CR #cs.SE
paper · pdf · doi:10.48550/arxiv.1812.11875
openalex publication_date 2018/12/31 · openalex created_date 2022/08/01 · openalex updated_date 2026/07/28
Of coverage-guided fuzzing's three main components: (1) testcase generation,\n(2) code coverage tracing, and (3) crash triage, code coverage tracing is a\ndominant source of overhead. Coverage-guided fuzzers trace every testcase's\ncode coverage through either static or dynamic binary instrumentation, or more\nrecently, using hardware support. Unfortunately, tracing all testcases incurs\nsignificant performance penalties---even when the overwhelming majority of\ntestcases and their coverage information are discarded because they do not\nincrease code coverage. To eliminate needless tracing by coverage-guided\nfuzzers, we introduce the notion of coverage-guided tracing. Coverage-guided\ntracing leverages two observations: (1) only a fraction of generated testcases\nincrease coverage, and thus require tracing; and (2) coverage-increasing\ntestcases become less frequent over time. Coverage-guided tracing works by\nencoding the current frontier of code coverage in the target binary so that it\nself-reports when a testcase produces new coverage---without tracing. This acts\nas a filter for tracing; restricting the expense of tracing to only\ncoverage-increasing testcases. Thus, coverage-guided tracing chooses to\ntradeoff increased coverage-increasing-testcase handling time for the ability\nto execute testcases initially at native speed. To show the potential of\ncoverage-guided tracing, we create an implementation based on the static binary\ninstrumentor Dyninst called UnTracer. We evaluate UnTracer using eight\nreal-world binaries commonly used by the fuzzing community. Experiments show\nthat after only an hour of fuzzing, UnTracer's average overhead is below 1%,\nand after 24-hours of fuzzing, UnTracer approaches 0% overhead, while tracing\nevery testcase with popular white- and black-box-binary tracers AFL-Clang,\nAFL-QEMU, and AFL-Dyninst incurs overheads of 36%, 612%, and 518%,\nrespectively.\n