Compositional Verification of Concurrent Systems by Combining Bisimulations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Formal Methods in System Design Année : 2021

Compositional Verification of Concurrent Systems by Combining Bisimulations

Résumé

One approach to verify a property expressed as a modal μ-calculus formula on a system with several concurrent processes is to build the underlying state space compositionally (i.e., by minimizing and recomposing the state spaces of individual processes in a hierarchical way, keeping visible only the relevant actions occurring in the formula), and check the formula on the resulting state space. It was shown previously that, when checking the formulas of the Lμ-dbr fragment of the μ-calculus (consisting of weak modalities only), individual processes can be minimized modulo divergence-preserving branching (div\-branching for short) bisimulation. In this paper, we refine this approach to handle formulas containing both strong and weak modalities, so as to enable a combined use of strong or div\-branching bisimulation minimization on concurrent processes depending whether they contain or not the actions occurring in the strong modalities of the formula. We extend Lμ-dbr with strong modalities and show that the combined minimization approach preserves the truth value of formulas of the extended fragment. We implemented this approach on top of the CADP verification toolbox and demonstrated how it improves the capabilities of compositional verification on realistic examples of concurrent systems. In particular, we applied our approach to the verification problems of the RERS 2019 challenge and observed drastic reductions of the state space compared to the approach in which only strong bisimulation minimization is used, on formulas not preserved by div\-branching bisimulation.
Fichier principal
Vignette du fichier
Lang-Mateescu-Mazzanti-21.pdf (974.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03159616 , version 1 (04-03-2021)
hal-03159616 , version 2 (10-09-2021)

Identifiants

Citer

Frederic Lang, Radu Mateescu, Franco Mazzanti. Compositional Verification of Concurrent Systems by Combining Bisimulations. Formal Methods in System Design, 2021, ⟨10.1007/s10703-021-00360-w⟩. ⟨hal-03159616v2⟩
175 Consultations
153 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More