Introduction
Formal verification often relies on translating programs into logic constraints to prove safety properties. For years, Constrained Horn Clauses (CHCs) have served as the standard for linear-time safety verification—proving that a "bad" state is never reached. However, CHCs struggle with branching-time properties, such as proving that a program has at least one non-terminating execution. These properties require existential quantification and disjunctions in the head of implications, leading to the more general Predicate Constraint Satisfaction Problem (pCSP).
The search space for pCSP solutions is massive and non-smooth. This paper introduces a novel framework that integrates probabilistic inference into a synthesis loop to efficiently navigate this space.
The pCSP Framework and Predicate Abstraction
To solve pCSPs, the authors employ a Counterexample Guided Inductive Synthesis (CEGIS) loop. The process begins with predicate abstraction, which maps the infinite search space of mathematical invariants to a finite Boolean Constraint Satisfaction Problem (bCSP). This abstraction allows the solver to search for true/false assignments over a set of base predicates rather than synthesizing complex formulas from scratch.
Probabilistic Inference via Survey Propagation
The core innovation of this work is the use of Survey Propagation (SP), a probabilistic inference algorithm derived from statistical physics. Instead of using a standard SAT solver to find any valid assignment, the authors utilize Survey Inspired Decimation (SID).
SP identifies "clusters" of solutions within a factor graph (see Figure 1). By sampling from these clusters, the solver can select candidate solutions that are both "simple" (adhering to Occam’s Razor) and "diverse." This diversity prevents the CEGIS loop from getting stuck in local minima and ensures that each iteration provides maximum information gain.
Experimental Evaluation
The proposed solver, PCSAT, was evaluated against standard benchmarks (SyGuS-Comp and CHC-COMP) and a new suite of pCSP problems involving non-termination.
As shown in Figure 3, the SID-based approach significantly outperforms standard SAT solvers. Specifically, using SID with 8 candidate solutions (#cand=8) allowed the solver to pass 100 out of 127 SyGuS instances. Furthermore, PCSAT successfully solved new pCSP benchmarks (e.g., nt-rec) in under 2 seconds—problems that existing CHC solvers are fundamentally unable to express.
Conclusion and Future Work
By combining predicate abstraction with probabilistic inference, this work provides a powerful tool for verifying branching-time properties. While PCSAT is already competitive with state-of-the-art CHC solvers, future work aims to improve engineering maturity and extend the framework to handle infinitely branching systems. A promising direction involves modeling pCSPs directly as factor graphs to bypass the Boolean abstraction step entirely.
Summary updated