Accession Number:

ADA250924

Title:

Symbolic Model Checking: An Approach to the State Explosion Problem

Descriptive Note:

Doctoral thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1992-05-01

Pagination or Media Count:

212.0

Abstract:

Finite state models of concurrent systems grow exponentially as the number of components of the system increases. This is known widely as the state explosion problem in automatic verification, and has limited finite state verification methods to small systems. To avoid this problem, a method called symbolic model checking is proposed and studied. This method avoids building a state graph by using Boolean formulas to represent sets and relations. A variety of properties characterized by least and greatest fixed points can be verified purely by manipulations of these formulas using Ordered Binary Decision Diagrams. Theoretically, a structural class of sequential circuits is demonstrated whose transition relations can be represented by polynomial space OBDDs, though the number of states is exponential. This result is born out by experimental results on example circuits and systems. The most complex of these is the cache consistency protocol of a commercial distributed multiprocessor. The symbolic model checking technique revealed subtle errors in this protocol, resulting from complex execution sequences that would occur with very low probability in random simulation runs. formal verification, temporal logic, model checking, state explosion problem, symbolic model checking, binary decision diagrams. cache consistency, cache coherence. protocol verification. hardware description languages, SMV, asynchronous circuits, Petri nets. occurrence nets, process invariants.

Subject Categories:

  • Electrical and Electronic Equipment

Distribution Statement:

APPROVED FOR PUBLIC RELEASE