A Heuristics-Based Incremental Probabilistic Model Checking at Runtime

摘要

Nowadays, more and more systems change during their life cycle dynamically, runtime probabilistic model checking is proposed to verify these systems. An important challenge of runtime probabilistic model checking is its performance. It should be fast enough to respond to runtime requirements and continuously verify whether the current system meets system requirements when the system changes dynamically. In this paper, in view of the efficiency of the runtime probabilistic model checking, we propose a heuristics-based incremental probabilistic model checking at runtime, which introduced the idea of incremental verification and developed a heuristic method to improve their performance. The heuristics reduce the number of numerical iterations in the verification process by reordering the state of the model after the model changes. We implement our method in model checking tool PRISM, and use two types of benchmark case models in PRISM to perform model verification on its reachability properties. The results of the experiments show that the method we proposed in this paper can reduce the system verification time of standard runtime probabilistic model checking by more than 40%.