Checking bounded reachability in asynchronous systems by symbolic event tracing

Abstract

This report presents a new symbolic technique for checking reachability properties of asynchronous systems by reducing the problem to satisfiability in restrained difference logic. The analysis is bounded by fixing a finite set of potential events, each of which may occur at most once in any order. The events are specified using high-level Petri nets. The logic encoding describes the space of possible causal links between events rather than possible sequences of states as in Bounded Model Checking. Independence between events is exploited intrinsically without partial order reductions, and the handling of data is symbolic. On a family of benchmarks, the proposed approach is consistently faster than Bounded Model Checking. In addition, this report presents a compact encoding of the restrained subset of difference logic in propositional logic.