SOURCE ARCHIVE
EXTRACTED CONTENT
119,914 chars Hardware Support to Improve Fuzzing
Performance and Precision
Ren Ding∗ Yonghae Kim∗ Fan Sang
Georgia Institute of Technology Georgia Institute of Technology Georgia Institute of Technology rding@gatech.edu yonghae@gatech.edu fsang@gatech.edu
Wen Xu Gururaj Saileshwar Taesoo Kim
Georgia Institute of Technology Georgia Institute of Technology Georgia Institute of Technology wen.xu@gatech.edu gururaj.s@gatech.edu taesoo@gatech.edu ABSTRACT 1 INTRODUCTION Coverage-guided fuzzing is considered one of the most efficient bug- Historically, bugs have been companions of software development finding techniques, given its number of bugs reported. However, due to the limitations of human programmers. Those bugs can coverage tracing provided by existing software-based approaches, lead to unexpected outcomes ranging from simple crashes, which such as source instrumentation and dynamic binary translation, render programs unusable, to exploitation toolchains, which grant can incur large overhead. Hindered by the significantly lowered attackers partial or complete control of user devices. As modern execution speed, it also becomes less beneficial to improve coverage software evolves and becomes more complex, a manual search for feedback by incorporating additional execution states. such unintentionally introduced bugs becomes unscalable. Various In this paper, we propose SNAP, a customized hardware platform automated software-testing techniques have thus emerged to help that implements hardware primitives to enhance the performance find bugs efficiently and accurately, one of which is fuzzing. Fuzzing and precision of coverage-guided fuzzing. By sitting at the bottom of in its essence works by continuously feeding randomly mutated the computer stack, SNAP leverages the existing CPU pipeline and inputs to a target program and watching for unexpected behavior. It micro-architectural features to provide coverage tracing and rich stands out from other software-testing techniques in that minimal execution semantics with near-zero cost regardless of source code manual effort and pre-knowledge about the target program are availability. Prototyped as a synthesized RISC-V BOOM processor required to initiate bug hunting. Moreover, fuzzing has proved its on FPGA, SNAP incurs a barely 3.1% tracing overhead on the SPEC practicality by uncovering thousands of critical vulnerabilities in benchmarks while achieving a 228× higher fuzzing throughput real-world applications. For example, Google’s in-house fuzzing than the existing software-based solution. Posing only a 4.8% area infrastructure ClusterFuzz [24] has found more than 25,000 bugs in and 6.5% power overhead, SNAP is highly practical and can be Google Chrome and 22,500 bugs in over 340 open-source projects. adopted by existing CPU architectures with minimal changes. According to the company, fuzzing has uncovered more bugs than CCS CONCEPTS over a decade of unit tests manually written by software develop- ers. As more and more critical bugs are being reported, fuzzing is • Security and privacy → Software security engineering; Domain- unarguably one of the most effective techniques to test complex, specific security and privacy architectures. real-world programs. An ideal fuzzer aims to execute mutated inputs that lead to bugs KEYWORDS at a high speed. However, certain execution cycles are inevitably Hardware-assisted fuzzing; Feedback-driven fuzzing; RISC-V BOOM wasted on testing the ineffective inputs that do not approach any ACM Reference Format: bug in practice. To save computing resources for inputs that are Ren Ding∗, Yonghae Kim∗, Fan Sang, Wen Xu, Gururaj Saileshwar, and Tae- more likely to trigger bugs, state-of-the-art fuzzers are coverage- soo Kim. 2021. Hardware Support to Improve Fuzzing Performance and guided and favor mutation on a unique subset of inputs that reach Precision. In Proceedings of the 2021 ACM SIGSAC Conference on Com- new code regions per execution. Such an approach is based on puter and Communications Security (CCS ’21), November 15–19, 2021, Vir- the fact that the more parts of a program that are reached, the tual Event, Republic of Korea. ACM, New York, NY, USA, 15 pages. https: better the chance an unrevealed bug can be triggered. In particular, //doi.org/10.1145/3460120.3484573 each execution of the target program is monitored for collecting ∗Both authors contributed equally to this work. runtime code coverage, which is used by the fuzzer to cherry-pick generated inputs for further mutation. For binaries with available Permission to make digital or hard copies of all or part of this work for personal or source code, code coverage information is traced via compile-time classroom use is granted without fee provided that copies are not made or distributed instrumentation. For standalone binaries, such information is traced for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM through dynamic binary instrumentation (DBI) [4, 11, 44], binary must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, rewriting [15, 48], or hardware-assisted tracing [31, 36]. to post on servers or to redistribute to lists, requires prior specific permission and/or a Nonetheless, coverage tracing itself incurs large overhead and fee. Request permissions from permissions@acm.org. CCS ’21, November 15–19, 2021, Virtual Event, Republic of Korea slows the execution speed, making fuzzers less effective. The re- © 2021 Association for Computing Machinery. sulting waste of computing resources can extend further with a ACM ISBN 978-1-4503-8454-4/21/11. . . $15.00 https://doi.org/10.1145/3460120.3484573
continuous fuzzing service scaling up to tens of thousands of ma- request aggregation, which minimizes the number of updates, and chines [24, 47]. For example, despite its popularity, AFL [61] suffers opportunistic bitmap update, which maximizes the utilization of free from a tracing overhead of nearly 70% due to source code instru- cache bandwidth for such updates and reduces their cost (§4.3). mentation and of almost 1300% in QEMU mode for binary-only Third, rich execution semantics can be extracted at the micro- programs [48]. Source code instrumentation brings in additional in- architecture layer. One may think that the raw data gathered at the structions to maintain the original register status at each basic block, hardware level largely loses detailed program semantics because the while DBI techniques require dynamic code generation, which is CPU executes the program at the instruction granularity. Counter- notoriously slow. Although optimized coverage-tracing techniques intuitively, we find that such low-level information not only enables have been proposed to improve performance, especially for binary- flexible coverage tracing, but also provides rich execution context only programs, they impose different constraints. RetroWrite [15] for fuzzing without performance penalty. For example, various requires the relocation information of position-independent code micro-architectural states are available in the processor pipeline (PIC) to improve performance for binary-only programs. Various during program execution, such as last-executed branches (which existing fuzzers [22, 26, 28] utilize Intel Processor Trace (PT) [36], a incur higher overhead to extract in software) and branch predictions hardware extension that collects general program execution infor- (which are entirely invisible to software). Using such rich micro- mation. Nevertheless, Intel PT is not tailored for the lightweight architectural information, SNAP is able to provide extra execution tracing required by fuzzing. The ad-hoc use of Intel PT in fuzzing semantics, including immediate control-flow context and approxi- results in non-negligible slowdown caused by extracting useful mated data flows, in addition to code coverage (§4.5). SNAP also information (e.g., coverage) from encoded traces, allowing a merely supports setting address constraints on execution-specific micro- comparable execution speed as source instrumentation in the best architectural states prior to execution, providing users the flexibility effort per large-scale profiling results [13, 33]. UnTracer [48] sug- to selectively trace and test arbitrary program regions. Thus, fuzzers gests coverage-guided tracing, which only traces testcases incurring on SNAP can utilize the runtime feedback that describes the actual new code paths. However, UnTracer adopts basic block coverage program state more precisely and make better mutation decisions. without edge hit count and measures a less accurate program execu- SNAP hosts clean software interfaces for adoption by the existing tion trace that misses information about control transfers and loops. AFL-based fuzzers with a minimal change of less than 100 LoCs. The overhead of software-based coverage tracing is inevitable be- We prototype SNAP on top of the RISC-V BOOM core [6], which cause it requires extra information not available during the original has one of the most sophisticated designs among the open-source program execution. Moreover, the applicability of fuzzing heav- processors. We also utilize a real hardware FPGA platform to evalu- ily depends on the availability of source code, given that existing ate the performance of SNAP. In particular, the tracing overhead of techniques commonly used for fuzzing standalone binaries are un- SNAP across the SPEC benchmarks is 3.1% on average, significantly acceptably slow and there is a need for faster alternatives. outperforming the software-based tracing method adopted by AFL In this paper, we propose SNAP, a customized hardware platform and its descendants. In addition, we fuzz a real-world collection of that implements hardware primitives to enhance the performance binary tools, Binutils v2.28 [21], with AFL assisted by SNAP. The and precision of coverage-guided fuzzing. When running on SNAP, evaluation results show that SNAP manages to achieve 228× higher fuzzing processes can achieve near-to-zero performance overhead. fuzzing throughput compared to that of the existing DBI scheme The design of SNAP is inspired by three key properties observed and outperforms the vanilla AFL in discovering new paths by 15.4% from the execution of a program at the hardware layer. thanks to the higher throughput. Furthermore, by improving cover- First, a hardware design can provide transparent support of age feedback with the rich execution semantics provided by SNAP, fuzzing without instrumentation, as coverage information can be we demonstrate that the modified AFL running on SNAP is capable collected directly in the hardware layer with minimal software of triggering a bug that can be barely reached by the vanilla AFL. intervention. By sitting at the bottom of the computer stack, SNAP Last, our synthesized FPGA is practical, posing only a 4.8% area can assist fuzzers to fuzz any binary efficiently, including third-party and 6.5% power overhead. libraries or legacy software, regardless of source code availability, In summary, this paper makes the following contributions: making fuzzing universally applicable. • We propose hardware primitives to provide transparent Second, we find that the code tracing routine, including measur- support of tracing and additional execution semantics for ing edge coverage and hit count, can be integrated seamlessly into fuzzing with minimal overhead. the execution pipeline of the modern CPU architecture, and a near- • We develop a prototype, SNAP, which implements the de- zero tracing overhead can be achieved without the extra operations signed primitives on a real hardware architecture. inevitable in software-based solutions. 1 To enable such low-cost • We evaluate the system on the benefits of fuzzing perfor- coverage tracing, SNAP incorporates two new micro-architectural mance and precision, and demonstrate its ease of adoption. units inside the CPU core: Bitmap Update Queue (BUQ) for gen- SNAP is available at https://github.com/sslab-gatech/SNAP. erating updates to the coverage bitmap and Last Branch Queue (LBQ) for extracting last branch records (§4.2). SNAP further adopts 2 BACKGROUND two micro-architectural optimizations to limit the overhead on the memory system from frequent coverage bitmap updates: memory In this section, we provide an overview of coverage-guided fuzzing. 1While PHMon [14] as a security monitor also provides hardware-based tracing, we We also introduce recent efforts in the research community to significantly outperform it with an optimized design more customized for fuzzing. See improve the quality of coverage feedback. Finally, we provide a §6 for more details. brief introduction to the typical workflow of modern processors.
2.1 Coverage-Guided Fuzzing 1 static void demangle_it (char *mangled) { 2 char *cur = mangled; Fuzzing has recently gained wide popularity thanks to its simplicity 3 ... and practicality. Fundamentally, fuzzers identify potential bugs by 4 while (*cur != ’\0’) { 5 switch (*cur) { generating an enormous number of randomly mutated inputs, feed- 6 case ’S’: ... // static members ing them to the target program and monitoring abnormal behaviors. 7 case ’L’: ... // local classes 8 case ’T’: ... // G++ templates To save valuable computing resources for inputs that approach real 9 } // more cases... 10 bugs, modern fuzzers prioritize mutations on such inputs under the 11 } guidance of certain feedback metrics, one of which is code coverage. 12 // buggy mangled pattern 13 if (has_SLLTS(mangled)) BUG(); Coverage-guided fuzzers [26, 43, 52, 61] rely on the fact that the 14 } more program paths that are reached, the better the chance that 15 int main (int argc, char **argv) { 16 ... bugs can be uncovered. Therefore, inputs that reach more code 17 for (;;) { paths are often favored. Coverage guidance has proved its power 18 static char mbuffer[32767]; 19 unsigned i = 0; by helping to discover thousands of critical bugs and has become 20 int c = getchar(); 21 // try to read a mangled name the design standard for most recent fuzzers [26, 43, 52, 61]. 22 while (c != EOF && ISALNUM(c) && i < sizeof(mbuffer)) { The common practice of measuring the code coverage of an input 23 mbuffer[i++] = c; 24 c = getchar(); is to count the number of reached basic blocks or basic block edges at 25 } runtime. To retrieve the coverage information, fuzzers either lever- 26 mbuffer[i] = 0; 27 if (i > 0) demangle_it(mbuffer); age software instrumentation accomplished during compile-time 28 } if (c == EOF) break; or use other techniques such as dynamic binary instrumentation 29 return 0; 30 (DBI) [4, 11, 44], binary rewriting [15, 48], or hardware-assisted 31 } tracing [31, 36] when source code is unavailable. For example, AFL Figure 1: An illustrative example for the runtime information gath- instruments every conditional branch and function entry while ered by SNAP. The code abstracts demangling in cxxfilt. compiling the target program and relies on QEMU assistance for standalone binaries. The collected information is then stored in a Algorithm 1: Edge encoding by AFL coverage bitmap, allowing efficient comparison across various runs. Although coverage feedback allows fuzzers to approach bugs more Input : BBsr c → BBd s t , pr ev Loc efficiently, coverage tracing itself incurs large overhead and slows 1 cur Loc = Random(BBd s t ) the execution speed, making fuzzers less effective. For instance, 2 bitmap[cur Loc ˆ pr ev Loc] += 1 AFL encounters a 70% performance overhead due to source code 3 pr ev Loc = cur Loc ≫ 1 instrumentation and a daunting 1300% performance overhead in Output :pr ev Loc – hash value for the next branch QEMU mode, making it unrealistic to fuzz large-scale binary-only with extra execution semantics. In particular, to achieve context programs. To unleash the true power of coverage-guided fuzzing, awareness, some fuzzers record additional execution paths if nec- we aim to minimize the overhead caused by coverage tracing with- essary [13, 19, 26, 28], while others track data-flow information out any constraint. Given the sizable computing resources used [3, 12, 18, 43, 52, 60] that helps to bypass data-driven constraints. by fuzzing services [24, 47], optimizing the performance allows These techniques enrich the coverage feedback and help a fuzzer more tests against a buggy program in finite time and renders an approach the bugs in Figure 1 sooner; yet they can be expensive and immediate return in the form of a substantial cost reduction. are thus limited. For example, traditional dynamic taint analysis can under-taint external calls and cause tremendous memory over- 2.2 Better Feedback in Fuzzing head. Although lightweight taint analysis for fuzzing [18] tries to Feedback in fuzzing aims to best approximate the program execu- reduce the overhead by directly relating byte-level input mutations tion states and capture the state changes affected by certain input to branch changes without tracing the intermediate data flow, it can mutations. The more accurate the feedback is in representing the still incur an additional 20% slowdown in the fuzzing throughput execution states, the more useful information it can provide to guide of AFL across tested benchmarks. the fuzzer toward bugs. Despite the success achieved by coverage- guided fuzzing, feedback that is solely based on the edges reached 2.3 Typical CPU Workflow by the generated inputs can still be coarse grained. Figure 1 depicts To motivate how hardware support can minimize the overhead an example of a buggy cxxfilt code snippet that reads an alphanu- of fuzzing, we explain the typical CPU workflow. When a CPU meric string from stdin (line 17-29) before demangling its contained runs a program, it fetches and executes the instructions stored in symbols based on the signatures (line 4-11). Specifically, BUG in the memory and constantly updates its program counter (PC), which program (line 13) results from a mangled pattern (i.e., SLLTS) in the points to the current location being executed. A typical CPU core input. With a seed corpus that covers all the branch transfers within consists of multiple pipeline stages, such as fetch, decode, execute, the loop (line 4-11), the coverage bitmap will be saturated even with and memory stages. Every instruction is processed in a specific way the help of edge hit count, as shown in Algorithm 1, guiding the throughout the pipeline stages based on its type. Among various in- fuzzer to blindly explore the bug without useful feedback. struction types, branch and jump instructions are notable since they To improve the quality of coverage feedback, much effort has can change the control flow of a program and thus alter the execu- been directed to more accurately approximate program states tion order of instructions. To handle the control-flow instructions
1 # [Basic Block]: 1 # preparing 8 spare registers 23 # saving register context 2 push %rbp Name Size (MB) Runtime Overhead (%) mov %rdx, (%rsp) 3 push %r15 baseline instrumented AFL-clang AFL-QEMU 4 mov %rcx, 0x8(%rsp) 4 push %r14 56 mov %rax, 0x10(%rsp) 5 ... perlbench 2.58 6.56 105.79 376.65 # bitmap update 6 mov %rax, %r14 7 mov $0x40a5, %rcx 7 # [Basic Block]: bitmap update bzip2 0.95 1.20 63.66 211.14 8 callq __afl_maybe_log 8 movslq %fs:(%rbx), %rax gcc 4.51 15.73 57.15 257.76 9 # restoring register context 9 mov 0xc8845(%rip), %rcx mcf 0.89 0.95 66.30 92.52 1011 mov 0x10(%rsp), %rax 10 xor $0xca59, %rax gobmk 4.86 8.11 44.80 224.27 mov (%rsp), %rdx 12 movl $0x652c, %fs:(%rbx) sjeng 1.04 1.38 47.36 261.04 12 mov 0x8(%rsp), %rcx 11 addb $0x1, (%rcx,%rax,1) hmmer 1.51 2.57 39.34 340.03 (a) AFL-gcc (b) AFL-clang libquantum 1.10 1.23 47.95 186.63 Figure 2: Source-instrumented assembly inserted at each basic block h264ref 1.70 3.43 49.32 542.73 omnetpp 3.72 7.31 48.97 186.35 between compilers. astar 1.10 1.39 43.57 124.93 while achieving high performance, modern computer architectures xalancbmk 8.49 49.56 107.64 317.63 adopt speculative execution, which allows the CPU to predict the Mean 2.70 8.29 (207.04%) 60.15 260.14 branch target instruction and proceed with the program execution Table 1: The cost of program size and runtime overhead for tracing based on the prediction result instead of stalling the pipeline until on an x86 platform across the SPEC benchmarks. a destination directed by a control-flow instruction is decided. If other hand, the overhead of source code instrumentation results the branch prediction turns out to be wrong, the CPU flushes its from the instructions inserted at each basic block that not only pipeline to discard the execution on the wrong path and restores profiles coverage but also maintains the original register values to the previous architecture states. Such a design reveals that every ensure that the instrumented program correctly runs. Figure 2a control-flow divergence during program execution is observed and depicts the instrumentation conducted by afl-gcc, which requires appropriately managed inside the CPU pipeline. Considering that assembly-level rewriting. Due to the crude assembly insertion at one essential task of fuzzing is to monitor control-flow transfer and each branch, the instructions for tracing (line 7-8) are wrapped manage code-coverage information, we discuss how to view fuzzing with additional instructions for saving and restoring register con- from a hardware perspective and benefit from possible advantages text (line 3-5 and line 10-12). Figure 2b shows the same processing available at the hardware level in §4. done by afl-clang, which allows compiler-level instrumentation 3 DISSECTING AFL’S TRACING OVERHEAD through intermediate representation (IR). The number of instruc- tions instrumented for tracing can thus be minimized (line 8-12) In this section, we provide a detailed examination of AFL, a state- thanks to compiler optimizations. Nevertheless, the instructions of-the-art coverage-guided fuzzer, on its excessive coverage tracing for maintaining the register values still exist and blend into the overhead as a motivating example. Among the existing coverage- entire workflow of the instrumented program (line 2-6). Table 1 guided fuzzers, AFL [61] is the most iconic one and has inspired lists the increased program sizes resulting from instrumentation numerous fuzzing projects [10, 17, 45]. Despite the differences in the by afl-clang, suggesting an average size increase of around 2×. adopted strategies for prioritizing seeds and generating testcases, The increase of program size and the runtime overhead given by coverage-guided fuzzers mostly choose to monitor code coverage afl-gcc can be orders of magnitude larger [62]. at edge granularity. In general, edge coverage is preferred over basic block coverage because of the additional semantics it embeds 4 SNAP to represent the program space. Specifically, a piece of code will be injected at each branch location of the program to capture the Motivated by the expensive yet inevitable overhead of existing control-flow transfer between a pair of basic blocks, along with coverage-tracing techniques, we propose SNAP, a customized hard- coarse-grained hit counts (i.e., number of times the branch is taken) ware platform that implements hardware primitives to enhance the for repetitive operations (e.g., loops) if necessary. Algorithm 1 de- performance and precision of coverage-guided fuzzing. A fuzzer picts the tracing logic adopted by AFL. coached by SNAP can achieve three advantages over traditional AFL injects the logic into a target program in two different ways coverage-guided fuzzers. based on the scenarios. When source code is available, AFL utilizes 1 Transparent support of fuzzing. Existing fuzzers instrument the compiler or the assembler to directly instrument the program. each branch location to log the control-flow transfer, as explained Otherwise, AFL relies on binary-related approaches such as DBI in §3. When source code is not available, the fuzzer has to adopt and binary rewriting. While source code instrumentation is typi- slow alternatives (e.g., Intel PT and AFL QEMU mode) to conduct cally preferred due to its significantly lower tracing overhead com- coverage tracing, a much less favored scenario compared to source pared to binary-related approaches, previous research indicates that code instrumentation. By sitting in the hardware layer, SNAP helps AFL can still suffer from almost a 70% slowdown under the tested fuzzers to construct coverage information directly from the proces- benchmarks [48]. Table 1 shows that the situation can worsen for sor pipeline without relying on any auxiliary added to the target CPU-bound programs, with an average tracing overhead of 60% program. SNAP thus enables transparent support of fuzzing any from source code instrumentation and 260% from DBI (i.e., QEMU). binary, including third-party libraries or legacy software, without In the worst case, DBI incurs a 5× slowdown. The tracing overhead instrumentation, making fuzzing universally applicable. from DBI mostly comes from the binary translation of all applicable 2 Efficient hardware-based tracing. At the hardware level, instructions and trap handling for privileged operations. On the many useful resources are available with low or zero cost, most of
User exe. Corpus Front-end Branch Prediction Decode Branch ❼ target address, prediction result Fuzzer Feedback Fetch Branch Rename Unit ❹Branch Resolution Info from dispatch stage, hwtrace() Syscall mmap() Controller Predictor Dispatch allocate new entries. ❸ LBQ Device Driver Fetched inst. Branch Recordsbb₀₀ bb b ... Cov. Bitmap Trace ⋅⋅⋅ LDQ1 STQ2 ❷ BUQ 1 b₂ ... 1 2 .... ❶ Decision A ✓✓ ✗ OS ✗ ✓✓ Logic Fetch Buffer UL ❻Aggregation {uses_buq, uses_lbq, inst_bytes} Issue CPU RegRead ❺ Opportunistic Execution Bitmap Update Unit L1 I-Cache L1 D-Cache Branch Predictor LBQ BUQ Mem Fetch Stage Execution Stage Memory Stage 1LDQ (Load Queue) HW 2STQ (Store Queue) (a) Overview of SNAP. (b) Architecture of the RISC-V BOOM core. Figure 3: Overview of SNAP with its CPU design. The typical workflow involves the components from userspace, kernel, and hardware. The architecture highlights the modified pipeline stages for the desired features, including trace decision logic, Bitmap Update Queue (BUQ), and Last Branch Queue (LBQ).
which are not exposed to higher levels and cause excessive over- Name Permission Description head to be obtained through the software stack. For example, SNAP BitmapBase Read/Write Base address of coverage bitmap provides the control-flow information by directly monitoring each BitmapSize Read/Write Size of coverage bitmap branch instruction and the corresponding target address that has TraceEn Read/Write Switch to enable HW tracing already been placed in the processor execution pipeline at runtime, TraceStartAddr Read/Write Start address of traced code region eliminating the effort of generating such information that is unavail- TraceEndAddr Read/Write End address of traced code region able in the original program execution from a software perspective. LbqAddr[0-31] Read Only Target addresses of last 32 branches This allows fuzzers to avoid program size increase and significant LbqStatus Read Only Prediction result of last 32 branches performance overhead due to the instrumentation mentioned in PrevHash Read/Write Hash of the last branch target inst. Table 1. In addition, SNAP utilizes idle hardware resources, such as Table 2: New control and status registers (CSRs) in SNAP. free cache bandwidth, to optimize fuzzing performance. 4.1 Overview of Hardware Primitives 3 Richer feedback information. To collect richer information for better precision of coverage, many existing fuzzers require SNAP provides hardware primitives to transparently trace program performance-intensive instrumentation. Surprisingly, we observe execution and maintain fuzzing metadata (e.g., coverage bitmap), that the micro-architectural state information already embeds rich avoiding the overhead of existing software-based techniques.2 Fig- execution semantics that are invisible from the software stack with- ure 3b shows an overview of the proposed hardware platform, out extra data profiling and processing. In addition to code coverage, highlighting the three new primitives blended into the processor SNAP exposes those hidden semantics to construct better feedback pipeline: 1 trace decision logic at the Fetch Stage to identify and tag that can more precisely approximate program execution states with- instructions that need to be traced (§4.2.1), 2 bitmap update queue out paying extra overhead. Currently, SNAP provides the records (BUQ) to manage coverage bitmap updates based on the tagged of last-executed branches and the prediction results to infer imme- instructions passing Execute Stage (§4.2.2), and 3 last branch queue diate control-flow context and approximated data flows. We leave (LBQ) to collect information about the last-executed branches from the support of other micro-architectural states as future work. the Branch Unit for additional contextual feedback (§4.2.3). We Figure 3a shows an overview of SNAP in action, which includes elaborate on each of the hardware units in §4.2. underlying hardware primitives, OS middleware for software sup- SNAP also introduces new control and status registers (CSRs) port, and a general fuzzer provided by the user. While running on as configuration interfaces between the hardware and the OS. SNAP, a fuzzer is allowed to configure the hardware and collect Table 2 contains the list of the new CSRs, each of 8 bytes in desired low-level information to construct input feedback through size, and their access permissions. BitmapBase and BitmapSize are interfaces exposed by the OS. In addition, the fuzzer coached by used to set the base address and size of the coverage bitmap. The SNAP can perform other fuzzing adjustments directly through the tracing in hardware is enabled by TraceEn. TraceStartAddr and hardware level, such as defining code regions for dedicated test- TraceEndAddr serve to define region-specific feedback when needed. ing on specific logic or functionalities. Although SNAP considers LbqAddr[0-31] and LbqStatus store the branch target addresses and fuzzing a first-class citizen, it is designed with versatility in mind for prediction results of the last 32 branches by default. Note that these all use cases that demand rich information about program execution two CSRs are read-only, as the kernel is not required to modify states. We provide further discussion in §6. 2 All of our hardware primitives use information originated from the existing CPU pipeline – e.g., the Program Counter and the raw bytes of an instruction available in the Fetch Stage, the branch-target address and branch-prediction results from the Branch Unit in the Execute Stage, etc.
State ⋅⋅⋅ Addr (4) s_done: Once the entry reaches this state, it is deallocated
tail à s_init ⋅⋅⋅ - when it becomes the head of the BUQ. s_load ⋅⋅⋅ C - Load can be speculatively executed. Figure 4 depicts the bitmap update operation in the BUQ designed s_load ⋅⋅⋅ B - Stalls until the dependent older s_load ⋅⋅⋅ A entry finishes its store. in a manner that imposes minimal overhead. Since the bitmap itself head à s_store ⋅⋅⋅ A - Store is executed in program order. is stored in user-accessible memory, its contents can be read and written via load and store operations with the base address of the Figure 4: Bitmap update operation in the Bitmap Update Queue. bitmap and specific offsets. To ensure the bitmap update opera- tion does not stall the CPU pipeline, the load part of the update their contents. Finally, PrevHash stores the hash of the last branch operation is allowed to proceed speculatively in advance of the target instruction to index the coverage bitmap, as described in §4.4. store operation, which is only executed when the corresponding in- During a context switch, the OS saves and restores this value to struction is committed. However, in case there are store operations ensure the correctness of the first bitmap update after the switch. pending for the same bitmap location from older instructions, such 4.2 Implementation of Hardware Primitives speculative loads are delayed until the previous store completes to prevent reading stale bitmap values. Moreover, each bitmap load We design and implement SNAP based on the out-of-order BOOM and store is routed through the cache hierarchy, which does not core [6], one of the most sophisticated open-source RISC-V pro- incur the slow access latency of the main memory. Note that the cessors to match commercial ones with modern performance opti- cache coherence and consistency of the bitmap updates can be en- mizations. Figure 3b highlights the lightweight modifications on sured by the hardware in a manner similar to that for regular loads key hardware components in SNAP. and stores in the shared memory. Last, a full BUQ can result in back 4.2.1 Trace Decision Logic. In the front-end of the BOOM core (Fig- pressure to the Execution Stage and cause pipeline stalls. To avoid ure 3b), instructions are fetched from the instruction cache (I-cache), this, we sufficiently increase the BUQ; our 24-entry BUQ ensures enqueued to the Fetch Buffer, and then sent onward for further exe- that such stalls are infrequent and incur negligible overhead. cution at every cycle. We extend the Fetch Controller by adding the Trace Decision Logic ( 1 ), which determines whether an instruc- 4.2.3 Last Branch Queue. The LBQ ( 3 ) is a circular queue record- tion inserted into the Fetch Buffer needs to be traced by SNAP. The ing the information of the last 32 branches as context-specific feed- trace decision results in tagging two types of instructions within back used by a fuzzer, as we describe in §4.5. Specifically, each the code region to be traced (i.e., between TraceStartAddr and entry of the LBQ stores the target address and the prediction result TraceEndAddr) using two reserved bits, uses_buq and uses_lbq. The for a branch (i.e., what was the branch direction and whether the uses_buq bit is used to tag the target instruction of every control- predicted direction from the branch-predictor was correct or not). flow instruction (i.e., a branch or a jump) to help enqueue bitmap Such information is retrieved through the branch resolution path update operations into the BUQ. Note that we choose to trace the from the branch unit ( 7 ), where branch prediction is resolved. To target instruction instead of the control-flow instruction itself for interface with the LBQ, we utilize the CSRs described in Table 2. the bitmap update due to our newly devised trace-encoding algo- Each LBQ entry is wired to a defined CSR and can be accessible from rithm (described later in §4.4). The control-flow instruction itself is software after each fuzzing execution using a CSR read instruction. also tagged with the uses_lbq bit to help enqueue the correspond- ing branch resolution information (i.e., the target address and the 4.3 Micro-architectural Optimizations prediction result) into the LBQ for additional contextual semantics Since the BUQ generates additional memory requests for bitmap (described later in §4.5). Overall, the trace decision logic conducts updates, it may increase cache port contention and cause non-trivial lightweight comparisons within a single CPU cycle in parallel to performance overhead. To minimize the performance impact, we the existing fetch controller logic and thus does not delay processor rely on the fact that the bitmap update operation is not on the execution or stall pipeline stages. critical path of program execution, independent of a program’s 4.2.2 Bitmap Update Queue. The BUQ ( 2 ) is a circular queue re- correctness. Hence, the bitmap update can be opportunistically per- sponsible for bitmap updates invoked by the instructions following formed during the lifetime of a process and also aggregated with control-flow instructions. A new entry in the BUQ is allocated when subsequent updates to the same location. Based on the observations, such an instruction tagged with uses_buq is dispatched during the we develop two micro-architectural optimizations. Execute Stage ( 4 ). Each entry stores the metadata for a single Opportunistic bitmap update. At the Memory Stage in Figure 3b, bitmap update operation ( 5 ) and performs the update sequentially memory requests are scheduled and sent to the cache based on the through four states: priority policy of the cache controller. To prevent normal memory (1) s_init: The entry is first initialized with the bitmap location requests from being delayed, we assign the lowest priority to bitmap to be updated, which is calculated using our trace encoding update requests and send them to the cache only when unused cache algorithm described in §4.4. bandwidth is observed or when BUQ is full. Combined with the (2) s_load: Subsequently, the current edge count at the bitmap capability of the out-of-order BOOM core in issuing speculative location is read from the appropriate memory address. bitmap loads for the bitmap updates, this approach allows us to (3) s_store: Then, the edge count is incremented by one and effectively utilize the free cache bandwidth while also minimizing written to the same bitmap location stored in the entry. the performance impact caused by additional memory accesses.
Algorithm 2: Edge encoding by SNAP 0x106cc li a5, 60 Input : BBsr c → BBd s t , pr ev Loc 0xdead bge a5, a4, 106cc 1 p = Addr ess(BBd s t ) + 0xc7b7 23 inst_byt es = I nst Byt es(BBd s t ) = 0x11fd6 … cur Loc = p ˆ inst_byt es[15 : 0] ˆ inst_byt es[31 : 16] 4 bitmap[cur Loc ˆ pr ev Loc] += 1 106cc: de ad c7 b7 lui a5, 0xdeadc 5 pr ev Loc = cur Loc ≫ 1 Output :pr ev Loc – hash value for the next branch Figure 5: An example of encoding a basic block ID. Memory request aggregation. A memory request aggregation and leverage the instruction bytes as a source of entropy without scheme ( 6 ) is also deployed to reduce the number of additional overhead to compensate the lack of randomness due to the RISC-V memory accesses. When the head entry of the BUQ issues a write instruction alignment. To be compatible with both 16- and 32-bit to update its bitmap location, it also examines the other existing long RISC-V instructions, SNAP always fetches two consecutive entries, which might share the same influencing address for subse- 16-bit sequences starting at the instruction address and performs quent updates. If found, the head entry updates the bitmap on behalf bitwise XOR twice to produce a basic bock ID (line 3 in Algorithm 2, of all the matched ones with the influence carried over, while the also in Figure 5). Therefore, each ID contains the entropy from vari- represented entries are marked finished and deallocated without ous data fields, including opcode, registers, and immediates, of either further intervention. This is effective, especially for loop statements, an entire instruction or two compressed ones. In addition, SNAP where the branch instruction repeatedly jumps to the same target chooses to operate on the destination instruction of a branching op- address across iterations. The BUQ can thus aggregate the bitmap eration to construct a basic block ID, as it provides a larger variety update operations aggressively with fewer memory accesses. of instruction types (i.e., more entropy) than the branch instruction itself. Similar to that of AFL, the encoding overhead of SNAP is considered minimal, as the operation can be completed within one 4.4 Edge Encoding CPU cycle. Note that Algorithm 2 can be easily converted to trace Algorithm 1 describes how AFL [61] measures edge coverage, where basic block coverage by discarding prevLoc (line 5), which tracks an edge is represented in the coverage bitmap as the hash of a pair control transfers (i.e., edges), and performing bitmap update (line of randomly generated basic block IDs inserted during compile time. 4) solely based on curLoc (line 3). To avoid colliding edges, the randomness of basic block IDs plays 4.5 Richer Coverage Feedback an important role to ensure the uniform distribution of hashing outputs. Rather than utilizing a more sophisticated hashing algo- As discussed in §2.2, edge coverage alone can be coarse-grained rithm or a bigger bitmap size to trade efficiency for accuracy, AFL and does not represent execution states accurately. Meanwhile, col- chooses to keep the current edge-encoding mechanism, as its practi- lecting additional execution semantics via software-based solutions cality is well backed by the large number of bugs found. Meanwhile, always incurs major performance overhead. SNAP aims to solve software instrumentation for coverage tracing requires excessive this dilemma from a hardware perspective. With various types of engineering effort and can be error-prone, especially in the case of micro-architectural state information available at the hardware complex COTS binaries without source code. Since it is non-trivial level, SNAP helps fuzzers to generate more meaningful feedback to instrument every basic block with a randomly generated ID, one that incorporates the immediate control flow context and approxi- viable approach is to borrow the memory address of a basic block mated data flow of a program run without extra overhead. as its ID, which has proved effective in huge codebase [22]. Such Capturing immediate control-flow context. Tracking long an approach works well on the x86 architecture where instructions control-flow traces can be infeasible due to noise from overly sen- have variable lengths, usually ranging from 1 to 15 bytes, to pro- sitive feedback and the performance overhead from comparing duce a decent amount of entropy for instruction addresses to serve long traces. Therefore, SNAP records only the last 32 executed as random IDs. In the case of the RISC-V architecture, however, branches of a program run in the circular LBQ by default. Note that instructions are defined with fixed lengths. Standard RISC-V in- SNAP provides the flexibility of configuring branch entry number structions are 32-bit long, while 16-bit instructions are also possible and address filters through software interfaces so that the hosted only if the ISA compression extension (RVC) is enabled [54]. As a fuzzer can decide to track the execution trace of an arbitrary pro- result, RISC-V instructions are well-aligned in the program address gram space, ranging from a loop to a cross-function code region. A space. Reusing their addresses directly as basic block IDs for edge unique pattern of the 32 branch target addresses recorded in LBQ encoding lacks enough entropy to avoid collisions. captures the immediate control-flow context of a program execution, To match the quality of edge encoding in AFL, we devise a such as the most recent sequence of executed parsing options inside new mechanism (Algorithm 2) for SNAP that produces a sufficient string manipulation loops. When the immediate control-flow con- amount of entropy with no extra overhead compared to the naive text is included in coverage feedback, a fuzzer is inspired to further employment of memory addresses. Specifically, SNAP takes both mutate the inputs that share identical edge coverage but trigger the memory address and the instruction byte sequence inside a ba- unseen branch sequences within the loop (Figure 1 line 4-11) that sic block to construct its ID. A pair of such basic block IDs are then will otherwise be discarded. As a result, the fuzzer is more likely to hashed to represent the corresponding edge in the coverage bitmap. generate the input that can reach the specific last-executed branch By sitting at the hardware level, SNAP is able to directly observe sequence (i.e., SLLTS) for the buggy constraint (line 13).
Input LBQ Branch Predictor address range to be traced. Overall, SNAP is designed to be flexible
12ₛₜnd Branch Sequence Historical for various use cases.
Sequence Table
S L L T T Branch Prediction Process management. Besides the software interface that allows
while(*cur != ‘\0’){ user programs to configure hardware through system calls, the
switch (*cur) {
case ‘S’: ... Prediction Result XOR kernel also manages the tracing information of each traced process.
case ‘L’: ... Specifically, we add new fields to the process representation in the
of the coverage bitmap, the address and the size of the branch queue,
}}case ‘T’: ... 12stnd ✓✓ ✓✓ ✓✓ ✓✓ ✗✓ PC Linux kernel (i.e., task_struct), including the address and the size the tracing address range, and the previous hash value. Those fields Figure 6: An example of data flow approximation between two runs are initialized with zeros upon process creation and later assigned leveraging the branch predictions stored in LBQ. accordingly by the system calls mentioned before. During a context Approximating data flow via branch prediction. Data flow switch, if the currently executing process is being traced, the kernel analysis has proved to be useful for fuzzers [12, 52, 60] to mu- disables the tracing and saves the hash value and branch records tate inputs more precisely (e.g., identify the input byte that affects in the hardware queue. In another case, if the next process is to be a certain data-dependent branch condition). However, recent re- traced, the SNAP CSRs will be set based on the saved field values to search [18] points out that traditional data-flow analysis requires resume the last execution. Note that when fuzzing a multi-threaded too much manual effort (e.g., interpreting each instruction with application, existing fuzzers typically do not distinguish code paths custom taint propagation rules) and is slow, making fuzzing less from different threads but record them into one coverage bitmap effective. Surprisingly, SNAP is able to provide an approximation of to test the application as a whole. Although maintaining unique data flow without paying extra performance overhead by leveraging bitmaps is supported, SNAP enables the kernel to copy all the SNAP- the branch prediction results in the LBQ. A typical branch predictor, related fields of a parent process, except the address of the branch such as the one used in RISC-V BOOM [7] and shown in Figure 6, is queue, into its newly spawned child process by default. In addition, capable of learning long branch histories and predicts the current when a target process exits, either with or without error, SNAP branch decision (i.e., taken vs. not-taken) based on the matching relies on the kernel to clean up the corresponding fields during the historical branch sequence. Conversely, given the prediction results exit routine of the process. However, the memory of the coverage of the recorded branch sequence in the LBQ, SNAP is able to infer information and the branch queue will not be released immediately, a much longer branch history than the captured one. Therefore, if as it is shared with the designated user programs (i.e., fuzzers) to a mutated input byte causes a change in the prediction result of a construct the tracing information. Instead, the memory will be freed certain branch, the branch condition is likely related to the input on demand once the data have been consumed in the userspace. offset, thus revealing dependency between them with near-zero Memory sharing. To share the memory created for the coverage cost. Since most branch conditions are data-dependent [12, 18, 59], bitmap and the branch queue with the userspace program, SNAP the prediction result thus approximates the data flow from the input extends the kernel with two corresponding device drivers. In gen- to any variables that affect the branch decision. In Figure 6, even if eral, the device drivers enable three file operations: open(), mmap(), the coverage map and the immediate control-flow context remain and close(). A user program can create a kernel memory region the same, the fuzzer can still rely on the approximated data flows to designated for either of the devices by opening the device accord- mutate further for the sequence of interest (i.e., line 13 in Figure 1) ingly. The created memory will be maintained in a kernel array when it is not captured by the LBQ. until it is released by the close operation. Moreover, the kernel can remap the memory to userspace if necessary. The overall design is similar to that of kcov [37], which exposes kernel code coverage 4.6 OS Support for fuzzing. Besides the hardware modification, kernel support is also critical for SNAP to work as expected. We generalize it into three com- 5 ponents, including configuration interface, process management, EVALUATION and memory sharing between kernel and userspace. Rather than We perform empirical evaluations on the benefits of SNAP on testing the validity of modified OS on the hardware directly, we also fuzzing metrics and answer the following questions: provide the RISC-V hardware emulation via QEMU [4], allowing • Performance. How much performance cost needs to be paid for easier debugging of the full system. tracing on SNAP? (§5.2) Configuration interface. Among the privilege levels enabled by • Accuracy. How well can SNAP preserve traces against other the standard RISC-V ISA [54], we define the newly added CSRs approaches of comparable CPU cycles throughout the lifetime of (Table 2) in supervisor-mode (S-mode) with constraints to access processes? (§5.3) through the kernel. To configure the given hardware, SNAP pro- • Effectiveness. Can SNAP increase coverage for fuzzing in a vides custom and user-friendly system calls to trace a target pro- finite amount of time? How do branch records and branch pre- gram by accessing the CSRs. For example, one can gather the last- dictions provide more context-sensitive semantics? (§5.4) executed branches to debug a program near its crash site by en- • Practicality. How easy is it to support various fuzzers on SNAP? abling the branch record only. Others might request dedicated How much power and area overhead does the hardware modifi- fuzzing on specific code regions or program features by setting the cation incur? (§5.5)
Clock 75 MHz L1-I cache 32KB, 8-way Name SNAP (%) AFL-gcc (%)
LLC 4MB L1-D cache 64KB, 16-way 32 KB 64 KB 128 KB
DRAM 16 GB DDR3 L2 cache 512KB, 8-way
Front-end 8-wide fetch perlbench 7.63 4.28 4.20 690.27
16 RAS & 512 BTB entries bzip2 2.32 2.21 2.10 657.05
gshare branch predictor gcc 7.85 5.11 4.97 520.81
mcf 1.75 1.54 1.54 349.83
Execution 3-wide decode/dispatch gobmk 16.92 5.25 4.92 742.98
96 ROB entries hmmer 0.72 0.60 0.54 749.56
100 int & 96 floating point registers sjeng 7.29 0.68 0.52 703.44
Load-store unit 24 load queue & 24 store queue entries libquantum 0.80 0.67 0.44 546.67
24 BUQ & 32 LBQ entries h264ref 10.37 0.27 0.07 251.56
omnetpp 13.88 5.55 5.37 452.89
Table 3: Evaluated BOOM processor configuration. astar 0.37 0.30 0.30 422.96
xalancbmk 21.24 11.26 11.11 1109.24
5.1 Experimental setup Mean 7.59 3.14 3.00 599.77 We prototype SNAP on Amazon EC2 F1 controlled by FireSim [39], Table 4: Tracing overhead from AFL source instrumentation and an open-source FPGA-accelerated full-system hardware simulation SNAP with various L1-D cache sizes across the SPEC benchmarks. platform. FireSim simulates RTL designs with cycle-accurate system components by enabling FPGA-hosted peripherals and system-level interface models, including a last-level cache (LLC) and a DDR3 Name Agg. Rate (%) L1 Cache Hit Rate (%) memory [8]. We synthesize and operate the design of SNAP at the Base SNAP ∆ default clock frequency of LargeBoomConfig, which is applicable perlbench 3.32 97.82 96.49 -1.33 to existing CPU architectures without significant design changes. bzip2 13.67 91.80 91.32 -0.47 While modern commercial CPUs tend to adopt a data cache (L1-D) gcc 25.14 68.53 67.42 -1.11 mcf 7.83 44.45 43.89 -0.56 larger than the instruction cache (L1-I) for performance [30, 34, 35], gobmk 8.78 95.51 91.81 -3.70 we mimic the setup with the default data cache size of 64 KB for hmmer 1.36 95.80 95.64 -0.17 our evaluation. In general, the experiments are conducted under sjeng 5.24 98.44 96.18 -2.26 libquantum 41.60 53.97 53.24 -0.73 Linux kernel v5.4.0 on f1.16xlarge instances with eight simulated h264ref 16.23 96.67 95.89 -0.78 RISC-V BOOM cores, as configured in Table 3. Our modified hard- omnetpp 4.69 82.10 79.68 -2.42 ware implementation complies with the RISC-V standard and has astar 3.77 87.39 87.09 -0.30 xalancbmk 30.04 82.94 77.17 -5.77 been tested with the official RISC-V verification suite. The area Mean 13.47 82.95 81.32 -1.63 and power overhead of the synthesized CPU with our modifica- Table 5: Memory request aggregation rates and L1 cache hit rates tion are measured by a commercial EDA tool, Synopsys Design between the baseline and SNAP across the SPEC benchmarks. Compiler [56]. We evaluate SNAP on the industry-standardized SPEC CPU2006 numbers for DBI solutions (e.g., AFL QEMU mode), the resulting benchmark suite to measure its tracing overhead. We use the refer- overhead is expected to be much heavier than source instrumenta- ence (ref ) dataset on the 12 C/C++ benchmarks compilable by the tion, as explained in §3. The near-zero tracing overhead of SNAP latest RISC-V toolchain. To profile the encoding collisions, we col- results from its hardware design optimizations, including oppor- lect full traces from the benchmark as the ground truth for uniquely tunistic bitmap update and memory request aggregation (§4.3). executed edges before comparing with the encoded bitmaps. In par- Table 5 shows that the bitmap update requests have been reduced ticular, we enable user emulation of QEMU v4.1.1 in nochain mode by 13.47% on average thanks to aggregation. In the best case, the re- to force the non-caching of translated blocks so that the entire exe- duction rate can reach above 40%, which effectively mitigates cache cution trace of each run is emitted. Meanwhile, we test AFL’s run- contention from frequent memory accesses (e.g., array iteration) time coverage increase and throughput with Binutils v2.28 [21], a and avoids unnecessary power consumption. real-world collection of binary tools that have been widely adopted Further investigation shows that the performance cost of SNAP for fuzzing evaluation [27, 40]. In general, we fuzz each binary for might also result from cache thrashing at the L1 cache level. In 24 hours with the default corpus from AFL in one experimental run general, applications with larger memory footprints are more likely and conduct five consecutive runs to average the statistical noise to be affected. Since bitmap updates by the BUQ are performed in in the observed data. the cache shared with the program, cache lines of the program data 5.2 Tracing Overhead by SNAP might get evicted when tracing is enabled, resulting in subsequent cache misses. Note that this problem is faced by all existing fuzzers We measure the tracing overhead imposed by SNAP and source in- that maintain a bitmap. For instance, Table 5 points out that gobmk strumentation (i.e., AFL-gcc3) across the SPEC benchmarks. Table 4 and xalancbmk both suffer from comparably higher overhead (≥ 5%) shows that SNAP incurs a barely 3.14% overhead with the default caused by reduced cache hit rates of over 3.5%. The impact of cache cache size of 64 KB, significantly outperforming the comparable thrashing can also be tested by comparing the tracing overhead of software-based solution (599.77%). While we have excluded the SNAP configured with different L1 D-cache sizes. Table 4 shows that a larger cache exhibits fewer cache misses and can consistently 3We use AFL-gcc rather than AFL-clang because LLVM has compatibility issues in introduce lower tracing overhead across benchmarks. In particular, compiling the SPEC benchmarks. the overhead can be reduced to 3% on average by increasing the
22 random shift 27.0 5 4.8 4.8 6.1 47 51.0 5 24 29.8 7
instb_16 rotate 6.3
21 instb_32 bswap 4 46 4 3.8 3.6 23 22.922.9 6
instb_48 20.420.4 3 3.2 22 5 5.25.1
20 instb_64 3 45
19 19.3 18.4 18.9 19.2 2 1.6 2.41.82.52.4 44 43.3 43.7 43.443.743.6 44.244.2 2 1.6 1.3 1.71.8 21 20.8 21.3 21.121.521.3 4 3.4 3.93.53.63.7
18 18.2 1 43 1 1.0 20 3
(a) perlbench (b) bzip2 (c) gcc (d) mcf (e) gobmk (f) hmmer
8 7.6 7.6 7.5 5 4.2 11 12.812.715.7 14 14.6 6 5.35.3 5.2 27 31.2
7 4 3.8 3.6 10 13 5 26
6 3 9 12 11.9 12.0 4 25 24.824.8
2.2 8.1 8.2 8.2 11.4 11.2 24.2 24.5
5 4.0 4.4 4.2 4.2 4.3 2 1.4 1.91.61.9 8 7.4 7.6 11 10.6 11.0 11.1 3 2.1 2.6 2.4 2.32.3 24 23.8 24.0 24.0
4 1 7 10 2 23
(g) sjeng (h) libquantum (i) h264ref (j) omnetpp (k) astar (l) xalancbmk
Figure 7: Collisions from encoded trace edges among benchmarks. random indicates the baseline by AFL with random basic block IDs. The instb_*
family by SNAP adopts both memory addresses and instruction bytes as IDs. shift, rotate and bswap present the best collision rates achieved by bitwise
operations on memory addresses alone.
cache size to 128 KB. Alternatively, the extra storage can be repur- Name #Block Collision Rate (%)
posed as a dedicated buffer for the coverage bitmap to avoid cache random instb_16 instb_32 instb_48 instb_64
misses due to bitmap update, which we leave for future work. perlbench 18,612 13.06 16.91 14.61 14.60 14.44
In addition, Table 4 shows that the tracing overhead of AFL-gcc bzip2 2,069 1.61 2.32 2.23 2.15 1.96
is much larger. With the CPU-bound benchmarks that best approx- gcc 55,222 32.39 34.99 32.55 32.71 32.61
mcf 1,493 0.87 1.67 1.34 1.34 1.70
imate the extreme circumstances, the overhead is expected [62], as gobmk 19,762 13.58 16.08 14.40 13.80 14.35
discussed in §3. This finding is generally consistent with the num- hmmer 3,360 2.47 3.21 3.02 3.57 3.33
sjeng 3,351 2.45 3.49 3.01 3.28 3.07
bers from the x86 setup, which also incurs an average of 228.09% libquantum 1,397 1.15 2.29 1.50 1.72 2.05
overhead on the same testing suite by AFL-gcc. The extra slow- h264ref 7,365 5.53 6.93 6.19 5.90 5.94
omnetpp 10,321 7.04 8.41 7.84 8.05 7.82
down in the current RISC-V experiment is caused by the additional astar 2,441 1.90 2.58 2.12 2.11 2.60
instrumented locations in binaries due to the difference in ISAs. For xalancbmk 27,169 18.06 18.82 18.51 18.45 18.47
example, RISC-V does not define a specific instruction for backward Mean 12,713 8.34 9.81 8.94 8.97 9.03
edges (i.e., ret), which are often not tracked on instrumented x86 Table 6: Collisions from encoded trace blocks among benchmarks.
binaries. Thus, the RISC-V benchmarks have 58.51% more instru- On the other hand, Algorithm 2 by SNAP can achieve collision
mentation than the x86 version, resulting in a 40.03% increase in the rates (11.70%) similar to those of AFL. By leveraging the entropy
binary size. Note that the cache size has negligible impact on the of RISC-V instruction(s) at the start of a basic block, SNAP signifi-
tracing overhead for the software-based solution. Although bitmap cantly outperforms the aforementioned approaches that solely rely
updates can still cause cache thrashing, the overhead mainly comes on memory addresses for encoding. Meanwhile, we cannot find a
from the execution cost of instrumented instructions. consistent pattern of including more instruction bytes for fewer
collisions beyond 32 bits, as shown in Figure 7. Since most instruc-
5.3 Preserving Traces tions are 32-bit long, gathering data fields (e.g., opcode, registers,
Figure 7 shows the collision rates of various edge-encoding schemes and immediates) beyond one instruction might not be helpful in
on the SPEC benchmarks with the reference workload. The colli- practice.
sions are confirmed by comparing full execution traces against their Besides edge coverage, basic block coverage also serves as a met-
resulting bitmaps accordingly. A lower collision rate implies that a ric adopted by existing fuzzers [43, 52] to measure code coverage.
more complete code trace is preserved when a binary is fully tested. Table 6 shows the collisions from SNAP using basic block coverage
Together with the result of gcc from a limited bitmap size (i.e., 64 (§4.4) across the same benchmarks. The mechanism proposed by
KB), Algorithm 1 by AFL consistently generates the lowest collision SNAP (i.e., instb_32) reaches a collision rate of 8.94% on average,
rates (11.47%) among all. With random basic block IDs inserted at similar to the rate by AFL (8.34%). Therefore, SNAP is considered
compile time, true randomness is introduced into the algorithm to equally accurate in terms of preserving either block or edge traces.
avoid collisions. In comparison, the approaches that directly adopt
the memory address of a basic block as its ID perform significantly
worse. Even with the bitwise operations (i.e., logical shifts, circular 5.4 Evaluating Fuzzing Metrics
shifts, or endian swaps N bits of the block addresses before bitwise To understand how SNAP improves fuzzing metrics, we evaluate it
XORing them), the impact from well-aligned RISC-V instructions on seven Binutils binaries. Given the default corpus, we compare
cannot be reduced. In particular, the most effective one, circular the code coverage and runtime throughput of AFL running for
shift, produces an average of 337 more colliding edges than AFL per 24 hours under the existing DBI scheme (i.e., AFL-QEMU), source
benchmark, with a worst case of a 5.29% increase (i.e., h264ref). instrumentation (i.e., AFL-gcc), and support of SNAP.
Collision Rate (%) Collision Rate (%)
400
AFL-QEMU 3.00K AFL-QEMU
300 AFL-gcc AFL-gcc
AFL-SNAP 263 258 2.00K AFL-SNAP
200 196 223 212 229 213 1.00K
166 159 154 163 169 152 165 0.00K
100 0 5 (a) 10 15 20 25h
cxxfilt
0 1 1 1 1 1 1 1 0.90K
0.60K
0.30K
Figure 8: The average execution speed from fuzzing with AFL- 0.00K 0 5 10 15 20 25h
QEMU, AFL-gcc and AFL-SNAP for 24 hours across the Binutils bi- (b)nm
naries. The numbers below the bars of AFL-QEMU show the number of 1.20K
executions per second for the mechanism. 0.80K
Fuzzing throughput. Figure 8 shows the fuzzing throughput 0.40K
across the compared mechanisms. Specifically, AFL on SNAP can 0.00K
achieve 228× higher execution speed than AFL-QEMU, which is lim- 0 5 (c) 10 15 20 25h
objdump
ited by the low clock frequency and its inefficient RISC-V support.
The average throughput of AFL-QEMU (i.e., 0.18 exec/s) is consis- 1.80K
tent with the previous findings in PHMon [14]. Note that SNAP im- 1.20K
proves the throughput much more significantly than PHMon, which 0.60K
only achieves a 16× higher throughput than AFL-QEMU. Despite 0.00K 0 5 (d) 10 15 20 25h
that the baseline BOOM core in SNAP is about 50% faster [65] than readelf
the baseline Rocket core [5] adopted by PHMon, SNAP achieves a 0.75K
14× higher throughput-increase in comparison mainly due to its 0.50K
design optimizations (e.g., opportunistic bitmap update and mem- 0.25K
ory request aggregation). Compared to AFL-gcc, SNAP can still
achieve a 41.31% higher throughput on average across the bench- 0.00K 0 5 (e)10size 15 20 25h
marks. More throughput comparisons on x86 platforms are shown
in Appendix A. 0.12K
Edge coverage. Figure 9 depicts the resulting coverage measure- 0.08K
ment, where the confidence intervals indicate the deviations across 0.04K
five consecutive runs on each benchmark. Given an immature seed 0.00K
corpus and a time limit, AFL with SNAP consistently covers more 0 5 (f) 10 15 20 25h
paths than the others throughout the experiment. Since no change strings
to fuzzing heuristics (e.g., seed selection or mutation strategies) 0.75K
is made, the higher throughput of SNAP is the key contributor to 0.50K
its outperformance. On average, AFL-QEMU and AFL-gcc have 0.25K
only reached 23.26% and 84.59% of the paths discovered by AFL- 0.00K
SNAP, respectively. Although larger deviations can be observed 0 5 (g) 10 15 20 25h
strip
when the program logic is relatively simple (Figure 9f), SNAP in Figure 9: The overall covered paths from fuzzing seven Binutils bi-
general can help explore more paths in programs with practical
sizes and complexity thanks to its higher throughput. For example, naries for 24 hours. The solid lines represent the means, and the shaded
AFL with SNAP manages to find 579 (16.74%), 237 (20.82%), and 378 areas suggest the confidence intervals of five consecutive runs.
(19.77%) more paths when fuzzing cxxfilt, objdump, and readelf, by N bits based on their relative positions in the sequence before
respectively. being bitwise XOR’ed. The encoded value is finally indexed into a
Adopting execution context. Given the last-executed branches separate bitmap from the one for edge coverage (i.e., trace_bits).
and their prediction results in LBQ, fuzzers on SNAP are equipped Reproducing a known bug. Running on SNAP, the modified
with additional program states. To take the feedback, one can easily AFL is able to trigger CVE-2018-9138 discovered by the previous
follow the mechanisms introduced previously [13, 26, 28]. Our work [13], which proposes using feedback similar to that provided
prototype of AFL instead adopts a feedback encoding mechanism by our platform. As in Figure 1, the vulnerability occurs when
similar to that in Algorithm 1 to showcase the usage. Specifically, cxxfilt consumes a long consecutive input of "F"s, each indicat-
the highest significant bit (HSB) of each 64-bit branch address is set ing that the current mangled symbol stands for a function. The
based on the respective prediction result (i.e., 1/0). To maintain the corresponding switch case in the loop (line 5-10) tries to further
order of branches, the records are iterated from the least recent to demangle the function arguments (i.e., demangle_args() before
the latest in the circular LBQ and right circular shift’ed (i.e., rotated) running into the next "F" to start a recursive call chain. Luckily,
Throughput Improvement (X)
(0.33) cxxfilt
(0.14) nm
(0.15) objdump
(0.12) readelf
(0.15) size
(0.22) strings
(0.14) strip
covered paths # covered paths # covered paths # covered paths # covered paths # covered paths # covered paths
Description Area (mm2) Power (mW) Usage beyond fuzzing. Although fuzzing is a first-class citizen
BOOM core 9.2360 36.4707 targeted by SNAP, other applications are also welcomed by the
SNAP core 9.6811 38.8513 general design. For example, SNAP can provide an efficient coverage
Table 7: Estimates of area and power consumption. estimation for unit testing, which incurs significant hassle and
overhead with existing mechanisms such as gcov [20] and Intel
SNAP offers the execution context by capturing branch sequences PT [36]. The information can also serve as an execution fingerprint triggered by mutated inputs. While a vanilla AFL cannot easily for logging and forensic purposes. Last, partial feedback, such as reach the faulty program state with only edge coverage feedback, branch prediction results, can serve as approximated performance our fuzzer can consistently achieve it within one fuzzing cycle, led metrics with profiled cache misses in a specific code region. by the guidance. Limitations and future directions. While SNAP is carefully de- 5.5 Practicality of SNAP signed not to hinder the maximum clock frequency, we are limited in our evaluation to a research-grade hardware setup with low Easy adoption. To show how SNAP can be easily adopted, we clock speed. We hope our work motivates future studies and adop- have integrated a variety of fuzzers from FuzzBench [25], including tion on more powerful cores [58] and custom ASICs by processor AFL [61], AFLFast [10], AFLSmart [51], FairFuzz [42], MOpt [45], vendors [38]. Additionally, while SNAP does not support kernel and WEIZZ [16]. The others are excluded from the list, not because coverage filtered by the privilege level, leveraging the hardware of fundamental challenges to adopt SNAP but due to the incom- for tracing kernel space is not fundamentally restricted. SNAP is patibility of RISC-V. For example, HonggFuzz [26], libFuzzer [43], also not suitable to track dynamic code generation with reused Entropic [9], laf-intel [41], and Ankou [46] fail to compile on code pages, such as JIT and library loading/unloading, as it affects Fedora/RISC-V due to the lack of support from LLVM, GO, and the validity of the coverage bitmap. If needed, annotations with their dependent libraries (e.g., libunwind). Otherwise, the adoption filters on the program space can be applied to reduce noise. Future of SNAP is straightforward, requiring only a change of less than work could include repurposing a buffer dedicated for coverage 100 LoCs consistently. Around 55 LoCs are C code that issues the bitmap storage to avoid extra cache misses, leveraging other micro- system calls for creating shared bitmap and branch records, as well architectural states from hardware, such as memory access patterns, as comparing execution context per testcase. The others are as- to identify dynamic memory allocations (e.g., heap) across program sembly that compiles RISC-V binaries to work with forkserver (i.e., runs, or adopting operands of comparing instructions for feedback afl-gcc). as suggested [41]. Alternatively, given filters in the debug unit of Area and power overhead. To estimate the area and power over- ARM’s CoreSight extension [2], the practicality of the design can head of SNAP, we synthesize our design using Synopsys Design be further demonstrated without relying on custom hardware. Compiler at 1GHz clock frequency. To obtain a realistic estimate of the SRAM modules such as L1 D-cache, L1 I-cache, and branch 7 RELATED WORK predictor (BPD) tables used in the BOOM core, we black-box all the SRAM blocks and use analytical models from OpenRAM [29]. Binary-only fuzzing. Runtime coverage tracing can be costly and Our synthesis uses 45nm FreePDK libraries [55] to measure the becomes even more complicated when handling closed-source tar- area and power consumption between the unmodified BOOM core gets, such as COTS binaries. In particular, a typical software-based and the modified SNAP core. Table 7 shows that SNAP only incurs solution falls into either static or dynamic binary instrumentation, 4.82% area and 6.53% power overhead, more area-efficient than each limited by different constraints. For example, DynInst [57] is the comparable solution (16.5%) that enables hardware-accelerated not widely adopted, as the binary rewriting mechanism is error- fuzzing [14]. When tracing is disabled, the power overhead can be prone due to its complexity and thus cannot be applied to many mostly avoided by clock gating through the switch CSR TraceEn. real-world use cases [15]. RetroWrite [15] requires relocation infor- 6 DISCUSSION mation of position-independent code to soundly instrument bina- ries. While most of the dynamic binary instrumentation schemes Comparison with PHMon. PHMon [14] is a recently proposed [4, 11, 44, 49, 63] are more accessible to fuzzers thanks to their hardware-based security monitor that enforces expressive policy ease of use, they typically suffer from significant overhead due to rules. Despite its demonstration of basic hardware-assisted trac- runtime translation or callback routines. Although UnTracer [48] ing for fuzzing, PHMon is not specifically designed for this pur- suggests coverage-guided tracing to achieve near-native execution pose. In comparison, SNAP outperforms PHMon by a 14× higher speed for most of the non-interesting fuzzing testcases, its current fuzzing throughput thanks to the optimizations dedicated to light- design and evaluation are based on basic block coverage, which weight tracing, including opportunistic updates to utilize free cache represents a less accurate program execution trace in regard to bandwidth, issuing speculative load operations to avoid delays, and branch transfers and loops. Despite that a revised edge coverage memory request aggregation to reduce operations. Moreover, SNAP tracker (without edge count) has been proposed, the performance enables additional execution semantics as context-aware fuzzing impact of switching to the new solution is unclear due to the po- feedback without extra performance cost by providing last-executed tential increase of interesting testcases. In contrast, SNAP avoids branches and their branch prediction results. Together with the such hassles by tracing at the hardware level. It removes the gap be- cleverly encoded bitmap of low collision rates, SNAP helps fuzzers tween source-based and binary-only tracing while providing richer explore more program states for more interesting mutations. execution feedback with near-zero performance overhead.
Hardware-assisted fuzzing. Besides the software-based solu- REFERENCES tions, existing fuzzers [13, 26, 28, 53, 64] turn to available hardware [1] Apple. 2020. M1: Apple Neural Engine. https://www.apple.com/newsroom/2020/ extensions [31, 32, 36] for guidance when fuzzing binaries without 11/apple-unleashes-m1/. source code. Intel PT [36] has been the most commonly adopted [2] ARM. 2009. CoreSight Components Technical Reference Manual. https: one, exposing the full trace of an execution in a highly compressed //developer.arm.com/documentation/ddi0314/h/. fashion for efficiency. Despite its generality, the use of Intel PT [3] Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, and Thorsten Holz. 2019. REDQUEEN: Fuzzing with Input-to-State Correspondence. for fuzzing can be ad-hoc, as the feature was originally designed In Proceedings of the 2019 Annual Network and Distributed System Security Sym- for helping debug a program execution with accurate and detailed posium (NDSS). San Diego, CA. traces without worrying about performance impact. Therefore, it [4] Fabrice Bellard. 2005. QEMU, a fast and portable dynamic translator. In Proceed- already incurs at least 20-40% combined overhead for tracing and ings of the 2005 USENIX Annual Technical Conference (ATC). Anaheim, CA. decoding before a fuzzer can incorporate the feedback for further [5] UC Berkeley. 2016. Rocket Chip Generator. https://github.com/chipsalliance/ rocket-chip. mutation [33, 48, 64]. Although PTrix [13] utilizes Intel PT to gather [6] UC Berkeley. 2017. The Berkeley Out-of-Order RISC-V Processor. https://github. traces under a parallel scheme without recovering the exact condi- com/riscv-boom/riscv-boom. tional branches for edge coverage to avoid major decoding over- [7] UC Berkeley. 2019. The Branch Predictor (BPD) in RISC-V BOOM. https://docs. head, it merely achieves a comparable execution speed as source boom-core.org/en/latest/sections/branch-prediction/backing-predictor.html. instrumentation. Similarly, since PHMon [14] is designed to suit dif- [8] David Biancolin, Sagar Karandikar, Donggyu Kim, Jack Koenig, Andrew Water- ferent use cases, such as providing shadow stack and watchpoints man, Jonathan Bachrach, and Krste Asanovic. 2019. FASED: FPGA-Accelerated Simulation and Evaluation of DRAM. In Proceedings of the 2019 ACM/SIGDA for a debugger, its usage for tracing is not optimized for fuzzing International Symposium on Field-Programmable Gate Arrays (FPGA ’19). either. In comparison, SNAP adopts a highly optimized design for [9] Marcel Bohme, Valentin Manes, and Sang Kil Cha. 2020. Boosting Fuzzer Effi- fuzzing and shows its advantage over the other approaches in §5.4. ciency: An Information Theoretic Perspective. In Proceedings of the 28th Joint Meeting of the European Software Engineering Conference (ESEC) and the ACM SIG- Despite the barrier to entry for a customized architecture, the ben- SOFT Symposium on the Foundations of Software Engineering (FSE). Sacramento, efits of SNAP under minimal changes to an existing CPU pipeline CA. can be intriguing to commodity hardware. Motivated by the ex- [10] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coverage- isting hardware-accelerated infrastructures dedicated for machine based greybox fuzzing as markov chain. In Proceedings of the 23rd ACM Conference on Computer and Communications Security (CCS). Vienna, Austria. learning [1, 23, 50], along with the increasing industrial demand [11] Derek Bruening and Saman Amarasinghe. 2004. Efficient, transparent, and com- of fuzzing services [24, 47], SNAP demonstrates the feasibility of prehensive runtime code manipulation. Ph.D. Dissertation. Massachusetts Institute performance boost by hardware-assisted fuzzing, complementing of Technology. Intel PT for various use cases. [12] Peng Chen and Hao Chen. 2018. Angora: Efficient Fuzzing by Principled Search. In Proceedings of the 39th IEEE Symposium on Security and Privacy (Oakland). San Francisco, CA. 8 CONCLUSION [13] Yaohui Chen, Dongliang Mu, Jun Xu, Zhichuang Sun, Wenbo Shen, Xinyu Xing, We present SNAP, a customized hardware platform that imple- Long Lu, and Bing Mao. 2019. Ptrix: Efficient hardware-assisted fuzzing for cots ments hardware primitives to enhance performance and precision of binary. In Proceedings of the 14th ACM Symposium on Information, Computer and Communications Security (ASIACCS). Auckland, New Zealand. coverage-guided fuzzing. SNAP is prototyped as a full FPGA imple- [14] Leila Delshadtehrani, Sadullah Canakci, Boyou Zhou, Schuyler Eldridge, Ajay mentation together with the necessary OS support. By leveraging Joshi, and Manuel Egele. 2020. PHMon: A Programmable Hardware Monitor and micro-architectural optimizations in the processor, our prototype Its Security Use Cases. In Proceedings of the 29th USENIX Security Symposium (Security). Boston, MA. enables not only transparent tracing but also richer feedback on [15] Sushant Dinesh, Nathan Burow, Dongyan Xu, and Mathias Payer. 2018. execution states with near-zero performance cost. Adopted fuzzers, Retrowrite: Statically instrumenting cots binaries for fuzzing and sanitization. In such as AFL, can achieve 41% and 228× faster execution speed Proceedings of the 41st IEEE Symposium on Security and Privacy (Oakland). (and thus higher coverage) running on SNAP than with existing [16] Andrea Fioraldi, Daniele Cono D’Elia, and Emilio Coppa. 2020. WEIZZ: Auto- tracing schemes, such as source instrumentation and DBI. The hard- matic Grey-box Fuzzing for Structured Binary Formats. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA). Los Angeles, ware design only poses a 4.8% area and 6.5% power overhead and CA. thus is applicable to existing CPU architectures without significant [17] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. 2020. AFL++: changes. Combining incremental steps of fuzzing research. In Proceedings of the 14th USENIX Workshop on Offensive Technologies (WOOT). 9 ACKNOWLEDGMENT [18] Shuitao Gan, Chao Zhang, Peng Chen, Bodong Zhao, Xiaojun Qin, Dong Wu, and Zuoning Chen. 2020. GREYONE: Data Flow Sensitive Fuzzing. In Proceedings We thank the anonymous reviewers, and our shepherd, David Chis- of the 29th USENIX Security Symposium (Security). Boston, MA. nall, for their helpful feedback. This research was supported, in [19] Shuitao Gan, Chao Zhang, Xiaojun Qin, Xuwen Tu, Kang Li, Zhongyu Pei, and part, by the NSF award CNS-1563848 and CNS-1749711 ONR un- Zuoning Chen. 2018. CollAFL: Path Sensitive Fuzzing. In Proceedings of the 39th IEEE Symposium on Security and Privacy (Oakland). San Francisco, CA. der grant N00014-18-1-2662, N00014-15-1-2162, N00014-17-1-2895, [20] GNU Compiler Collection (GCC). 2012. Gcov is a test coverage program. https: DARPA AIMEE HR00112090034 and SocialCyber HR00112190087, //gcc.gnu.org/onlinedocs/gcc/Gcov-Intro.html. ETRI IITP/KEIT[2014-3-00035], and gifts from Facebook, Mozilla, [21] GNU Project. 2020. GNU Binutils. https://www.gnu.org/software/binutils. Intel, VMware and Google. [22] Google. 2018. syzkaller – kernel fuzzer. https://github.com/google/syzkaller. [23] Google. 2020. Cloud TPU: Empowering businesses with Google Cloud AI. https: //cloud.google.com/tpu. [24] Google. 2020. ClusterFuzz. https://google.github.io/clusterfuzz. [25] Google. 2020. FuzzBench: Fuzzer benchmarking as a service. https://github.com/ google/fuzzbench.
[26] Google. 2020. Honggfuzz. https://github.com/google/honggfuzz. [47] Microsoft Security Response Center (MSRC). 2020. OneFuzz. https://github.com/ [27] Google. 2020. OSS-Fuzz - Continuous Fuzzing for Open Source Software. https: microsoft/onefuzz. //github.com/google/oss-fuzz. [48] Stefan Nagy and Matthew Hicks. 2019. Full-speed fuzzing: Reducing fuzzing over- [28] Google Project Zero. 2020. WinAFL. https://github.com/googleprojectzero/ head through coverage-guided tracing. In Proceedings of the 40th IEEE Symposium winafl. on Security and Privacy (Oakland). San Francisco, CA. [29] Matthew R. Guthaus, James E. Stine, Samira Ataei, Brian Chen, Bin Wu, and [49] Anh-Quynh Nguyen and Hoang-Vu Dang. 2014. Unicorn: Next Generation CPU Mehedi Sarwar. 2016. OpenRAM: An Open-Source Memory Compiler. In Pro- Emulator Framework. In Black Hat USA Briefings (Black Hat USA). Las Vegas, ceedings of the 35th International Conference on Computer-Aided Design (ICCAD). NV. [30] IBM. 2016. IBM z13 Technical Guide. https://www.redbooks.ibm.com/redbooks/ [50] Nvidia. 2020. NVIDIA DRIVE AGX ORIN: Advanced, Software-Defined Platform pdfs/sg248251.pdf. for Autonomous Machines. https://www.nvidia.com/en-us/self-driving-cars/ [31] Intel. 2011. Intel® 64 and ia-32 architectures software developer’s manual. Volume drive-platform/hardware/. 3B: System programming Guide, Part 2 (2011). [51] Van-Thuan Pham, Marcel Bohme, Andrew Santosa, Alexandru Caciulescu, and [32] Intel. 2011. Intel BTS: Real time instruction trace. https://www.intel.com/content/ Abhik Roychoudhury. 2019. Smart Greybox Fuzzing. In IEEE Transactions on dam/www/public/us/en/documents/reference-guides/real-time-instruction- Software Engineering. trace-atom-reference.pdf. [52] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, [33] Intel. 2013. Intel processor trace decoder library. https://github.com/intel/libipt. and Herbert Bos. 2017. Vuzzer: Application-aware evolutionary fuzzing. In Pro- ceedings of the 2017 Annual Network and Distributed System Security Symposium [34] Intel. 2020. 10th Generation Intel Core Processor Families. https: (NDSS). San Diego, CA. //www.intel.com/content/www/us/en/products/docs/processors/core/10th- [53] Sergej Schumilo, Cornelius Aschermann, Robert Gawlik, Sebastian Schinzel, and gen-core-families-datasheet-vol-1.html. Thorsten Holz. 2017. KAFL: Hardware-assisted feedback fuzzing for OS kernels. [35] Intel. 2020. 11th Generation Intel Core Processor (UP3 and UP4). https://cdrdv2. In Proceedings of the 26th USENIX Security Symposium (Security). Vancouver, BC, intel.com/v1/dl/getContent/631121. Canada. [36] James R. 2013. Processor Tracing. https://software.intel.com/content/www/us/ [54] SiFive Inc. 2017. The RISC-V Instruction Set Manual. https://riscv.org//wp- en/develop/blogs/processor-tracing.html. content/uploads/2017/05/riscv-spec-v2.2.pdf. [37] Simon Kagstrom. 2015. Kcov is a FreeBSD/Linux/OSX code coverage tester. [55] J. E. Stine, I. Castellanos, M. Wood, J. Henson, F. Love, W. R. Davis, P. D. Franzon, https://github.com/SimonKagstrom/kcov. M. Bucher, S. Basavarajaiah, J. Oh, and R. Jenkal. 2007. FreePDK: An Open- [38] Michael Kan. 2021. Intel to Build Chips for Other Companies With New Source Variation-Aware Design Kit. In 2007 IEEE International Conference on Foundry Business. https://in.pcmag.com/processors/141636/intel-to-build-chips- Microelectronic Systems Education (MSE’07). for-other-companies-with-new-foundry-business. [56] Synopsys. 2020. DC Ultra. https://www.synopsys.com/implementation-and- [39] Sagar Karandikar, Howard Mao, Donggyu Kim, David Biancolin, Alon Amid, signoff/rtl-synthesis-test/dc-ultra.html. Dayeol Lee, Nathan Pemberton, Emmanuel Amaro, Colin Schmidt, Aditya Chopra, [57] Cisco Talos. 2014. AFL-Dyninst: AFL fuzzing blackbox binaries. https://github. Qijing Huang, Kyle Kovacs, Borivoje Nikolic, Randy Katz, Jonathan Bachrach, and com/Cisco-Talos/moflow/tree/master/afl-dyninst. Krste Asanović. 2018. FireSim: FPGA-accelerated Cycle-exact Scale-out System [58] TechPowerUp. 2020. RISC-V Processor Achieves 5 GHz Frequency at Just 1 Watt Simulation in the Public Cloud. In Proceedings of the 45th Annual International of Power. https://www.techpowerup.com/275463/risc-v-processor-achieves-5- Symposium on Computer Architecture (ISCA ’18). ghz-frequency-at-just-1-watt-of-power. [40] George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018. [59] Renju Thomas, Manoj Franklin, Chris Wilkerson, and Jared Stark. 2003. Improv- Evaluating Fuzz Testing. In Proceedings of the 25th ACM Conference on Computer ing Branch Prediction by Dynamic Dataflow-based Identification of Correlated and Communications Security (CCS). Toronto, ON, Canada. Branches from a Large Global History. In Proceedings of the 30th ACM/IEEE [41] lafintel. 2016. LAF LLVM Passes. https://gitlab.com/laf-intel/laf-llvm-pass. International Symposium on Computer Architecture (ISCA). San Diego, CA, USA. [42] Caroline Lemieux and Koushik Sen. 2018. FairFuzz: A targeted mutation strat- [60] Tielei Wang, Tao Wei, Guofei Gu, and Wei Zou. 2010. TaintScope: A checksum- egy for increasing greybox fuzz testing coverage. In Proceedings of the 33rd aware directed fuzzing tool for automatic software vulnerability detection. In IEEE/ACM International Conference on Automated Software Engineering (ASE). Proceedings of the 31th IEEE Symposium on Security and Privacy (Oakland). Oak- Corum, France. land, CA. [43] LLVM Project. 2020. libFuzzer - a library for coverage-guided fuzz testing. https: [61] Michal Zalewski. 2014. american fuzzy lop. http://lcamtuf.coredump.cx/afl/. //llvm.org/docs/LibFuzzer.html. [62] Michal Zalewski. 2019. Fast LLVM-based instrumentation for afl-fuzz. https: [44] Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff //github.com/google/AFL/blob/master/llvm_mode/README.llvm. Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin: [63] Google Project Zero. 2020. TinyInst: A lightweight dynamic instrumentation building customized program analysis tools with dynamic instrumentation. Acm library. https://github.com/googleprojectzero/TinyInst. sigplan notices 40, 6 (2005), 190–200. [64] Gen Zhang, Xu Zhou, Yingqi Luo, Xugang Wu, and Erxue Min. 2018. PTfuzz: [45] Chenyang Lyu, Shouling Ji, Chao Zhang, Yuwei Li, Wei-Han Lee, Yu Song, and Guided fuzzing with processor trace feedback. In IEEE Access (vol. 6). Raheem Beyah. 2019. {MOPT}: Optimized mutation scheduling for fuzzers. In Proceedings of the 28th USENIX Security Symposium (Security). Santa Clara, CA. [65] Jerry Zhao, Korpan Ben, Gonzalez Abraham, and Asanovic Krste. 2020. Sonic- [46] Valentin Manes, Soomin Kim, and Sang Kil Cha. 2020. Ankou: Guiding Grey-box BOOM: The 3rd Generation Berkeley Out-of-Order Machine. In Fourth Workshop Fuzzing towards Combinatorial Difference. In Proceedings of the 42th International on Computer Architecture Research with RISC-V. Conference on Software Engineering (ICSE). Seoul, South Korea.
1.2 AFL-gcc The finding generally aligns with that of the AFL whitepaper [62],
AFL-clang-fast 14.04% suggesting the performance gain of less than 10% for most binaries
1.1 7.10% 6.97% 7.19% other than CPU-bound benchmarks. The only exception occurs
5.06% 4.04% 4.32% when fuzzing strings (14.04%). This is because AFL’s feedback adopts
1.0 edge counters, driving the fuzzer to to search for longer inputs with
more printable strings, while the gain is magnified due to more
0.9 iterations and branch encounters consequentially. Thus, given the
relative edges over AFL-gcc (Figure 8 and Figure 10) and the posing
overhead on the SPEC benchmarks (Table 4 and Table 1), we would
expect SNAP to outperform AFL-clang on the RISC-V platform with
Figure 10: The average execution speed from fuzzing with AFL-gcc higher fuzzing throughput.
and AFL-clang-fast for 12 hours across the Binutils binaries. The
numbers below the bars of AFL-gcc show the number of executions per
second for the mechanism.
A APPENDIX
A.1 AFL throughput on x86 platforms
Although the fuzzing throughput from AFL-clang on the RISC-V
platform is left out due to technical difficulties, a similar comparison
for the numbers on x86 platforms is gathered instead. In particular,
we compile the Binutils binaries through AFL-gcc and AFL-clang,
and conduct five consecutive fuzzing runs of 12 hours to reduce the
statistical noise. Figure 10 shows that AFL-clang takes consistent
advantage of the compiler-based optimizations over AFL-gcc, which
manually instruments at the assembly-level, and outperforms in all
evaluating cases by an average of 6.96% faster execution speed.
Throughput Improvement (X)
(1718)
cxxfilt
nm(972)
objdump (941)
(1112)
readelf
size(932)
strings (171)
strip (932)