Full-Speed Fuzzing: Reducing Fuzzing Overhead through Coverage-Guided Tracing
- 1 May 2019
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 787-802
- https://doi.org/10.1109/sp.2019.00069
Abstract
Coverage-guided fuzzing is one of the most successful approaches for discovering software bugs and security vulnerabilities. Of its three main components: (1) test case generation, (2) code coverage tracing, and (3) crash triage, code coverage tracing is a dominant source of overhead. Coverage-guided fuzzers trace every test case's code coverage through either static or dynamic binary instrumentation, or more recently, using hardware support. Unfortunately, tracing all test cases incurs significant performance penalties–-even when the overwhelming majority of test cases 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 test cases increase coverage, and thus require tracing; and (2) coverage-increasing test cases become less frequent over time. Coverage-guided tracing encodes the current frontier of coverage in the target binary so that it self-reports when a test case produces new coverage–-without tracing. This acts as a filter for tracing; restricting the expense of tracing to only coverage-increasing test cases. Thus, coverage-guided tracing trades increased time handling coverage-increasing test cases for decreased time handling non-coverage-increasing test cases. 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 test case with popular white- and black-box-binary tracers AFL-Clang, AFL-QEMU, and AFL-Dyninst incurs overheads of 36%, 612%, and 518%, respectively. We further integrate UnTracer with the state-of-the-art hybrid fuzzer QSYM and show that in 24-hours of fuzzing, QSYM-UnTracer executes 79% and 616% more test cases than QSYM-Clang and QSYM-QEMU, respectively.Keywords
This publication has 28 references indexed in Scilit:
- VUzzer: Application-aware Evolutionary FuzzingPublished by Internet Society ,2017
- Continuous Fuzzing with libFuzzer and AddressSanitizerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- LAVA: Large-Scale Automated Vulnerability AdditionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- SOK: (State of) The Art of War: Offensive Techniques in Binary AnalysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- Turning programs against each other: high coverage fuzz-testing using binary-code mutation and dynamic slicingPublished by Association for Computing Machinery (ACM) ,2015
- SAGE: Whitebox Fuzzing for Security TestingQueue, 2012
- Anywhere, any-time binary instrumentationPublished by Association for Computing Machinery (ACM) ,2011
- PinPublished by Association for Computing Machinery (ACM) ,2005
- Extracting safe and precise control flow from binariesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Generic control flow reconstruction from assembly codePublished by Association for Computing Machinery (ACM) ,2002