ShapFuzz: Efficient Fuzzing via Shapley-Guided Byte Selection

ShapFuzz: Efficient Fuzzing via Shapley-Guided Byte Selection

Speakers: Kunpeng Zhang

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=QFwfR-qhQ5o

Overview

Mutation-based fuzzing stands as a critical technique in the arsenal of vulnerability researchers, instrumental in uncovering software bugs and exploring uncharted code paths. Despite its widespread adoption and proven efficacy, a fundamental inefficiency persists: the indiscriminate mutation of input bytes. Traditional fuzzers often lack a nuanced understanding of which specific bytes within an input exert the most influence over program execution and, consequently, new code discovery. This leads to a significant waste of computational resources, as a vast majority of mutations fail to yield meaningful progress. Kunpeng Zhang's talk on SHAPFUZZ at the NDSS Symposium directly addresses this inefficiency by introducing a novel, principled approach to quantify and leverage the importance of individual input bytes.

SHAPFUZZ proposes a paradigm shift, moving beyond simplistic byte-by-byte or constraint-focused analysis to a more sophisticated, game-theoretic understanding of byte contributions. Drawing inspiration from Shapley Analysis in cooperative game theory and integrating Contextual Multi-Armed Bandits (CMAB), SHAPFUZZ dynamically identifies and prioritizes "high-value" bytes—those most likely to unlock new code paths. This talk outlines how SHAPFUZZ, by focusing mutation energy on these critical bytes, significantly enhances fuzzing efficiency, leading to superior edge coverage and bug discovery with minimal overhead. The research highlights that a small fraction of bytes are disproportionately responsible for uncovering new code, particularly those involved in multiple path constraints.

The significance of SHAPFUZZ lies in its ability to overcome the limitations of existing methods, such as the computational expense of taint analysis, the complexity of inference-based approaches, and the modeling challenges of deep learning fuzzers. By offering a lightweight, adaptable framework for intelligent byte selection, SHAPFUZZ promises to accelerate vulnerability discovery across a wide range of software, ultimately contributing to more robust and secure systems. Its empirical validation against state-of-the-art fuzzers underscores its potential to become a cornerstone in the next generation of fuzzing tools.

Background

▶ Watch: Introduction: problem with current fuzzing methods (0:00)

The landscape of fuzzing has seen continuous innovation, yet the core challenge of efficiently exploring program state remains. Traditional mutation-based fuzzers, while effective, often operate under the assumption that all input bytes hold equal potential for triggering new behaviors. However, empirical observations and the design of SHAPFUZZ challenge this assumption, revealing that only a small fraction of input bytes are truly impactful. Specifically, research shows that merely 18% of constraint-related bytes can be effectively mutated to discover new code, indicating a substantial waste of resources in current fuzzing strategies.

Existing solutions attempt to address this by identifying constraint-related bytes, often through methods like taint analysis (e.g., TaintScope, Dowser, Angora), inference-based approaches (e.g., GREYONE, REDQUEEN), or deep learning-based fuzzers (e.g., NEUZZ, MTFuzz). While these methods have their merits, they frequently suffer from significant drawbacks. Taint analysis can be slow for large inputs and typically focuses on single-constraint relationships. Inference-based techniques can be computationally intensive, requiring byte-by-byte investigation, and deep learning models can lead to out-of-memory errors when processing complex or large inputs. These approaches often necessitate an extra, time-consuming analysis stage that SHAPFUZZ aims to circumvent.

SHAPFUZZ's conceptual foundation is built upon two key machine learning and game theory concepts: Shapley Analysis and Contextual Multi-Armed Bandits (CMAB).

Shapley Analysis, derived from cooperative game theory, provides a robust framework for fairly attributing contributions among players in a coalition. In the context of fuzzing, the "players" are the individual input bytes, and the "gain" is the discovery of new code (specifically, new edges in the program's control flow graph). The Shapley value precisely quantifies each byte's marginal contribution across all possible mutation combinations, offering an unbiased measure of its importance. This technique has proven its utility in diverse fields, including feature importance quantification in deep learning models.

Contextual Multi-Armed Bandit (CMAB) is a decision-making framework designed to navigate the exploration-exploitation trade-off under uncertainty. It enables an agent to choose from a set of "arms" (in SHAPFUZZ's case, byte positions to mutate) and receive a reward, with the crucial addition of "context" or side information. This context allows the expected reward of an arm to vary based on the current state of the fuzzing process, making it ideal for dynamically assessing and adapting to the evolving importance of bytes. CMAB helps SHAPFUZZ intelligently decide whether to exploit bytes known to be highly effective or explore less-chosen bytes to gather new information about their potential.

The motivation for integrating Shapley values into fuzzing stems from compelling empirical observations. Extensive experiments, where the "gain" was defined as the number of new edges discovered by a byte combination, revealed a stark imbalance in byte contributions. Due to the combinatorial explosion of possible byte combinations, these experiments were conducted by running AFL++ with random mutations for 48 hours on single seeds across 18 programs, repeating each experiment six times. The meticulous recovery and testing of all subsets of related bytes allowed for accurate Shapley value calculations. The results were striking: a small fraction of bytes consistently contributed the most to discovering new edges. For instance, in pdftotext, the top 4% of byte positions accounted for 97.43% of new edges, and in flvmeta, they contributed a remarkable 100%. This phenomenon is largely attributed to path coupling, where a single input byte is involved in multiple path constraints simultaneously. An analysis across 16 programs (Figure 2 in the paper) confirmed that 86% of bytes are related to more than two CMP instructions, with some bytes linked to as many as 10 CMPs at once. This insight forms the bedrock of SHAPFUZZ: focusing mutation energy on these high-importance, multi-constraint-related bytes can drastically improve fuzzing efficiency compared to prior work like hybrid fuzzing (e.g., Driller, Dowser, SymFuzz, QSYM) which struggles with path explosion, or taint-based fuzzing (e.g., Angora, Matryoshka, REDQUEEN, ProFuzzer) which can be slow and often focuses on single constraints.

Key Findings

▶ Watch: Background: Shapley Analysis and Contextual Multi-Armed Bandits (2:00)

The research underpinning SHAPFUZZ yielded several fundamental insights that redefine the understanding of byte importance in mutation-based fuzzing. These key findings are critical for designing more efficient and effective fuzzing strategies:

1. Small, Critical Portion of Byte Positions: Empirical experiments using Shapley analysis unequivocally demonstrated that the discovery of new code and increased coverage are overwhelmingly dependent on a small, critical subset of input byte positions. This challenges the traditional notion of uniform byte importance, revealing that not all bytes contribute equally to fuzzing progress. For example, the top 4% of bytes contributed 97.43% of new edges in pdftotext and 100% in flvmeta.
2. Repeated Mutation of High-Importance Bytes is Effective: It was observed that the repeated mutation of these same high-importance byte positions can consistently discover new code. This is a pivotal insight, as it suggests that fuzzers can achieve greater efficiency by concentrating their mutation efforts on these identified critical bytes, rather than distributing mutations randomly or broadly.
3. Multi-Constraint Relationship as a Root Cause: This phenomenon of disproportionate byte importance is largely attributed to the nature of program logic, where a single input byte can be related to multiple path constraints simultaneously. The analysis showed that 86% of constraint-related bytes are involved in more than two CMP instructions, with some bytes tied to as many as 10 CMP operations. Targeting these multi-constrained bytes offers significant opportunities for efficiency gains.

Based on these findings, the main contributions of SHAPFUZZ are:

• Empirical Validation of Byte Contribution: Conducting rigorous empirical experiments using Shapley analysis to quantify byte contributions to code discovery, providing concrete evidence that focused mutation on a small set of positions significantly boosts fuzzing efficiency due to multi-constraint relationships.
• Formalization and Dynamic Update of Shapley Values: Formalizing byte selection as a Shapley analysis problem and transforming its calculation into an incrementally updatable form for minimal overhead during fuzzing. This led to the proposal of SHAPFUZZ, a novel fuzzer that guides byte selection using these dynamic Shapley values.
• Integration of Contextual Multi-Armed Bandit (CMAB): Optimizing the byte selection process by integrating a CMAB approach, which intelligently balances the exploitation of high-Shapley-value bytes with the exploration of less-chosen ones to ensure robust and efficient fuzzing.
• Superior Performance and Real-World Impact: Implementing SHAPFUZZ as a prototype based on AFL++ 10 and demonstrating its superior performance through extensive evaluation on UNIFUZZ and MAGMA benchmarks. SHAPFUZZ consistently outperformed ten state-of-the-art fuzzers in edge coverage and bug discovery, identifying 4170 more edges and 19 more bugs than the best byte-scheduling fuzzer, 20 more bugs than the best commonly used fuzzer, and 6 more CVEs on MAGMA. Notably, it discovered 11 new bugs in widely used programs, with 3 confirmed by vendors.

Technical Deep Dive

▶ Watch: Empirical evidence: small byte subset drives new code coverage (2:50)

SHAPFUZZ's core technical innovation lies in its ability to formalize byte selection as a Shapley analysis problem and then transform the computationally intensive Shapley value calculation into an incrementally updatable form that can be integrated into the fuzzing loop with minimal overhead. This is achieved through a clever combination of game theory, dynamic family structures, and a contextual multi-armed bandit algorithm.

At its heart, SHAPFUZZ models byte mutation as a cooperative game. For any given seed input, the "players" in this game are its individual bytes. A "coalition" is defined as a subset of these bytes that are mutated together. The "gain" of such a coalition is quantified by the number of self-new edges discovered by the mutated input. "Self-new edges" are crucial for consistency, referring to edges discovered relative to the initial seed, thereby avoiding statefulness issues where the gain might be influenced by the order of previous mutations.

A full, exact Shapley analysis for every byte across all possible inputs is combinatorially prohibitive. To address this, SHAPFUZZ introduces the concept of temporary Shapley values derived from incomplete analysis. Empirical evidence suggests that bytes exhibiting high temporary Shapley values are still strongly correlated with multiple unseen path constraints, making this approximation effective.

To further reduce computational overhead, SHAPFUZZ employs a seed family concept. A family comprises seeds that originate from the same initial seed, maintain the same length, and thus share identical relative byte positions. This allows SHAPFUZZ to compute Shapley values for the first seed in a family and then share these values across all other family members, significantly amortizing the computational cost.

The calculation of Shapley values is transformed into an incrementally updatable form. The traditional Shapley value $\Phi_j$ for player $x_j$ (Equation 1 in the paper) is extended to consider that the gain $F(G)$ for a subset of bytes $G$ originates from all possible combinations of byte values within $G$. This leads to Equation (2), $F(V) = \sum_{v \in V} F(v)$, where $V$ is the set of all possible combinations of byte values in $G$. Further mathematical derivations (Equations 3 and 4) enable the calculation of a local contribution $\phi_{j,v}$ for byte $x_j$ based on an individual input $v$. For simplicity, SHAPFUZZ sets the weighting factor $k(P)$ to 1.

During the fuzzing process, these Shapley values are dynamically updated. If a mutation fails to discover self-new edges, the Shapley value for the mutated byte remains unchanged. If self-new edges are found, SHAPFUZZ identifies and removes redundant bytes—those whose mutation did not actually contribute to the new edges. For the remaining "necessary" bytes, SHAPFUZZ simplifies the update by assuming they contribute equally to the newly discovered edges.

The family structure itself is dynamic. When a seed is mutated and new edges are discovered, SHAPFUZZ attempts to identify and "withdraw" any mutators that changed the seed's length. If the new input, stripped of length-changing mutations, still yields the same new edges, it is added to the current family. Otherwise, it forms a new family. This mechanism ensures that shared Shapley values are based only on length-preserving mutations, maintaining consistency while balancing accuracy and computational efficiency by managing a reasonable number of families.

The system design of SHAPFUZZ, depicted in Figure 4 of the paper, integrates this Shapley analysis with a Contextual Multi-Armed Bandit (CMAB) algorithm to optimize byte selection. The fundamental principle is to allocate more mutation energy to bytes with higher Shapley values, as these are more likely to uncover new code. However, a naive approach of always selecting the highest-value byte could lead to local optima. CMAB addresses this by balancing the exploitation of known high-value bytes with the exploration of less-chosen ones, thereby continuously refining the understanding of byte importance.

For each byte position p in a seed s, CMAB calculates a score using Equation (5): Score(s,p) = EΦ_pf_s + 0.5 * U_s,p.

• EΦ_pf_s represents the expected reward for mutating byte p given the current context f_s. The context f_s is a feature vector derived from the execution path's edges. This vector is computed by calculating the cosine similarity between the current seed's execution path and the paths of ten diverse "center seeds" from the corpus.
• U_s,p is the upper confidence bound, which acts as an exploration bonus. This term encourages the selection of less-frequently chosen bytes, ensuring they periodically receive mutation opportunities. Its value decreases as a byte is selected more often.

To calculate EΦ_pf_s and U_s,p, SHAPFUZZ maintains a tuple (D_p, R_p) for each byte p. D_p is a matrix accumulating historical feature vectors, and R_p is a vector accumulating historical Shapley values. These are updated using Equation (6): D_p ← D_p + f_s f_s^T and R_p ← R_p + Φ_p f_s. The expected reward EΦ_pf_s is then estimated using ridge regression, as shown in Equations (7) and (8), where θ is the best coefficient vector. The upper confidence bound U_s,p is calculated using Equation (9): U_s,p = (f_s^T (D_p^T D_p + I_k)^-1 * f_s).

Finally, the scores calculated for all bytes are converted into a probability distribution. In each mutation cycle, SHAPFUZZ first randomly determines n, the number of sub-mutations to perform. Then, for each sub-mutation, the fuzzer uses this probability distribution to select which byte will be mutated. This contextual, Shapley-guided selection process enables SHAPFUZZ to efficiently navigate the complex trade-off between exploiting known high-value bytes and exploring new potential areas, ultimately leading to more effective code discovery.

Demo / Proof of Concept

▶ Watch: SHAPFUZZ's technical approach: byte selection as cooperative game (4:15)

While the talk did not feature a live demonstration in the traditional sense, the extensive and rigorous experimental evaluation of SHAPFUZZ serves as its proof of concept, demonstrating its practical implementation and superior performance against a wide array of state-of-the-art fuzzers.

The prototype of SHAPFUZZ was built upon AFL++ 10, with primary modifications focused on the mutation process and the byte scheduling mechanism. The goal was to seamlessly integrate the Shapley-guided byte selection without disrupting AFL++'s core fuzzing logic, thereby ensuring minimal performance overhead.

For evaluation, SHAPFUZZ was tested on two widely recognized third-party platforms: UNIFUZZ 21 and MAGMA 14. UNIFUZZ provides a collection of real-world programs, while MAGMA offers a ground-truth fuzzing benchmark with known bugs, allowing for accurate and consistent evaluation. The experimental setup was robust, utilizing a system running Ubuntu 18.04 with 103 Intel Xeon Gold 6230R CPU cores and 256 GB of RAM. Each fuzzer was allocated a single CPU core per target program to ensure fair comparisons.

Evaluation metrics included counting unique edges discovered (using afl-showmap from AFL++) as the primary coverage metric, and unique bugs detected. For bug detection, target programs were compiled with ASAN 29 enabled, and the "top-three rule 16" was applied for de-duplication. Sixteen commonly used programs were selected from UNIFUZZ and other research papers, covering diverse input formats such as ELF, TIFF, PDF, MP4, FLV, WAV, JPG, MP3, and JS. All fuzzers used the same initial seed sets from UNIFUZZ, FuzzBench 27, and public corpora.

The evaluation results highlight SHAPFUZZ's exceptional performance:

• Comparison with Byte-Scheduling Fuzzers: Against GreyOne 12, ProFuzzer 37, NEUZZ 32, PreFuzz 36, and Angora 6, SHAPFUZZ demonstrated remarkably low analysis overhead. For all seed sets (ALL SEEDS, SEEDS10000, SEEDS1000), SHAPFUZZ's analysis time was approximately 2% of GreyOne's (e.g., 103 seconds vs. 54777s for ALL SEEDS). It consistently achieved the highest edge coverage, discovering 4170 more edges than the best baseline for ALL SEEDS. Furthermore, SHAPFUZZ found 103 unique bugs (ALL SEEDS), which is 19 more than Angora, and revealed 36 bugs not found by any other fuzzer, with 18 originating from entirely new code regions.
• Comparison with Commonly Used Fuzzers: When compared against AFL 40, AFL++ 10, AFLFast 3, FairFuzz 18, MOPT 25, and EMS 26, SHAPFUZZ consistently maintained a lower median rank for edge discovery (1.5 for 1 and 3 hours, 1.81 for 24 hours). It triggered 152 unique bugs on UNIFUZZ, outperforming AFL++ (132 bugs) by 20 bugs, and performed best on 8 out of 16 programs, including nm, readelf, flvmeta, and objdump. Crucially, SHAPFUZZ discovered 11 new bugs in the latest versions of 6 widely used programs, with 3 confirmed by vendors.
• Overhead: Despite its advanced analysis, SHAPFUZZ's throughput was comparable to other fuzzers, being slightly lower than MOPT, AFL++, AFL, and AFLFast by 6-10% but higher than FairFuzz by 9.75%, demonstrating minimal performance overhead.
• Evaluation on MAGMA: On the MAGMA ground-truth benchmark, SHAPFUZZ again excelled in bug discovery, exposing the most bugs on 7 of 9 programs, including libsndfile (7.00 bugs vs. AFL++'s 6.89), libxml2 (4.22 vs. 4.00), openssl (4.00 vs. 2.67), and sqlite3 (4.56 vs. 2.56).
• Time to Bug (TTB): SHAPFUZZ exhibited the fastest TTB for 29 CVEs, discovering 25 bugs twice as fast as AFL++. It uniquely exposed CVEs like 2017-2518 and 2019-19317, showcasing its ability to solve complex path constraints rapidly.
• Ablation Study: An ablation study comparing SHAPFUZZ with a variant, SHAPFUZZ-modeling (using random byte selection), confirmed the effectiveness of the Shapley-guided mutation strategy, as SHAPFUZZ consistently discovered more new edges.
• Detailed Inference-based Fuzzers Comparison: In a focused 3-hour experiment, SHAPFUZZ's average proportion of useful bytes (UR) was up to 70.5%, significantly outperforming GreyOne (UR 16.1%) and ProFuzzer (UR 17.8%), demonstrating its superior ability to identify impactful bytes quickly.

The consistent outperformance across diverse metrics, benchmarks, and comparisons with leading fuzzers provides compelling evidence of SHAPFUZZ's efficacy and efficiency. The discovery of vendor-confirmed new bugs further validates its real-world impact.

Defensive Implications

▶ Watch: Optimizing Shapley calculation: temporary values and seed families (4:50)

SHAPFUZZ's advancements in intelligent byte selection for fuzzing carry significant implications for software defenders, offering new avenues to enhance proactive security measures and improve the efficiency of vulnerability discovery.

Firstly, the core finding that a small, critical portion of input bytes disproportionately contributes to new code discovery empowers defenders to adopt a more targeted and efficient approach to security testing. Instead of relying solely on broad, untargeted fuzzing, organizations can integrate tools like SHAPFUZZ to rapidly identify vulnerabilities in critical components. This means that even with limited computational resources, highly impactful areas of code are more likely to be reached and tested, accelerating the discovery of exploitable flaws. The ability to find bugs faster (demonstrated by SHAPFUZZ's superior Time to Bug for 29 CVEs) allows development teams to patch vulnerabilities earlier in the software development lifecycle, reducing exposure windows.

Secondly, SHAPFUZZ's minimal analysis overhead (approximately 2% of GreyOne's) makes it particularly attractive for continuous integration/continuous deployment (CI/CD) pipelines. Integrating such an efficient fuzzer allows for more frequent and comprehensive security testing without significantly impacting build times or resource allocation. This continuous feedback loop can help catch regressions and new vulnerabilities introduced during rapid development cycles, fostering a "shift left" security posture.

Thirdly, the revelation that many critical bytes are involved in multiple path constraints (86% related to more than two CMP instructions) provides valuable insight for developers. When designing and reviewing code, particularly input parsing and handling routines, developers should be acutely aware of how single input elements might influence multiple control flow decisions. This understanding can guide the implementation of more robust input validation and sanitization, specifically focusing on these high-impact bytes to prevent complex bypasses or unexpected behaviors that could lead to vulnerabilities. Code reviews and static analysis efforts could be augmented by identifying these "multi-constraint" bytes and scrutinizing their handling.

Finally, SHAPFUZZ's ability to discover 11 new bugs in widely used programs, with 3 confirmed by vendors, underscores its practical utility in real-world vulnerability research. Security teams can leverage open-source implementations of SHAPFUZZ (such as the one available at https://github.com/ShapFuzz/ShapFuzz) to augment their existing fuzzing infrastructure, potentially uncovering previously unknown vulnerabilities in their own software or third-party dependencies. This leads to a higher rate of unique bug discovery and a more comprehensive security assessment, ultimately leading to more secure software ecosystems. Defenders should consider adopting or incorporating the principles of Shapley-guided byte selection into their fuzzing strategies to maximize the return on their security testing investments.

Key Takeaways

• Byte Importance Varies Significantly: Not all input bytes contribute equally to discovering new code; a small, critical subset of bytes is disproportionately responsible for fuzzing progress, often due to their involvement in multiple path constraints.
• Shapley Analysis for Byte Prioritization: SHAPFUZZ leverages Shapley Analysis from cooperative game theory to quantify the precise contribution of individual bytes to code discovery, formalizing byte selection as an optimization problem.
• Dynamic and Efficient Fuzzing: SHAPFUZZ dynamically updates Shapley values during fuzzing and integrates a Contextual Multi-Armed Bandit (CMAB) algorithm to intelligently balance exploiting high-value bytes with exploring new ones, ensuring efficient and robust code exploration with minimal overhead (e.g., 2% of GreyOne's analysis time).
• Superior Performance in Coverage and Bugs: SHAPFUZZ consistently outperforms state-of-the-art fuzzers in both edge coverage (e.g., 4170 more edges than best baseline) and bug discovery (e.g., 19 more bugs than Angora, 20 more bugs than AFL++, 11 new vendor-confirmed bugs).
• Faster Vulnerability Discovery: The approach leads to significantly faster Time to Bug (TTB) for numerous CVEs, uniquely exposing complex vulnerabilities like CVE-2017-2518 and CVE-2019-19317.
• Actionable Insights for Defenders: The research provides actionable insights for developers and security teams to focus testing and code review efforts on critical, multi-constraint-related bytes, improving the efficiency of proactive security testing and vulnerability patching.

About the Speaker(s)

Kunpeng Zhang is the speaker for this presentation on SHAPFUZZ. Based on the provided metadata and transcript, he is the primary researcher presenting this novel approach for efficient fuzzing. No further biographical details, such as his title or specific company affiliation, are available in the provided input.