Predictive Context-sensitive Fuzzing

Predictive Context-sensitive Fuzzing

Speakers: Pietro Borrello

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=2AJ2B_ulV1c

Overview

Fuzz testing, or fuzzing, stands as a cornerstone in modern software security, invaluable for proactively identifying vulnerabilities before they can be exploited. The predominant method, coverage-guided fuzzing (CGF), relies on code coverage metrics to steer test case generation towards unexplored program paths. While highly effective for a broad spectrum of bugs, CGF often falls short when vulnerabilities are contingent not merely on reaching a specific code location, but on the context—the particular sequence of calls or argument values—that leads to that location. This talk introduces a groundbreaking approach: Predictive Context-sensitive Fuzzing, a novel methodology designed to overcome these limitations by selectively applying contextual awareness.

Presented by Pietro Borrello at the NDSS Symposium, this work addresses the inherent challenges of prior context-sensitive fuzzing techniques, such as the precision loss due to hash collisions and the performance degradation caused by state explosion. The proposed solution leverages a sophisticated static analysis to intelligently identify and instrument only the most "promising" program regions for context-sensitive tracking. By doing so, it achieves a superior balance between precision and performance, significantly enhancing bug discovery capabilities. This article will delve into the technical underpinnings of this innovative fuzzer, its impressive evaluation results, and the profound implications it holds for the future of automated vulnerability research.

Background

▶ Watch: Introduction to fuzzing and context-sensitive bug challenges (0:00)

The landscape of software security has been profoundly shaped by fuzzing, a technique responsible for unearthing countless bugs and preventing critical vulnerabilities. At its core, coverage-guided fuzzing (CGF) operates on the principle that increased code coverage correlates directly with a higher probability of bug discovery. Fuzzers like AFL++ continuously monitor code execution, using feedback on newly covered edges or blocks to mutate existing test cases and explore previously unreachable parts of the program. This feedback loop has proven remarkably effective for identifying crashes, memory errors, and other common vulnerabilities.

However, a significant class of bugs remains elusive to standard CGF: context-sensitive vulnerabilities. These bugs manifest only when a function is invoked from a particular call site, or with specific argument values, creating a unique program state that standard CGF's function-local metrics (like edge coverage) cannot adequately distinguish. For example, a memory corruption might occur in a utility function only when called by a specific high-level parser with a malformed input structure, while other callers of the same utility function remain unaffected.

Previous attempts to introduce context-sensitivity into fuzzing, notably inspired by approaches like ANGORA, have typically involved augmenting edge coverage with information derived from the call stack, often through hashing. While conceptually sound, these "best-effort" methods face critical limitations. Firstly, hash-based context encoding is inherently prone to collisions. Different call stacks might produce the same hash, leading to a loss of precision and causing the fuzzer to incorrectly perceive distinct execution paths as identical. To mitigate this, fuzzers might resort to larger coverage maps, which in turn severely degrade throughput due to increased memory access latency and cache misses. Secondly, a fully context-sensitive approach, attempting to track every possible calling context, quickly succumbs to an inherent state explosion problem. The fuzzer's queue becomes flooded with an excessive number of test cases, each representing a unique context, leading to an intractable search space and drastically reducing overall efficiency. This combination of precision loss and performance degradation is collectively termed "internal wastage," a fundamental barrier that Predictive Context-sensitive Fuzzing aims to systematically overcome.

Key Findings

▶ Watch: Core insight 1: Function cloning for precise context tracking (4:00)

The research presented by Pietro Borrello introduces a highly effective and novel approach to context-sensitive fuzzing, fundamentally improving the efficiency and depth of vulnerability discovery. The core findings and contributions are multifaceted and significant:

1. Selective Context-Sensitive Fuzzing: The work proposes a paradigm shift from "best-effort" or "full" context-sensitivity to a selective approach. Instead of attempting to track all possible contexts (which leads to state explosion), the fuzzer intelligently augments only those program portions predicted to yield the most valuable contextual information. This targeted instrumentation drastically reduces overhead while maximizing impact.

1. Collision-Free Context Encoding via Function Cloning: A key innovation is the use of function cloning as a backward-compatible instrumentation primitive. This technique creates distinct copies of a function for specific calling contexts identified as important. By redirecting calls to the appropriate clone, existing collision-free edge coverage mechanisms (like those in AFL++) can naturally differentiate execution paths based on context, eliminating the precision issues and runtime overhead associated with hash-based methods.

1. Data-Flow Analysis for Predictive Prioritization: To enable this selective approach, the researchers developed a sophisticated data-flow analysis capable of predicting which call sites are most likely to benefit from context-sensitive tracking. This oracle prioritizes cloning for call sites where the callee receives a higher diversity of incoming argument values, particularly pointer-type arguments, signaling potentially distinct and interesting program behaviors.

1. Open-Source LLVM Implementation: The entire system is implemented as a set of analysis and transformation passes within the LLVM compiler infrastructure, comprising approximately 2,000 lines of C++ code. This open-source implementation seamlessly integrates with off-the-shelf fuzzers, specifically demonstrated with AFL++ version 3.15a, ensuring practical applicability and ease of adoption.

1. Superior Bug Finding Effectiveness: Extensive evaluation on the industry-standard FuzzBench suite demonstrated that the predictive fuzzer consistently outperformed both state-of-the-art context-sensitive and context-insensitive techniques. It achieved a FuzzBench score of 94.14, significantly higher than AFL++'s collision-free edge coverage (82.30) and ANGORA-style context-sensitivity (63.42). This translated to finding 22.55% more bugs than the ANGORA-style approach and 11.6% more bugs than the strong collision-free baseline.

1. Discovery of Real-World Vulnerabilities: Beyond quantitative metrics, the predictive fuzzer proved its mettle by exposing 8 enduring security vulnerabilities in 5 popular and heavily-tested subjects: ffmpeg, njs, stb, libhevc, and matio. Crucially, 6 of these issues received CVE identifiers upon responsible disclosure, and **5 were found only by the predictive approach**, underscoring its unique capability to uncover previously overlooked flaws.

1. Minimal Internal Wastage: Unlike prior context-sensitive fuzzers, the predictive approach achieved these gains with manageable overhead. While its median queue size was moderately larger than the baseline (26.4%), this increase was instrumental for bug discovery, contrasting sharply with the 81.7% increase seen in best-effort context-sensitive fuzzing. Throughput reduction was minimal (6.5% slower than baseline), and code coverage was maintained or even improved for 8 subjects, effectively mitigating the state explosion and performance degradation issues.

These findings collectively present a compelling case for the efficacy of predictive context-sensitive fuzzing, marking a significant advancement in the field of automated vulnerability discovery.

Technical Deep Dive

▶ Watch: Core insight 3: Data-flow analysis to predict promising regions (6:00)

The technical ingenuity of Predictive Context-sensitive Fuzzing lies in its three core insights: function cloning, a selective approach, and a data-flow analysis to predict promising regions. These are integrated into a robust system design built upon the LLVM compiler infrastructure.

Function Cloning for Collision-Free Context Tracking

The first insight addresses the fundamental problem of precision and overhead in context tracking. Instead of dynamically tracking the call stack at runtime, which is costly and prone to hash collisions, the approach introduces function cloning. This is a backward-compatible instrumentation primitive that operates at compile time. For each specific calling context that the analysis deems important to differentiate, a distinct clone of the target function is created. When a caller invokes the original function, its invocation is redirected to the appropriate clone.

For example, if a function parse_seg is called by both get_seg_A1_A2 and get_seg_B, and the analysis determines that the context from get_seg_B is critical for parse_seg's behavior, a clone of parse_seg (e.g., parse_seg_from_get_seg_B) is created. All calls from get_seg_B are then redirected to parse_seg_from_get_seg_B, while calls from get_seg_A1_A2 continue to target the original parse_seg or another specific clone. This allows existing collision-free edge coverage techniques, such as those employed by AFL++, to naturally disambiguate calling contexts. The presence of edges within a cloned function implicitly carries precise contextual information, without requiring any runtime overhead or modifications to the fuzzer's core logic. This effectively solves the collision problem inherent in hash-based context encoding.

The Selective Approach to Context-Sensitivity

The second insight recognizes that while full context-sensitivity is conceptually powerful, it is practically intractable due to the state explosion problem. FuzzBench subjects, for instance, can have millions or even billions of potential calling contexts, making it impossible to track all of them efficiently. The solution is a selective approach: restrict cloning efforts to only those program portions that are predicted to benefit most from contextually refined edge profiles. This strategy bounds the increase in program size and ensures that context-sensitivity is applied efficiently and only where it truly matters for bug discovery. This avoids the "internal wastage" that plagues unconstrained context-sensitive fuzzing.

Data-Flow Analysis for Predictive Prioritization

The third, and arguably most critical, insight is the development of an oracle to identify these "promising regions" for cloning. This is achieved through a data-flow analysis that scrutinizes the diversity of incoming argument values at call sites. The core intuition is that significant differences in argument values across different invocations of the same function often reflect relevant variations in program behavior, potentially leading to less common internal states that context-sensitive coverage can help expose.

The analysis primarily focuses on pointer-type arguments, as these often dictate access to diverse data structures and thus influence control flow more significantly. It leverages SVF's FlowSensitive analysis, a state-of-the-art Andersen-style, field- and flow-sensitive points-to analysis. While this analysis provides accurate points-to sets for C/C++ code, it maintains scalability by remaining array- and context-insensitive.

The priority p for a given call site is calculated using the formula: p = (1/n) * sum(n - n_o).

Here, n represents the total number of call sites for the target function, and n_o is the number of call sites where a specific abstract object o (identified from the current call site's arguments) appears. This formula effectively favors call sites where arguments contain abstract objects that are rarely seen at other call sites, thereby promoting diversity. A refinement is also included to lower the priority of call sites targeting error-handling functions, which, despite often exhibiting high data-flow diversity, are typically less interesting for uncovering security vulnerabilities.

System Design and Implementation

These techniques are implemented as a set of analysis and transformation passes within the LLVM compiler infrastructure, specifically targeting its Intermediate Representation (IR). The system comprises approximately 2,000 lines of C++ code.

The process begins by taking a link-time-ready whole-program IR file, obtained using the GLLVM helper. This IR file is then processed by the custom LLVM passes, which selectively clone functions based on the predictive policy derived from the data-flow analysis. The output is a modified IR file that is subsequently fed to an off-the-shelf fuzzer. For evaluation, AFL++ version 3.15a was chosen due to its widespread adoption and high performance.

To ensure comprehensive bug detection, the compilation process integrates popular sanitizers like ASAN (AddressSanitizer) and UBSAN (UndefinedBehaviorSanitizer). These sanitizers are crucial for exposing silent bugs, such as memory errors or undefined behavior, that might otherwise go unnoticed by crashes alone.

A critical aspect of the system design is managing the coverage map size. Good fuzzing practices recommend keeping map sizes within standard L2 cache limits, typically 256 KB, to prevent performance degradation. The analysis incorporates a mechanism to estimate the coverage map size increase for each cloning decision. This allows the system to set a budget for cloning, ensuring that the resulting map fits within the 256 KB limit. This careful tuning enables the fuzzer to discriminate and explore new program states without incurring the dreaded "internal wastage."

Regarding implementation specifics, while the prototype technically supports reasoning about indirect-call sites by promoting them into conditional direct calls, this feature was disabled by default. The precision required for accurate static call-target set construction for indirect calls is notoriously difficult, and preliminary tests showed it often led to path explosion. However, the potential for profile-guided indirect call promotion is acknowledged for future work. The entire compilation process, including analysis and transformation, is automated via a simple Python helper script, which also handles sanitizer insertion and ensures that binaries are built with the -O3 optimization level for optimal performance during fuzzing.

Demo / Proof of Concept

▶ Watch: System design and implementation using LLVM and AFL++ (8:00)

While the talk did not feature a live, interactive demo, the efficacy of Predictive Context-sensitive Fuzzing was rigorously demonstrated through comprehensive evaluation on the FuzzBench testing infrastructure, a recognized standard for fuzzing research. The experiments focused on the 'type: bug' configuration, involving 20 trials of 23 hours each across 16 benchmarks from the FuzzBench suite.

Four fuzzer configurations were compared:

1. context: AFL++'s best-effort context-sensitive fuzzing, replicating ANGORA's approach with a 2^18 map size.
2. 1to: AFL++'s collision-free edge coverage with link-time optimization, serving as the strong baseline for context-insensitive fuzzing.
3. predictive: The proposed predictive context-sensitive fuzzing approach.
4. random: An uninformed prioritization policy for selective context-sensitivity, used to baseline the effectiveness of the prediction scheme.

Effectiveness in Bug Finding (RQ1)

The results unequivocally showed that the predictive fuzzer consistently outperformed all other configurations. It achieved a FuzzBench score of 94.14, significantly higher than 1to (82.30), random (82.98), and context (63.42). This translates to predictive finding 22.55% more bugs than context and 11.6% more than 1to across the FuzzBench suite.

In a more granular analysis, predictive identified 125 unique bugs, compared to 112 for 1to and 102 for context. Notably, predictive found 43 unique bugs that context missed entirely. A comparison between predictive and the strong 1to baseline revealed that predictive found 24 bugs (19.2% of its total) that 1to missed, while 1to found 11 bugs (10.7% of its total) that predictive missed. This crucial finding indicates that predictive not only uncovers more bugs but also discovers a different set of bugs, enriching the overall bug discovery landscape.

Further analysis through test case dissection provided insights into how these bugs were found:

• For 16 bugs, predictive triggered crashes in code that 1to had already covered without crashing. This suggests that the introduced context-sensitivity allowed predictive to exploit existing coverage more effectively, reaching specific buggy states that context-insensitive fuzzing overlooked.
• For 7 bugs, predictive even reached entirely new code coverage, demonstrating its ability to explore previously unreachable paths.
• The analysis confirmed that for 14 bugs, the intelligent cloning decisions directly contributed to reaching the buggy program location, and for 21 bugs, the contextual information helped retain ancestor test cases, guiding further mutations towards vulnerabilities.

Real-World Vulnerabilities

Despite FuzzBench subjects being heavily tested, the predictive fuzzer uncovered 8 enduring security issues in 5 popular programs: ffmpeg, njs, stb, libhevc, and matio. A testament to their severity, six of these issues received CVE identifiers upon responsible disclosure. Critically, **five of these issues were found only by the predictive approach**, highlighting its unique capability to expose vulnerabilities that had eluded other advanced fuzzers.

A notable case study involved a heap use-after-free vulnerability in the stb image processing library. This bug manifested as an out-of-bound array write during JPEG decoding, specifically within the stbi_process_marker function. Context-insensitive fuzzers failed to differentiate program states when invalid segments reached this function from its second call site. This prevented them from retaining test cases that, with further mutations, could lead to the bug. The predictive fuzzer, however, introduced context-sensitive instances of the loop edges within stbi_process_marker, becoming sensitive to different payload lengths induced from the second call site. This allowed it to retain and mutate associated test cases, eventually exposing the use-after-free. The predictor had selected this specific call site for cloning with a high priority of 0.91, validating the effectiveness of the data-flow analysis.

Internal Wastage (RQ2)

The predictive approach demonstrated minimal internal wastage, contrasting sharply with prior context-sensitive methods. While predictive's median queue size was moderately larger than 1to (by 26.4%), this increase was directly instrumental in providing the "stepping stones" necessary for discovering more bugs. In stark contrast, the context configuration experienced an 81.7% increase in queue size, indicative of significant internal wastage without proportional bug-finding gains.

In terms of throughput, predictive was only 6.5% slower than 1to, a negligible overhead considering its superior bug-finding capabilities. The context configuration, however, suffered a substantial 20.3% reduction in throughput. Furthermore, predictive achieved code coverage comparable to 1to, and even improved it for 8 subjects, demonstrating that the selective approach effectively avoids the coverage degradation observed with unconstrained context-sensitive fuzzing.

Analysis and Compilation Costs (RQ3)

The one-time costs associated with the analysis and compilation phase were found to be manageable. The points-to analysis took an average of 139.94 seconds and consumed 1.96 GB of memory. The most demanding benchmark, ffmpeg, required 2193.75 seconds and 22 GB of memory for its analysis. Compilation time for predictive binaries increased by an average of 153 seconds, and the resulting binary size increased by a geometric mean of 3.6x. However, these increases are well within acceptable limits for a one-time setup cost and do not adversely affect the performance of the fuzzing campaign itself, whether in persistent or fork-based scenarios.

Defensive Implications

▶ Watch: Implementation details: SVF's FlowSensitive points-to analysis (10:00)

The insights and capabilities offered by Predictive Context-sensitive Fuzzing have profound implications for software defenders, developers, and security practitioners. Understanding and potentially adopting this methodology can significantly bolster an organization's security posture.

1. Elevate Fuzzing Strategies: Organizations relying on fuzzing for vulnerability discovery should recognize the limitations of purely coverage-guided approaches and consider integrating advanced context-sensitive techniques. The talk clearly demonstrates that a significant class of bugs, including critical CVEs, remains hidden to standard fuzzers. Adopting or developing tools based on selective context-sensitive principles can fill this blind spot.

1. Focus on Context-Sensitive Code Review: Developers and security auditors should be more vigilant about functions called from diverse contexts, particularly those handling external input or complex data structures. The data-flow diversity heuristic highlights that call sites with varying pointer-type arguments are prime candidates for context-sensitive bugs. Prioritizing manual code review or static analysis efforts on such areas, especially those identified by a similar predictive analysis, can be highly effective.

1. Integrate Predictive Analysis into CI/CD: The underlying data-flow analysis and function cloning mechanisms could be integrated into continuous integration/continuous deployment (CI/CD) pipelines. While the analysis incurs a one-time cost, this can be absorbed during build processes, generating fuzzing-ready binaries that are inherently more effective at finding sophisticated bugs. This would elevate the security assurance level for every new code commit.

1. Leverage Sanitizers as a Standard: The research underscores the critical role of sanitizers like ASAN and UBSAN in conjunction with fuzzing. These tools are indispensable for exposing silent bugs that might not immediately crash a program but represent exploitable vulnerabilities (e.g., memory errors). Defenders should ensure that all fuzzing campaigns, regardless of their sophistication, are run with comprehensive sanitization enabled.

1. Prioritize Fuzzing Efforts Strategically: The predictive analysis can serve as an invaluable guide for allocating fuzzing resources. By identifying "promising regions" for context-sensitive instrumentation, organizations can focus their most intensive fuzzing efforts on the most complex and potentially vulnerable parts of their codebase, maximizing the return on investment for their security testing.

1. Demand Contextual Awareness in Security Tools: As the industry evolves, there should be a greater demand for static and dynamic analysis tools that incorporate contextual awareness. The ability to reason about execution paths beyond simple function boundaries is crucial for uncovering modern, subtle vulnerabilities.

By embracing the principles of selective and precise context-sensitive fuzzing, defenders can move beyond generic code coverage and target the intricate interactions within software that often harbor the most dangerous flaws, proactively safeguarding against advanced threats.

Key Takeaways

• Context is Critical for Bug Discovery: Many significant vulnerabilities, including real-world CVEs, are contingent not just on reaching a code location but on the specific calling context or argument values, making them invisible to traditional coverage-guided fuzzers.
• Selective Context-Sensitivity Overcomes Prior Limitations: The proposed approach of intelligently selecting and instrumenting only promising regions for context tracking, using function cloning, successfully resolves the precision issues (hash collisions) and performance degradation (state explosion) that plagued previous context-sensitive fuzzing efforts.
• Data-Flow Analysis is an Effective Oracle: A novel data-flow analysis, focusing on the diversity of pointer-type arguments at call sites, accurately predicts which program regions will benefit most from context-sensitive instrumentation, ensuring efficient and targeted fuzzing.
• Significant Improvement in Bug Finding: Predictive Context-sensitive Fuzzing demonstrably outperforms state-of-the-art context-sensitive and insensitive fuzzers, finding significantly more bugs (e.g., 22.55% more than ANGORA-style) and uncovering a different set of vulnerabilities, including 8 enduring security issues (6 CVEs) in popular software.
• Manageable Overhead for Enhanced Effectiveness: The method achieves these superior bug-finding capabilities with minimal internal wastage (e.g., only 6.5% throughput reduction) and acceptable one-time analysis/compilation costs, making it a practical and scalable enhancement to existing fuzzing workflows.
• Open-Source Integration with LLVM: The approach is implemented as an open-source set of LLVM passes, seamlessly integrating with off-the-shelf fuzzers like AFL++, facilitating adoption and further research in the community.

About the Speaker(s)

Pietro Borrello is the presenter of this work on Predictive Context-sensitive Fuzzing at the NDSS Symposium. Based on the content of the talk, he is a researcher deeply involved in advancing the field of software security, particularly in fuzz testing methodologies. His expertise lies in developing sophisticated static analysis techniques and compiler-based instrumentation to enhance the effectiveness and efficiency of automated vulnerability discovery. The detailed technical explanations and rigorous evaluation presented demonstrate his significant contributions to improving context-sensitive fuzzing, leading to the identification of real-world security vulnerabilities.