×

Constructing quantified invariants via predicate abstraction. (English) Zbl 1202.68251

Steffen, Bernhard (ed.) et al., Verification, model checking, and abstract interpretation. 5th international conference, VMCAI 2004, Venice, Italy, January 11–13, 2004. Proceedings. Berlin: Springer (ISBN 3-540-20803-8/pbk). Lect. Notes Comput. Sci. 2937, 267-281 (2004).
Summary: Predicate abstraction provides a powerful tool for verifying properties of infinite-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 where the system state contains mutable function and predicate state variables. Such a model can describe systems containing arbitrarily large memories, buffers, and arrays of identical processes. We describe a form of predicate abstraction that constructs a formula over a set of universally quantified variables to describe invariant properties of the function state variables. We provide a formal justification 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 with unbounded FIFO channels.
For the entire collection see [Zbl 1031.68005].

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: DOI