Predictive Context-sensitive Fuzzing

Predictive Context-sensitive Fuzzing Pietro Borrello∗, Andrea Fioraldi†, Daniele Cono D’Elia∗, Davide Balzarotti†, Leonardo Querzoni∗and Cristiano Giuffrida‡ ∗Sapienza University of Rome †EURECOM ‡Vrije Universiteit Amsterdam {borrello, delia, querzoni}@diag.uniroma1.it, {fioraldi, balzarot}@eurecom.fr, giuf[email protected] Abstract—Coverage-guided fuzzers expose bugs by progressively mutating testcases to drive execution to new program locations. Code coverage is currently the most effective and popular exploration feedback. For several bugs, though, also how execution reaches a buggy program location may matter: for those, only tracking what code a testcase exercises may lead fuzzers to overlook interesting program states. Unfortunately, context-sensitive coverage tracking comes with an inherent state explosion problem. Existing attempts to implement contextsensitive coverage-guided fuzzers struggle with it, experiencing non-trivial issues for precision (due to coverage collisions) and performance (due to context tracking and queue/map explosion). In this paper, we show that a much more effective approach to context-sensitive fuzzing is possible. First, we propose function cloning as a backward-compatible instrumentation primitive to enable precise (i.e., collision-free) context-sensitive coverage tracking. Then, to tame the state explosion problem, we argue to account for contextual information only when a fuzzer explores contexts selected as promising. We propose a prediction scheme to identify one pool of such contexts: we analyze the data-flow diversity of the incoming argument values at call sites, exposing to the fuzzer a contextually refined clone of the callee if the latter sees incoming abstract objects that its uses at other sites do not. Our work shows that, by applying function cloning to program regions that we predict to benefit from context-sensitivity, we can overcome the aforementioned issues while preserving, and even improving, fuzzing effectiveness. On the FuzzBench suite, our approach largely outperforms state-of-the-art coverageguided fuzzing embodiments, unveiling more and different bugs without incurring explosion or other apparent inefficiencies. On these heavily tested subjects, we also found 8 enduring security issues in 5 of them, with 6 CVE identifiers issued. I. INTRODUCTION Fuzz testing (or fuzzing for short) techniques earned a prominent place in the software security research landscape over the last decade. Their efficacy in generating unexpected or invalid inputs that make a program crash helps developers catch bugs early, even before they turn into vulnerabilities [1]. As an example, their deployment at scale in the OSS-Fuzz [2] initiative has led so far to the discovery of over 30 000 bugs in the daily testing of hundreds of open-source projects. The most popular and researched form of fuzzing is coverage-guided fuzzing (CGF), which uses code or other coverage information from program execution to deem whether the current testing input led to interesting (for example, previously unseen) portions of a program. The main intuition behind much CGF research is that code coverage is strongly correlated with bug coverage [3] and no dynamic testing technique can detect a bug if execution does not reach the corresponding program point at least once. A flourishing topic of research is to enlarge the covered code by improving the effectiveness of the input generation process, e.g., by guiding input mutations to meet complex control-flow conditions in the program [4], [5], [6]. However, for software testing, coverage is only one part of the equation [7], and the ultimate metric for the effectiveness of fuzzing remains the ability to discover bugs. As recently observed in [8], successful CGF embodiments balance between exploration and exploitation. While exploration aims to increase coverage, exploitation tries to trigger bugs in already-covered program regions by varying the inputs used to reach them before. As there is no immediate feedback for exploitation, fuzzers have to count on input mutations to execute such code “sufficiently well” to trigger bugs in it [8]. Therefore, other efforts focus on retaining for further mutation inputs that, while being equivalent to prior executions in terms of covered program points, exercise new valuable execution paths and/or internal states of the program [9]. Intuitively, these inputs offer alternative (and possibly more profitable) “starting points” for the above-said mutations to trigger some bugs. For example, most state-of-the-art CGF systems track edge coverage information to distinguish visits to the same basic block from different predecessor blocks [10]. Edge coverage and other function-local metrics track and summarize program execution for its effects on entities (e.g., code blocks, variable values) involving individual functions. A limitation of this strategy is that it may lead a fuzzer to overlook internal program states for which also how an entity is reached matters. In program analysis, this concept goes under the name of context-sensitivity and has seen many applications, such as refining the precision of pointer analyses [11] and developing compiler optimizations [12]. ANGORA [1] showcases the benefits of context-sensitivity for fuzzing by augmenting edge coverage with calling-context information, which captures the sequence of active function calls on the stack leading to the currently executing function [13]. In principle, such a fully context-sensitive approach can differentiate the coverage of each testcase in a fine-grained manner and lead to the discovery of more bugs [1], [10]. Network and Distributed System Security (NDSS) Symposium 2024 26 February - 1 March 2024, San Diego, CA, USA ISBN 1-891562-93-2 https://dx.doi.org/10.14722/ndss.2024.24113 www.ndss-symposium.org However, as an accurate call-stack tracking and context encoding would be costly and degrade the fuzzer’s throughput, ANGORA [1] and other fuzzers [14], [15] embody a best-effort strategy for full context-sensitivity. In particular, they model the calling context as a hash of the call stack and compute context-sensitive coverage identifiers by combining the hash for the current context with the function-local edge identifier upon entering a basic block. This scheme is naturally prone to collisions, which are detrimental to fuzzing as they may lead to missing many relevant testcases [16]. To mitigate this shortcoming, these fuzzers employ larger coverage maps (e.g., 220 entries in ANGORA [1]), a choice that does not come cheap as it can severely harm the fuzzing throughput. More importantly, as we study, fully context-sensitive approaches are prone to state explosion, enlarging the fuzzer’s queue with additional testcases that further reduce fuzzing efficiency, as the fuzzer will often fall short of the time needed to schedule or sufficiently mutate them [10]. In this paper, we will refer to all such kinds of detrimental effects as the internal wastage that the fuzzer experiences. Our approach: We argue that the current “all-ornothing” approach to context-sensitive fuzzing is unnecessarily inefficient, and that a much more effective approach is possible. The design we propose builds on three main insights: 1We show that we can do away with run-time call stack tracking by relying on a code specialization primitive. For a given calling context, with function cloning we create a clone of each callee and redirect the caller invocation to it. As a result, existing function-local coverage tracking techniques can naturally disambiguate calling contexts with no changes. For example, edges from cloned functions can benefit from the collision-free encoding of modern fuzzers as their presence implicitly carries (precise) contextual information, opposed to current approaches that enforce (and, as we study, further deteriorate) an imprecise hash-based edge encoding scheme. 2We show that, while fully context-sensitive approaches are in general problematic due to an inherent state explosion problem, selective approaches can be a much better alternative. Through techniques that restrict cloning to program portions that are likely to benefit from contextually refined edge profiles, we can bound our cloning efforts to trade a modest increase in program size with efficient contextsensitivity provided only for the callees that “matter”. We term our approach predictive context-sensitive fuzzing. 3We show that data-flows for function call arguments can be an effective predictor for several such regions. We analyze the flow of objects through function arguments at call sites and pick those call targets that see a highly diverse incoming data-flow if compared to other invocations of the function in the rest of the program. The intuition is that such differences may reflect relevant variations in program behavior that we want to capture by means of context-sensitive coverage tracking. Moreover, we show how to realize the strategy without analyzing full calling contexts, but building instead atop a standard context-insensitive inter-procedural analysis. This design results in a practical and performant contextsensitive fuzzing solution. On the popular FuzzBench suite [17], our approach can reveal more unique bugs than ANGORA-style context-sensitivity (+22.55%). Also, it outperforms a collision-free edge coverage solution boosted with link-time optimization (+11.6%), with the bugs found across trials being different than with edge coverage alone by 19.2%. These improvements mainly come from our ability to trigger bugs in code regions that other solutions explore but fail to exploit. Our approach experiences only a limited growth of retained testcases (+26% w.r.t. edge coverage, opposed to +81.7% from ANGORA-style context-sensitivity) and a modest impact on the fuzzing throughput (−6.5% vs. −20.3%). Finally, despite the FuzzBench subjects we study are welltested in prior efforts and daily in OSS-Fuzz, our tests revealed 8 long-standing security issues involving 5 of these subjects, with 6 CVE identifiers issued upon responsible disclosure. Contributions: To summarize, this paper proposes: •A selective approach to context-sensitive fuzzing that augments only promising program portions with contextual information, using function cloning to enable a collisionfree encoding with no run-time tracking machinery; •A data-flow analysis to predict program portions likely to benefit from contextual refinement when fuzzing, using a strong signal given by call-argument value diversity among the different callers of a given target function. •An open-source implementation in LLVM that produces programs suitable for out-of-the-box fuzzing (available at: https://github.com/eurecom-s3/predictive-cs-fuzzing). •An evaluation of our approach atop AFL++ on the FuzzBench suite, where we consistently outrank state-ofthe-art context sensitive and insensitive techniques, also exposing 8 enduring vulnerabilities in 5 popular subjects. II. BACKGROUND This section covers fundamental concepts of fuzzing and the points-to analysis primitives that back our predictive context-sensitive approach. A. Coverage-guided Fuzzing Fuzzing techniques have a prominent place in software security research due to their effectiveness in bug discovery [18]. In the most naive embodiment, a fuzzer is a system that attempts repeated executions of a target program over randomly generated testcases while monitoring it for crashes. Many techniques are available to optimize the testcase generation process, e.g., to discover more bugs within a given time budget [19] or prioritize specific code regions for testing [20]. The amount of information that a modern fuzzer acquires during the (many) executions of the program under test can vary, leading to a distinction between black-box [21], [22], white-box [23], [24], and grey-box [25], [26] fuzzers. In particular, grey-box fuzzers use lightweight instrumentation to track coarse-grained state information such as the code coverage achieved by each testcase and are largely popular due to their effectiveness. As we anticipated in Section I, tracking code coverage can also serve as a feedback for coverage-guided fuzzers, allowing them to distinguish the program behaviors distinctive of each testcase by profiling, e.g., the control-flow edges taken during 2 the execution (edge coverage). Ultimately, this choice improves the ability of a fuzzer to find vulnerabilities [27]. Coverage-guided fuzzers instrument program code to update a coverage map (e.g., when the program takes a controlflow edge) that eventually serves as a profile of the testcase execution. Some also keep track of hit counts at coverage points. A relevant aspect of map updates involves collisions, which harm the effectiveness of fuzzing: a fuzzer may overlook program behaviors (and in turn bug discovery opportunities) if the encoding scheme for map updates treats two distinct coverage facts as if they were the same [16]. For instance, the popular AFL fuzzer [25] tracks edge coverage by combining, upon entering a basic block, the index of the current block with the one of its predecessors as curr⊕(prev >> 1). Despite a limited run-time overhead, this hashing scheme incurs frequent collisions [16]. Fuzzers such as AFL++ and LIBFUZZER mitigate this problem by inserting dummy basic blocks to disambiguate critical edges [28] in the control-flow graph. Thanks to this transformation, they can track the original edges by using only the (unique) identifier of the currently executing basic block in the modified program, therefore achieving collision-free edge coverage. B. Points-to Analysis A points-to analysis is a static program analysis that is able to identify the possible targets of a pointer expression [29] by building the points-to set of abstract objects that each expression may reference. An abstract object represents an allocation site and concisely captures all the concrete object instances that the program may create there. Points-to sets are sound, meaning they never miss feasible objects. Sensitivity properties of a specific analysis influence the accuracy of the sets it produces (for the presence of unfeasible abstract objects) and its ability to scale with program complexity. Points-to analyses are nowadays used in several security scenarios (e.g., [30], [31], [32]), also thanks to recent technical advances and state-of-the-art implementations (e.g., [33], [34]) available for mainstream compilers. In this paper, we use a state-of-the-art points-to analysis to study data-flow diversity properties for function call arguments. III. MOTIVATION AND OPEN PROBLEMS We use the code in Listing 1 as a running example to showcase how context-sensitive coverage information can help a fuzzer explore and eventually exploit a faulty program statement that may trigger a bug only when execution reaches it along certain program paths. The program processes input data as a stream of bytes. Segments of type A1 and A2 contain a variable-size payload of 128 to 192 bytes. Payloads for segments of type B can host up to 127 bytes. For all segments, the payload hosts 16 elements stored adjacently. Element sizes are encoded in the input as 16 consecutive bytes prepended to the payload: these will eventually populate the sizes array of the segment structure of the program. Accepted inputs contain one segment of type A1 or A2 followed by one segment of type B; the logic enacting this constraint is not shown in the listing for brevity. 1#define MAX_SEG_SIZE 192 2#define SEG_A12_SIZE 192 3#define SEG_B_SIZE 127 4#define EOSEGM(x) ((x) == 0x23) 5 6struct { 7u16 type, len; 8u8 sizes[16]; 9u8 data[]; 10 } segment; 11 12 segment*cur; 13 14 void parse_seg(char*stream, segment*d) { 15 int n = 0; 16 u8 tmp[MAX_SEG_SIZE]; 17 for (int i=0; i<16; ++i) { 18 d->sizes[i] = *stream++; 19 n += d->sizes[i]; 20 } 21 if (n > MAX_SEG_SIZE) error("too long"); 22 for (int i=0; i < n; ++i) 23 tmp[i] = decode_byte(*stream++, d->type); 24 if (!EOSEGM(tmp[n-1])) error("invalid data"); 25 memcpy(d->data, tmp, n); 26 d->len = n; 27 } 28 29 void get_seg_A1_A2(char*stream, u16 type) { 30 cur = malloc(sizeof(segment) + SEG_A12_SIZE); 31 cur->type = type; 32 parse_seg(stream, cur); 33 } 34 35 void get_seg_B(char*stream) { 36 cur = malloc(sizeof(segment) + SEG_B_SIZE); 37 cur->type = SEG_TYPE_B; 38 parse_seg(stream, cur); 39 } 40 41 void process_segment(char*stream) { 42 u16 type = decode_type(stream); 43 switch(type) { 44 case SEG_TYPE_A1: 45 case SEG_TYPE_A2: 46 get_seg_A1_A2(stream+2, type); break; 47 case SEG_TYPE_B: 48 get_seg_B(stream+2); break; 49 } 50 // [...] parsing logic continues 51 } Listing 1. Motivating example for context-sensitive fuzzing. Function parse_seg contains a heap-overflow bug at line 25. To trigger it, the program state must satisfy two conditions: (i) the input contains a segment of type B with a stated payload size higher than 127 bytes and (ii) the last payload byte, once decoded, corresponds to the segment termination marker. In the early stages of fuzzing, a CGF system will have to generate an input containing a segment of type A1 or A2 through progressive mutations of intermediate testcases. This implies that overly long inputs will be rejected at line 16 and that the segment termination marker should appear as the last decoded symbol in the tmp buffer to overcome the check at line 24. Both checks lead to immediate program termination. Later on, once mutations materialize also a segment of type B in the input, a CGF system based on edge coverage may easily change the 16 bytes related to sizes to have overly 3 long payloads meeting condition (i), but will not retain such a testcase for further mutations because its execution does not cover any new edge (or hit count bucket) unless get_seg_B is being called for the very first time in the campaign. Therefore, the fuzzer can expose the bug only if condition (ii) is already met by chance when generating such a testcase. ANGORA [1] extends edge coverage to distinguish executions of the same branch by different calling contexts (defined in Section I). To this end, it dynamically tracks the calling context as the hash of the current call stack, computed by XOR-ing at each call and return instruction the current hash value with the unique numeric identifier of the involved function. Then, it combines this hash with AFL’s edge hash identifiers, obtaining a feedback where each map entry should ideally capture a distinct context-sensitive edge instance. We call such kind of feedback best-effort. Challenges: We studied the internal fuzzer wastage that comes with best-effort context-sensitivity approaches by analyzing popular programs from fuzzing literature. We consider two standard configurations of the popular AFL++ fuzzer: 1) EDGES, the context-insensitive AFL-style setup with a coverage map of a standard size of 216 entries indexed by edge hashes (Section II-A); 2) LTO, the configuration of AFL++ optimized for collisionfree edge coverage, with unique edge identifiers assigned during link-time optimization. We remark that LTO is currently the most performant setting in the CGF practice. For context-sensitive fuzzing (CONTEXT), we consider the specific configuration of AFL++ for it (used also in, e.g., [15]), which reproduces the working of ANGORA [1] by combining AFL’s edge encoding with the XOR-based call-stack hash described above. We test it in two flavors, using coverage maps of 216 (AFL’s default) and 220 (as in ANGORA) entries. Figure 1 plots statistics collected from a 24-h fuzzing campaign on a subject, libxml2, that is particularly representative of the issues behind current approaches. To conduct the experiment, we use the driver and seeds from FuzzBench commit 81d0ed8 and the default timeout of AFL++. We study the size of the queue, the throughput (completed executions), the number of distinct map entries covered by the testcases, and, where applicable, how many per-entry unique collisions we identified. A collision at a map entry implies that the fuzzer met and erroneously treated at least two distinct contextsensitive edge instances as if they were the same. The resulting data highlight two efficiency issues leading to internal wastage for current context-sensitive fuzzers: we will refer to them as coverage map explosion and queue explosion. To understand coverage map explosion issues, we took a closer look at ANGORA. As acknowledged by the authors [1], their encoding method for context-sensitive edge instances is prone to hash collisions: we identified them on 50.7% of the map entries for the CONTEXT 216 fuzzer configuration. Collisions are undesirable, since they lead to loss of context-sensitivity1and ultimately increase the likelihood of discarding useful testcases [16]. Therefore, ANGORA uses a larger map with 220 entries. While this choice can effectively mitigate collisions (1.2% for CONTEXT 220), it can hamper the Executions / Map entries Fuzzer configuration Queue size sec (large L2) Used / Total Colliding EDGES (216 map) 9 911 609.04 19.86% of 64 KB 9.8% LTO (collision-free) 11 093 572.02 15.59% of 50 KB - CONTEXT (216 map) 33 675 530.10 79.54% of 64 KB 50.7% CONTEXT (220 map) 21 157 84.38 7.21% of 1 MB 1.2% PREDICTIVE 15 455 490.62 9.28% of 256 KB - 00:00 04:00 08:00 12:00 16:00 20:00 24:00 time 3000 4000 5000 6000 7000 8000 edge coverage Fig. 1. Fuzzer’s internal wastage vs. edge coverage over 24 hours with besteffort context-sensitivity. Peak values for degradation are highlighted in bold. throughput of the fuzzer because of higher map access latency (as the map would no longer fit common L2 cache sizes, which can accommodate up to 218 entries) and slower processing at the end of each execution. On standard hardware, we observed induced slowdowns of one order of magnitude. To partially mitigate this coverage map explosion problem, we collected our data on a high-end Intel Xeon Platinum 8160 with a 1-MB L2 cache. Even on such a high-end configuration, the number of completed executions dropped from ˜45 millions to ˜7 millions. Such low fuzzing throughput ultimately resulted in much poorer (context-insensitive) edge coverage after 24 hours than any other configuration. The second problem, queue explosion, is well-understood in literature: as observed in [10], while retaining more seeds offers “stepping stones for more meaningful mutations that lead to final crashes, [retaining] too many of them would hurt the fuzzing performance” as the differences between most such seeds are likely so tiny that would hardly result in new bugs. For the CONTEXT 216 configuration, the queue size grows significantly (from 9 911 to 33 675 retained testcases), but the edge coverage achieved over time is appreciably lower than EDGES (where 9.8% of map entries see collisions) and much lower than the one obtainable with a collision-free LTO solution. The problem is less noticeable in the CONTEXT 220 configuration (although the queue size still doubles to 21 157), but only because the much lower throughput (and edge coverage) masks the queue explosion problem. Summarizing, our analysis shows that current contextsensitive strategies (CONTEXT) struggle to achieve good precision without introducing internal wastage due to explosion issues: by allowing more collisions, they lose context-sensitivity (at the cost of discarding important testcases), whereas by reducing collisions, they overly discriminate contexts (at the cost of retaining too many testcases and trashing the fuzzing 1And, even worse, weaker path sensitivity than a context-insensitive baseline, since a single hash is used for calling contexts and edges. Therefore, one may suggest combining a collision-free edge ID with a hash of the context. Unfortunately, this method would be much poorer than the one of ANGORA due to the limited entropy of edge identifiers, which would be completely marginal compared to the one of contexts. 4 throughput). The performance of CONTEXT falls behind by an appreciable margin not only the collision-free edge coverage setting of LTO, but even EDGES. Best-effort context-sensitivity was similarly outclassed for bug finding capabilities in the full evaluation that we will illustrate in Section VI-A (Table III). The key reason why this is essentially an impossible needle to thread is that prior strategies are entirely blind to which of the many distinct contexts are important to capture in order to retain interesting testcases. As an example, libxml2 can see potentially up to 16-million distinct contexts originating from its main; more in general, their number is often exponentially large w.r.t. the number of program functions [11]. Our Approach: In this paper, we explore a selective angle to deploy context-sensitive fuzzing in a more effective way: we augment only certain program regions with contextual information, devising then a novel predictive solution to statically identify regions that are likely to benefit from contextsensitive profiles for the edges traversed during execution. As a concrete instance of this strategy, we favor call sites that see a higher diversity for the incoming data-flow at call arguments. For our example, such a predictor would recognize that the segment object flowing into the buggy function comes from different allocation sites depending on the caller. Then, as we study only data-flows for function arguments across different call sites, instead of the full calling-context we can rely on a much lighter context abstraction that discriminates only the identity of the caller function. Our approach (PREDICTIVE) augments an LTO-style map with entries for collision-free context-sensitive profiles of edges from selected regions. For the rest of the code, we use collision-free context-insensitive edge tracking as LTO does. We bound our selection so that the map fits standard L2 caches. Ultimately, all these choices allow us to hit the “sweet spot” between insufficient and excessive context-sensitivity, uncovering more bugs in well-known benchmarks with only a moderate impact on the fuzzer’s internal wastage. IV. PREDICTIVE CONTEXT-SENSITIVITY This section presents the three main pillars of our approach: 1) a collision-free method to encode context-sensitivity; 2) a selective approach to restrict context-sensitive fuzzing to program regions of interest for the sake of scalability; 3) a data-flow analysis to predict regions likely to benefit from having been selected when a coverage-guided exploration reaches them. We produce a transformed program containing contextsensitive instances of control-flow edges, added according to a user-specified budget and in a cost-effective manner. Existing CGF systems can test it without requiring any changes. A. Function Cloning A way to turn a context-insensitive program analysis into a context-sensitive one is to expose to the analysis a separate instance (clone) of the code unit of interest at each different encountered context. For instance, if contextual information is represented only by the caller of a function, the analysis may produce separate results for the unique clones of the callee devised for each possible caller. Such an approach has two main advantages: it offers backward compatibility for existing fuzzing instrumentation solutions and can accommodate different context-sensitivity definitions. Let us consider calling-context information, initially on recursion-free programs for simplicity. One may disambiguate the calling context for a specific function by taking the call graph of the program and, for each maximal acyclic path that reaches the function, introducing a clone at every caller-callee pair on the backward walk to its root node. In this way, whenever the analysis reaches a clone of the original function, the path from the root function to it is unique. Therefore, the identity of the clone is sufficient to precisely determine the invocation context. To handle recursion, we look for functions involved in direct and indirect recursion by analyzing the strongly connected components (SCCs) of the call graph [35]. During path analysis and cloning, we treat each SCC as a single node without a self-edge. This allows us to retain precise contextual information before and after entering recursive sequences (which in general may be unbounded in depth), treating only the recursive parts in a context-insensitive manner. For a coverage-guided fuzzer, we need a way to discriminate different clones of a function of interest that is both cheap to maintain or retrieve at run-time and composable with other encoding techniques in a space-efficient and collision-free way. An elegant and effective way to maintain context-sensitivity for program points is to manipulate the code of the program and add concrete copies of the involved functions. This choice brings several advantages. By exposing contextual information through new code locations, we offload the collision problem to the feedback mechanism already in use by the coverageguided fuzzer. With edge coverage, existing collision-free edge encodings will just assign unique (context-sensitive) edge identifiers to code from clones. Therefore, function cloning effectively solves the collision problem we saw in Section III. Furthermore, when deploying context-sensitivity in the selective flavor that we present in the next section, another advantage of our scheme is that it brings virtually no run-time overhead for tracking and retrieving the context, as we trade this efficiency for a modest increase in program size. Let us use as running example our program from Listing 1. The relevant caller-callee pairs are (get_seg_A1_A2, parse_seg) and (get_seg_B,parse_seg). For simplicity, we pick the second for specialization as we know that such path can expose the bug at line 25. Our cloning primitive adds to the program a duplicate of parse_seg, which we call __clone_ps, and patches the call at line 38 to invoke it in lieu of the original function. When a coverage-guided fuzzer executes the augmented program, the branch originally at line 22 will benefit from separate coverage information when reached via get_seg_B, allowing the fuzzer to treat it as an interesting testcase (and, in more detail, to become sensitive to the different payload lengths that its hit count may capture). By choosing to work on call sites, we can virtually model any notion of context-sensitivity based on tracking portions of 5 TABLE I. CODE FEATURES OF FUZZBENCH SUBJECTS. Benchmark Type Edges Functions Call sites Calling contexts ffmpeg C, some C++ 716 046 5 314 44 500 8 014 021 file C, some C++ 15 986 250 985 19 217 grok C++ 94 092 535 2 234 11 025 libarchive C 67 096 866 4 377 27 984 301 libgit2 C 107 785 1 718 5 467 3 024 953 libhevc C 119 646 197 853 125 907 libhtp C++ 11 203 181 706 6 718 libxml2 C 104 351 1 147 6 708 44 652 617 060 matio C 24 112 300 1 795 2 793 663 muparser C++ 14 007 103 483 6 120 ndpi C 49 216 355 1 991 10 507 njs C 57 402 588 3 818 12 671 908 openh264 C++ 78 819 384 1638 28 441 stb C/C++ 11 861 144 881 11 501 usrsctp C 96 225 405 4 303 3 294 931 527 zstd C/C++ 38 863 848 5 027 140 141 the call stack: a global policy will ensure that each cloning action draws out a piece of the desired portion. The call sites present within an added clone may be in turn disambiguated for context-sensitivity by applying cloning recursively. B. The Need for Selective Sensitivity While cloning can expose context-sensitivity information for program points in a “fuzzer-friendly” manner, it does not help us get around the path explosion problem that comes with calling contexts (Section III). As evidence of this issue, Table I reports statistics collected for programs from the FuzzBench test suite that we later use for evaluation purposes (Section VI). As a fuzzing harness often tests only a relevant subset of a code base, we collect the figures after removing all the functions unreachable according to LLVM’s static analyses. In the edges column, we report the number of basic blocks that a collision-free edge coverage scheme instruments after breaking all the critical edges in program functions [26]. The last three columns represent, respectively, the number of nodes, edges, and acyclic paths in the call graph. For many subjects, the number of contexts appears intractable for any practical collision-free attempt (we will return to this in Section VII), including cloning. Even when the contexts are not millions or more, the number of “contextsensitive” edges to disambiguate may still increase dramatically when the call sites are many, requiring in turn (inefficient) large coverage maps for their (collision-free) tracking. However, we argue that a much more effective approach is possible: adding context-sensitivity only to selected program portions. Algorithm 1 presents the high-level workflow: we process the call graph at call-site granularity and follow a prioritization policy to pick individual call sites for cloning. As a baseline, we consider a random policy that prioritizes them uniformly at random. We surveyed static analysis literature for contextual information representation in the programming language community (e.g., [36], [37], [38]) and derived three policies that approximate their core ideas by performing a visit of the call graph and assigning priorities (captured by visit order) according to topological properties: •top: assigns higher priority to call sites from nodes closer to the root(s) of the call graph, progressively exposing the context in a top-down fashion as in [37]. Algorithm 1: Priority-based Cloning function CloneByPriority(program, budget) callsites ←Sf∈program GetAllCallsites(f) priorities ←GetPriorities(callsites) pqueue ←PriorityQueue(callsites, priorities) while program.size <budget do callsite ←pqueue.pop() target ←GetCallTarget(callsite) new target ←CloneFunction(target) SetCallTarget(callsite, new target) new callsites ←GetAllCallsites(new target) new priorities ←GetPriorities(new callsites) pqueue.push_all(new callsites, new priorities) •bottom: assigns higher priority to call sites closer to leaves. This policy progressively exposes the last entries on the call stack as in call strings [36], which in some domains can effectively replace the full calling context. •uniform: treats every call site with the same priority. It resembles [38] and mixes the effects of the other policies, exposing the top or bottom call-stack entries leading to a node depending on its proximity to a root node or a leaf. In preliminary tests2, these policies exposed a few more bugs than standard edge coverage (thus already outclassing best-effort context-sensitive solutions) and did not experience any evident internal wastage. However, their apparent benefits were modest and also difficult to understand when compared to random, as the policies often resulted in similar performance. Eventually, we looked at these results retrospectively. Policies of this kind are well suited for static program analysis scenarios, where partial contextual information may still expose to an analysis sufficient information to reason on all the possible refined program states and, in turn, the user can measure the improvement (if any) in the precision of the returned answers. Instead, coverage-guided fuzzing is a dynamic analysis technique based on a lightweight abstraction of program state: no direct static measurement of the benefits of context-sensitivity seems possible. To effectively take advantage of any added context-sensitivity (which can be available only in a limited quantity), we concluded that we need a predictor for program portions that may practically benefit from it during fuzzing. C. Data Flow-based Prediction A pivotal element of our proposal is a prediction-based policy that prioritizes for cloning those call sites where the callee sees higher diversity in the incoming data-flow compared to other uses of the same function in the rest of the program. Specifically, we favor cases where the abstract objects potentially incoming as arguments for the callee function are more peculiar (i.e., less frequently met) w.r.t. other call sites where the function is invoked. Our hypothesis is that such diversity can be a promising indicator that the program may enter “less common” internal states along these execution contexts. Prioritizing such contexts for cloning and, in turn, retaining testcases that hit them during execution may allow the fuzzer 2The results for top (shown as ‘bfs’) and uniform can be found at https: //www.fuzzbench.com/reports/experimental/2021-05-25-cloning/index.html, whereas for random and bottom at https://www.fuzzbench.com/reports/ experimental/2021-07-09-cloning/index.html. 6 to delve more pervasively into these behaviors, both locally at the callee and in any subsequently reached code that is affected by the data flow. As we will explore in Section VI, the analysis we present below turns out to be a good predictor in practice for eliciting profitable states and uncovering new bugs. We argue that function arguments are a natural way for programs to orchestrate data-flows through their code units. Therefore, we study the invocation of every function at its different call sites in the call graph and analyze what values are possible for each of its arguments. We prioritize cloning those call sites that pass as arguments abstract objects that never or rarely appear at other call sites. In other words, we find it reasonable to differentiate those call sites (i.e., to introduce clones for callees) that see peculiar incoming objects, while we predict a lower benefit from doing so at call sites that see objects that recur at other places too. For example, for a function with two call sites, we have little interest in cloning it if the two pass similar objects; instead, when the two pass very different objects, we find it reasonable to differentiate them for the fuzzer to explore both. In this paper, we focus on pointer-type arguments and use an off-the-shelf analysis to build points-to sets (Section II-B), obtaining the possible abstract objects that an argument may reference when passed at a call site. We compute the prediction to use as priority value in Algorithm 1 as follows. Let the target function be in use at ncall sites in the call graph3and Obe the set of all abstract objects that may be passed via its arguments at the current call site. The priority pof the call site is: p=1 n×X o∈O (n−no) where nois the number of call sites for fwhere object o may appear in any of its arguments. As we said earlier, we seek to favor the diversity of the incoming data-flow: an object othat does not appear at other call sites for the target will contribute with a n−1addend, whereas an object that may appear at all call sites will give a zero addend. Eventually, the edge coverage collected for the clones exposes the incoming data-flow diversity to the fuzzer, favoring a more pervasive exploration of the underlying program states. D. Discussion With our approach, we propose to overcome the precision and efficiency limitations of current context-sensitive fuzzing flavors by augmenting only selected program points with contextual information. Our data flow-driven prioritization policy shows promise in practice, retaining for further mutations inputs that eventually led us to discover new (or more) bugs. In our approach, we chose to focus on pointers because pointer diversity always leads to data-flow deviations, while non-pointer diversity does not necessarily do so. We also believe memory errors to be more likely in presence of data-flow deviations, and fuzzers are notoriously effective in exposing them [39] (especially in combination with sanitizers [40]). An interesting follow-up may be to study what non-pointer variables in a program can lead to “helpful” diversity and, in turn, to what extent. In this scenario, a practical aspect to account for is the precision of value analysis techniques for non-pointers (e.g., value range analysis [41] on integer arguments), as too coarse results could mask real diversity. Compiler-based instrumentation is a natural way to deploy our approach. For fuzzing programs available only as binaries, binary rewriting techniques or a modified runtime can intercept and divert call sites. However, analyzing pointer arguments may be challenging as, among others, it would need to recover object locations. We leave this investigation to future work. V. IMPLEMENTATION We implement our techniques as a set of analysis and transformation passes (˜2k C++ LOC) for the intermediate representation (IR) of the LLVM compiler, a popular choice for fuzzers that instrument source code. We operate on a link time-ready whole-program IR file that the GLLVM helper [42] obtains for the uninstrumented program. We produce a transformed IR file and feed an off-the-shelf fuzzer with it. As for evaluation purposes we opted for the state-of-theart AFL++ [14] fuzzer (version 3.15a), we devise a simple Python helper that automates the compilation process and also the insertion of sanitization machinery. Our cloning pass has provisions to correctly handle the instrumentation introduced by popular sanitizers such as ASAN and UBSAN, which insert tripwires that help fuzzers expose silent bugs [43]. For sizing purposes, we implement an analysis to estimate, for each cloning decision, the coverage map size increase due to the unique identifiers that the collision-free edge coverage encoding of AFL++ would introduce for the clone. We simulate a cloning action and reuse AFL++’s instrumentation algorithm to count the edge entries the clone would need in the map. Good fuzzing practices [1] recommend map sizes no larger than standard L2 cache sizes (i.e., 256 KB), whereas overly large maps can be detrimental for performance even on favorable hardware, as we saw in Section III. Once we set a maximum desirable map size, we can use as residual budget for cloning the “free” map entries after we accounted for the edges currently in the program and, potentially, add clones up to its exhaustion. Our evaluation sets a budget of 256 KB, which can host up to 218 map entries. In practice, this tuning choice allowed our fuzzers to discriminate and pervasively delve into new program states without incurring internal wastage. To analyze pointer arguments at call sites, we use the stateof-the-art points-to analysis FlowSensitive from the popular SVF framework [33]. Among the analyses implemented in SVF, it is expected to bring the most accurate points-to sets for general code, as it carries an Andersen-style analysis enhanced with fieldand flow-sensitivity (while it remains arrayand context-insensitive for the sake of scalability). As an implementation refinement, we attempt to lower the priority of a recurrent class of uninteresting call-site targets: error-handling functions that lead to program termination. In the programs we study, many such functions see a very high number of callers and, consequently, an inherently diverse incoming data-flow at various call sites. We opt for lowering the priority of the call sites whose target is a function called by at least 25% (a value set empirically) of all functions in 3We remark that we compute priority values on the unmodified program. 7 the program. We have verified that this choice affected only error-handling functions in our tests. Our prototype can also attempt to reason on paths involving indirect-call sites, by promoting each indirect call into a conditional selection of direct calls to plausible targets [44], [45], [46]. However, this is disabled by default since precise reasoning on indirect calls is notoriously hard. With a static approach, the precision of the analysis for building call-target sets is crucial [47]: in most of the cases we analyzed using points-to analysis, the size of the resulting sets led to path explosion. Nonetheless, as we will see throughout Section VI, the effects of our techniques allowed us to expose bugs and report security vulnerabilities in heterogeneous programs written in C/C++ and object oriented-style C. As future work, we plan to explore the potential benefits of profile-guided indirect call promotion [44] for these subjects, for instance using testcases from a short fuzzing session, as well as of recent advances in static type-based dependence analysis techniques [48]. VI. EVALUATION We study the performance of predictive context-sensitive fuzzing using the FuzzBench testing infrastructure. Popular in academia and industry since its release in 2020, FuzzBench has become a de-facto standard benchmarking platform and program collection for fuzzing research. FuzzBench targets realworld programs, pinning specific versions for reproducibility and result validation [17]. We select the ‘type: bug‘ configuration of FuzzBench, a choice made also in other recent bug-oriented studies [49], [50], [51]. We study different dimensions of our approach for the following research questions: RQ1: Can we outperform the state of the art in bug finding? Can we find vulnerabilities that existing approaches overlook? RQ2: To what extent do we induce internal wastage, if any? RQ3: What burden do we place on the compilation pipeline? Atop the AFL++ [14] fuzzer, we test these configurations: •context:best-effort context-sensitivity as evaluation baseline, using the implementation available in AFL++ that reproduces what proposed in ANGORA [1]; •lto: collision-free edge coverage boosted with link-time optimization. It is the the most effective setting available for context-insensitive coverage-guided fuzzers [14] and serves as a reference point to show (in further detail than in Section III) the internal wastage effects of context; •predictive: the approach we propose in this paper; •random: an uninformed prioritization policy serving as a baseline for selective context-sensitivity; For context, we use a coverage map of 218 entries to fill the L2 cache (256 KB) typical of most machines, including the FuzzBench cloud infrastructure on which we ran our tests. We do not evaluate larger sizes as we experienced significant internal wastage for the reasons discussed in Section III. We also remark that context reproduces only ANGORA’s context-sensitive edge coverage encoding: that is, it does not perform the taint tracking or gradient-descent based search that are other distinctive features of ANGORA. The reason for it is that we want to stress context-sensitivity alone (which other fuzzers, like WEIZZ [15], already use): the independent contributions of such features would only pollute the analysis. For lto, the number of instrumented edges in each program (Table I) determines the map size. For predictive and random, we use the largest cloning budget value such that the resulting map still fits4an L2 cache of 256 KB (i.e., up to 218 entries). We could obtain a compilable whole-program IR file (Section V) for 16 of the 22 benchmarks from FuzzBench. Bugs and missing features in the GLLVM [42] helper5and other compilation errors unrelated to our techniques prevented us from testing the other programs. The link-time primitives that recently became available in LLVM may help for them for future implementation extensions. For all the fuzzer configurations that we study, we instrument each whole-program IR file with the ASAN and UBSAN sanitizers [52] to expose common classes of silent bugs. All the fuzzer configurations that we test work on binaries built with -O3 optimization level. A. RQ1: Effectiveness in Bug Finding To evaluate the bug finding capabilities of our four fuzzer configurations (hereafter fuzzers for brevity), we initially rely on the infrastructure of FuzzBench to count unique bugs via automatic crash deduplication based on unique stack traces. As we run the fuzzers on its cloud platform, each configurationbenchmark pair sees 20 trials of 23 hours each. 1) General Trends: Following standard practices [53], we reason on the median values over all trials to mitigate the well-known effects of randomness in fuzzing. Figure 2 reports the boxplots for each benchmark showing the number of bugs found by each fuzzer. For each benchmark, the fuzzers appear in the ranking order given by their median number of bugs found across the trials and using their maximum number to break ties when necessary. To compare the effectiveness of each fuzzer, we first consider the average score metric from FuzzBench. For each benchmark, the score of a fuzzer in a ‘type: bug‘ campaign is given by expressing the median number of bugs6it finds as the percentage of the median number of bugs from the fuzzer that performed best on that benchmark. The final cross-benchmark average score for a fuzzer, shown in Table II, is the average of individual benchmark scores and mitigates distortion effects due to benchmarks having a different number of total bugs [17]. We note that cross-benchmark average scores reflect the relative performance of each fuzzer in one experiment setting: therefore, they do not generalize for comparisons with other selections of fuzzers and/or programs. The best-performing fuzzer is the one using our predictive policy: predictive obtains the highest score with an 11.84 net difference with lto, which in turn largely outperforms 4Except for ffmpeg, for which the number of unique edges requires more than 218 entries already with lto: therefore, we set the budget for it to the nearest feasible multiple of two (768 KB). 5Two practical limitations we observed with GLLVM are i) its incorrect handling of source files that a build system may supply to a linker (while this may seem an unorthodox behavior, both clang and gcc allow it; we reported the issue to its developers) and ii) when it invokes llvm-link to merge the bitcode files, the IR elements for indirect functions (GNU IFUNC) are lost. 6Coverage-centric experiments use the median code coverage instead. 8 B C A D 0 1 2 3 4 5 6 7 8 bugs ffmpeg_ffmpeg_demuxer_fuzzer B A D C 0.0 0.5 1.0 1.5 2.0 2.5 3.0 bugs file_magic_fuzzer B D C A 0 1 2 3 4 5 6 bugs grok_grk_decompress_fuzzer C A B D 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 bugs libarchive_libarchive_fuzzer A B C D 1.00 1.25 1.50 1.75 2.00 2.25 2.50 2.75 3.00 bugs libgit2_objects_fuzzer A B C D 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 bugs libhevc_hevc_dec_fuzzer D C B A 0 1 2 3 4 5 6 bugs libhtp_fuzz_htp B C D A 2.5 5.0 7.5 10.0 12.5 15.0 17.5 bugs libxml2_libxml2_xml_reader_for_file_fuzzer A D B C 12 14 16 18 20 22 24 26 bugs matio_matio_fuzzer B D A C 0.0 0.2 0.4 0.6 0.8 1.0 bugs muparser_set_eval_fuzzer B C D A 2 4 6 8 10 bugs ndpi_fuzz_ndpi_reader B C D A 0.0 0.2 0.4 0.6 0.8 1.0 bugs njs_njs_process_script_fuzzer B C D A 3 4 5 6 7 8 bugs openh264_decoder_fuzzer B D C A 7 8 9 10 11 12 13 14 bugs stb_stbi_read_fuzzer B C D A 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 bugs zstd_stream_decompress A: context B: predictive C: lto D: random Fig. 2. Boxplots with mean value (4) and raw data points (·) for bugs uncovered in the FuzzBench programs across 20 trials. Fuzzers are ordered by hmedian, maximuminumber of bugs found. We leave out usrsctp as no fuzzer found bugs for it. TABLE II. CROSS-BENCHMARK AVERAGE SCORE FROM FUZZBENCH. Fuzzer configuration FuzzBench score predictive 94.14 random 82.98 lto 82.30 context 63.42 context (and even random does too). The predictive fuzzer will similarly stand out also in the analysis of individual bugs that we provide in the next section. As we move to the other fuzzers, we remark how the lto state-of-the-art configuration is a strong baseline. In addition to collision-free encoding of edges, which outperforms classic (collision-prone) edge tracking and refinements [16], it benefits from link-time optimizations such as additional inlining. For instance, LLVM may inline a short-sized callee at a call site for performance, incidentally providing some contextsensitivity [54] as the inlined edge instances get new identifiers. However, an optimizing compiler follows performancebased (rather than context sensitivity-based) inlining policies. When our data flow-based prediction mechanism drives the cloning decisions, we can observe a significantly larger number of bugs found for the subjects considered in this evaluation. On the contrary, the best-effort context-sensitivity of context suffers from a combination of the problems analyzed in Section III. While we defer a detailed discussion of internal wastage effects to Section VI-B, collisions hamper its ability to distinguish, and thus explore, useful program states that not only predictive, but even lto can often retain in its queue. Combined with the time spent analyzing likely uninteresting testcases that pollute its queue and the lower endto-end throughput (Section VI-B), context ranks on average as the least effective fuzzer configuration in our tests. 2) In-depth Analysis: We now qualitatively analyze the unique bugs identified by the fuzzers predictive (125), lto (112), and context (102). We leave out random (110) for brevity. We start by discussing the left part of Figure 3, which compares the unique bugs found by predictive against the lto and context fuzzers, which embody the state of the art in context-insensitive and sensitive fuzzing. Table III lists how many bugs we found on each subject. Due to internal wastage effects, context missed 27 of the unique bugs that both predictive and lto could find. Of the 102 unique bugs context found, 74 were found by both the others, and 82 by predictive. As for the 18 bugs found only by context, 15 are from matio—on which, as we discuss next, our predictive strategies are less effective. On the other hand, predictive revealed twice as many (43) unique bugs missed by context, found in 9 of the 16 subjects we study, and 23 more bugs in total (+22.55%). Finally, the two fuzzers find an identical number of bugs in 5 subjects. We conclude that our approach significantly outperforms the state of the art in context-sensitive fuzzing. Comparing the counts for predictive and lto, the former found 13 more bugs in total (+11.6%). Also, 24 of its 125 bugs (19.2% of the total) were missed by lto; this amount equals the 21.4% of the lto count. Of the 112 bugs found by lto, our approach missed 11 bugs (10.7% of the lto count). Hence, our approach not only significantly outperforms best-effort context-sensitivity, but does not show appreciable internal wastage compared to lto. With more and different bugs found, we may argue that our approach has benefited the exploitation work of the fuzzer (Section III). Testcase Dissection: To better understand these results and how refined contextual information may be behind the bugs that only predictive found, we analyze several char9 [42] I. A. Mason, “Whole Program LLVM in Go,” https://github.com/ SRI-CSL/gllvm, 2021, [Online; accessed 2 Sep. 2021]. [43] S. Dinesh, N. Burow, D. Xu, and M. Payer, “Retrowrite: Statically instrumenting cots binaries for fuzzing and sanitization,” in 2020 IEEE Symposium on Security and Privacy (SP), 2020, pp. 1497–1511. [44] I. Baev and Q. I. Center, “Profile-based indirect call promotion,” in LLVM Developers Meeting, Oct, 2015. [45] N. Amit, F. Jacobs, and M. Wei, “Jumpswitches: Restoring the performance of indirect branches in the era of spectre,” in 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Jul. 2019, pp. 285–300. [Online]. Available: https://www.usenix.org/conference/atc19/presentation/amit [46] V. Duta, C. Giuffrida, H. Bos, and E. van der Kouwe, “Pibe: Practical kernel control-flow hardening with profile-guided indirect branch elimination,” in Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ser. ASPLOS 2021. ACM, 2021, p. 743–757. [Online]. Available: https://doi.org/10.1145/3445814.3446740 [47] P. Biswas, N. Burow, and M. Payer, “Code specialization through dynamic feature observation,” in Proceedings of the Eleventh ACM Conference on Data and Application Security and Privacy, ser. CODASPY ’21. ACM, 2021, p. 257–268. [Online]. Available: https://doi.org/10.1145/3422337.3447844 [48] K. Lu, “Practical program modularization with type-based dependence analysis,” in 2023 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, may 2023, pp. 1610–1624. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/SP46215.2023.00092 [49] A. Mantovani, A. Fioraldi, and D. Balzarotti, “Fuzzing with data dependency information,” in 7th IEEE European Symposium on Security and Privacy, ser. EuroS&P ’22, IEEE, Ed., 2022. [50] A. Fioraldi, A. Mantovani, D. Maier, and D. Balzarotti, “Dissecting American Fuzzy Lop: A FuzzBench evaluation,” ACM Trans. Softw. Eng. Methodol., vol. 32, no. 2, mar 2023. [Online]. Available: https://doi.org/10.1145/3580596 [51] D. Liu, J. Metzman, M. B¨ ohme, O. Chang, and A. Arya, “SBFT Tool Competition 2023 - Fuzzing Track,” in 2023 IEEE/ACM International Workshop on Search-Based and Fuzz Testing (SBFT), 2023, pp. 51–54. [52] D. Song, J. Lettner, P. Rajasekaran, Y. Na, S. Volckaert, P. Larsen, and M. Franz, “SoK: Sanitizing for security,” in 2019 IEEE Symposium on Security and Privacy (SP), 2019, pp. 1275–1295. [53] G. Klees, A. Ruef, B. Cooper, S. Wei, and M. Hicks, “Evaluating fuzz testing,” in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’18. ACM, 2018, pp. 2123–2138. [Online]. Available: https://doi.org/10.1145/3243734. 3243804 [54] X. Wang, N. Zeldovich, M. F. Kaashoek, and A. Solar-Lezama, “Towards optimization-safe systems: Analyzing the impact of undefined behavior,” in Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, ser. SOSP ’13. ACM, 2013, p. 260–275. [Online]. Available: https://doi.org/10.1145/2517349.2522728 [55] C. Salls, C. Jindal, J. Corina, C. Kruegel, and G. Vigna, “Token-Level fuzzing,” in 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, Aug. 2021, pp. 2795–2809. [Online]. Available: https://www.usenix.org/conference/usenixsecurity21/presentation/salls [56] E. G¨ uler, P. G¨ orz, E. Geretto, A. Jemmett, S. ¨ Osterlund, H. Bos, C. Giuffrida, and T. Holz, “Cupid: Automatic fuzzer selection for collaborative fuzzing,” in Annual Computer Security Applications Conference, ser. ACSAC ’20. ACM, 2020, pp. 360–372. [Online]. Available: https://doi.org/10.1145/3427228.3427266 [57] Y. Chen, Y. Jiang, F. Ma, J. Liang, M. Wang, C. Zhou, X. Jiao, and Z. Su, “EnFuzz: Ensemble fuzzing with seed synchronization among diverse fuzzers,” in 28th USENIX Security Symposium (USENIX Security 19). USENIX Association, Aug. 2019, pp. 1967–1983. [Online]. Available: https://www.usenix.org/conference/ usenixsecurity19/presentation/chen-yuanliang [58] A. Fioraldi, D. C. D’Elia, and D. Balzarotti, “The use of likely invariants as feedback for fuzzers,” in 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, Aug. 2021, pp. 2829–2846. [Online]. Available: https://www.usenix.org/ conference/usenixsecurity21/presentation/fioraldi [59] “Circumventing Fuzzing Roadblocks with Compiler Transformations,” https://lafintel.wordpress.com/2016/08/15/ circumventing-fuzzing-roadblocks-with-compiler-transformations/, 2016, [Online; accessed 28 Mar. 2023]. [60] M. B¨ ohme, L. Szekeres, and J. Metzman, “On the reliability of coverage-based fuzzer benchmarking,” in Proceedings of the 44th International Conference on Software Engineering, ser. ICSE ’22. ACM, 2022, pp. 1621–1633. [Online]. Available: https: //doi.org/10.1145/3510003.3510230 [61] S. Yan, C. Wu, H. Li, W. Shao, and C. Jia, “Pathafl: Pathcoverage assisted fuzzing,” in Proceedings of the 15th ACM Asia Conference on Computer and Communications Security, ser. ASIA CCS ’20. ACM, 2020, pp. 598–609. [Online]. Available: https://doi.org/10.1145/3320269.3384736 [62] R. Padhye, C. Lemieux, K. Sen, L. Simon, and H. Vijayakumar, “FuzzFactory: Domain-specific fuzzing with waypoints,” Proc. ACM Program. Lang., vol. 3, no. OOPSLA, Oct. 2019. [Online]. Available: https://doi.org/10.1145/3360600 [63] A. Herrera, M. Payer, and A. Hosking, “datAFLow: Towards a data-flow-guided fuzzer,” in 1st International Fuzzing Workshop, ser. FUZZING ’22, I. Society, Ed., 2022. [64] G. Ammons, T. Ball, and J. R. Larus, “Exploiting hardware performance counters with flow and context sensitive profiling,” in Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation, ser. PLDI ’97. ACM, 1997, pp. 85–96. [Online]. Available: https://doi.org/10.1145/258915.258924 [65] W. N. Sumner, Y. Zheng, D. Weeratunge, and X. Zhang, “Precise calling context encoding,” in Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1, ser. ICSE ’10. ACM, 2010, pp. 525–534. [Online]. Available: https://doi.org/10.1145/1806799.1806875 [66] M. D. Bond and K. S. McKinley, “Probabilistic calling context,” in Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, ser. OOPSLA ’07. ACM, 2007, pp. 97–112. [Online]. Available: https://doi.org/10.1145/1297027.1297035 [67] D. C. D’Elia, C. Demetrescu, and I. Finocchi, “Mining hot calling contexts in small space,” Software: Practice and Experience, vol. 46, no. 8, pp. 1131–1152, 2016. [Online]. Available: https: //doi.org/10.1002/spe.2348 [68] Y. Li, T. Tan, A. Møller, and Y. Smaragdakis, “A principled approach to selective context sensitivity for pointer analysis,” ACM Trans. Program. Lang. Syst., vol. 42, no. 2, may 2020. [Online]. Available: https://doi.org/10.1145/3381915 [69] Y. Smaragdakis, G. Kastrinis, and G. Balatsouras, “Introspective analysis: Context-sensitivity, across the board,” in Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLDI ’14. ACM, 2014, pp. 485–495. [Online]. Available: https://doi.org/10.1145/2594291.2594320 [70] Z.-M. Jiang, J.-J. Bai, K. Lu, and S.-M. Hu, “Fuzzing error handling code using Context-Sensitive software fault injection,” in 29th USENIX Security Symposium (USENIX Security 20). USENIX Association, Aug. 2020, pp. 2595–2612. [Online]. Available: https://www.usenix.org/conference/usenixsecurity20/presentation/jiang [71] Z. Jiang, J. Bai, K. Lu, and S. Hu, “Context-sensitive and directional concurrency fuzzing for data-race detection,” in 29th Annual Network and Distributed System Security Symposium, NDSS 2022, San Diego, California, USA, April 24-28, 2022. The Internet Society, 2022. [72] P. Godefroid, N. Klarlund, and K. Sen, “Dart: Directed automated random testing,” in Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLDI ’05. ACM, 2005, pp. 213–223. [Online]. Available: https://doi.org/10.1145/1065010.1065036 [73] V. Ganesh, T. Leek, and M. Rinard, “Taint-based directed whitebox fuzzing,” in 2009 IEEE 31st International Conference on Software Engineering, 2009, pp. 474–484. [74] P. Borrello, D. C. D’Elia, L. Querzoni, and C. Giuffrida, “Constantine: Automatic side-channel resistance using efficient control and data flow linearization,” in Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’21. ACM, 2021. 16 [75] K. Bhat, E. van der Kouwe, H. Bos, and C. Giuffrida, “Probeguard: Mitigating probing attacks through reactive program transformations,” in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, ser. ASPLOS ’19. ACM, 2019, pp. 545–558. [Online]. Available: https://doi.org/10.1145/3297858.3304073 [76] C. Tice, T. Roeder, P. Collingbourne, S. Checkoway, ´ U. Erlingsson, L. Lozano, and G. Pike, “Enforcing Forward-Edge Control-Flow Integrity in GCC and LLVM,” in Proceedings of the USENIX Security Symposium (USENIX Security), 2014. [77] Clang, “LLVM’s Control Flow Integrity,” 2018, [Online; accessed 28 Mar. 2023]. [Online]. Available: https://clang.llvm.org/docs/ ControlFlowIntegrity.html [78] V. van der Veen, D. Andriesse, E. G¨ oktas¸, B. Gras, L. Sambuc, A. Slowinska, H. Bos, and C. Giuffrida, “Practical context-sensitive cfi,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’15. ACM, 2015, p. 927–940. [Online]. Available: https://doi.org/10.1145/2810103.2813673 APPENDIX A ADDITIONAL BUG ANALYSIS RESULTS The CVE identifiers for the security issues in the FuzzBench programs mentioned in Section VI-A3 are the following: CVE-2022-28041, CVE-2022-28042, and CVE-202228048 for stb, CVE-2022-1475 for ffmpeg, CVE-20221515 for matio, and CVE-2022-28049 for njs. This appendix includes four tables (Table VI, VII, VIII, and IX) that complement the bug counts reported in Table III and the inclusion relations of Figure 3 with more detailed comparisons based on bug identity at each benchmark. Benchmark Only predictive Both Only context ffmpeg 5 6 0 file 1 2 1 grok 5 2 0 libarchive 0 0 0 libgit2 0 3 0 libhevc 0 1 1 libhtp 0 5 0 libxml2 19 3 0 matio 0 26 17 muparser 1 0 0 ndp 6 11 1 njs 1 0 0 openh264 1 7 0 stb 3 15 0 usrsctp 0 0 0 zstd 1 1 0 TABLE VI. INCLUSION RELATIONS FOR BUGS FOUND BY predictive AND lto IN THE FUZZBENCH EXPERIMENTS (CF.LEFT PART OF FIGURE 3). Benchmark Only predictive Both Only lto ffmpeg 2 9 1 file 2 1 0 grok 1 6 0 libarchive 0 0 2 libgit2 0 3 0 libhevc 0 1 1 libhtp 0 5 1 libxml2 6 16 0 matio 2 24 2 muparser 1 0 0 ndp 2 15 3 njs 0 1 0 openh264 1 7 1 stb 7 11 0 usrsctp 0 0 0 zstd 0 2 0 TABLE VII. INCLUSION RELATIONS FOR BUGS FOUND BY predictive AND lto IN THE FUZZBENCH EXPERIMENTS (CF.LEFT PART OF FIGURE 3). Benchmark Only context Both Only lto ffmpeg 0 6 4 file 2 1 0 grok 0 2 4 libarchive 0 0 2 libgit2 0 3 0 libhevc 1 1 1 libhtp 0 5 1 libxml2 0 3 13 matio 17 26 0 muparser 0 0 0 ndp 2 10 8 njs 0 0 1 openh264 0 7 1 stb 4 11 0 usrsctp 0 0 0 zstd 0 1 1 TABLE VIII. INCLUSION RELATIONS FOR BUGS FOUND BY context AND lto IN THE FUZZBENCH EXPERIMENTS (CF.LEFT PART OF FIGURE 3). Benchmark Only predictive All Only others ffmpeg 2 9 1 file 1 2 1 grok 1 6 0 libarchive 0 0 2 libgit2 0 3 0 libhevc 0 1 2 libhtp 0 5 1 libxml2 6 16 0 matio 0 26 17 muparser 1 0 0 ndp 1 16 4 njs 0 1 0 openh264 1 7 1 stb 3 15 0 usrsctp 0 0 0 zstd 0 2 0 TABLE IX. INCLUSION RELATIONS FOR BUGS FOUND BY predictive VS.THE ENSEMBLE OF context AND lto IN THE FUZZBENCH EXPERIMENTS (CF.LEFT PART OF FIGURE 3). NOTE THAT THE ENSEMBLE HAS THE UNFAIR ADVANTAGE OF HAVING DONE TWICE AS MANY TRIALS. 17