Dissecting Software Graphs: Structural Insights for Driver-Guided Fuzzing

This paper presents an empirical study of software structure under multi-driver fuzzing. The authors propose a structural abstraction that uses a static call graph as a shared backbone and projects driver-specific dynamic coverage onto it to derive driver-induced subgraphs. Based on this abstraction, they develop a four-phase methodology for backbone construction, fuzzing and profiling, graph-based analysis, and research-question-driven evaluation. They apply it to 27 OSS-Fuzz-derived C/C++ projects, spanning 43 executables and 854 driver configurations.

The study's key findings are that under the same total budget, multi-driver fuzzing outperforms the best single-driver baseline, increasing covered call-graph nodes by 27.9% and CFG-edge coverage by 73.5%, and revealing 11 unique bugs and abnormal behaviors largely missed by single-driver fuzzing. However, driver contributions are uneven, subgraphs differ substantially in cohesion, fragmentation, modularity, overlap, and residual under-exploration follows recurring regimes rather than a homogeneous tail. These results show that multi-driver fuzzing is fundamentally a structural exploration problem.

The paper makes the following contributions:

• It presents an execution-driven structural abstraction for studying configuration-rich software under fuzzing, based on a shared function-level call graph and driver-induced subgraphs derived from dynamic execution.

• It develops lightweight tool support, MFuzz and GDissert, that operationalizes controlled multi-driver execution, strict per-driver runtime attribution, and offline graph-based structural analysis for empirical study.

• It develops a scalable empirical methodology and structural metric set for analyzing exploration scope, cohesion, fragmentation, modularity, overlap, and region-level under-exploration across execution modes.

• It conducts a large-scale empirical study on OSS-Fuzz-derived benchmarks and provides a systematic graph-level characterization of how multi-driver fuzzing explores software structure, including recurring residual-gap regimes and their implications for driver-aware fuzzing.

The study investigates five research questions:

• RQ1: Does multi-driver fuzzing achieve greater overall coverage than the best single driver under the same total fuzzing budget? The results show that MFuzz improves coverage by an average of 27.9% in covered call-graph nodes and 73.5% in covered CFG edges. It also exposed 13 unique bugs and abnormal behaviors, only 3 of which were also found by MFuzz-single.

• RQ2: Do drivers exhibit heterogeneous fuzzing effectiveness under equal time budgets? The results show that driver effectiveness under equal time budgets is systematically heterogeneous. While a small subset of programs exhibits near-uniform contribution, most executables demonstrate moderate to strong imbalance, and several show dominant-driver behavior in which a few drivers account for most structural activation.

• RQ3: How are driver-induced subgraphs structurally organized? The results show that driver-induced subgraphs exhibit substantial variation in structural cohesion, fragmentation, and community organization. While some executables remain consistently cohesive, most programs show wide dispersion in LCC ratios, #WCC, and modularity values, indicating that configuration modes often activate structurally distinct execution regions.

• RQ4: To what extent do drivers overlap in the functionality they cover? The results show that driver-induced subgraphs exhibit highly heterogeneous structural overlap. Some executables show strong structural diversity, where most driver pairs activate largely disjoint call-graph regions, while others show substantial redundancy, with most drivers traversing nearly identical structural cores. Many programs also contain mixed overlap structure.

• RQ5: Which structural regions remain under-explored after round-robin multi-driver fuzzing, and why? The results show that residual region coverage after round-robin multi-driver fuzzing remains highly heterogeneous across executables and falls into three recurring regimes: backbone-dominated gaps, partial exploration with a substantial residual tail, and broad exploration with only localized residual pockets.

The paper concludes that multi-driver fuzzing is not merely a matter of running more drivers, but of understanding how different execution modes partition and complement the program graph. The findings suggest several practical implications for driver-aware fuzzing, including measuring the marginal value of each driver, accounting for overlap and redundancy among drivers, prioritizing drivers that extend exploration into weakly covered regions, reallocating effort differently for different residual regimes, using richer feedback than aggregate coverage alone, and improving driver–input combinations for persistent residual regions.

Improvements to AI Systems:

1. Graph-Structured Coverage Feedback for Fuzzing Agents: Replace aggregate coverage metrics with the proposed call-graph projection (driver-induced subgraphs) as reward signals for RL-based fuzzing agents. This enables the AI to optimize for structural diversity (e.g., minimizing overlap, maximizing new LCC nodes) rather than raw edge counts, leading to more efficient exploration of configuration-rich software.

2. Driver-Aware Test Generation via Residual-Regime Classification: Train a classifier on the three recurring residual-gap regimes (backbone-dominated, partial-exploration, broad-exploration) using graph features (modularity, #WCC, LCC ratio). The AI can then dynamically switch fuzzing strategies per region—e.g., for backbone-dominated gaps, prioritize inputs that trigger rarely-called functions; for partial-exploration tails, focus on mutating driver-specific arguments.

3. Marginal-Value Estimation for New Drivers: Use the structural overlap and cohesion metrics to predict the expected coverage gain of adding a new driver before running it. An AI system can rank candidate drivers by estimated marginal contribution (based on subgraph disjointness from existing drivers) and allocate time budgets accordingly, avoiding redundant drivers that traverse near-identical cores.

4. Adaptive Time Allocation Across Drivers: Implement a controller that monitors per-driver subgraph growth rates and overlap in real time. When a driver’s contribution plateaus or its subgraph becomes a subset of another’s, the AI reallocates its remaining budget to drivers with higher fragmentation or lower LCC ratios, directly addressing the uneven effectiveness found in RQ2.

5. Persistent-Region Input Synthesis: For residual regions that remain unexplored despite multi-driver fuzzing, use a generative model conditioned on the static call graph and driver-specific entry points. The AI can synthesize new driver–input combinations that specifically target weakly connected components or low-modularity regions, as suggested by the paper’s implications for persistent residual areas.

6. Structural Overlap-Aware Bug Triage: When multiple drivers find the same bug, the AI can use subgraph overlap metrics to distinguish whether the bug is driver-specific or core-reachable. This improves prioritization: bugs found in low-overlap, driver-specific regions are more likely to be configuration-dependent and require distinct fixes, while core-overlap bugs indicate systemic issues.

What the Improved AI System Can Do:

• Achieve significantly higher structural coverage (e.g., +27.9% nodes, +73.5% edges) with the same fuzzing budget by using graph-projected rewards.

• Automatically identify and deprioritize redundant drivers, reducing wasted compute by up to the observed overlap ratios.

• Detect and characterize under-explored code regions in real time, then generate targeted inputs for those regions, reducing residual gaps from heterogeneous tails to localized pockets.

• Provide explainable, graph-based diagnostics for why certain drivers fail or succeed, enabling human developers to write more effective driver configurations.

• Scale to large C/C++ projects (like OSS-Fuzz benchmarks) with minimal overhead, using the lightweight MFuzz/GDissert tooling as a basis for continuous integration.