Efficient deadlock detection for concurrent systems
Saddek Bensalem, Andreas Griesmayer, Axel Legay, Thanh-Hung Nguyen, Doron Peled · 2011
Concurrent systems are prone to deadlocks that arise from competing access to shared resources and synchronization between the components. At the same time, concurrency leads to a dramatic increase of the possible state space due to interleavings of computations, which makes standard verification techniques often infeasible. Previous work has shown that approximating the state space of component based systems by computing invariants allows to verify much larger systems then standard methods that compute the exact state space. The approach comes with the drawback, though, that not all of the reported specification violations may be reachable in the system. This paper deals with that problem by combining the information from the invariant with model checking techniques and strategies for reducing the memory footprint. The approach is implemented as post processing step for generating the exact set of reachable specification violations along with traces to demonstrate the error.