Efficient verification of concurrent systems using synchronisation analysis and SAT/SMT solving

Journal article

This article investigates how the use of approximations can make the formal verification of concurrent systems scalable. We propose the idea of synchronisation analysis to automatically capture global invariants and approximate reachability. We calculate invariants on how components participate on global system synchronisations and use a notion of consistency between these invariants to establish whether components can effectively communicate to reach some system state. Our synchronisation-analysis techniques try to show either that a system state is unreachable by demonstrating that components cannot agree on the order they participate in system rules or that a system state is unreachable by demonstrating components cannot agree on the number of times they participate on system rules. These fully automatic techniques are applied to check deadlock and local-deadlock freedom in the PairStatic framework. It extends Pair (a recent framework where we use pure pairwise analysis of components and SAT checkers to check deadlock and local-deadlock freedom) with techniques to carry out synchronisation analysis. So, not only can it compute the same local invariants that Pair does, it can leverage global invariants found by synchronisation analysis, thereby improving the reachability approximation and tightening our verifications. We implement PairStatic in our DeadlOx tool using SAT/SMT and demonstrate the improvements they create in checking (local) deadlock freedom.

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

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Software Engineering and Methodology
• Volume: 28
• Issue: 3
• Article number: 18
• Publication date: 2019-08-17
• Acceptance date: 2019-01-02
• DOI: 10.1145/3335149
• EISSN: 1557-7392
• ISSN: 1049-331X
• Keywords: local-deadlock freedom; synchronisation analysis; reachability approximation; invariants; approximate verification; concurrent systems; SMT solving; deadlock freedom; SAT solving