A Practical and Complete Approach to Predicate Refinement

Ranjit Jhala, Kenneth L. McMillan

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 RELAX procedure 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

Abstract

Predicate abstraction is a method of synthesizing the strongest inductive invariant of a system expressible as a Boolean combination of a given set of atomic predicates. A predicate selection method can be said to be complete for a given theory if it is guaranteed to eventually find atomic predicates sufficient to prove a given property, when such exist. Current heuristics are incomplete, and often diverge on simple examples. We present a practical method of predicate selection that is complete in the above sense. The method is based on interpolation and uses a “split prover”, somewhat in the style of structure-based provers used in artificial intelligence. We show that it allows the verification of a variety of simple programs that cannot be verified by existing software model checkers.
BibTeX
@inproceedings{jhala2006practical,
  author = {Ranjit Jhala and Kenneth L. McMillan},
  title = {{A Practical and Complete Approach to Predicate Refinement}},
  booktitle = {TACAS},
  year = {2006},
  doi = {10.1007/11691372\_33},
}
Figure