Carnegie Mellon University
Browse

Indexed Predicate Discovery for Unbounded System Verification

journal contribution
posted on 2004-01-01, 00:00 authored by Shuvendu K. Lahiri, Randal BryantRandal Bryant

Predicate abstraction has been proved effective for verifying several
infinite-state systems. In predicate abstraction, an abstract system is automatically constructed given a set of predicates. Predicate abstraction coupled with automatic predicate discovery provides for a completely automatic verification scheme. For systems with unbounded integer state variables (e.g. software), counterexample guided predicate discovery has been successful in identifying the necessary
predicates.
For verifying systems with function state variables, which include systems with
unbounded memories (microprocessors), arrays in programs, and parameterized systems, an extension to predicate abstraction has been suggested which uses predicates with free (index) variables. Unfortunately, counterexample guided predicate discovery is not applicable to this method. In this paper, we propose a simple heuristic for discovering indexed predicates. We illustrate the effectiveness of the approach for verifying safety properties of two systems: (i) a version of the Bakery mutual exclusion protocol, and (ii) a directory-based cache coherence protocol with unbounded FIFO channels per client.

History

Publisher Statement

All Rights Reserved

Date

2004-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC