Introduction
In software model checking, predicate abstraction is a cornerstone technique used to verify complex, infinite-state programs. By approximating these programs as simpler, finite-state systems based on a set of Boolean predicates (e.g., $x > 0$), tools can reason about program behavior more efficiently. However, the effectiveness of this approach hinges on predicate refinement: the process of discovering new predicates when the current set is insufficient to prove a property.
Historically, refinement heuristics—such as those based on weakest preconditions—have struggled with divergence. In scenarios like a loop incrementing a variable, these tools often generate an infinite sequence of specific predicates (e.g., $x=1, x=2, x=3$) without ever identifying the general invariant (e.g., $x \ge 0$) needed to complete the proof. This paper introduces a "complete" refinement method that ensures if a quantifier-free inductive invariant exists within a given logic, the tool will eventually find it.
Methodology: Restricted Interpolation and the Split Prover
The authors' approach builds on Craig Interpolation, a technique that generates a formula (an interpolant) to explain why a specific execution path is infeasible. To prevent divergence and ensure completeness, the paper introduces three core innovations:
1. $L$-Restricted Interpolants
The primary insight is that restricting a prover's vocabulary can force it to find more general invariants. By defining a language $L$ that initially forbids specific large integer constants, the system is prevented from "chasing" increments. If the prover cannot find an interpolant within the restricted language, it indicates that a more general explanation is required.
2. The RELAX Procedure
To maintain completeness, the authors use the RELAX procedure. This algorithm starts with a highly restrictive language $L_0$. If a proof cannot be found, the algorithm iteratively "relaxes" these restrictions ($L_1, L_2, \dots$), gradually expanding the search space to include more complex predicates and constants. This stratification transforms an infinite search space into a series of finite ones.
3. The Split Prover
Generating restricted interpolants efficiently requires a specialized architecture. The authors developed a Split Prover, which replaces a monolithic theorem prover with a sequence of communicating provers. Each prover is responsible for a single step in a program path and can only communicate with its neighbors using formulas that satisfy the current language restrictions ($L$). This local reasoning mimics human logic, passing only the most relevant abstract information across program steps.
Experimental Evaluation
The proposed method was integrated into the BLAST model checker and evaluated against 13 C programs involving complex loop structures, array manipulations, and string concatenations (e.g., strcpy, strcat). The performance was compared against other leading tools of the time, including SATABS, MAGIC, and the standard version of BLAST.
Key Results
- Effectiveness: The split-prover version of BLAST successfully verified 12 out of 13 programs. In contrast, SATABS and MAGIC failed on all 13 cases, primarily due to predicate divergence.
- Efficiency: Despite the added constraints of restricted communication, the split prover's overhead was negligible. The run-time performance was comparable to standard, unrestricted provers, proving that the approach is a viable drop-in replacement for existing verification engines.
- Generalization: In several test cases, the tool avoided divergence by failing to find an interpolant with specific constants, which immediately forced the discovery of a general invariant at the $L_0$ level.
Limitations and Future Directions
While the approach is a significant step forward, it has specific limitations:
- Quantifier-Free Invariants: The current refinement method only synthesizes quantifier-free predicates. It cannot automatically discover quantified properties, such as "all elements in an array are initialized to zero."
- Theory Support: The implementation is currently optimized for difference bound arithmetic and equality. Extending this to bit-vectors or full linear arithmetic is a subject for future work.
- Heuristic Optimization: In cases requiring large constants (e.g., a loop bound of 200), the
RELAXprocedure may iterate many times before succeeding. Optimizing how the language $L$ is expanded could improve performance in these edge cases.
Conclusion
By combining restricted interpolation with a stratified search strategy, the authors provide a practical solution to the long-standing problem of predicate divergence. The "Split Prover" demonstrates that limiting a tool's vocabulary is not just a theoretical curiosity but a powerful mechanism for forcing the generalization necessary for robust software verification.
Summary updated