Compositional Verification in Action

Hubert Garavel, Frédéric Lang, and Laurent Mounier

Proceedings of the 23rd International Conference on Formal Methods for Industrial Critical Systems (FMICS'18), Maynooth, Ireland, volume 11119 of Lecture Notes in Computer Science, pages 189--210, September 2018


Concurrent systems are intrinsically complex and their verification is hampered by the well-known ``state-space explosion'' issue. Compositional verification is a powerful approach, based on the divide-and-conquer paradigm, to address this issue. Despite impressive results, this approach is not used widely enough in practice, probably because it exists under multiple variants that make knowledge of the field hard to attain. In this article, we highlight the seminal results of Graf & Steffen and propose a survey of compositional verification techniques that exploit (or not) these results.

27 pages