SOURCE ARCHIVE
EXTRACTED CONTENT
133,319 charsSession 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
Same Coverage, Less Bloat: Accelerating Binary-only Fuzzing
with Coverage-preserving Coverage-guided Tracing
Stefan Nagy Anh Nguyen-Tuong Jason D. Hiser
Virginia Tech University of Virginia University of Virginia Blacksburg, Virginia Charlottesville, Virginia Charlottesville, Virginia snagy2@vt.edu nguyen@virginia.edu hiser@virginia.edu
Jack W. Davidson Matthew Hicks
University of Virginia Virginia Tech Charlottesville, Virginia Blacksburg, Virginia jwd@virginia.edu mdhicks2@vt.edu ABSTRACT ACM Reference Format: Stefan Nagy, Anh Nguyen-Tuong, Jason D. Hiser, Coverage-guided fuzzing’s aggressive, high-volume testing has Jack W. Davidson, and Matthew Hicks. 2021. Same Coverage, Less Bloat: Ac- helped reveal tens of thousands of software security flaws. While celerating Binary-only Fuzzing with Coverage-preserving Coverage-guided executing billions of test cases mandates fast code coverage tracing, Tracing. In Proceedings of the 2021 ACM SIGSAC Conference on Computer the nature of binary-only targets leads to reduced tracing perfor- and Communications Security (CCS’21), November 15–19, 2021, Virtual Event, mance. A recent advancement in binary fuzzing performance is Republic of Korea. ACM, New York, NY, USA, 15 pages. Coverage-guided Tracing (CGT), which brings orders-of-magnitude https://doi.org/10.1145/3460120.3484787 gains in throughput by restricting the expense of coverage tracing 1 INTRODUCTION to only when new coverage is guaranteed. Unfortunately, CGT suits only a basic block coverage granularity—yet most fuzzers re- Coverage-guided fuzzing has become one of the most popular and quire finer-grain coverage metrics: edge coverage and hit counts. It is successful techniques for software security auditing. Its aggressive, this limitation which prohibits nearly all of today’s state-of-the-art high-volume testing strategy has revealed countless security vul- fuzzers from attaining the performance benefits of CGT. nerabilities in software, and helped proactively secure many of the This paper tackles the challenges of adapting CGT to fuzzing’s world’s most popular codebases [8]. Today, software projects of most ubiquitous coverage metrics. We introduce and implement all sizes rely on fuzzing to root out bugs and vulnerabilities both a suite of enhancements that expand CGT’s introspection to fuzz- throughout and beyond the software development cycle. ing’s most common code coverage metrics, while maintaining its Fuzzing consists of three main steps: (1) test case generation, orders-of-magnitude speedup over conventional always-on cover- (2) code coverage tracing, and (3) test case triage. Many works im- age tracing. We evaluate their trade-offs with respect to fuzzing prove fuzzing at the generation level by incorporating input gram- performance and effectiveness across 12 diverse real-world binaries mars [21], path prioritization [34], better mutators [36], or con- (8 open- and 4 closed-source). On average, our coverage-preserving straint solving [3]; while others focus on refining triage with sani- CGT attains near-identical speed to the present block-coverage- tizers [15] or other heuristics. However, given fuzzing’s core goal only CGT, UnTracer; and outperforms leading binary- and source- of producing—and eventually executing—a large volume of test level coverage tracers QEMU, Dyninst, RetroWrite, and AFL-Clang cases, maintaining high-performance test case execution is critical by 2–24×, finding more bugs in less time. to effective fuzzing. Recent work shows both “dumb” and “smart” fuzzers spend the majority of their time executing test cases and CCS CONCEPTS collecting their coverage traces [37]. However, in binary-only fuzz- • Security and privacy → Software and application security. ing contexts, the semantically-poor and opaque nature of a binary prevents the tight integration of coverage-tracing routines that is KEYWORDS possible in source-available contexts. This inflates the tracing over- Fuzzing, Binaries, Code Coverage head by up to two orders of magnitude compared to compiler-based instrumentation of source code. Even in an ideal world where black- box instrumenters approach compiler-level performance, recent Permission to make digital or hard copies of all or part of this work for personal or work shows that coverage tracing increases test case execution classroom use is granted without fee provided that copies are not made or distributed time by roughly 30% [15]. To address this performance gap and for profit or commercial advantage and that copies bear this notice and the full citation the time wasted by needless coverage tracing, many binary-only on the first page. Copyrights for components of this work owned by others than ACM fuzzing efforts [18, 23, 30, 51] are eschewing conventional always- must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a on coverage tracing for an on-demand tracing strategy known as fee. Request permissions from permissions@acm.org. Coverage-guided Tracing (CGT) [37]. CGT restricts the expense of ©CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea. tracing to only when new coverage is guaranteed (roughly 1 test 2021 Association for Computing Machinery. case in every 10,000), thereby increasing fuzzing throughput by ACM ISBN 978-1-4503-8454-4/21/11. . . $15.00 https://doi.org/10.1145/3460120.3484787 500–600% over the leading binary-only tracers.
351
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
While some practitioners are leveraging the idea of CGT [18, 23, always-on binary- and source-level tracers—in edge cover-
30], we are not aware of any fuzzer that has adopted it as a replace- age, loop coverage, and bug-finding fuzzing effectiveness. ment for always-on tracing. Our survey of 27 fuzzers reveals why • We show that coverage-preserving CGT’s speed is nearly such performance benefits sit unrealized: CGT only supports basic indistinguishable from that of block-only CGT, and—despite block coverage (instruction sequences ending in control-flow trans- being a binary-only technique—is >2× the speed of even fer), but most fuzzers rely on finer-grained coverage metrics. Specif- source-level tracing approaches. ically, our study shows 25/27 adopt edges (transitions between • We open-source HeXcite, our implementation of binary- blocks), and 26/27 further track block or edge hit counts (execution only coverage-preserving CGT, and our evaluation bench- frequencies). This lack of support for the most common coverage marks at: https://github.com/FoRTE-Research/HeXcite. metrics inhibits CGT’s adoption in nearly all fuzzers. While CGT’s 2 BACKGROUND near-0% tracing overhead is ideal for fuzzing’s high-throughput needs, its coverage deficiencies force today’s state-of-the-art fuzzers To understand our improvements to Coverage-guided Tracing, it is to instead rely on orders-of-magnitude slower, always-on tracing— crucial to understand the core details of coverage-guided fuzzing, its leaving their full performance potential unrealized. code coverage metrics, and the high-performance tracing strategy This paper tackles the challenge of extending CGT to fuzzing’s known as Coverage-guided Tracing. most ubiquitous coverage metrics—edges and hit counts—making high-performance tracing available for all existing (and future) 2.1 Software Fuzzing fuzzers. At the core of our efforts are binary-level and fuzzing en- Software fuzzing broadly represents one of today’s most popular hancements that broaden CGT’s coverage while maintaining its software quality assurance approaches. Unlike other forms of soft- orders-of-magnitude speedup: for edge coverage, we introduce a ware testing that vet functionality (e.g., unit testing, mutational zero-overhead strategy called jump mistargeting that addresses the testing), fuzzing’s primary focus is security auditing; test cases are most common (statically and dynamically) form of critical edges generated and fed to the target program with their effects moni- while keeping control flow intact. To maintain completeness of tored for signs of security violations. Many software vulnerabilities edge coverage, we back jump mistargeting with a low-overhead have been (and continue to be) uncovered via fuzzing, and its use binary-only implementation of a control-flow transformation that among developers large and small continues to grow each year [18]. eliminates critical edges through block insertion called branch split- Fuzzing encompasses a variety of techniques accommodating ting (e.g., LLVM’s SanitizerCoverage [50]). To extend CGT to hit specific use cases, with the most common distinction being search count coverage, we exploit the observation that execution frequency strategy; directed fuzzers constrain testing to specific code or paths changes are highly localized to loops, devising a bucketed unrolling (e.g., newly-patched [6] or likely-vulnerable code [11]), while guided strategy to encode them with a minimally-invasive hit count track- fuzzers aim to maximize the program’s state space along some pre- ing mechanism congruent with current fuzzers [18, 59]. specified metric (e.g., memory accesses or code coverage). By far We implement our coverage-preserving Coverage-guided Tracing, the most common and successful form of fuzzing is coverage-guided HeXcite, and evaluate it against the current block-coverage-only fuzzing [59] which, as the name implies, aims to maximize test CGT implementation UnTracer [37]; the leading binary-only fuzz- cases’ code coverage to uncover hidden program bugs. ing coverage tracers QEMU [59], Dyninst [26], and RetroWrite [15]; and the popular source-level coverage tracing via AFL-Clang [59]. 2.2 Coverage-guided Fuzzing 4In evaluations across 12 diverse real-world binaries (8 open- and Coverage-guided fuzzing’s scalability, easy adoption, and time- closed-source), HeXcite attains a throughput near identical to tested effectiveness have made it widely popular among both de- UnTracer’s; 3–24× that of conventional always-on binary-only trac- velopers and security practitioners. As shown in Figure 1, given a ers QEMU, Dyninst, and RetroWrite; and 2.8× that of source-level target program, a typical coverage-guided fuzzing workflow con- tracing with AFL-Clang. HeXcite’s coverage-preserving transfor- sists of the following recurring steps: mations further enable it to find 12–749% more unique bugs than UnTracer as well as always-on binary- and source-level tracers seed for mutation in standard coverage-guided grey-box fuzzing integrations—while finding 16 known bugs and vulnerabilities in 32–52% less time. 1 Test new coverage Case Through the following contributions, this paper enables the Gen. use of the fastest tracing approach in fuzzing—Coverage-guided test cases 2 Coverage 3 Tracing Tracing—by the majority of today’s fuzzers: and Test new crash Case Execution Triage Monitoring • We introduce jump mistargeting: a control-flow redirection discarded strategy which alters the common-case of edge instructions such that they self-report edge coverage at native speed. instrumented target • We introduce bucketed unrolling: a technique which clones Figure 1: The high-level steps of coverage-guided fuzzing. loop conditions at discrete intervals, enabling the self-reporting of loop hit-count coverage at near-native speed. (1) Generation. Genetic algorithms (typically a mix of random • We demonstrate that with these techniques, our coverage- and deterministic byte mutations) create batches of candidate preserving CGT eclipses block-only CGT—and conventional test cases from one or more ancestors.
352
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
(2) Coverage Tracing & Execution Monitoring. Lightweight bit representing one of eight ranges (0–1, 2, 3, 4–7, 8–15, 16–31, statically- or dynamically-inserted instrumentation captures 32–127, 128+); test cases are seeded if they jump from one bucket each test case’s runtime code coverage given some pre-specified to another for any block/edge. While tracking exact hit counts (e.g., coverage metric(s), while monitoring their other execution VUzzer and TIFF) reveals finer-grained state changes, it risks over- behavior (e.g., terminating signal). saturating the fuzzer seed pool with needless test cases (e.g., one (3) Triage. Candidates are grouped based on observed execution per new loop iteration), and is hence seldom used. behavior; those increasing coverage are preserved for future mutation, while those triggering crashes are deduplicated in 2.4 Coverage-guided Tracing anticipation of manual bug analysis. Many recent works improve fuzzing with smarter test case gen- Coverage-guided fuzzing’s balance of feedback-guided auditing eration or triage. But despite these advancements, the maximal and aggressive, high-volume testing continues to reign supreme performance of both standard and state-of-the-art coverage-guided over other automated security testing methodologies; its effective- fuzzers is subject to a key constraint: code coverage is traced for all ness is evidenced by the deep (and ever-growing) vulnerability test cases, yet less than 1 in 10,000 actually increase coverage [37]. trophy cases held by prominent fuzzers such as Google’s AFL [59], While this has little impact in use cases where tracing instrumenta- honggFuzz [49], and libFuzzer [45]; and its fundamental principles tion is already fast (i.e., open-source software), it is the principal form the core of today’s most state-of-the-art fuzzing efforts. bottleneck for those where tracing is costly—i.e., closed-source software. For this reason, a number of binary-only fuzzing ef- 2.3 Fuzzing’s Code Coverage Metrics forts [18, 23, 30, 51] are instead adopting a lighter-weight strategy To maximally vet the target application, coverage-guided fuzzing called Coverage-guided Tracing (CGT), which restricts the expense collects a test case’s dynamic code coverage and subsequently mu- of tracing to only the < 0.01% of test cases that increase coverage. tates only those which attain new coverage. In our efforts to under- stand fuzzing’s current coverage landscape, we survey 27 of today’s seed for mutation state-of-the-art coverage-guided fuzzers (Table 1) and identify three 1 Test new coverage universal coverage metrics: basic blocks, edges, and hit counts. We Case remove interrupts Gen. discuss these coverage metrics in detail below. test cases 2 Coverage 33 Tracing Test new crash Interest hit interrupt and Case Oracle Execution Triage Monitoring Name Cov Hit Name Cov Hit Name Cov Hit AFL [59] ➤ ✔ EnFuzz [12] ➤ ✔ ProFuzzer [57] ➤ ✔ no interrupt AFL++ [18] ➤ ✔ FairFuzz [34] ➤ ✔ QSYM [58] ➤ ✔ AFLFast [7] ➤ ✔ honggFuzz [49] ➤ ✗ REDQUEEN [3] ➤ ✔ instrumented target AFLSmart [41] ➤ ✔ GRIMORE [5] ➤ ✔ SAVIOR [11] ➤ ✔ Figure 2: Coverage-guided Tracing’s core workflow. Angora [9] ➤ ✔ lafIntel [1] ➤ ✔ SLF [56] ➤ ✔ CollAFL [19] ➤ ✔ libFuzzer [45] ➤ ✔ Steelix [35] ➤ ✔ DigFuzz [60] ➤ ✔ Matryoshka [10] ➤ ✔ Superion [53] ➤ ✔ Given a target binary, CGT constructs two versions: a coverage Driller [48] ➤ ✔ MOpt [36] ➤ ✔ TIFF [29] ■ ✔ Eclipser [13] ➤ ✔ NEUZZ [46] ➤ ✔ VUzzer [43] ■ ✔ oracle with an interrupt (e.g., 0xCC) inserted at every basic block, Table 1: A survey of recent coverage-guided fuzzers and their coverage metrics and a tracer instrumented for conventional fuzzing coverage tracing. (edges/blocks and hit counts). Key: ➤ (edges), ■ (blocks). As shown in Figure 2, CGT runs each test case first on the oracle; if an interrupt is hit, the test case’s full coverage is then captured Basic Block Coverage: Basic blocks refer to straight-line (i.e., with the tracer, and all visited blocks’ have their corresponding single entry and exit) instruction sequences beginning and ending oracle interrupts removed; and if no interrupt was hit, the test in control-flow transfer (i.e., jumps, calls, or returns), and comprise case is simply discarded following its run on the oracle. Most test the nodes of a program’s control-flow graph. Tracking basic block cases (> 99.9% [37]) revisit already-seen coverage and thus will coverage necessitates instrumenting each to record their execution not trigger interrupts, sparing them of tracing; and because the in some data structure (e.g., an array [44] or bitmap [59]). Two oracle’s mechanism of reporting new coverage is just interrupts modern fuzzers that employ basic block coverage are VUzzer [43] (and not instrumentation callbacks) this majority of test cases are and its successor TIFF [29]. run at speed equivalent to the original binary’s—giving CGT a Edge Coverage: Edges refer to block-to-block transitions, and near-native runtime overhead of 0.3%, and 500–600% higher test offer a finer-grained approximation of paths taken. As Table 1 case throughput over the conventional always-on tracing used in shows, most fuzzers rely on edge coverage; AFL [59] and its many binary-only fuzzing like AFL-Dyninst [26] and AFL-QEMU [59]. derivatives [18] record edges as hashes of their start/end block tuples in a bitmap data structure; while LLVM SanitizerCoverage- The Code Coverage Dilemma: Though CGT enables orders-of- based [50] fuzzers honggFuzz and libFuzzer track edges from the magnitude higher binary-only fuzzing throughput, it is currently in- block level by splitting critical edges (edges whose start/end blocks compatible with all of the state-of-the-art coverage-guided fuzzers have at least two outgoing/incoming edges, respectively). we surveyed in Table 1: whereas CGT presently supports only a ba- Hit Count Coverage: Hit counts refer to block/edge execu- sic block coverage level, 25/27 fuzzers instead rely on edge coverage, tion frequencies, and are commonly tracked to reveal progress in and 26/27 further track hit counts. Allowing the broad spectrum of coverage-guided fuzzers to obtain the performance benefits of CGT state exploration (e.g., iterating on a loop). libFuzzer, AFL, and AFL necessitates an answer to this disparity in code coverage metrics. derivatives approximate hit counts using 8-bit “buckets”, with each
353
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
3 A COVERAGE-PRESERVING CGT as critical edges: edges whose start/end blocks have two or more Coverage-guided Tracing (CGT) accelerates binary-only fuzzing incoming/outgoing edges, respectively [50]. by restricting the expense of code coverage tracing to only the few Program Total Edges Crit. Edges Prop. test cases that reach new coverage. Unfortunately, CGT’s lack of bsdtar 42911 9867 0.23 support for fuzzing’s most common coverage metrics, edges and cert-basic 7544 1642 0.22 hit counts, leaves its performance benefits untapped for nearly all clean_text 8762 1592 0.18 of today’s state-of-the-art fuzzers. jasper 21637 5878 0.27 To address this incompatibility, we observe how CGT achieves readelf 30959 7301 0.24 sfconvert 8358 2022 0.24 lightweight coverage tracking at the control-flow level; and de- tcpdump 36200 7312 0.20 vise two new techniques exploiting this paradigm to facilitate unrtf 2505 465 0.19 Table 2: Proportion of critical edges in eight real-world programs. finer-grained coverage—jump mistargeting (for edge coverage) and Mean 22% bucketed unrolling (for hit counts)—without compromising CGT’s minimally-invasive nature. Below we discuss the inner workings 1. Conditional target (e.g., jle 0x100’s True branch) of jump mistargeting and bucketed unrolling, and the underlying insights and observations that motivate them. 3.2. Conditional fall-through (e.g., jle 0x100’s False branch) Indirect jump (e.g., jmp %eax) 4. Indirect call (e.g., call %eax) 5. Return (e.g., ret) Table 3: Examples of x86 critical edge instructions by transfer type.
Program CndTarg CndFall IndJmp IndCall Ret
bsdtar 1.00 0.00 0.00 0.00 0.00
cert-basic 0.84 0.10 0.02 0.00 0.05
clean_text 0.87 0.02 0.00 0.01 0.10
jasper 0.97 0.03 0.00 0.00 0.00
readelf 0.70 0.03 0.01 0.12 0.14
sfconvert 0.84 0.02 0.00 0.00 0.13
tcpdump 0.98 0.01 0.00 0.00 0.01
unrtf 0.94 0.03 0.00 0.00 0.02
(a) bsdtar (b) cert-basic Mean 89.3% 2.9% 0.4% 1.6% 5.7%
Table 4: Proportion of encountered critical edges by transfer type.
Diving deeper into critical edges: Supporting block-centric
edge coverage requires resolving all critical edges. LLVM’s Sani-
tizerCoverage achieves this by splitting each critical edge with a
“dummy” block, creating two new edges. Continuing example § 3.1,
dummy d will split critical edge #» #» #»
# » ac into ad and dc, thus permitting
abc. But while such approach is
path adc to be differentiated from # »
indeed compatible with CGT’s block-centric, interrupt-driven cov-
erage, our analysis of eight real-world binaries shows over 1 in 5
(c) clean_text (d) jasper edges are critical (Table 2), revealing that splitting every critical edge
Figure 3: Visualization of the proportion of critical edges by transfer type with a new block leaves a significant control-flow footprint—and encountered throughout fuzzing. inevitably, a higher baseline binary fuzzing overhead. To understand the impact of critical edges on fuzzing, we instru- 3.1 Supporting Edge Coverage ment the same eight real-world binaries and dynamically record AFL and its derivatives utilize hash-based edge coverage, instru- their instruction traces.1 In conjunction with the statically-generated menting each basic block to dynamically record edges as hashes of control-flow graphs, we analyze each trace to measure the occur- their start/end blocks. However, as CGT’s key speedup comes from rences of critical edges; and further quantify them by transfer type, replacing per-block instrumentation with far cheaper interrupts, it which on the x86 ISA takes on one of five forms (shown in Table 3).2 is thus incompatible with AFL-style hash-based edge coverage. As shown in Figure 3 and Table 4, our findings reveal that con- libFuzzer and honggFuzz track edges using LLVM’s Sanitizer- ditional jump target branches make up an average of 89% of all Coverage instrumentation, which forgoes hashing to instead infer dynamically-encountered critical edges. edges from the set of covered blocks. For example, given a control- flow graph with edges #» #» Observation 1: Conditional jump target branches make up the vast covering edge #» ab and bc, covering blocks a and b#»implies majority of critical edges encountered during fuzzing. ab; and subsequently covering c implies bc. How- ever, such block-centric edge coverage does not suffice if there exists 1 We limit instruction tracing to one hour of fuzzing due to the massive size of the #» a third edge ac 2As critical edges are, by definition, one of at least two outgoing edges from their start- edges #» #». In this case, covering blocks a, b, and c implies resulting trace data (ranging from 200GB to 7TB per benchmark). ab and bc; but since c has already been covered, there is no #». Formally, these problematic edges are referred to ing block, transfers with at most one destination (direct jumps/calls and unconditional way to detect ac fall-throughs) can never be critical edges.
354
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
3.1.1 Jump Mistargeting. Splitting critical edges with dummy (2) Zero-address Interrupts. As nearly all x86/x86-64 code is blocks adds a significant number of new instructions to each exe- position-independent and hence uses PC-relative address- cution, and with it, more runtime overhead—slowing binary-only ing, an alternative and less analysis-intensive mistargeting fuzzing down even further. For the common case of critical edges approach is to interrupt the program by resolving the jump’s (conditional jump target branches), we observe that the edge’s des- displacement to the zero address (i.e., 0x00). For example, tination address is encoded within the jump instruction itself, and taking the conditional jump represented by byte sequence thus can be statically altered to direct the edge elsewhere. Our ap- [0F 8F 7C 00 00 00] at address 0x400400 normally proach, jump mistargeting, exploits this phenomena to “mistarget” branches to address 0x400400+6+0x0000007C (i.e., the PC the jump’s destination so that it resolves into a CGT-style interrupt— + instruction length + displacement); but to resolve it to the permitting a signaling of the critical edge’s coverage without any zero address merely requires the displacement be rewrit- #» in § 3.1’s example ten to 0xFFBFFB7E (i.e., the negative sum of the PC and need for a dummy block (i.e., identifying edge ac without the additional dummy block d). instruction length). As 8–16 bit displacements do not pro- An overview of jump addressing: The x86 ISA has three types vide enough “room” to cover the large virtual address space of jumps: short, near (or long), and far. Short and near jumps achieve of modern programs, zero-address mistargeting is generally intra-segment transfer via program counter (PC)-relative addressing: restricted to jumps with 32-bit displacements, however, most short jumps use 8-bit signed displacements, and thus can reach x86-64 branches fit this mold. up to +127/-128 bytes relative to the PC; while near jumps use much larger 16–32-bit signed displacements. In contrast, far jumps Technique 1: Jumps’ self-encoded targets can be rewritten to resolve achieve inter-segment transfer via absolute addressing (i.e., to a fixed to addresses that result in interrupts, enabling binary-level CGT edge location irrespective of the PC). All three jumps share the common coverage at native speed (i.e., without needing to insert additional instruction layout of an opcode followed by a 1–4 byte destination basic blocks). operand (an encoding of the relative/absolute address). Since the adoption of position-independent layouts, most x86/x86-64 code utilizes relative addressing. 3.2 Supporting Hit Counts Redirecting jumps to interrupts: Jump mistargeting alters Most fuzzers today adopt AFL-style [59] bucketed hit count cov- conditional jump target critical edges to trigger interrupts when erage, which coarsely tracks changes in block/edge execution fre- taken. When used in CGT, its effect is identical to combining inter- quencies over a set of eight ranges: 0–1, 2, 3, 4–7, 8–15, 16–31, rupts with conventional (yet more invasive) edge splitting—while 32–127, and 128+. Unfortunately, CGT’s interrupt-driven coverage avoiding the associated cost of inserting new blocks. We envision currently only supports a binarized notion of coverage (i.e., tak- two possible jump mistargeting strategies (Figure 4): one leveraging en/not taken), and thus requires a fundamentally new approach to embedded interrupts, and another with zero-address interrupts. support finer-grained frequencies. Diving deeper into hit counts: In exploring the importance of hit counts, we observe that most new hit count coverage is localized to loops (e.g., for(), while()). As Rawat and Mounier [43] demon- strate that as many as 42% of binary code loops induce buffer over- flows (e.g., by iterating over user-provided input with strcpy()), it is imperative to track hit counts as a means of assessing—and prioritizing—fuzzer “progress” toward higher loop iterations. How- Figure 4: A visualization of jump mistargeting via embedded (left) and zero- ever, inferring a loop’s iteration count is achievable purely from address interrupts (right). monitoring its induction variable—eliminating the expense of track- (1) Embedded Interrupts. The simplest mistargeting approach ing hit counts for every loop block (as AFL and libFuzzer do). is to replace each jump’s destination with a garbage address, Observation 2: Hit counts provide fuzzing a notion of loop explo- ideally resolving to an illegal instruction (thus interrupting ration progress, but need only be tracked once per loop iteration. the program). However, as many instructions have one-byte opcodes, a carelessly-chosen destination may very well initi- ate an erroneous sequence of instructions. 3.2.1 Bucketed Unrolling. AFL-style [59] hit count tracking A more complete strategy is to instead redirect the jump adds counters to each block/edge to dynamically update their re- to a location where an interrupt opcode is embedded. For spective hit counts in a shared memory coverage bitmap. However, example, the byte sequence [00 CC] at address 0x405500 this approach is fundamentally incompatible with the binarized normally resolves to instruction [add %cl,%ah]; but as 0xCC nature of CGT’s block-centric, interrupt-driven coverage. While a is itself an opcode for interrupt int3, it suffices to redirect the naive solution is to instead add CGT’s interrupts following the ap- target critical edge jump to 0x405501, which subsequently plication of a loop peeling transformation—making several copies of fetches and executes 0xCC, thus triggering the interrupt in- the loop’s body and stitching them together with direct jumps (e.g., struction. A key challenge (and bottleneck) of this approach head → body1 → ... → body𝑛 → tail)—the resulting binary will is scanning the bytespace in the jump’s displacement range be exceedingly space inefficient due to excessive code duplication— to pinpoint embedded interrupts. especially for nested loops.
355
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
In search of a more performant solution, we develop bucketed binary rewriters—Dyninst [40], McSema [14], RetroWrite [15], and unrolling—drawing from compiler loop unrolling principles to en- ZAFL [38]—and distill a set of properties we feel are best-suited code the functionality of AFL-style bucketed hit counts as a series supporting jump mistargeting and bucketed unrolling: (1) a modi- of binarized range comparisons. fiable control-flow representation; (2) dominator flow analysis [2]); and (3) sound code transformation and generation. We select ZAFL as Original Loop With Bucketed Unrolling the basis for HeXcite as it is the highest performance rewriter that on ranges = {0-1, 2, 3-7, 8+} possesses the above three properties in addition to an LLVM-like transformation API. We expect that with additional engineering Header A Header A effort, our findings apply to the other rewriters listed. i > 1 i = [0,1] Like most static binary rewriters, ZAFL operates by first dis- i > 2 i = 2 assembling and lifting the input binary to an intermediate repre- i > 7 i = [3,7] sentation;3 and performing all code transformation at this IR level Loop C B i = [8,∞) Body (e.g., injecting bucketed unrolling’s range checks § 4.3), adjusting B Body Loop C the binary’s layout as necessary before reconstituting the final Figure 5: Bucketed unrolling applied to a simple loop. executable. While relocating direct (i.e., absolute and PC-relative) control flow is generally trivial, attempting so for indirect trans- As shown in Figure 5, bucketed unrolling augments each loop fers is undecidable and risks corrupting the resulting binary, as header with a series of sequential conditional statements weighing their respective targets cannot be identified with any generalizable the loop induction variable against the desired hit count bucket accuracy [39, 54]. ZAFL addresses this challenge conservatively ranges (e.g., AFL’s eight). To support CGT, each conditional’s fall- via address pinning [25, 27], which “pins” any unmovable items through block is assigned an interrupt; taking any conditional’s tar- (including but not limited to: indirectly-called function entries, get branch jumps directly to the loop’s body, indicating no change callee-to-caller return targets, data, or items that cannot be pre- from the current bucket range; and taking the fall-through triggers cisely disambiguated as being either code or data) to their original the next sequential interrupt, thus signaling an advancement to addresses;4 while safely relocating the remaining movable items the next bucket. The resulting code replicates the functionality of around these pins (often via chained jumps). Though address pin- AFL-style hit count tracking—but obtains much higher performance ning will likely over-approximate the set of unmovable items at by doing so at just one instrumentation location per loop. slight cost to binary performance and/or space efficiency (particu- larly for exceedingly-complex binaries with an abundance of jump Technique 2: Encoding conventional bucketed hit count tracking as tables, handwritten assembly, or data-in-code), its general-purpose a series of sequential, binarized range checks enables CGT to cap- soundness, speed, and scalability [38] makes it promising for facili- ture binary-level loop exploration progress—while upholding its fast, tating coverage-preserving CGT. Our current prototype, HeXcite, interrupt-driven coverage-tracing strategy. supports binary fuzzing of x86-64 Linux C and C++ executables. Control-flow Mapping: A key requirement of CGT is a map- 4 IMPLEMENTATION: HEXCITE ping of each oracle basic block’s address (i.e., where an interrupt In this section we introduce HeXcite—High-Efficiency eXpanded is added) to its corresponding tracer binary trace-block ID; when Coverage for Improved Testing of Executables—our implementation a coverage-increasing test case is found, the tracer is invoked to of binary-only coverage-preserving Coverage-guided Tracing. Below capture the test case’s full coverage, for which all interrupts are sub- we discuss HeXcite’s core architecture, and our design decisions sequently removed at their addresses in the oracle. To generate this in realizing jump mistargeting and bucketed unrolling. mapping, we save the original and rewritten control-flow graphs for both the oracle and tracer binaries. We then parse the pair of original 4.1 Architectural Overview control-flow graphs to find their corresponding matches, and subse- quently map each to their oracle and tracer binary counterparts (i.e., HeXcite consists of three main components: (1) binary genera- (cfgBB,oracleBB) → (cfgBB,tracerBB)). From there, we gener- tion, (2) control-flow mapping, and (3) the fuzzer. We imple- ate the necessary (oracleAddr,tracerID,interruptBytes) map- ment components 1–2 as a set of analysis and transformation passes ping for each block (e.g., (0x400400,30,0xCC)). If mapping should atop the ZAFL static rewriting platform [38], and component 3 atop fail (e.g., a tracer block with no corresponding oracle block), we the industry-standard fuzzer AFL [59]. Below we briefly discuss omit the block to avoid problematic interrupts; we observe this gen- each and their synergy in facilitating coverage-preserving CGT. erally amounts to no more than a handful of instances per binary, Binary Generation: HeXcite’s workflow is similar in nature and does not impact HeXcite’s overall coverage (§ 5.2.1–§ 5.2.2). to UnTracer’s (Figure 2); i.e., we generate two versions of the orig- The Fuzzer: Like UnTracer, we implement HeXcite atop the inal target binary: (1) an oracle (run for every test case) with in- industry-standard fuzzer AFL [59] 2.52b with several changes in terrupts added to each basic block; and (2) a tracer (run only for coverage-increasing test cases) equipped with conventional tracing instrumentation. While many fuzzers embrace compiler instrumen- 3 ZAFL’s disassembly supports mixing-and-matching of recursive descent and linear tation for its speed and soundness (i.e., LLVM [33]), there are by sweep. The current tools utilized are based on IDA Pro [24] and GNU objdump [20]. now a number of static binary rewriters with comparable qualities. 4 To support address pinning, ZAFL conservatively scans for addresses likely targeted We examine several popular and/or emerging security-oriented by indirect control flow; generally this is achieved via rudimentary heuristics (e.g., post-call instructions, jump table entries, etc.). Additionally, ZAFL pins all data items.
356
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
test case handling logic (Figure 6). We default to conventional trac- LLVM (§ 6.1). While recent work [31] reveals the possibility that ing for any executions where coverage is required (e.g., calibration indirect edges may be modeled at the binary level, such approaches and trimming), while not re-executing or saving timeout-producing are still too imprecise to be realistically deployed; hence, we conser- test cases. As jump mistargeting triggers signals that might oth- vatively omit indirect critical edges as we observe they have little erwise appear as valid crashes (e.g., SIGSEGV), we alter HeXcite’s overall significance on dynamically-seen control-flow (Figure 3). fuzzer-side crash-handling logic as follows: if a test case crashes the oracle, we re-run it on the tracer to verify whether it is a true or 4.3 Implementing Bucketed Unrolling a mistargeted crash; if it does not crash the tracer, we conclude it is We implement bucketed unrolling to replicate AFL-style loop hit the result of taking a mistargeted critical edge (i.e., a SIGSEGV from count tracking, beginning with an analysis pass to retrieve all code jumping to the zero address), and save it to the fuzzer queue. We loops from the target binary based on the classic dominance-based note that the core principles of coverage-preserving CGT scale to loop detection [42]: given the control-flow graph and dominator any fuzzer (e.g., honggFuzz), as evidenced by emerging CGT-based tree (generally available in any off-the-shelf static rewriter’s API), efforts within the fuzzing community [18, 23, 30]. we mark a set of blocks S as a loop if (1) there exists a header block h that dominates all blocks in S; and (2) there exists a backward edge Coverage-preserving Coverage-guided Tracing #» Fuzzer-side Test Case Handling bh from some block b ∈ S such that h dominates b.5 Though binary- New no Discard level loop head/body detection is difficult—particularly around com- Coverage? yes Save to plex optimizations like Loop-invariant Code Motion—we observe interrupt no fault Queue Calibrate that the standard dominance-based algorithm is sufficient; and Run crash Crashes++ no Discard Tracer Total NewCrash while HeXcite attains the highest loop coverage in our evalua- tmout Coverage? yes Unique Save to tion (§ 5.2.2), we expect that future advances in optimized-binary Run crash Crashes++ Crashes Oracle loop detection will only improve these capabilities. Total Discard As pinpointing a loop’s induction variable (the target of bucketed tmout Tmouts++ Figure 6: HeXcite’s fuzzer-side test case handling logic. Like UnTracer, we unrolling’s discrete range checks) is itself semantically challenging discard timeout-producing test cases; however, we re-run crashing test cases at the binary level, we opt for a simpler approach and instead add to determine whether they are a true crash (i.e., occurring on both the ora- a “fake” loop counter before each loop header; and augment the cle and tracer) or the result of hitting an oracle mistargeted edge (generally header with an instruction to increment this counter per iteration triggering a SIGSEGV from the jump being redirected to the zero address). (e.g., x86’s incl). Where the increment is inserted in the header ultimately depends on the static rewriter of choice; Dyninst [40] 4.2 Implementing Jump Mistargeting prefers to conservatively insert new code at basic block entrypoints We implement zero-address jump mistargeting for the common- to avoid clobbering occupied registers; while RetroWrite [15] and case of critical edges, conditional jump target branches (§ 3.1), as ZAFL [38] analyze register liveness to more tightly weave code follows. To statically identify critical edges we first enumerate all with the original instructions. Either style is supportive of HeXcite, control-flow edges, and mark an edge as critical if at least two edges though tight code insertion is preferable for higher runtime speed. both precede and succeed it. We subsequently parse each critical We implement bucketed unrolling’s sequential range checks (per edge and categorize it by type by examining its starting block’s AFL’s 8-bucket hit count scheme) as a transformation pass directly last instruction (Table 3). Lastly, we update an offline record of before the loop’s first body block; and connect each to the first body each critical edge by type (e.g., “conditional jump target”) and its block via direct jumps, and to each other via fall-throughs. The respective starting/ending basic block addresses. resulting assembly resembles the following (shown in Intel syntax): We enumerate all conditional jump target critical edges; as x86- 1 _loop_head: 64 conditional jumps are 6-bytes in length and encoded with a 2 incl rdx 32-bit PC-relative displacement, we compute the sum of the in- 3 cmpl rdx, 1 struction’s address and its length, and determine the 2’s comple- 4 jle _loop_body 5 cmpl rdx, 2 ment (i.e., negative binary representation). Using basic file I/O we 6 jle _loop_body then statically overwrite the jump’s displacement operand with 7 ... the little-endian encoding of the zero-address-mistargeted displace- 8 _loop_body: ment, and update our oracle-to-tracer mapping accordingly (e.g., To facilitate signaling of a range change, we flag the start of each (0x400400,30,0x7C000000) for the example in § 3.1). sequential range check (e.g., lines 3 and 5 above) with the one-byte If a critical edge cannot accommodate zero-address mistargeting 0xCC interrupt. To maintain control-flow congruence, we apply this (e.g., from having a <32-bit displacement), we attempt to fall-back to transformation to both the oracle and tracer binaries. conventional SanitizerCoverage-style [50] edge splitting, inserting a dummy block and connecting it to the edge’s end block. Conditional 5 fall-through critical edges require careful handling, as accommo- EVALUATION dating the transfer from the edge’s starting block to the dummy Our evaluation of the effectiveness of coverage-preserving Coverage- requires the dummy be placed immediately after the starting block guided Tracing is motivated by three key questions: (i.e., the next sequential address). However, splitting indirect critical 5 edges remains a universal problem even for robust compilers like In compiler and graph theory, a basic block a is said to dominate basic block b if and only if every path through b also covers a. [2]
357
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
Q1: Do jump mistargeting and bucketed unrolling improve cov- benchmarks are selected from versions with well-known bugs to erage over basic-block-only CGT? ensure a self-evident comparison in our bug-finding evaluation. Q2: What are the performance impacts of expanding CGT to For each tracing approach we omit benchmarks that are unsup- finer-grained code coverage metrics? ported or fail: sam2p and sfconvert for QEMU (due to repeated Q3: How do the benefits of coverage-preserving CGT impact deadlock); lzturbo, pngout, rar, and unrar for Dyninst (due to its fuzzing bug-finding effectiveness? inability to support closed-source, stripped binaries [38]); jasper, 5.1 Experiment Setup nasm, sam2p, lzturbo, pngout, rar, and unrar for RetroWrite (due to crashes on startup and/or being position-dependent/stripped); Below we provide expanded detail on our evaluation: the coverage- and lzturbo, pngout, rar, and unrar for AFL-Clang (due to it only tracing approaches we are testing, our benchmark selection, and supporting open-source targets). our experimental infrastructure and analysis procedures. Infrastructure: We carry out all evaluations on the Microsoft Competing Tracing Approaches: Table 5 lists the fuzzing Azure cloud infrastructure. Each fuzzing trial is issued its own coverage-tracing approaches tested in our evaluation. We eval- isolated Ubuntu 16.04 x86-64 virtual machine. Following Klees et uate our binary-only coverage-preserving CGT implementation, al.’s [32] standard we run 16×24-hour trials per benchmark for each HeXcite, alongside the current block-coverage-only CGT approach of the coverage-tracing approaches listed in Table 5, amounting UnTracer [37].6 To test HeXcite’s fidelity against the conventional to over 2.4 years’ of total compute time across our entire evalua- always-on coverage tracing in binary fuzzing, we also evaluate the tion. All benchmarks are instrumented on an Ubuntu 16.04 x86-64 leading binary tracers QEMU (AFL [59] and honggFuzz’s [49] de- desktop with a 6-core 3.50GHz Intel Core i7-7800x CPU and 64GB fault approach for fuzzing binary-only targets); Dyninst (a popular memory. We repurpose the same system for all data post-processing. static-rewriting-based alternative [26]); and RetroWrite [15] (a recent static-rewriting-based instrumenter). Lastly, we replicate 5.2 Q1: Coverage Evaluation UnTracer’s evaluation for open-source targets by further compar- To understand the trade-offs of adapting CGT to finer-grained cov- ing against AFL-Clang (AFL’s [59] source-level always-on trac- erage metrics, we first evaluate HeXcite’s code and loop coverage ing) [37]. We report HeXcite’s best-performing coverage configu- against the block-coverage-only Coverage-guided Tracer UnTracer; ration (edge coverage or edge+count coverage) in all experiments. as well as conventional always-on coverage-tracing approaches QEMU, Dyninst, RetroWrite, and AFL-Clang. We detail our experi- Approach Tracing Type Level Coverage mental setup and results below. HeXcite coverage-guided binary edge + counts UnTracer [37] coverage-guided binary block 5.2.1 Code Coverage. We compare the code coverage of all trac- QEMU [59] always-on binary edge + counts ing approaches in Table 5. We utilize AFL++’s Link Time Optimiza- Dyninst [26] always-on binary edge + counts RetroWrite [15] always-on binary edge + counts tion (LTO) instrumentation [18] to build collision-free edge-tracking Clang [59] always-on source edge + counts versions of each binary; the same technique is applied to our four Table 5: Fuzzing coverage tracers evaluated alongside HeXcite; and their type, closed-source benchmarks (Table 6) with the help of the industry- level, and coverage metric. standard binary-to-LLVM lifting tool McSema [14]. We measure Binary Package Source Input File each trial’s code coverage by replaying its test cases on the LTO jasper jasper-1.701.0 ✔ JPG binary using AFL’s afl-showmap [59] utility and compute the av- mjs mjs-1.20.1 ✔ JS erage across all 16 trials. Table 7 reports the average across all nasm nasm-2.10 ✔ ASM benchmark–tracer pairs as well as Mann-Whitney U significance sam2p sam2p-0.49.3 ✔ BMP scores at the 𝑝 = 0.05 significance level; and Figure 7 shows the sfconvert audiofile-0.2.7 ✔ WAV tcpdump tcpdump-4.5.1 ✔ PCAP relative edge coverage over 24-hours for several benchmarks. unrtf unrtf-0.20.0 ✔ RTF Versus UnTracer: As Table 7 shows, HeXcite surpasses Un- yara yara-3.2.0 ✔ YAR Tracer in total coverage across all benchmarks by 1–18% for a mean lzturbo lzturbo-1.2 ✗ LZT pngout Mar 19 2015 ✗ PNG improvement of 6.2%, with statistically higher coverage on 10 of 12 rar rarlinux-4.0.0 ✗ RAR benchmarks. The impact of coverage granularity on CGT is signifi- unrar rarlinux-4.0.0 ✗ RAR Table 6: Our evaluation benchmark corpora. cant; besides seeing the worst coverage on unrtf (Figure 7c) and sfconvert, block-only coverage UnTracer is bested by AFL-Clang on all 8 open-source benchmarks, demonstrating that sheer speed Benchmark Selection: Our benchmark selection (Table 6) fol- is not enough to overcome a sacrifice in code coverage—whereas lows the current standard in the fuzzing literature, consisting of HeXcite’s coverage-preserving CGT averages the highest overall eight binaries from popular open-source applications varying by code coverage in our entire evaluation. input file format (e.g., images, audio, video) and characteristics. Versus binary-only always-on tracing: We see that HeXcite Furthermore, as CGT’s most popular usage to date [18, 23, 30] is in achieves a mean 23.1%, 18.1%, and 6.3% higher code coverage over accelerating binary-only fuzzing, we also incorporate a set of four binary-only always-on tracers QSYM, Dyninst, and RetroWrite closed-source binary benchmarks distributed as free software. All (respectively), with statistically significant improvements on all 6As UnTracer is partially reliant on AFL’s source-level instrumentation and is hence but one binary per comparison (yara for QEMU, and sfconvert impossible to use on binary-only targets in its original form, we implement a fully for Dyninst and RetroWrite). For sfconvert in particular, we find binary-only version suitable across all 12 of our evaluation benchmarks. that all tracers’ runs are dominated by timeout-inducing inputs,
358
Rel. Edge Coverage
Rel. Edge Coverage
Rel. Edge Coverage
5 4 3 2 1 0 1110 9 8 7 6 5 4 3 2 1 0
Rel. Edge Coverage
8 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Rel. Edge Coverage
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
Clang Dyninst HeXcite Clang QEMU UnTracer Clang QEMU UnTracer QEMU UnTracer HeXcite QEMU UnTracer HeXcite
QEMU UnTracer RetroWrite Dyninst HeXcite RetroWrite Dyninst HeXcite
1.000 1.0 1.00 1.0 1.0
0.975 0.9 0.95 0.9 0.8
0.950 0.8 0.90
0.925 0.7 0.85 0.8 0.6
0.900 0.6 0.80 0.7
0.875 0.75 0.4
0.850 0.5 0.70 0.6
0.825 0.4 0.65 0.2
0.8000 10⁰ 10¹ 0.3 0 10⁰ 10¹ 0.600 10⁰ 10¹ 0.5 0 10⁰ 10¹ 0 10⁰ 10¹
Hours of Fuzzing (log-scale) Hours of Fuzzing (log-scale) Hours of Fuzzing (log-scale) Hours of Fuzzing (log-scale) Hours of Fuzzing (log-scale)
(a) nasm (b) tcpdump (c) unrtf (d) pngout (e) unrar
Figure 7: HeXcite’s mean code coverage over time relative to all supported tracing approaches per benchmark. We log-scale the trial duration (24 hours) to more
clearly show the end-of-fuzzing coverage divergence.
vs. Coverage-guided Tracing vs. Binary- and Source-level Always-on Tracing
Binary HeXcite / UnTracer HeXcite / QEMU HeXcite / Dyninst HeXcite / RetroWrite HeXcite / Clang
Rel. Cov MWU Rel. Cov MWU Rel. Cov MWU Rel. Cov MWU Rel. Cov MWU
jasper 1.04 0.403 1.71 <0.001 1.77 <0.001 ✗ ✗ 1.01 0.209
mjs 1.05 0.002 1.07 <0.001 1.09 <0.001 1.04 0.001 1.01 0.231
nasm 1.06 <0.001 1.15 <0.001 1.17 <0.001 ✗ ✗ 1.03 <0.001
sam2p 1.03 0.003 ✗ ✗ 1.12 <0.001 ✗ ✗ 1.02 0.292
sfconvert 1.04 <0.001 ✗ ✗ 1.00 0.057 1.00 0.492 0.99 0.031
tcpdump 1.11 <0.001 1.41 <0.001 1.16 <0.001 1.13 <0.001 1.08 0.002
unrtf 1.18 0.002 1.02 0.168 1.03 0.041 1.06 0.002 1.00 0.440
yara 1.03 0.057 1.08 0.028 1.12 0.034 1.09 0.034 0.95 0.061
lzturbo 1.01 <0.001 1.06 <0.001 ✗ ✗ ✗ ✗ ✗ ✗
pngout 1.08 0.001 1.33 <0.001 ✗ ✗ ✗ ✗ ✗ ✗
rar 1.02 0.004 1.02 0.026 ✗ ✗ ✗ ✗ ✗ ✗
unrar 1.10 0.005 1.47 <0.001 ✗ ✗ ✗ ✗ ✗ ✗
Mean Increase +6.2% +23.1% +18.1% +6.3% +1.1%
Table 7: HeXcite’s mean code coverage relative to UnTracer, QEMU, Dyninst, Retrowrite, and AFL-Clang. ✗ = the competing tracer is incompatible with the
respective benchmark and hence omitted. Statistically significant improvements for HeXcite (i.e., Mann-Whitney U test 𝑝 < 0.05) are bolded.
causing each to see roughly equal execution speeds, and hence, code Relative Max Consecutive Iterations Per Loop Relative Max Consecutive Iterations Per Loop
coverage. While we expect that timeout-laden binaries are less likely 1.0 1.0 1.0 1.0 1.0 1.0 4.73 1.0 2.09 1.12 1.0 1.0 1.0 0.33 1.0 1.0 1.0 1.0 4.06 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
to see benefit from CGT in general, overall, HeXcite’s balance of 1.01.0 1.01.0 1.01.0 1.01.0 1.01.0 1.01.0 0.691.0 0.691.0 1.041.0 1.041.0 1.01.0 2.091.0 6.77 1.09 1.0 1.1 16.12 1.0 8.9 3.18
fine-grained coverage and speed easily rank it the highest-coverage 1.0 1.0 1.41 2.13 1.0 1.0 1.0 1.0 1.05 1.0 1.0 1.0 1.07 1.0 3.58 10.75 3.0 1.38 1.68 1.05
binary-only tracer. 2.26 1.0 2.85 1.0 1.0 1.38 1.0 1.02 0.14 2.1 3.71 1.0 2.28 4.38 4.25 10.56 1.1 8.1 10.56 1.33
1.0 0.31 2.37 0.6 4.17 0.81 2.31 4.17 1.64 1.64 9.0 2.47 10.64 6.98 1.49 3.76 2.77 1.07 1.07 1.5
Versus source-level always-on tracing: Across all eight open- 2.66 0.73 0.51 1.0 1.0 1.83 0.77 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 0.6 1.0 1.0 1.0 1.0 2.13 1.0 1.0 2.27 1.6 1.0 1.0 13.04 2.0 1.0 2.88
source benchmarks HeXcite averages 1.1% higher coverage than 1.0 2.04 1.51 1.09 1.0 1.23 1.65 2.41 8.86 0.8 1.08 1.0 1.0 2.25 10.62 5.0 2.1 7.46 1.35 0.53
AFL’s source-level tracing, AFL-Clang. Despite having statistically 1.0 1.0 0.65 4.06 1.0 8.33 1.02 1.0 1.0 1.0 1.46 7.0
1.49 6.67 6.4 1.31 1.0 4.64 1.0 5.59 3.76
worse coverage on sfconvert (due to its heavy timeouts), HeX- 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7
cite’s coverage is statistically better or identical to AFL-Clang’s on (a) jasper (b) mjsbin
7/8 benchmarks, confirming that coverage-preserving CGT brings Relative Max Consecutive Iterations Per Loop Relative Max Consecutive Iterations Per Loop
coverage tracing at least as effective as source-level tracing—to 4.5 4.5 7.86 1.76 3.0 4.5 1.0 1.0 1.0 1.0 1.1 1.0 1.0 1.0 0.84
1.0 0.84 1.0 1.0 1.0 1.0 1.01 1.03 5.0
binary-only fuzzing use cases. 4.31 8.5 1.24 3.26 5.7 1.0 1.0 0.02 1.0 1.0 1.0 11.33 7.03 1.0 8.17
0.98 1.14 8.75 1.64 1.2 1.95 2.0 1.5 1.0 5.13 4.07 1.13 1.79 7.9 1.0
1.0 1.0 1.51 1.0 1.0 1.0 4.52 1.0 1.0
HeXcite HeXcite 1.53 5.33 1.5 1.0 2.18 2.18 13.14 0.04 1.0 1.0 1.52 1.0 4.73 1.0 1.0
Binary / UnTracer / Clang 1.0 1.0 1.33 1.7 12.65 2.19 1.23 1.0 1.0 1.0 1.0 1.0 1.0 1.2 0.6
Rel. LoopCov Rel. LoopCov 1.0 1.0 1.0 1.0 78.0 1.25 1.0 3.62 1.16
jasper 1.56 1.14 6.89 6.9
mjs 3.61 1.06 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8
nasm 2.54 1.85
sam2p 1.05 1.19 Figure 8: (c) unrtf (d) yara
sfconvert 1.89 2.56 HeXcite’s mean loop coverage relative to UnTracer. Each box rep-
tcpdump 1.21 1.39 resents a mutually-covered loop, with values indicating the mean maximum
unrtf 3.54 0.73 consecutive iterations (capped at 128 total iterations to match AFL) over all
yara 2.98 0.95 16 trials. Green and pink shading indicate a higher relative loop coverage for
Mean Increase +130% +36% HeXcite and UnTracer (respectively), while grey indicates no change.
Table 8: HeXcite’s mean loop coverage (i.e., average maximum consecutive none of our binary-to-LLVM lifters (McSema, rev.ng, RetDec, reopt,
iterations capped at 128) relative to block-only CGT UnTracer and the source-
level conventional tracer AFL-Clang. llvm-mctoll, or Ghidra-to-LLVM) succeeded in recovering the loop
metadata necessary for our LLVM loop transformation to work; thus
our loop analysis is restricted to our eight open-source benchmarks.
5.2.2 Loop Coverage. To determine if coverage-preserving CGT We compare HeXcite to UnTracer and AFL-Clang as they sup-
is more effective at covering code loops, we develop a custom port all eight open-source benchmarks (and hence omit QEMU,
LLVM instrumentation pass to report the maximum consecutive Dyninst and RetroWrite which only support a few). We compute
iterations per loop per trial. Despite our success in lifting our closed- each loop’s mean from the maximum consecutive iterations for all
source benchmarks to add edge-tracking instrumentation (§ 5.2.1), trials per benchmark–tracer pair, capping iterations at 128 as AFL
359
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
QEMU Dyninst RetroWrite Clang HeXcite
1.0
80 12.5
0.8
60 10.0
40 7.5 0.6
5.0 0.4
20 2.5 0.2
0 x x x 0.0 x x xxx xxx xxx xxx 0.0
jasper sam2p yara mjs nasm sfconvert tcpdump unrtf lzturbo pngout rar unrar Rel. Mean
Figure 9: HeXcite’s mean throughput relative to conventional coverage tracers. We normalize throughput to the worst-performing tracer per benchmark, and
compute each tracer’s mean performance relative to HeXcite’s across all benchmarks (shown in the rightmost plot). For each benchmark we omit incompatible
tracers (denoted by a colored ✗). All comparisons to HeXcite yield a statistically significant difference (i.e., Mann-Whitney U test 𝑝 < 0.05).
omits hit counts beyond this range. Table 8 reports HeXcite’s mean Binary Edge / Block Full / Block Best / Block
coverage across all loops for each binary relative to UnTracer and Rel. Perf MWU Rel. Perf MWU Rel. Perf MWU
AFL-Clang; and Figure 8 shows a heatmap of HeXcite’s per-loop jasper 0.52 <0.001 0.54 <0.001 0.54 <0.001
coverage relative to UnTracer’s for several benchmarks. mjs 0.93 0.046 0.65 <0.001 0.93 0.046
Versus UnTracer: As Table 8 shows, HeXcite’s bucketed un- nasm 1.46 <0.001 2.61 <0.001 2.61 <0.001
sam2p 0.99 0.433 1.07 0.090 1.07 0.090
rolling brings 130% higher loop penetration coverage over Un- sfconvert 1.06 <0.001 1.24 <0.001 1.24 <0.001
Tracer. We see that UnTracer beats HeXcite on a minutia of loops tcpdump 0.96 0.150 0.64 <0.001 0.96 0.150
per benchmark (Figure 8)—expectedly—as its inability to track loop unrtf 1.04 0.332 0.78 <0.001 1.04 0.332
yara 0.97 0.125 0.18 <0.001 0.97 0.125
progress inevitably constrains fuzzing to exploring the same few lzturbo 0.74 0.292 0.82 0.448 0.82 0.448
loops trial after trial. We find that HeXcite queues over 2× as many pngout 1.02 0.002 0.99 0.332 1.02 0.002
test cases, thus showing that its loop-progress-aware coverage leads rar 1.01 0.492 0.68 <0.001 1.01 0.492
unrar 0.97 0.188 0.90 0.047 0.97 0.188
fuzzing to sacrifice focusing on the same few loops in favor of a Mean Rel. Perf. 97% 92% 110%
higher diversity of loops per binary. Table 9: Performance trade-offs of different CGT coverage granularities. We
Versus source-level always-on tracing: We see that, on aver- compute mean throughputs for three HeXcite coverage granularities (edge,
full, and the best of both) relative to UnTracer’s block-only granularity.
age, HeXcite attains a 36% higher loop coverage than source-level
always-on tracing with AFL-Clang. Though this improvement is § 5.2.2 show, coverage-preserving CGT attains the highest edge
modest, these results show that bucketed unrolling outperforms and loop coverage of all tracers in our evaluation—offsetting the
conventional coverage tracing’s exhaustive (i.e., on every basic performance deficits expected of finer-grained coverage (e.g., from
block) hit count tracking—yet only instruments loop headers. While spending more time covering more loops). Furthermore, as column
we posit that bucketed unrolling has further optimization potential 3 in Table 9 shows, HeXcite’s best-case performance is nearly in-
(e.g., halving the number of buckets, selective insertion, etc.), we distinguishable from UnTracer’s, with performance statistically
leave exploring this trade-off space to future work. improved or identical on all but two benchmarks.
Q1: Jump mistargeting and bucketed unrolling enable Coverage- Versus binary-only always-on tracing: As Figure 9 shows,
preserving CGT to achieve the highest overall coverage versus block- HeXcite averages 11.4×, 24.1×, and 3.6× the throughput of always-
only CGT—as well as conventional binary and source-level tracing. on binary-only tracers QEMU, Dyninst, and RetroWrite, respec-
tively. Furthermore, we observe that all 23 comparisons to HeXcite
yield a statistically significant improvement in HeXcite’s speed
5.3 Q2: Performance Evaluation over these competing binary-only tracers.
To measure the impacts of finer-grained coverage on CGT perfor- 2.8×Versus source-level always-on tracing: HeXcite averages
mance, we perform a piece-wise evaluation of the fuzzing test case the throughput of AFL’s main source-level coverage tracer
throughput (i.e., mean total test cases processed in 24-hours) of AFL-Clang. In only one case (nasm) does HeXcite face lower a
HeXcite’s edge (via jump mistargeting) and full (jump mistargeting throughput of around 19%; however, the remaining seven open-
+ bucketed unrolling) coverage versus UnTracer’s block-only cov- source benchmarks see HeXcite attaining a statistically higher
erage, shown in Table 9. To ascertain where coverage-preserving throughput. Thus, we conclude that HeXcite’s coverage-preserving
CGT’s performance stands with respect to always-on tracing, we CGT indeed upholds the speed advantages of CGT—outperforming
further evaluate HeXcite’s best-case throughput alongside the even the ordinarily-fast source-level tracing.
leading binary- and source-level coverage tracers QEMU, Dyninst,
RetroWrite, and AFL-Clang, shown in Figure 9. Q2: Coverage-preserving CGT trades-off a negligible amount of speed
Versus UnTracer: As Table 9 shows, incorporating edge cov- to attain the highest binary-only code and loop coverage—and still
erage in CGT incurs a mean throughput slowdown of 3%, while outperforms conventional always-on binary- and source-level tracing
supporting full coverage (i.e., edges and counts) sees a slightly with over 2–24× the test case throughput.
higher slowdown of 8%. However, as the experiments in § 5.2.1 and
360
Relative Total Executions
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
Clang Dyninst HeXcite Clang Dyninst HeXcite Clang QEMU UnTracer QEMU UnTracer HeXcite
QEMU UnTracer RetroWrite UnTracer RetroWrite Dyninst HeXcite
1.0 1.0 1.0 1.0
0.8 0.8 0.8 0.8
0.6 0.6 0.6 0.6
0.4 0.4 0.4 0.4
0.2 0.2 0.2 0.2
0.0 0 4 8 12 16 20 24 0.00 4 8 12 16 20 24 0.0 0 4 8 12 16 20 24 0.00 4 8 12 16 20 24
Hours of Fuzzing Hours of Fuzzing Hours of Fuzzing Hours of Fuzzing
(a) nasm (b) sfconvert (c) unrtf (d) pngout
Figure 10: HeXcite’s mean unique bugs over time relative to all supported tracing approaches per benchmark.
vs. Coverage-guided Tracing vs. Binary- and Source-level Always-on Tracing
Binary Rel.HeXciteRel./ UnTracer HeXcite / QEMU HeXcite / Dyninst HeXcite / RetroWrite HeXcite / Clang
Bugs MWU Rel. Rel. MWU Rel. Rel. MWU MWU
Crash Crash Bugs Crash Bugs Rel. Rel. MWU Rel. Rel.
Crash Bugs Crash Bugs
jasper 1.40 0.97 0.241 25.32 19.92 <0.001 42.50 37.00 <0.001 ✗ ✗ ✗ 1.31 1.12 0.216
mjs 1.37 1.02 0.462 17.33 6.71 <0.001 12.27 3.38 <0.001 5.92 1.84 <0.001 5.22 1.82 <0.001
nasm 1.99 1.21 <0.001 20.03 13.63 <0.001 18.93 19.24 <0.001 ✗ ✗ ✗ 1.74 1.27 <0.001
sam2p 1.43 1.05 0.447 ✗ ✗ ✗ 2.24 1.36 <0.001 ✗ ✗ ✗ 1.32 1.21 0.018
sfconvert 1.52 1.23 <0.001 ✗ ✗ ✗ 1.42 1.35 <0.001 1.56 1.53 <0.001 1.78 1.88 <0.001
tcpdump 1.28 1.04 0.212 2.43 1.64 <0.001 1.91 1.27 <0.001 1.29 1.09 0.048 1.01 1.05 0.084
unrtf 1.88 1.48 <0.001 1.37 1.35 0.001 1.67 1.46 <0.001 1.18 1.28 0.001 1.10 1.63 <0.001
yara 0.72 1.02 0.215 16.80 2.34 <0.001 22.49 2.89 <0.001 12.58 2.05 <0.001 10.47 1.72 <0.001
pngout 1.27 1.36 <0.001 2.49 2.17 <0.001 ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗
unrar 1.25 0.80 0.279 2.00 2.00 0.039 ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗
Mean Increase +41% +12% +997% +521% +1193% +749% +350% +56% +199% +46%
Table 10: HeXcite’s mean crashes and bugs relative to UnTracer, QEMU, Dyninst, RetroWrite, and AFL-Clang. We omit lzturbo and rar as none trigger any
crashes for them. ✗ = the tracer is incompatible with the respective benchmark and hence omitted. Statistically significant improvements in mean bugs found for
HeXcite (i.e., Mann-Whitney U test 𝑝 < 0.05) are bolded.
5.4 Q3: Bug-finding Evaluation binaries (respectively). Overall, beating even source-level tracers
We evaluate the crash- and bug-finding effectiveness of coverage- highlights HeXcite’s value at binary-only coverage.
preserving CGT across our 12 benchmarks. To triage raw crashes 5.4.2 Bug Diversity. Following additional triage to map discov-
into bugs, we apply the popular “fuzzy stack hashing” methodology, ered crashes to previously-reported vulnerabilities and bugs, we
trimming stack traces to their top-6 entries, and hash each with conduct several case studies to further examine HeXcite’s practi-
their corresponding fault address and reported error. We make use cality in real-world bug-finding versus existing tracers.
of the binary-only AddressSanitizer implementation QASan [17] to To determine whether coverage-preserving CGT effectively re-
extract crash stack traces and errors. veals many bugs, or is merely constrained to the same few time
after time, we compare the total bugs found by HeXcite to the
5.4.1 Unique Bugs and Crashes. Table 10 shows the HeXcite’s best-performing always-on coverage-tracers, RetroWrite (binary-
mean crash- and bug-finding relative to block-coverage-only CGT only) and AFL-Clang (source-level). As Figure 11 shows, despite
UnTracer; and always-on fuzzing coverage tracers QEMU, Dyninst, some overlap, HeXcite reveals 1.4× the unique bugs as RetroWrite
RetroWrite, and AFL-Clang. Figure 10 shows the mean unique and AFL-Clang—with a higher number of bugs that only HeXcite
crashes over time for several benchmarks. We omit lzturbo and successfully reveals—confirming that coverage-preserving CGT is
rar as no fuzzing run found crashes in them. practical for real-world bug-finding.
Versus UnTracer: As Table 10 shows, HeXcite exposes a mean
12% more bugs than UnTracer. In conjunction with the plots shown
in Figure 10, we see that coverage-preserving CGT’s small sacrifice 98 147 28 141 197 48
in speed is completely offset by the much higher number of bugs
and crashes found—attaining effectiveness statistically better than (a) HeXcite vs. RetroWrite (b) HeXcite vs. AFL-Clang
or identical to UnTracer on all 12 benchmarks. Figure 11: HeXcite’s total unique bugs found versus the fastest conventional
Versus binary-only always-on tracing: As expected, HeX- always-on tracers RetroWrite (binary-only) and AFL-Clang (source-level).
cite’s coverage-preserving CGT attains a mean improvement of
521%, 1193%, and 56% in fuzzing bug-finding over always-on binary-
only tracers QEMU, Dyninst, and RetroWrite (respectively). Just as 5.4.3 Bug Time-to-Exposure. We further compare HeXcite’s
in our performance experiments (§ 5.3), all 21 comparisons yield a mean time-to-exposure for 16 previously-reported bugs versus
statistically significant improvement for HeXcite. block-only CGT UnTracer; and always-on coverage tracers QEMU,
Versus source-level always-on tracing: Across all eight open- Dyninst, RetroWrite, and AFL-Clang. As Table 11 shows, HeX-
source benchmarks, HeXcite achieves a 46% higher bug-finding cite accelerates bug discovery by 52.4%, 48.9%, 41.2%, 43.5%, and
effectiveness than source-level tracer AFL-Clang, with statistically 32.3% over UnTracer, QEMU, Dyninst, RetroWrite, and AFL-Clang
improved and statistically identical bug-finding on 6/8 and 2/8 (respectively). While HeXcite is not the fastest on every bug, its
361
Rel. Unique Bugs
Rel. Unique Bugs
Rel. Unique Bugs
Rel. Unique Bugs
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
Identifier Category Binary Coverage-guided Tracing Binary- and Source-level Always-on Tracing
HeXcite UnTracer QEMU Dyninst RetroWrite Clang
CVE-2011-4517 heap overflow jasper 13.1 hrs 18.2 hrs ✗ ✗ ✗ 8.70 hrs
GitHub issue #58-1 stack overflow mjs 13.3 hrs 19.0 hrs ✗ ✗ 15.30 hrs ✗
GitHub issue #58-2 stack overflow mjs 13.6 hrs 16.4 hrs ✗ 22.6 hrs ✗ 15.70 hrs
GitHub issue #58-3 stack overflow mjs 5.88 hrs 6.80 hrs ✗ 14.7 hrs ✗ ✗
GitHub issue #58-4 stack overflow mjs 8.60 hrs 10.7 hrs ✗ 20.1 hrs 19.6 hrs ✗
GitHub issue #136 stack overflow mjs 1.30 hrs 7.50 hrs ✗ 1.30 hrs ✗ ✗
Bugzilla #3392519 null pointer deref nasm 12.1 hrs 13.5 hrs ✗ ✗ ✗ ✗
CVE-2018-8881 heap overflow nasm 5.06 hrs 14.6 hrs ✗ ✗ ✗ 13.9 hrs
CVE-2017-17814 use-after-free nasm 3.54 hrs 6.31 hrs ✗ ✗ ✗ 5.91 hrs
CVE-2017-10686 use-after-free nasm 3.84 hrs 5.40 hrs ✗ ✗ ✗ 4.70 hrs
Bugzilla #3392423 illegal address nasm 8.17 hrs 14.2 hrs ✗ ✗ ✗ ✗
CVE-2008-5824 heap overflow sfconvert 13.1 hrs 14.8 hrs ✗ 14.3 hrs 15.4 hrs ✗
CVE-2017-13002 stack over-read tcpdump 8.34 hrs 12.5 hrs ✗ 13.5 hrs 11.5 hrs 8.04 hrs
CVE-2017-5923 heap over-read yara 3.24 hrs 5.67 hrs 1.87 hrs ✗ 9.33 hrs 6.19 hrs
CVE-2020-29384 integer overflow pngout 5.40 min 34.5 min 18.0 min ✗ ✗ ✗
CVE-2007-0855 stack overflow unrar 10.7 hrs 17.6 hrs ✗ ✗ ✗ ✗
HeXcite’s Mean Relative Speedup 52.4% 48.9% 41.2% 43.5% 32.3%
Table 11: HeXcite’s mean bug time-to-exposure relative to block-coverage-only CGT UnTracer; and conventional always-on coverage tracers QEMU, Dyninst, RetroWrite, and AFL-Clang. ✗ = the competing tracer is incompatible with the benchmark or does not uncover the bug.
overall improvement over competing tracers further substantiates should the comparison match (e.g., if(%eax == foo): jump foo). the improved fuzzing effectiveness of coverage-preserving CGT. While promotion is applicable to nearly all indirect branches (and hence indirect critical edges), branch target prediction accuracy is Q3: Coverage-preserving CGT’s balance of speed and coverage im- never guaranteed. Existing approaches attempt to maximize pre- proves fuzzing effectiveness, revealing more bugs than alternative cision by profiling indirect branches in advance for their “most tracing approaches—in less time. probable” targets, however, fuzzing may expose (and prioritize) new targets previously considered unlikely by profiling. 6 DISCUSSION Hybrid Instrumentation: A third possibility for indirect criti- Below we discuss several limitations of coverage-preserving CGT cal edges is to default back to AFL-style hashing-based edge cover- and our prototype implementation, HeXcite. age (§ 2.3). While it is impossible to identify each indirect edge’s targets accurately, a conservative approach is to instead instrument 6.1 Indirect Critical Edges the set of all potential indirect branch targets, as their heuristics are generally well-known (e.g., function entrypoints for indirect While resolving direct critical edges is straightforward through calls, and post-call blocks for returns). We can thus imagine future jump mistargeting or edge splitting (§ 3.1), indirect critical edges target-tailored CGT approaches balancing fast speed for common- (i.e., indirect jumps/calls/returns) remain a universal problem even case critical edges with more precise handling (e.g., header splitting, for source-level solutions like LLVM’s SanitizerCoverage [50]. Be- promotion, and hybrid instrumentation) of infrequent ones. low we discuss several emerging and/or promising techniques for resolving indirect critical edges, and their trade-offs with respect 6.2 Trade-offs of Hit Count Coverage to supporting a binary-level coverage-preserving CGT. Hit counts measure fuzzing exploration progress in loops and cycles, Block Header Splitting: LLVM’s SanitizerCoverage supports but as with any coverage metric, their implementation must care- resolving indirect critical edges whose end blocks have one or more fully balance precision and speed to support effective bug-finding. incoming direct edges. For example, given a CFG with indirect critical edge #» Two considerations central to hit count coverage implementations ib (with i having outgoing indirect edges to some other blocks x and y) and direct edge #» are (1) the size and number of bucket ranges; and (2) the frequency ab, SanitizerCoverage first cuts block at which hit counts are tracked. We discuss both of these below. b’s header from its body into two copies, b0𝑖 and b0𝑎. Second, as Bucket Granularity: Our current implementation of bucketed the indirect transfer’s destination is resolved dynamically and thus unrolling (§ 4.3) mimics the hit count tracking of conventional cannot be statically moved, b0𝑖 ’s location must be pinned to that of fuzzers by injecting conditional checks against eight bucket ranges the original block b. Finally, the twin header blocks (b0𝑖 and b0𝑎) are (0–1, 2, 3, 4–7, 8–15, 16–31, 32–127, 128+). However, these eight appended with a direct jump to b’s body, b1—effectively splitting bucket ranges are merely an artifact of AFL’s original implementa- #» # » # » the original indirect critical edge ib with edges ib and direct edge #» # » # » 0𝑖 and b0𝑖 b1; tion (each hashed edge is mapped to an 8-bit index in its coverage ab with ab0𝑎 and b0𝑎b1. However, the inability to bitmap). Adding more buckets makes it possible to track more subtle statically alter indirect transfer destinations makes this approach changes in loop iteration counts, while using fewer buckets trades- only applicable for indirect critical edges that are the sole indirect off this level of introspection for higher fuzzing throughput. While edge to their end block; i.e., should there be multiple indirect critical it is unclear which bucket ranges achieve the best balance of speed edges (i# »1b and i# »2b), at most one can be split. and coverage with respect to bug-finding, we expect that future Indirect Branch Promotion: Originally designed as a mitiga- research will address these unanswered questions and more. tion for branch target prediction attacks, indirect branch promo- Frequency of Tracking: How often hit counts are tracked fur- tion aims to “rewrite” indirect transfers as direct: at runtime, each ther influences fuzzing exploration and bug-finding. Conventional dynamically-resolved indirect branch target is compared to sev- exhaustive (per-edge) hit counts shed light on frequencies of cycle eral statically-encoded candidates, with a conditional jump to each subpaths (e.g., how many times a loop break is taken), but risk
362
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
saturating a fuzzer’s search space with redundant or noisy paths. trees [2], INSTRIM [28], CollAFL [19]), their principles are well- Bucketed unrolling instead trades-off coverage exhaustiveness for suited to binary-only fuzzing. A recent fork of AFL-Dyninst [26] speed by restricting hit count tracking to only a subset of the pro- omits instrumentation from blocks preceded by unconditional di- gram state (e.g., loop iteration counters). While our analysis of rect transfer, as their coverage is directly implied by their ancestor’s. the bugs exclusively found by exhaustive hit counts (Figure 11b) In addition to accelerating execution of HeXcite’s tracer binary, reveals that none are outside the reach of HeXcite, we expect we see the potential for such control-flow-centric analyses to help that future work will explore adapting selective and synergistic hit determine how HeXcite’s control-flow-altering transformations count schemes to better cover complex loops, cycles, and compiler (e.g., bucketed unrolling) should optimally be applied. optimizations at high speed. 6.3 Improving Performance 7.3 Faster Execution The fuzzing-oriented binary transformation platform currently Besides instrumentation, execution is itself a bottleneck to fuzzing, utilized in HeXcite, ZAFL [38], adopts a code layout algorithm as faster execution enables more test cases to be run on the tar- that rewrites all direct jumps to have 32-bit PC-relative signed get program in less time. Most modern binary-only fuzzing efforts displacements. While this is well-suited to our implementation of have abandoned slow process creation-based execution for faster zero-address jump mistargeting (§ 4.2)—enabling virtually every snapshotting, leveraging cheap copy-on-write cloning to rapidly conditional jump in the program’s address space to be mistargeted initiate target execution from a pre-initialized state (e.g., AFL’s fork- to 0x00—32-bit displacements accumulate more runtime overhead server [59]). Xu et al. [55] achieve even faster snapshotting through over 8–16-bit displacements. As ZAFL has experimental code lay- fuzzing-optimized Linux kernel extensions. The recent technique outs that instead prioritize smaller displacements, we thus envision of persistent/in-memory execution offers higher speed by restrict- potential for faster “hybrid” mistargeting schemes that coalesce ing execution to only a pre-specified target program code region both zero-address and embedded interrupt styles. (essentially interposing a loop), and is gaining support among pop- ular binary-only fuzzing toolchains (e.g., WinAFL [22], AFL-QEMU, 6.4 Supporting Other Software & Platforms UnicornAFL). Many efforts are also exploring the benefits of amor- Our current coverage-preserving CGT prototype, HeXcite, sup- tizing fuzzing execution speed through parallelization; off-the-shelf ports 64-bit Linux C and C++ binaries. Extending support to other binary-only fuzzers like AFL [59] and honggFuzz [49] support par- software characteristics (e.g., 32-bit) or platforms (e.g., Windows) allelization out-of-the-box, and recent work by Falk [16] achieves requires retooling of its underlying static binary rewriting engine. even faster speed by leveraging vectorized instruction sets. As exe- However, as this component is orthogonal to the fundamental prin- cution and coverage tracking work hand-in-hand during fuzzing, ciples of coverage-preserving CGT, we expect that HeXcite will we view such accelerated execution mechanisms as complementary capitalize on future engineering improvements in static rewriting to HeXcite’s accelerated coverage tracking. to bring accelerated fuzzing to the broader software ecosystem. 7 RELATED WORK 8 CONCLUSION We discuss recent efforts to improve binary-only fuzzing perfor- Coverage-preserving Coverage-guided Tracing extends the prin- mance that are orthogonal to coverage-preserving CGT: (1) faster ciples behind CGT’s performance-maximizing, waste-eliminating instrumentation, (2) less instrumentation, and (3) faster execution. tracing strategy to the finer-gained coverage metrics it is not nat- urally supportive of: edge coverage and hit counts. We introduce 7.1 Faster Instrumentation program transformations that enhance CGT’s introspection capa- As binary fuzzing effectiveness depends heavily on maintaining bilities while upholding its minimally-invasive nature; and show fast coverage tracking, a growing body of research is targeting how these techniques improve binary-only fuzzing effectiveness instrumentation-side optimizations. Efforts to improve dynamic over conventional CGT, while keeping an orders-of-magnitude per- translation-based instrumentation (e.g., AFL-QEMU [59], DrAFL [47], formance advantage over the leading binary-only coverage tracers. UnicornAFL [52]) generally focus on simplifying or expanding the Our results reveal it is finally possible for today’s state-of-the- caching of translated code [4]; while those using static rewriting art coverage-guided fuzzers to embrace the acceleration of CGT— (e.g., ZAFL [38], Dyninst [40], RetroWrite [15]) tackle various chal- without sacrificing coverage. We envision a new era in software lenges related to generated code performance. Though our coverage- fuzzing, where synergistic and target-tailored approaches will max- preserving CGT prototype, HeXcite, currently leverages the ZAFL imize common-case performance with infrequent-case precision. rewriter, we believe that future advances in binary instrumentation will enable it to achieve performance even closer to native speed. ACKNOWLEDGEMENT 7.2 Less Instrumentation We thank our shepherd Jun Xu and our reviewers for helping us improve the paper. We also thank Peter Goodman and Trail of Bits Another way to reduce the footprint of coverage tracking is to for assisting us with binary-to-LLVM lifting. This material is based eliminate needless instrumentation from the program under test. upon work supported by the Defense Advanced Research Projects While most other control-flow-centric approaches only exist in Agency under Contract No. W911NF-18-C-0019 and the National compiler instrumentation-based implementation (e.g., dominator Science Foundation under Grant No. 1650540.
363
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
REFERENCES Conference, ACSAC, 2018. [1] laf-intel: Circumventing Fuzzing Roadblocks with Compiler Transformations, [30] Jinho Jung, Stephen Tong, Hong Hu, Jungwon Lim, Yonghwi Jin, and Taesoo 2016. URL: https://lafintel.wordpress.com/. Kim. WINNIE: Fuzzing Windows Applications with Harness Synthesis and Fast [2] Hiralal Agrawal. Dominators, Super Blocks, and Program Coverage. In ACM Cloning. In Network and Distributed System Security Symposium, NDSS, 2021. SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL, [31] Sun Hyoung Kim, Cong Sun, Dongrui Zeng, and Gang Tan. Refining Indirect 1994. Call Targets at the Binary Level. In Network and Distributed System Security [3] Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, and Symposium, NDSS, 2021. Thorsten Holz. REDQUEEN: Fuzzing with Input-to-State Correspondence. In [32] George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. Evalu- Network and Distributed System Security Symposium, NDSS, 2018. ating Fuzz Testing. In ACM SIGSAC Conference on Computer and Communications [4] Andrea Biondo. Improving AFL’s QEMU mode performance, 2018. URL: https: Security, CCS, 2018. //abiondo.me/2018/09/21/improving-afl-qemu-mode/. [33] C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program [5] Tim Blazytko, Cornelius Aschermann, Moritz Schlögel, Ali Abbasi, Sergej Schu- analysis & transformation. In International Symposium on Code Generation and milo, Simon Wörner, and Thorsten Holz. GRIMOIRE: Synthesizing Structure Optimization, CGO, 2004. while Fuzzing. In USENIX Security Symposium, USENIX, 2019. [34] Caroline Lemieux and Koushik Sen. FairFuzz: A Targeted Mutation Strategy for [6] Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoud- Increasing Greybox Fuzz Testing Coverage. In ACM/IEEE International Conference hury. Directed Greybox Fuzzing. In ACM SIGSAC Conference on Computer and on Automated Software Engineering, ASE, 2018. Communications Security, CCS, 2017. [35] Yuekang Li, Bihuan Chen, Mahinthan Chandramohan, Shang-Wei Lin, Yang Liu, [7] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. Coverage-based and Alwen Tiu. Steelix: Program-state Based Binary Fuzzing. In ACM Joint Greybox Fuzzing As Markov Chain. In ACM SIGSAC Conference on Computer Meeting on Foundations of Software Engineering, ESEC/FSE, 2017. and Communications Security, CCS, 2016. [36] Chenyang Lv, Shouling Ji, Chao Zhang, Yuwei Li, Wei-Han Lee, Yu Song, and [8] Ella Bounimova, Patrice Godefroid, and David Molnar. Billions and Bil- Raheem Beyah. MOPT: Optimize Mutation Scheduling for Fuzzers. In USENIX lions of Constraints: Whitebox Fuzz Testing in Production. Technical report, Security Symposium, USENIX, 2019. 2012. URL: https://www.microsoft.com/en-us/research/publication/billions-and- [37] Stefan Nagy and Matthew Hicks. Full-speed Fuzzing: Reducing Fuzzing Overhead billions-of-constraints-whitebox-fuzz-testing-in-production/. through Coverage-guided Tracing. In IEEE Symposium on Security and Privacy, [9] Peng Chen and Hao Chen. Angora: efficient fuzzing by principled search. In Oakland, 2019. IEEE Symposium on Security and Privacy, Oakland, 2018. [38] Stefan Nagy, Anh Nguyen-Tuong, Jason D Hiser, Jack W Davidson, and Matthew [10] Peng Chen, Jianzhong Liu, and Hao Chen. Matryoshka: Fuzzing Deeply Nested Hicks. Breaking Through Binaries: Compiler-quality Instrumentation for Better Branches. In ACM SIGSAC Conference on Computer and Communications Security, Binary-only Fuzzing. In USENIX Security Symposium, USENIX, 2021. CCS, 2019. [39] Chengbin Pang, Ruotong Yu, Yaohui Chen, Eric Koskinen, Georgios Portokalidis, [11] Yaohui Chen, Peng Li, Jun Xu, Shengjian Guo, Rundong Zhou, Yulong Zhang, Bing Mao, and Jun Xu. SoK: All You Ever Wanted to Know About x86/x64 Binary Taowei, and Long Lu. SAVIOR: Towards Bug-Driven Hybrid Testing. In IEEE Disassembly But Were Afraid to Ask. In IEEE Symposium on Security and Privacy, Symposium on Security and Privacy, Oakland, 2020. arXiv: 1906.07327. Oakland, 2021. [12] Yuanliang Chen, Yu Jiang, Fuchen Ma, Jie Liang, Mingzhe Wang, Chijin Zhou, [40] Paradyn Tools Project. Dyninst API, 2018. URL: https://dyninst.org/dyninst. Xun Jiao, and Zhuo Su. EnFuzz: Ensemble Fuzzing with Seed Synchronization [41] Van-Thuan Pham, Marcel Böhme, Andrew E. Santosa, Alexandru Răzvan Căci- among Diverse Fuzzers. In USENIX Security Symposium, USENIX, 2019. ulescu, and Abhik Roychoudhury. Smart Greybox Fuzzing. IEEE Transactions on [13] Jaeseung Choi, Joonun Jang, Choongwoo Han, and Sang Kil Cha. Grey-box Con- Software Engineering, 2019. colic Testing on Binary Code. In International Conference on Software Engineering, [42] Ganesan Ramalingam. On Loops, Dominators, and Dominance Frontiers. ACM ICSE, 2019. transactions on Programming Languages and Systems, page 22, 2002. [14] Artem Dinaburg and Andrew Ruef. McSema: Static Translation of X86 Instruc- [43] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, tions to LLVM, 2014. URL: https://github.com/trailofbits/mcsema. and Herbert Bos. VUzzer: Application-aware Evolutionary Fuzzing. In Network [15] Sushant Dinesh, Nathan Burow, Dongyan Xu, and Mathias Payer. RetroWrite: and Distributed System Security Symposium, NDSS, 2017. Statically Instrumenting COTS Binaries for Fuzzing and Sanitization. In IEEE [44] Sanjay Rawat and Laurent Mounier. Finding Buffer Overflow Inducing Loops in Symposium on Security and Privacy, Oakland, 2020. Binary Executables. In IEEE International Conference on Software Security and [16] Brandon Falk. Vectorized Emulation: Hardware accelerated taint tracking at 2 Reliability, SERE, 2012. trillion instructions per second, 2018. URL: https://gamozolabs.github.io/fuzzing/ [45] Kosta Serebryany. Continuous fuzzing with libfuzzer and addresssanitizer. In 2018/10/14/vectorized_emulation.html. IEEE Cybersecurity Development Conference, SecDev, 2016. [17] Andrea Fioraldi, Daniele Cono D’Elia, and Leonardo Querzoni. Fuzzing Binaries [46] Dongdong She, Kexin Pei, Dave Epstein, Junfeng Yang, Baishakhi Ray, and Suman for Memory Safety Errors with QASan. In IEEE Secure Development Conference, Jana. NEUZZ: Efficient Fuzzing with Neural Program Smoothing. In IEEE SecDev, 2020. Symposium on Security and Privacy, Oakland, 2019. [18] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. AFL++: Com- [47] Maksim Shudrak and Battelle. drAFL, 2019. URL: https://github.com/mxmssh/ bining Incremental Steps of Fuzzing Research. In USENIX Workshop on Offensive drAFL. Technologies, WOOT, 2020. [48] Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang, [19] S. Gan, C. Zhang, X. Qin, X. Tu, K. Li, Z. Pei, and Z. Chen. CollAFL: Path Sensitive Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna. Fuzzing. In IEEE Symposium on Security and Privacy, Oakland, 2018. Driller: Augmenting Fuzzing Through Selective Symbolic Execution. In Network [20] GNU Project. GNU gprof, 2018. URL: https://sourceware.org/binutils/docs/gprof/. and Distributed System Security Symposium, NDSS, 2016. [21] Patrice Godefroid, Adam Kiezun, and Michael Y Levin. Grammar-based whitebox [49] Robert Swiecki. honggfuzz, 2018. URL: http://honggfuzz.com/. fuzzing. In ACM SIGPLAN Conference on Programming Language Design and [50] The Clang Team. SanitizerCoverage, 2019. URL: https://clang.llvm.org/docs/ Implementation, PLDI, 2008. SanitizerCoverage.html. [22] Google Project Zero. WinAFL, 2016. URL: https://github.com/googleprojectzero/ [51] Fabian Toepfer and Dominik Maier. BSOD: Binary-only Scalable fuzzing Of winafl. device Drivers. In International Symposium on Research in Attacks, Intrusions and [23] Samuel Groß and Google Project Zero. Fuzzing ImageIO, 2020. URL: https: Defenses, RAID, 2021. //googleprojectzero.blogspot.com/2020/04/fuzzing-imageio.html. [52] Nathan Voss and Battelle. AFL-Unicorn, 2019. URL: https://github.com/Battelle/ [24] Ilfak Guilfanov and Hex-Rays. IDA, 2019. URL: https://www.hex-rays.com/ afl-unicorn. products/ida/. [53] Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. Superion: Grammar-Aware [25] William H. Hawkins, Jason D. Hiser, Michele Co, Anh Nguyen-Tuong, and Jack W. Greybox Fuzzing. In International Conference on Software Engineering, ICSE, 2019. Davidson. Zipr: Efficient Static Binary Rewriting for Security. In IEEE/IFIP arXiv: 1812.01197. International Conference on Dependable Systems and Networks, DSN, 2017. [54] Matthias Wenzl, Georg Merzdovnik, Johanna Ullrich, and Edgar Weippl. From [26] Marc Heuse. AFL-Dyninst, 2018. URL: https://github.com/vanhauser-thc/afl- Hack to Elaborate Technique—A Survey on Binary Rewriting. ACM Computing dyninst. Surveys, 52(3), 2019. [27] Jason Hiser, Anh Nguyen-Tuong, William Hawkins, Matthew McGill, Michele [55] Wen Xu, Sanidhya Kashyap, Changwoo Min, and Taesoo Kim. Designing New Op- Co, and Jack Davidson. Zipr++: Exceptional Binary Rewriting. In Workshop on erating Primitives to Improve Fuzzing Performance. In ACM SIGSAC Conference Forming an Ecosystem Around Software Transformation, FEAST, 2017. on Computer and Communications Security, CCS, 2017. [28] Chin-Chia Hsu, Che-Yu Wu, Hsu-Chun Hsiao, and Shih-Kun Huang. INSTRIM: [56] Wei You, Xuwei Liu, Shiqing Ma, David Perry, Xiangyu Zhang, and Bin Liang. Lightweight Instrumentation for Coverage-guided Fuzzing. In NDSS Workshop SLF: Fuzzing without Valid Seed Inputs. In International Conference on Software on Binary Analysis Research, BAR, 2018. Engineering, ICSE, 2019. [29] Vivek Jain, Sanjay Rawat, Cristiano Giuffrida, and Herbert Bos. TIFF: Using Input [57] Wei You, Xueqiang Wang, Shiqing Ma, Jianjun Huang, Xiangyu Zhang, XiaoFeng Type Inference To Improve Fuzzing. In Annual Computer Security Applications Wang, and Bin Liang. ProFuzzer: On-the-fly Input Type Probing for Better Zero- day Vulnerability Discovery. In IEEE Symposium on Security and Privacy, Oakland,
364
Session 2A: Fuzzing and Bug Finding CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea
[58] Insu Yun, Sangho Lee, Meng Xu, Yeongjin Jang, and Taesoo Kim. QSYM: A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing. In USENIX Security Symposium, USENIX, 2018. [59] Michal Zalewski. American fuzzy lop, 2017. URL: http://lcamtuf.coredump.cx/afl/. [60] Lei Zhao, Yue Duan, Heng Yin, and Jifeng Xuan. Send Hardest Problems My Way: Probabilistic Path Prioritization for Hybrid Fuzzing. In Network and Distributed System Security Symposium, NDSS, 2019.
365