Proving Reachability Using FShell - (Competition Contribution)

Andreas Holzer, Daniel Kroening, Christian Schallhart, Michael Tautschnig, Helmut VeithTACAS 2012 · OpenReview

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:

  1. 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.
  2. Trace Automata: FShell translates FQL queries into mathematical state machines (automata) representing the execution paths that satisfy the user's query.
  3. 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.
Architecture of the FShell toolchain, showing the flow from C source and FQL queries to a minimized test suite.

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

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 SV-COMP we specify coverage of ERROR labels. As 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.
BibTeX
@inproceedings{holzer2012proving,
  author = {Andreas Holzer and Daniel Kroening and Christian Schallhart and Michael Tautschnig and Helmut Veith},
  title = {{Proving Reachability Using FShell - (Competition Contribution)}},
  booktitle = {TACAS},
  year = {2012},
  url = {https://openreview.net/forum?id=go5uKvMR1n},
}
Figure