Software Model Checking via Summary-Guided Search

Ruijie Fang, Zachary Kincaid, Thomas Reps

TL;DR

The paper introduces GPS (Guided by Path Summaries), a software model-checking algorithm that uses compositional static analysis to guide a two-layered search for both bugs and safety proofs. By leveraging over-approximate path summaries to direct test generation and prune infeasible paths, GPS effectively bridges the gap between formal verification and automated testing, significantly outperforming state-of-the-art tools on complex, input-dependent programs.

What Problem Does This Paper Address?

Software model checking aims to either prove a program is safe or find a counter-example (a bug). However, existing tools often fall into two traps:

  1. The "Unreachable" Failure: Tools fail to prove safety because they explore paths one-by-one, failing to find a general correctness argument that covers all possible executions.
  2. The "Reachable" Failure: Tools fail to find a real bug because the error path is extremely long or requires a very specific, non-deterministic input—what the authors call a "Lock & Key" problem.

Concolic testing (testing combined with symbolic execution) struggles with these "Lock & Key" scenarios because it often lacks the "global" view needed to guess the right input to unlock a deep error state. Static analysis has the global view but is often too imprecise to find concrete bugs. GPS aims to combine the strengths of both.

Methods

GPS is built on three main pillars:

  • Summary-Directed Search: GPS uses algebraic program analysis to compute "path summaries"—formulas that over-approximate the behavior of sets of paths. If a summary indicates an error might be reachable, GPS asks an SMT solver for a "model" (a specific input) to generate a directed test.
  • Dead-End Interpolation: When a generated test fails to reach the error (a "dead end"), GPS doesn't just throw it away. It uses Craig interpolation to generalize why that path failed, creating candidate invariants that can prove an entire class of paths (even infinite sets) is safe.
  • Two-Layered Search & "Gas" Instrumentation: GPS interleaves a breadth-first search (to pick which paths to explore) with a depth-first search (to execute tests). To ensure the algorithm eventually finds a bug if one exists (refutation completeness), the authors instrument programs with a gas variable. This non-deterministic bound prevents the executor from getting stuck in infinite loops while still allowing it to explore very deep paths if the SMT solver suggests they are promising.

Datasets

The authors evaluated GPS on a total of 297 benchmarks:

  • Suite #1 (SV-COMP): 230 intraprocedural benchmarks from the "ReachSafety-Loops" category of the 2024 Software Verification Competition.
  • Suite #2 (Safety Exs): 9 hand-crafted safe programs designed to test complex loop patterns.
  • Suite #3 (Lock & Key): 58 unsafe benchmarks specifically designed to be "Lock & Key" problems. This includes 50 parametrized versions of challenging problems from prior literature where the "key" (the input needed to trigger the bug) is scaled to be increasingly difficult to find.

Key Insights and Ideas

  • Summaries as a Compass: The "aha moment" is realizing that an over-approximate summary—usually used only for proofs—is a fantastic tool for bug-hunting. If the summary is satisfiable, the solver's witness is a high-probability "map" to the bug.
  • Synergy of Failure: GPS turns failed test generation into a verification win. By using interpolants from dead ends, the tool learns to prune massive sections of the search space that it now knows can never lead to an error.
  • Non-Uniform Search: Unlike bounded model checkers that increase depth linearly (1, 2, 3...), GPS’s use of summaries allows it to jump straight to a depth of 1,000 or more if the static analysis suggests that's where the "lock" is.

Key Results

  • Superior Performance: GPS solved 280 out of 297 benchmarks, significantly outperforming the baseline Impact algorithm (which solved 136).
  • Beating the State-of-the-Art: GPS outperformed top-tier portfolio tools from SV-COMP. For instance, it solved 214 SV-COMP benchmarks compared to VeriAbs (201) and Symbiotic (158).
  • Robustness: On "Lock & Key" problems, GPS was nearly immune to the "depth" of the bug. While other tools timed out as the required loop iterations increased, GPS's execution time remained nearly flat because its summaries correctly guided the solver to the right input immediately.

Limitations and Future Work

  • Language Features: The current prototype is limited to Linear Integer Arithmetic (LIA). It does not yet handle pointers, arrays, or heap-allocated data structures.
  • Intraprocedural Scope: The algorithm currently operates on single functions (intraprocedural). While it can in-line some calls, it isn't yet a full interprocedural analyzer.
  • Static Analysis Dependency: GPS is only as good as its underlying summary generator. If the static analysis is too coarse, the "guidance" provided to the test generator becomes less effective.
  • Future Directions: The authors suggest extending GPS to handle richer data types and integrating it with interprocedural engines like Spacer.

Summary updated

Abstract

In this work, we describe a new software model-checking algorithm called GPS. GPS treats the task of model checking a program as a directed search of the program states, guided by a compositional, summary-based static analysis. The summaries produced by static analysis are used both to prune away infeasible paths and to drive test generation to reach new, unexplored program states. GPS can find both proofs of safety and counter-examples to safety (i.e., inputs that trigger bugs), and features a novel two-layered search strategy that renders it particularly efficient at finding bugs in programs featuring long, input-dependent error paths. To make GPS refutationally complete (in the sense that it will find an error if one exists, if it is allotted enough time), we introduce an instrumentation technique and show that it helps GPS achieve refutation-completeness without sacrificing overall performance. We benchmarked GPS on a diverse suite of benchmarks including programs from the Software Verification Competition (SV-COMP), from prior literature, as well as synthetic programs based on examples in this paper. We found that our implementation of GPS outperforms state-of-the-art software model checkers (including the top performers in SV-COMP ReachSafety-Loops category), both in terms of the number of benchmarks solved and in terms of running time.
BibTeX
@inproceedings{fang2025software,
  author = {Ruijie Fang and Zachary Kincaid and Thomas Reps},
  title = {{Software Model Checking via Summary-Guided Search}},
  booktitle = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  doi = {10.1145/3763142},
}

Loading related content...

Figure