Abstract
FShell is an automated white-box test-input generator for C programs, computing test data with respect to user-specified code coverage criteria. The pillars of FShell are the declarative specification language FQL (FShell Query Language), an efficient back end for computing test data, and a mathematical framework to reason about coverage criteria. To solve the reachability problem posed in the Software Verification Competition (SV-COMP), we specify coverage of ERROR labels. As a back end, FShell uses bounded model checking, building upon components of CBMC and leveraging the power of SAT solvers for efficient enumeration of a full test suite.
Introduction
In software verification, a significant gap often exists between traditional testing (executing code to find bugs) and formal verification (mathematically proving safety). The Software Verification Competition (SV-COMP) highlights this through the reachability problem: determining if a program can ever reach a specific "ERROR" label under any possible input. While traditional testing may miss these labels in large input spaces, full formal verification can be computationally prohibitive for complex C programs. FShell bridges this gap using a "query-driven" approach to automate the generation of white-box test inputs targeting these specific code locations.
Methodology
FShell's architecture is built on three main pillars that transform program analysis into a query-based task:
- FQL (FShell Query Language): A declarative language allowing users to specify coverage criteria (e.g., "reach this specific error label") as if they were querying a database.
- Trace Automata: FShell translates FQL queries into mathematical state machines (automata) representing the execution paths that satisfy the user's query.
- Bounded Model Checking (BMC) Back End: Leveraging the CBMC engine, FShell converts the C program and the trace automata into a massive Boolean equation. If a solution exists, a SAT solver (MiniSat) finds it, which is then converted back into a concrete test input.
The process concludes with Test Suite Minimization. Since multiple inputs might cover the same code paths, FShell treats this as a "minimum set cover" problem, using SAT instances to prune the test suite to its smallest possible size.
Evaluation and Results
The tool was evaluated using benchmarks from SV-COMP, specifically focusing on categories like ControlFlowInteger (complex branching logic) and DeviceDrivers (hardware driver code).
Key Insights
- Query-Driven Testing: By treating program analysis as a database query, FShell allows for flexible, targeted testing strategies rather than hard-coded ones.
- BMC for Test Generation: While BMC is typically used to prove properties, FShell uses it to find specific inputs that make a "bad" property true, effectively repurposing a verification engine into a high-powered test generator.
- Precision over Soundness: FShell prioritizes finding real bugs. By disabling "early aborts" on unbounded loops, the tool can identify reachable errors (UNSAFE results) even when it cannot mathematically prove a program is SAFE for all possible iterations.
Performance
FShell demonstrated high precision, being one of only two participants in the competition that never reported a false positive (spurious "UNSAFE"). It correctly determined results for over 70% of instances in the targeted categories. However, its overall score (19%) was impacted by the competition's scoring system, which penalizes tools that cannot provide definitive "SAFE" proofs for programs with unbounded loops.
Limitations and Future Work
As a bounded model checker, FShell is inherently incomplete; it may wrongly report a program as "SAFE" if a bug exists beyond the checked loop iterations. Additionally, the version evaluated did not support multi-threaded programs (concurrency). Future work aims to improve the back-end robustness to handle more complex categories and refine the distinction between "SAFE" and "UNKNOWN" results when loop bounds are reached.
Summary updated