DeepGo: Predictive Directed Greybox Fuzzing

DeepGo: Predictive Directed Greybox Fuzzing

Speakers: Peihong Lin

Conference: NDSS Symposium

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

Overview

In the realm of software security, Directed Greybox Fuzzing (DGF) has emerged as a powerful technique for efficiently identifying vulnerabilities by guiding fuzzing efforts towards specific target code areas. However, current state-of-the-art DGF methods primarily rely on heuristic algorithms that leverage historical execution data. This reliance creates a significant limitation: these fuzzers often lack foresight, struggling to navigate complex, unexplored paths or satisfy intricate constraints that are hard to guess through random mutations. This leads to inefficiencies, particularly when dealing with deeply nested or conditionally protected code.

Peihong Lin's presentation on DeepGo: Predictive Directed Greybox Fuzzing introduces a groundbreaking approach to overcome this inherent challenge. DeepGo addresses the foresight problem by integrating deep neural networks and reinforcement learning to predict optimal execution paths and guide fuzzing mutations more intelligently. By combining historical execution information with predicted future insights, DeepGo aims to generate viable paths, avoid infeasible execution branches, and reach target sites with unprecedented precision and efficiency.

This talk is crucial for security researchers, developers, and practitioners who are invested in advanced vulnerability discovery techniques. DeepGo represents a significant leap forward in directed fuzzing, demonstrating how predictive modeling and intelligent optimization can dramatically improve the speed and effectiveness of finding bugs in critical software components. The work provides a robust framework for designing next-generation fuzzers that can proactively anticipate program behavior rather than merely react to observed execution traces.

Background

▶ Watch: Introduction: DGF limitations and DeepGo's challenges (0:00)

DeepGo builds upon several foundational concepts in fuzzing and artificial intelligence. Understanding these underlying technologies is key to appreciating DeepGo's innovations.

Directed Greybox Fuzzing (DGF): The core motivation for DeepGo stems from DGF, a technique pioneered by tools like AFLGo. DGF aims to minimize the "distance" between generated inputs and a predefined target site within a program. It typically calculates this distance using static analysis information, such as call graphs and control-flow graphs, and combines it with runtime metrics like condition complexity to form a fitness metric. Subsequent DGF techniques have refined these metrics, using trace similarity (e.g., Hawkeye), data conditions (CAFL), or data flow information (WindRanger). Sequence-based approaches like Berry and Lolly also emerged, while others like BEACON and MC2 focused on pruning unreachable paths or constructing queryable oracles to improve efficiency. Despite their advancements, a common thread among these methods is their reliance on historical data, which inherently limits their ability to anticipate unexplored paths.

Deep Neural Networks (DNNs): The rise of DNNs has profoundly impacted various fields, including program analysis and security. In fuzzing, DNNs have been successfully employed to simulate program branching behavior and guide optimization. Projects like NEUZZ, MTFuzz, and FUZZGUARD have demonstrated DNNs' capability to learn from mutated inputs and predict covered branches, effectively creating a model of the program's execution environment. This capability forms the bedrock of DeepGo's Virtual Ensemble Environment (VEE), allowing it to predict path transitions without actual execution.

Reinforcement Learning (RL): RL provides a framework for agents to learn optimal decision-making strategies by interacting with an environment. Modeled as a Markov process, an RL agent takes actions, receives feedback (rewards), and adjusts its policy to maximize cumulative rewards over time. DeepGo casts the DGF problem as a Markov process, enabling the application of RL to optimize fuzzing strategies. This allows the fuzzer to learn how to select mutations that are most likely to lead to a target, based on both immediate and long-term expected rewards.

Model-Based Policy Optimization (MBPO): DeepGo draws inspiration from MBPO, a class of RL algorithms that combine a virtual environment (often built with DNNs) with a reinforcement learning network. The agent interacts with this virtual environment to generate numerous predicted path transitions, which are then used to train the RL network and learn an optimal policy. DeepGo specifically adopts MBPO's k-step branch rollout strategy to integrate DNNs and RL, allowing for foresight into future path transitions.

Particle Swarm Optimization (PSO): PSO is an evolutionary computation technique that mimics the social behavior of bird flocking or fish schooling. Particles, each representing a potential solution, move through a search space, adjusting their velocity and position based on their own best-found solution (local best) and the best solution found by the entire swarm (global best). In fuzzing, PSO has been applied (e.g., in MOPT) to optimize parameters like mutation operator selection probabilities. DeepGo extends this with its Multi-elements Particle Swarm Optimization (MPSO) to simultaneously optimize multiple, interdependent fuzzing strategies.

Key Findings

▶ Watch: Background on Directed Greybox Fuzzing (DGF) (2:00)

DeepGo's research yielded several pivotal findings and contributions that significantly advance the state of directed greybox fuzzing:

1. Novel Path Transition Model: DeepGo reframes DGF as a process of navigating specific path transition sequences. Instead of solely relying on distance to target, it introduces sequence rewards as a fitness metric, quantifying the difficulty and value of reaching targets through a series of transitions. This model provides a more granular and predictive understanding of fuzzing progress.

1. Predictive Virtual Ensemble Environment (VEE): The creation of a Virtual Ensemble Environment (VEE), powered by Deep Neural Networks (DNNs), is a cornerstone of DeepGo. The VEE accurately predicts potential path transitions and their corresponding rewards without actual program execution. This predictive capability provides the fuzzer with crucial foresight into unexplored paths, achieving an impressive average accuracy of over 90% in predicting both next paths and rewards. This directly addresses the "lack of foresight" limitation of previous DGF approaches.

1. Reinforcement Learning for Fuzzing (RLF) Model: DeepGo integrates an RLF model that intelligently combines historical execution data with the VEE's predicted path transitions. Based on the Soft Actor-Critic (SAC) algorithm, the RLF model learns an optimal policy to guide mutation strategies, effectively generating optimal path transition sequences and steering the fuzzer away from infeasible or hard-to-execute paths. Evaluation showed that DeepGo's average reward was 4.26 higher than a version without RLF/FO, highlighting its effectiveness.

1. Comprehensive Fuzzing Strategy Optimization with Action Group: DeepGo introduces an action group concept, enabling the simultaneous optimization of five critical fuzzing elements: seed selection (SS), seed energy (SE), havoc rounds (HR), mutator selection (MT), and mutation location (LC). This holistic approach, managed by a Multi-elements Particle Swarm Optimization (MPSO) algorithm, allows for more precise and efficient guidance towards target sites compared to optimizing individual strategies in isolation.

Evaluation Results: DeepGo's superior performance was rigorously validated through extensive experiments:

• Target Reachability (TTR): DeepGo reached 73 out of 80 target sites on the UniBench 27 benchmark within a 24-hour budget, vastly outperforming AFLGo (22/80), BEACON (11/80), WindRanger (19/80), and ParmeSan (9/80). It achieved speedups ranging from 3.23x to 4.83x compared to these state-of-the-art baselines.
• Vulnerability Exposure (TTE): DeepGo exposed 19 out of 20 known vulnerabilities on the AFLGo testsuite 6, demonstrating speedups from 2.43x to 3.32x against the baselines.
• Ablation Studies: The studies confirmed that all core components (VEE, RLF, and FO) are indispensable for DeepGo's enhanced performance. Removing the VEE or RLF/FO significantly reduced target reachability (e.g., DeepGo-v reached 32/80 targets, DeepGo-r reached 18/80, compared to DeepGo's 73/80). DeepGo also generated more Reachable Seeds (Rseed) (2788) and had a higher Proportion of Reachable Seeds (PRseed) (72.6%).

These findings collectively demonstrate that DeepGo’s predictive and optimized approach enables it to generate optimal and viable paths, effectively avoiding inefficient exploration and significantly accelerating the discovery of target sites and vulnerabilities.

Technical Deep Dive

▶ Watch: Reinforcement Learning (RL) model for fuzzing (3:00)

DeepGo's technical innovation lies in its intricate integration of predictive modeling and reinforcement learning into a directed greybox fuzzer. This section elaborates on the core technical components.

Path Transition Model

DeepGo's fundamental conceptualization of DGF is as a sequence of path transitions. Each mutation of a seed potentially leads to a new execution path, which is considered a transition. The model quantifies the immediate impact of these transitions using rewards and assesses the long-term potential of a sequence of transitions using sequence rewards.

Key elements of this model include:

• Path: Represented by an entry in the fuzzer's seed queue, uniquely identified by AFL's trace_bits which records covered branches and their hit counts.
• Action: A mutation operation at a specific byte location within a seed.
• Path Transition: Occurs when a mutated input results in an execution path different from the original seed. A "self-path-transition" means the path remains the same.
• Reward: Quantifies the change in a seed's value due to a path transition.
• Policy: The strategy employed by the fuzzer to select actions, typically expressed as probabilities for each available action.

To quantify the effectiveness of paths and transitions, DeepGo defines Seed Value (Vs(pt)), which is a weighted sum of four characteristics, with weights (W1-W4) determined by the Entropy Weight Method:

1. Seed Distance (ds): The static distance from the seed's current location to the target site. Shorter distances are preferred.
2. Difficulty (EDs): Measures the difficulty of satisfying branch inversions to cover unexplored branches. It's the arithmetic mean of the branch probabilities (P(br)) for all unexplored branches in the seed's path, where P(br) is based on hitor (branch hit count).
3. Execution Speed (Exs): Faster execution speed is preferred, as loops or computationally intensive paths can reduce efficiency.
4. Favored (Fvs): A binary indicator, where "favored" seeds are those that have covered all explored branches, making them good candidates for branch inversion to discover new paths.

The Reward (r(pt, at, Pt+1)) for a path transition from pt to Pt+1 via action at is simply the difference in their seed values: r(pt, at, Pt+1) = Vs(Pt+1) - Vs(pt). This forms the fundamental four-tuple (path, action, next_path, reward) for RL training.

The Expected Sequence Reward (Qπ(p,a)) is the core metric for evaluating a sequence of path transitions. It represents the expected sum of rewards following a given policy π, computed recursively using the Bellman equation: Qπ(ρ,α) = E_r(p,a,p') + γVπ(p'). Here, γ is the discount factor (optimal value of 0.8 found), and Vπ(p') is the transition value of the next path p'. Vπ(p') is 0 for terminal paths (where all actions lead to self-path-transitions) and otherwise the weighted average of Qπ(p',a) for all actions from p'. Maximizing this Qπ allows the fuzzer to learn an optimal policy that guides it along high-reward paths.

System Design and Architecture

DeepGo's architecture comprises four interconnected components:

1. Directed Greybox Fuzzing (DGF) Component: This is the modified fuzzer engine, built upon AFLGo. It includes a static analyzer that, during compile time, uses LLVM 11.0 for instrumentation to calculate basic-block-level distances and record sibling branches. At runtime, it continuously mutates seeds, and critically, integrates the path transition model to guide the fuzzing process.

1. Virtual Ensemble Environment (VEE): The VEE is a crucial predictive component built with Deep Neural Networks (DNNs). It predicts potential next_path and reward for a given (path, action) input without actual program execution.

• Input and Output Encoding: Paths (AFL's trace_bits) are encoded into a 20-dimensional continuous vector using the Coupled Data Embedding (CDE) algorithm to preserve features while reducing dimensionality. Actions are encoded based on mutation location (e.g., byte offset). Rewards are scalars.
• Training VEE: The VEE is trained using (path, action, next_path, reward) four-tuples. To handle aleatoric uncertainty (unpredictability in fuzzing), it predicts next_path and reward using Gaussian probability distributions. Epistemic uncertainty (due to random sampling in DNNs) is addressed by using Probabilistic Ensembles with Trajectory Sampling (PETS) algorithm with 6 identical DNNs, whose weighted average prediction mitigates individual DNN biases.
• Path Transition Determination: Given a (path, action), the VEE outputs potential next_paths and rewards as Gaussian distributions, from which specific transitions are sampled.

1. Reinforcement Learning for Fuzzing (RLF) Model: This model learns an optimal policy by combining historical and predicted path transitions to maximize sequence rewards. It is based on the Soft Actor-Critic (SAC) algorithm and consists of an Actor network, a Q-Critic network, and a V-Critic network.

• Training Data: The RLF collects two types of data: Historical Path Transitions (actual observations from fuzzing) and Predicted Path Transitions. The latter is generated using a k-step branch rollout strategy (optimal k value of 4 found), where the RLF agent selects a sequence of actions, and the VEE predicts the k-length path transition sequence. This provides foresight.
• Training RLF Model: The RLF model is trained to maximize the sum of rewards and entropy (to encourage exploration). The Actor network learns the policy π*, while Q-Critic and V-Critic networks minimize the difference between predicted and target Q/V values.

1. Fuzzing Optimization (FO) Component: This component translates the optimal policy learned by RLF into actionable fuzzing strategies.

• Action Group: DeepGo defines an action group as a tuple of five critical fuzzing elements: Seed-selection (SS) (which seed to fuzz), Seed-energy (SE) (how much fuzzing effort for a seed), Havoc-round (HR) (number of havoc mutations, 7D vector), Mutator (MT) (which mutator to use, 16D vector), and Location (LC) (where to mutate, 2D vector for optimal vs. common locations). These are concatenated into a 27-dimensional vector.
• Multi-elements Particle Swarm Optimization (MPSO): Each action group is treated as a particle in a 27-dimensional space. MPSO optimizes these elements simultaneously, adjusting particle velocity and position based on local best (lbesti) and global best (gbesti) values. The inertia factor w is dynamically adjusted using the Linearly Decreasing Inertia Weight (LDIW) method. Efficiency feedback from the RLF model (local and global average expected sequence rewards) guides the MPSO algorithm.

Implementation Details

DeepGo's implementation is a hybrid system:

• The fuzzer component is built on AFLGo with approximately 2100 lines of C code. It utilizes LLVM 11.0 for static analysis and instrumentation.
• The VEE and RLF models are implemented in Python, totaling around 1300 lines of code. The DNNs within the VEE use Pytorch-1.13.0, featuring five fully connected layers with Swish activation functions, trained for 500 epochs with automatic convergence detection via TensorBoard.
• The RLF model's Actor, Q-Critic, and V-Critic networks comprise three fully connected layers, with learning rates carefully set to 0.005 for efficient convergence.
• A key operational aspect is the concurrent execution of fuzzing, VEE/RLF training, and prediction. An extra GPU offloads the training and prediction tasks, ensuring these operations are accounted for within the overall wall clock fuzzing time budget.
• DeepGo operates in 20-minute fuzzing cycles. Within each cycle, it performs four tasks: fuzzer testing (generating historical data), VEE prediction (generating predicted data), RLF model training (learning policies), and FO component optimization (refining fuzzing strategies), before iterating to the next cycle.

Demo / Proof of Concept

▶ Watch: DeepGo's adoption of Model-Based Policy Optimization (3:25)

While the talk did not feature a live, interactive demonstration, the research included a compelling case study that served as a proof of concept for DeepGo's capabilities. This case study focused on the lame3.99.5 program, a well-known open-source MP3 encoder.

The objective was to reach a specific, hard-to-satisfy target site within lame3.99.5. This particular target was chosen because it was known to involve complex path constraints that typically hinder traditional heuristic-based fuzzers. The results vividly illustrated DeepGo's advantage:

• Both AFLGo and WindRanger, leading state-of-the-art DGF fuzzers, failed to reach this target site within the 24-hour time budget. Their reliance on historical data and lack of foresight prevented them from effectively navigating the intricate conditions required.
• In contrast, DeepGo successfully reached the target site in just 282 minutes. This achievement was attributed to its intelligent selection of high-reward actions and its ability to avoid low-reward or infeasible paths, as accurately predicted by its RLF model and VEE.

This case study effectively demonstrated DeepGo's core innovation: its capacity to leverage predictive modeling to overcome complex path constraints, significantly reducing the time and effort required to reach challenging target code. It provided concrete evidence that DeepGo's integrated approach of foresight and optimized strategy translates into tangible improvements in vulnerability discovery.

Defensive Implications

▶ Watch: DeepGo's novel Path Transition Model explained (4:00)

DeepGo's advancements in predictive directed greybox fuzzing carry significant implications for software defenders and developers. As fuzzing tools become more sophisticated and efficient at uncovering vulnerabilities, the pressure on developers to build more robust and secure software intensifies.

1. Proactive Security Testing: The primary implication is the need for organizations to adopt more advanced and proactive security testing methodologies. Tools like DeepGo, with their enhanced ability to reach deep, complex code paths and expose vulnerabilities faster, mean that traditional, less intelligent fuzzing might leave critical bugs undiscovered for longer. Defenders should integrate advanced DGF techniques, or even DeepGo itself if it becomes open-source, into their Continuous Integration/Continuous Deployment (CI/CD) pipelines to catch bugs earlier in the development lifecycle.

1. Focus on "Hard-to-Reach" Code: DeepGo's ability to navigate hard-to-satisfy path constraints highlights that code previously considered "safe" due to its complexity or deeply nested nature is now more accessible to automated bug finding. Developers must pay closer attention to the security of such complex logic, intricate state machines, and deeply conditional code paths, as they are no longer implicitly protected by the limitations of fuzzers. Prioritizing security reviews and static analysis on these areas becomes even more critical.

1. Threat Modeling and Attack Surface Expansion: The increased efficiency of fuzzers means that the effective attack surface for automated tools expands. Defenders should reconsider their threat models, assuming that sophisticated fuzzers can reach almost any part of their codebase, given sufficient time. This necessitates a more comprehensive approach to identifying potential entry points and sensitive data flows, even in less obvious execution paths.

1. Secure Coding Practices and Robustness: The underlying message for developers is to double down on secure coding practices. DeepGo's success in exposing vulnerabilities faster underscores that fundamental flaws, even if hidden, will eventually be found. Emphasis should be placed on input validation, error handling, memory safety, and robust state management. Furthermore, designing code with fuzzability in mind – making it easier for fuzzers to explore different paths – can paradoxically help uncover issues faster and lead to more secure software in the long run.

In essence, DeepGo serves as a powerful reminder that the arms race in cybersecurity continues. As offensive techniques improve, defensive strategies must evolve to incorporate equally advanced tools and methodologies, shifting towards a more predictive and comprehensive approach to software security.

Key Takeaways

• DeepGo addresses the inherent "lack of foresight" in traditional Directed Greybox Fuzzing (DGF) by leveraging predictive modeling.
• It introduces a novel Path Transition Model that quantifies fuzzing progress through sequence rewards, providing a more nuanced fitness metric.
• The Virtual Ensemble Environment (VEE), powered by Deep Neural Networks, accurately predicts potential path transitions and rewards with over 90% accuracy, enabling foresight into unexplored paths.
• A Reinforcement Learning for Fuzzing (RLF) model combines historical and predicted data to learn optimal mutation policies, guiding the fuzzer to avoid infeasible paths.
• DeepGo achieves comprehensive fuzzing strategy optimization through an action group and Multi-elements Particle Swarm Optimization (MPSO), simultaneously tuning seed selection, energy, mutators, and locations.
• Evaluation demonstrates significant speedups (e.g., 3.23x to 4.83x in reaching targets) and enhanced vulnerability exposure compared to state-of-the-art DGF fuzzers.

About the Speaker(s)

Peihong Lin is the speaker who presented the work on DeepGo: Predictive Directed Greybox Fuzzing at the NDSS Symposium. Based on the technical depth and innovative nature of this research, Peihong Lin is actively engaged in advanced security research, particularly in the areas of fuzzing, program analysis, and the application of artificial intelligence and machine learning techniques to enhance vulnerability discovery. The detailed technical contributions and rigorous evaluation presented in the talk reflect expertise in designing and implementing sophisticated security tools.