Predicate Abstraction for Infinite State Verification

27 concepts22 papers1 proposal

When verifying the correctness of software or hardware systems, formal methods frequently run into the "state explosion problem." If a program contains a few 32-bit integers, the number of possible concrete states is astronomically large; if it involves continuous physical variables or unbounded loops, the state space becomes mathematically infinite. Standard model checking, which relies on exploring individual states, fails completely in these domains.

Predicate abstraction solves this problem by shifting the focus from concrete values to logical properties. Instead of tracking whether an integer variable x is 1, 2, or 5,000,000, we track the truth values of a small set of Boolean predicates, such as $P_1 \equiv (x > 0)$ or $P_2 \equiv (x == y)$. By grouping an infinite or massive set of concrete data states into a finite number of equivalence classes defined by these formulas, we can transform an intractable verification problem into a simple, finite-state symbolic model.

The Mechanics of Boolean Programs

The foundational application of predicate abstraction involves translating complex source code into a simplified "Boolean program." In a Boolean program, all original variables are discarded, and the state is represented entirely by a vector of Boolean variables, each corresponding to a specific predicate over the original variables.

As detailed by Thomas Ball 0001 et al. in The SLAM project: debugging system software via static analysis, this transformation preserves the control flow of the original program while drastically reducing data complexity. When the original code executes an assignment statement, an automated theorem prover or Satisfiability Modulo Theories (SMT) solver determines how the truth values of the abstract predicates should change. This methodology was successfully scaled to industrial software verification by Thomas Ball 0001 et al. in SLAM and Static Driver Verifier: Technology Transfer of Formal Methods inside Microsoft, demonstrating that abstracting C programs into Boolean programs makes verifying complex interface usage rules computationally tractable.

Concrete Program                     Abstract Boolean Program
----------------                     ------------------------
int x = 0;                           // Predicate P is (x == 0)
x = x + 1;                           bool P = true;
if (x > 0) { ... }                   P = false; // Evaluated via SMT
                                     if (!P) { ... }

This logical state modeling is not restricted to scalar variables. Thomas Reps et al. in Static Program Analysis via 3-Valued Logic demonstrated that predicate-based abstraction can model complex heap structures and pointer relationships. By defining how operations modify the truth values of predicates using a 3-valued logic (true, false, and unknown), the authors formally tracked dynamic memory configurations without manual implementation proofs.

Counterexample-Guided Abstraction Refinement

Because predicate abstraction groups many concrete states together, it acts as an over-approximation. It captures all behaviors of the original program, but it can also introduce "spurious behaviors"—paths through the abstract model that are physically impossible in the real code.

To resolve this, verification frameworks employ a loop called Counterexample-Guided Abstraction Refinement (CEGAR). When an abstract model checker finds a path leading to an error state, a bit-precise solver evaluates whether that path can actually be executed by the concrete code. If the path is a false alarm, the solver identifies the boundary where the abstraction failed and extracts new predicates to refine the model, systematically eliminating the spurious behavior.

  +--------------------------------------------------+
  |                                                  |
  v                                                  |
[Extract Predicates] -> [Build Abstract Model] -> [Check Safety]
                                                       |
                                                       v
        [Refine Predicates] <- Spurious? <- (Error Found) or (Safe! -> Done)

This refinement loop is highly versatile. Gérard Basler et al. implemented this in satabs: A Bit-Precise Verifier for C Programs - (Competition Contribution), utilizing bit-vector logic to ensure low-level software properties remain precise.

Furthermore, the mechanism extends directly to hardware verification. Daniel Kroening et al. developed VCEGAR: Verilog CounterExample Guided Abstraction Refinement, which applies word-level predicate abstraction to Register Transfer Level (RTL) designs. By tracking Boolean properties of high-level registers rather than flattening the design into individual bits, the authors preserved structural information and avoided the state explosion typical of gate-level netlists.

Bridging Continuous and Infinite Domains

The true power of predicate abstraction becomes apparent when moving beyond standard software into systems that mix discrete logic with continuous physical dynamics, such as Cyber-Physical Systems (CPS). As emphasized by Richard M. Murray et al. in Verification of Cyber-Physical Systems (Dagstuhl Seminar 14122), abstraction techniques are vital to simplify these complex behaviors for formal analysis.

By integrating SMT solvers with predicate abstraction, researchers can map continuous real-valued states into discrete symbolic regions. Alessandro Cimatti et al. demonstrated in SMT-Based Verification of Hybrid Systems that background mathematical theories (like linear arithmetic) allow for the formal verification of hybrid automata networks that would otherwise be computationally intractable.

Rather than exploring every possible real value, verification tools can focus exclusively on the boundaries where system behavior changes. For example, Guy Katz in Towards Repairing Scenario-Based Models with Rich Events leveraged SMT solvers to partition infinite state spaces containing continuous variables into finite transition graphs, enabling automated safety repairs without altering the underlying source code.

This strategy also scales to multi-agent environments. Panagiotis Kouvaros et al. in Parameterised Verification of Infinite State Multi-Agent Systems via Predicate Abstraction tackled "doubly unbounded" systems—those containing both an unlimited number of agents and agents with infinite-state variables—by mapping continuous or integer-based domains into discrete symbolic regions, reducing the verification task to a small, finite model check.

Probabilistic and Stochastic Extensions

Predicate abstraction is not limited to deterministic systems; it has been adapted to handle non-determinism and probability. Mark Kattenbelt et al. introduced language-level predicate abstraction for probabilistic models in Game-Based Probabilistic Predicate Abstraction in PRISM, replacing concrete variables with Boolean predicates to generate tighter verification bounds for massive probabilistic state spaces.

When failures occur in stochastic settings, isolating the root cause is notoriously difficult. Kenneth Rogale et al. in Efficient Discovery of Actual Causality in Stochastic Systems combined predicate abstraction with an iterative refinement loop to simplify stochastic models, allowing SMT solvers to efficiently pinpoint the actual causes of failures.

Similarly, the search for complex mathematical invariants can be cast as a discrete constraint satisfaction problem. Yuki Satake et al. in Probabilistic Inference for Predicate Constraint Satisfaction mapped infinite-state search spaces into finite Boolean domains by representing potential invariants as combinations of base predicates, solving branching-time properties via probabilistic inference.

Advanced Frontiers: Templates, Summaries, and Learning

To maximize efficiency, modern research focuses on optimizing how predicates are grouped, structured, or learned. One optimization involves restricting the search space for invariants to specific structural templates. Shaz Qadeer et al. demonstrated in Intra-module Inference that restricting the search to monomial templates reduces the complexity of inferring internal module annotations from PSPACE-complete to Co-NP complete, making large-scale software verification practical.

In data-aware dynamic systems that incorporate linear arithmetic, researchers rely on identifying a semantic property known as a "finite summary." As proven by Paolo Felli et al. in Linear-Time Verification of Data-Aware Dynamic Systems with Arithmetic, tracking the symbolic relationships between values instead of exact numerical data allows infinite configurations to be aggregated into a finite set of symbolic states. The authors extended this concept to runtime monitoring in Monitoring Arithmetic Temporal Properties on Finite Traces, constructing finite-state monitors for properties that involve continuous or unbounded arithmetic variables.

This core principle of grouping infinite inputs into symbolic predicates also underpins modern automata learning. Kengo Irie et al. introduced an active learning algorithm in Active Learning of Symbolic Mealy Automata that generalizes concrete input-output observations into symbolic ranges. By grouping inputs that trigger identical system behaviors, a finite state model can successfully learn and represent transitions over entirely infinite input domains.

Finally, predicate abstraction can guide the synthesis of systems. Jie Fu et al. in Abstractions and sensor design in partial-information, reactive controller synthesis combined predicate abstraction with CEGAR to partition continuous coordinates into discrete regions of interest. This allowed the framework to automatically synthesize reactive robotic controllers and determine the exact sensing capabilities required to complete a task.

Key Foundational Work

The SLAM project: debugging system software via static analysis (2002) — contributed 2 concept elements to this direction.
SLAM and Static Driver Verifier: Technology Transfer of Formal Methods inside Microsoft (2004) — contributed 2 concept elements to this direction.
Static Program Analysis via 3-Valued Logic (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_predicate_abstraction_af9cb379,
  title = {predicate abstraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/predicate-abstraction/rdr_af9cb3797d584311a9d774bc44e41569},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_predicate_abstraction_af9cb379_v1,
  title = {predicate abstraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/predicate-abstraction/rdr_af9cb3797d584311a9d774bc44e41569/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake