Predicate Abstraction with Indexed Predicates

Predicate abstraction provides a powerful tool for verifying properties of innite-state systems using a combination of a decision procedure for a subset of first-order logic and symbolic methods originally developed for finite-state model checking. We consider models containing rst-order state variables, where the system state includes mutable functions and predicates. Such a model can describe systems containing arbitrarily large memories, buers, and arrays of identical pro-cesses. We describe a form of predicate abstraction that constructs a formula over a set of universally quantied variables to describe invariant properties of the first-order state variables. We provide a formal justication of the soundness of our approach and describe how it has been used to verify several hardware and software designs, including a directory-based cache coherence protocol