Combining theorem proving with model checking through predicate abstraction

This article presents a procedure for proving invariants of infinite-state reactive systems using a combination of two formal verification techniques: theorem proving and model checking. This method uses term rewriting on the definition of the target system to reduce an invariant proof of the target system to a reachability analysis on a finite predicate abstraction, which can be discharged through model checking. The method affords substantial automation in invariant proofs, while preserving the expressiveness and control afforded by theorem proving. The authors discuss how their approach enables the two disparate techniques, theorem proving and model checking, to complement one another. The procedure has been interfaced with the ACL2 theorem prover, and the authors describe its use in verifying cache coherence protocols in ACL2. © 2007 IEEE.