Efficient verification of comcurrent systems using local analysis based approximations and SAT solving

Journal article

This work develops a type of local analysis that can prove concurrent systems deadlock free. As opposed to examining the overall behaviour of a system, local analysis consists of examining the behaviour of small parts of the system to yield a given property. We analyse pairs of interacting components to approximate system reachability and propose a new sound but incomplete/approximate framework that checks deadlock and local-deadlock freedom. By replacing exact reachability by this approximation, it looks for deadlock (or local-deadlock) candidates, namely, blocked (locally-blocked) system states that lie within our approximation. This characterisation improves on the precision of current approximate techniques. In particular, it can tackle non-hereditary deadlock-free systems, namely, deadlock-free systems that have a deadlocking subsystem. These are neglected by most approximate techniques. Furthermore, we demonstrate how SAT checkers can be used to efficiently implement our framework, which, typically, scales better than current techniques for deadlock-freedom analysis. This is demonstrated by a series of practical experiments.

Authors: Antonino, P; Gibson-Robinson, T; Roscoe, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Formal Aspects of Computing
• Volume: 31
• Issue: 3
• Pages: 375–409
• Publication date: 2019-05-13
• Acceptance date: 2019-04-10
• DOI: 10.1007/s00165-019-00483-2
• ISSN: 0934-5043
• Keywords: model checking; deadlock freedom; SAT solving; local analysis; approximate verification; approximate reachability; formal verification