Software Model Checking via Summary-Guided Search (Extended Version)

Ruijie Fang, Zachary Kincaid, Thomas Reps

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.

Introduction

Software model checking is a critical field aimed at either proving program safety or identifying concrete bugs (counter-examples). However, existing tools often struggle with two primary failure modes. The first is the "Unreachable" failure, where tools fail to find a general correctness argument because they explore paths individually. The second is the "Reachable" failure, often occurring in what we term "Lock & Key" problems—scenarios where a bug is hidden behind a very long error path or requires a highly specific, non-deterministic input.

While concolic testing is effective at local exploration, it lacks the global perspective needed to solve deep "Lock & Key" scenarios. Conversely, static analysis provides a global view but often lacks the precision to generate concrete test cases. This paper introduces GPS (Guided by Path Summaries), an algorithm that bridges this gap by using compositional static analysis to guide a two-layered search for both bugs and safety proofs.

The GPS Methodology

GPS is built upon three core pillars designed to optimize the search for program states:

  1. Summary-Directed Search: The algorithm utilizes algebraic program analysis to compute "path summaries." These formulas over-approximate the behavior of sets of paths. When a summary suggests an error might be reachable, GPS queries an SMT solver for a model (a specific input) to generate a directed test case.
  2. Dead-End Interpolation: If a generated test fails to reach the target error (a "dead end"), GPS employs Craig interpolation to generalize the reason for failure. This allows the tool to create candidate invariants that can prune entire classes of safe paths from the search space.
  3. Two-Layered Search & "Gas" Instrumentation: GPS interleaves breadth-first search (for path selection) with depth-first search (for test execution). To ensure refutation completeness—the guarantee that a bug will be found if it exists—the program is instrumented with a non-deterministic gas variable. This prevents the executor from becoming trapped in infinite loops while still allowing deep exploration when guided by the SMT solver.
Overview of program EX-2: (a) pseudo-code, (b) control-flow graph, and (c) a generated path tree.

By treating over-approximate summaries as a "compass," GPS can jump directly to extreme depths (e.g., 1,000+ iterations) if the analysis indicates that is where a bug resides, rather than increasing depth linearly like traditional bounded model checkers.

Experimental Evaluation

We evaluated GPS against a suite of 297 benchmarks, including 230 intraprocedural benchmarks from the SV-COMP "ReachSafety-Loops" category and 58 "Lock & Key" problems designed to test scalability relative to bug depth.

GPS demonstrated superior performance, solving 280 out of 297 benchmarks. In comparison, the baseline Impact algorithm solved only 136. When compared to top-tier SV-COMP portfolio tools, GPS solved 214 benchmarks, significantly outperforming VeriAbs (201) and Symbiotic (158). Notably, on "Lock & Key" problems, GPS's execution time remained nearly flat as the required loop iterations increased, whereas other tools timed out as the search space grew.

Conclusion and Future Work

GPS effectively leverages the synergy between static analysis and testing. By using failed tests to generate proofs and using summaries to guide test generation, it achieves a high degree of efficiency in both bug-finding and safety verification.

Current limitations include a focus on Linear Integer Arithmetic (LIA) and intraprocedural scope, without support for pointers or complex heap-allocated structures. Future work will focus on extending GPS to handle richer data types and integrating it with interprocedural engines like Spacer to expand its applicability to larger, more complex software systems.

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 (Extended Version)}},
  booktitle = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  doi = {10.1145/3763142},
}
Figure