Protocol checking for concurrent systems

Abstract

A verification of the protocol between the various communicating elements of a concurrent system may be performed directly using the actual code that implements the element when it is actually operating. This is achieved by combining stateless search techniques with partial order methods, namely, persistent set and sleep set methods. In particular, the code of each element of a system is exercised by a scheduler in such a way that global states of the system are visited according to a stateless search, which is a search that does not use an explicit representation of the global states. A global state is a state in which the next operation to be executed by every element of the system is a visible operation. The set of visible operations includes at least those operations related to communication between the elements. The global states are visited using an intelligent state space exploration technique so that only a selected subset of all the global states are visited while ensuring that those global states that are not visited need not be visited to verify the existence or absence of selected problems that might exist in the protocol. Such selected properties can include the existence of 1) deadlocks, 2) assertion violations, 3) divergences, and 4) livelocks. Advantageously, complex protocols in systems having many elements may be efficiently verified, while using prior art comprehensive search techniques could not verify even a simplistic toy protocol within a reasonable amount of time.