Parametrised Compositional Verification with Multiple Process and Data Types
Antti Siirtola, Keijo Heljanko · 2013
We present an LTS-based (Labelled Transition System) CSP-like (Communicating Sequential Processes) formalism for expressing parametrised systems. The parameters are process types, which determine the number of replicated components, and data types, which enable components with a parametrised state space. We prove that the formalism is compositional and show how to combine two existing results for parametrised verification in order to check trace refinement between parametrised processes. The combined approach gives upper bounds, i.e., cut-offs, for types such that a parametrised verification task collapses into finitely many checks solvable by using existing finite state refinement checking tools. We have implemented the approach and applied it to prove mutual exclusion properties of network protocols and systems with shared resources. To the best our knowledge, our technique is the only one that combines compositionality and completeness with support for multiple parametric process and data types.