Advanced Saturation-based Model Checking of Well-formed Coloured Petri Nets

Abstract

The failure of safety-critical embedded systems may have catastrophic consequences, therefore their development process requires a strong verification procedure to obtain a high confidence of correctness in the specification and implementation. Formal modelling and model checking provides a rigorous, mathematically precise verification method. Practical embedded systems are typically complex, distributed and asynchronous, thus they need expressive and compact formal models, and efficient model checking approaches.

The saturation algorithm has an efficient iteration strategy. Combined with symbolic data structures, it can be used for state space generation and model checking of asynchronous systems. Coloured Petri nets are a good choice for modelling distributed and asynchronous systems, however their integration with saturation has not been solved in the past. In this paper we describe a new approach for applying saturation-based state space generation and model checking to coloured Petri nets. We demonstrate the performance of our new algorithm on the verification of a safety function used in the Reactor Protection System of a nuclear power plant.