Probabilistic Model Checking: Applications and Trends

Marta Kwiatkowska, Gethin Norman, David Parker · 2025

Read Probabilistic Model Checking: Applications and Trends by Marta Kwiatkowska, Gethin Norman, David Parker (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-12968.txt.

Introduction

Marta Kwiatkowska, Gethin Norman and David Parker survey 25 years of probabilistic model checking in 2025. The method builds formal models of random systems. It checks traits with math proof, not just trials. That proof base is what sets it apart from plain simulation.

Main use fields are traced over time, from networks to bio systems and more. Core theory lines and tools that drove growth are summed up. Worked cases show gains such as faults found before build. The survey aims to guide new users to the right tools. It also points to where the field should go next and which open problems matter most.

Catalog record

CREATORMarta Kwiatkowska, Gethin Norman, David Parker
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-12968

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Probabilistic Model Checking: Applications and Trends Marta Kwiatkowska, Gethin Norman, David Parker Abstract Probabilistic model checking is an approach to the formal modelling and analysis of stochastic systems. Over the past twenty five years, the number of different formalisms and techniques developed in this field has grown considerably, as has the range of problems to which it has been applied. In this paper, we identify the main application domains in which probabilistic model checking has proved valuable and discuss how these have evolved over time. We summarise the key strands of the underlying theory and technologies that have contributed to these advances, and highlight examples which illustrate the benefits that probabilistic model checking can bring. The aim is to inform potential users of these techniques and to guide future developments in the field. 1 Introduction Probabilistic model checking [ 10 ] is a technique for the formal verification of stochastic systems. Properties to be verified are specified in temporal logic and then algorithmically checked against a model of the system. Some of the earliest work in the field dates from the 1980s [ 76 , 31 ] , where algorithms were developed for computing the probability that linear temporal logic specifications are satisfied by sequential or concurrent probabilistic programs. The primary motivation was to establish the correctness of randomised algorithms, which had proved to be difficult, particularly in the context of concurrency. Further verification techniques for these models, which are now typically referred to as discrete-time Markov chains (DTMCs) and Markov decision processes (MDPs), were soon developed. The now widely used temporal logic PCTL was proposed for DTMCs [ 42 ] and MDPs [ 18 ] , expanding the range of properties that could be specified. Cited motivations included verifying the performance and reliability of, e.g., computer networks. An extension of PCTL to the continuous-time setting was proposed in the late 1990s, called CSL [ 6 ] . This was designed for continuous-time Markov chains (CTMCs), a well established model for assessing performance and dependability properties of computing and communication systems. Efficient model checking algorithms were also developed [ 8 ] . The further integration of costs and rewards, well-known notions from Markov modelling, into the probabilistic model checking framework led to additional temporal logics [ 44 ] , allowing a modeller to reason about other quantitative characteristics such as power consumption. The flexibility of these formalisms meant that they applied equally well in non-traditional application domains such as biological systems. For the model of MDPs, interest grew in synthesising “correct-by-construction” controllers or policies, using temporal logic to specify the desired behaviour of the system under control. Existing temporal logics and model checking algorithms were extended to incorporate various cost- and reward-based measures and multi-objective specifications [ 37 ] . This opened up new applications, including a variety of scheduling and planning problems. Probabilistic variants of the timed automata formalism, extending MDPs with clocks, allowed modelling of stochastic systems with real-time constraints and delays [ 64 ] . Fast forwarding to the present day, we observe a further significant expansion to the range of stochastic models for which temporal logics and model checking algorithms have been developed [ 57 ] : partially observable variants of MDPs, widely used in AI and planning, allow modelling of autonomous systems with unreliable sensors or of security protocols deploying secret keys; stochastic games provide reasoning about agents operating either competitively or collaboratively in probabilistic settings; and uncertain (or robust) Markov models formally capture epistemic uncertainty resulting, e.g., from data driven modelling. To back up these advances in modelling formalisms and property specification languages, tool support has evolved and is now readily available. This comes in the form of both mature, general-purpose probabilistic model checkers, such as PRISM [ 56 ] , Storm [ 47 ] or the Modest toolset [ 43 ] , and various specialised verification tools [ 5 ] . A multitude of larger tool-chains and software frameworks have also been built, as probabilistic model checkers have become more robust and offer a variety of file formats and APIs with which to interface. The availability of this software, combined with the breadth of available formalisms, have seen probabilistic model checking used in a large and diverse range of applications, both within and outside computer science. In this paper, we provide an overview of the broad range of problems to which probabilistic model checking has been applied, with a view to showcasing the current state of the field and giving some insight into its history. We identify a number of key areas in which the techniques have been particularly successful and consider how these have evolved over time, from the early work in the field to the present day. We also draw out the particular characteristics of the methods that make it well suited to each application area, and mention some of the key developments in theories and technologies that have been leveraged. Throughout, we highlight various case studies, illustrating the different ways in which probabilistic model checking can be deployed, the types of insight it can bring and the diversity of its usage. We hope that this paper therefore also serves as a guide to both current and potential users when selecting a formalism and analysis method for a given target application. 2 Applications of Probabilistic Model Checking In the following sections we discuss, in loosely chronological order, a selection of key application areas for probabilistic model checking. For context, Figure 1 presents a graphical illustration of how these areas have evolved over time. For this visualisation, we considered application-oriented publications from the online bibliography of the PRISM model checker [ 81 ] , in which many of the examples mentioned in this paper can be found. We categorise them according to the areas discussed below and show the publications that appeared in each year. Figure 1 : Categorisation of approximately 400 application-oriented publications from the PRISM bibliography [ 81 ] , illustrating how applications have evolved. 2.1 Randomised distributed algorithms Motivated by the success of existing model checking techniques in identifying bugs and unexpected behaviour in concurrent systems, a fruitful initial area of study for probabilistic verification was randomised distributed algorithms . In this setting, the use of randomisation is a crucial tool for breaking symmetry between concurrent processes, in order to establish correct termination or fairness between participants. However, the subtle interaction between the parallelisation of processes and their probabilistic behaviour makes it challenging to formally reason about their correctness or evaluate their efficiency. Probabilistic model checking was used to analyse the correctness and efficiency of various randomised distributed algorithms, including for consensus, byzantine agreement, leader election and self-stabilisation [ 62 ] . MDPs (and the closely related model of probabilistic automata) are ideally suited to modelling the mixture of stochasticity and concurrency that arises here. In some cases (e.g., fully synchronous settings), DTMCs are also a useful model. The scalability of verification techniques to these applications was enhanced significantly by the development of symbolic implementations of probabilistic model checking, based on (multi-terminal) binary decision diagrams [ 7 , 66 ] . While the size of the state spaces of the models grows rapidly, the high degree of regularity and

Read the complete text