Introduction
Software verification is a critical yet challenging process aimed at ensuring program correctness. Modern software systems often feature complex control flows and intricate conditions that lead to "state space explosion," where the number of possible execution paths exceeds the analytical capacity of traditional tools. To address this, hybrid verification approaches combine Fuzzing—using random inputs to detect crashes—with Bounded Model Checking (BMC), which mathematically proves properties within defined depths.
However, these hybrid tools typically possess numerous configuration flags, such as solver selection and loop unwinding depths, which require expert tuning. Most users rely on default settings, often leading to suboptimal performance, excessive resource consumption, or missed vulnerabilities. FuSeBMC AI addresses this by integrating machine learning to automatically predict optimal configuration flags for C programs.
Methodology: The AI-Driven Verification Workflow
FuSeBMC AI introduces a machine-learning layer atop the existing FuSeBMC engine to automate parameter tuning. The system operates through a three-stage pipeline:
- Feature Extraction: The tool performs static analysis on the "Program Under Test" (PUT) to identify structural characteristics. These features include the count and average depth of various loop types (
for,while,do-while), the complexity ofif-elseconditions, and the presence of non-deterministic function calls. - ML Prediction: Extracted features are processed by machine learning models, including Decision Tree Classification (DTC), Support Vector Classification (SVC), and Neural Network Regression (NNR).
- Optimization: The models predict the most effective combination from 384 possible configuration flags. These flags govern the verification strategy, the underlying mathematical solver (e.g., Boolector or Z3), and loop "unwinding" parameters.
The core innovation lies in framing configuration as a classification task. Models are trained to predict an "output class" (ranging from 0 to 5), where lower classes indicate faster bug detection or superior code coverage.
Datasets and Training
The ML models were developed using industry-standard benchmarks:
- SV-Comp Benchmarks: Utilized for initial training across categories such as memory safety and termination.
- Test-Comp 2024 Benchmarks: Served as the primary evaluation set, encompassing 3,352 benchmarks focused on branch coverage and error detection.
- Training Data Generation: To build a robust dataset, the authors executed 111 benchmarks across all 384 flag combinations, resulting in 55,488 training samples.
Key Insights
- Structural Predictability: A program's physical structure, particularly loop nesting depth, serves as a reliable indicator for the most effective formal verification strategy.
- State Space Reduction: By accurately predicting loop "unwinding" times, the ML model minimizes the state space the BMC engine must explore, preventing it from stalling on infinite loops.
- Intelligent Orchestration: Rather than replacing the underlying engines, the AI optimizes their application, ensuring the right tools are used for specific code structures.
Results and Evaluation
Evaluations conducted during the Test-Comp 2024 competition demonstrated that FuSeBMC AI significantly outperforms default configurations:
- Resource Efficiency: The tool achieved an 86% reduction in resource consumption for "ControlFlow" programs and an 84% reduction in the "Termination" category while maintaining coverage.
- Enhanced Coverage: Code coverage improved by 4% for BusyBox memory safety tests and 1.2% for hardware-related benchmarks.
- Overall Impact: Across all categories, FuSeBMC AI reduced total resource utilization by approximately 3% without compromising the quality of generated test cases.
Limitations and Future Work
While effective, the current ML models are dependent on the diversity of their training data, which primarily consists of competition benchmarks. Future research will focus on expanding the dataset to include more varied program structures and applying the methodology to large-scale, real-world open-source projects to validate its general-purpose utility.
Summary updated