Computer Science Department
School of Computer Science, Carnegie Mellon University
Statistical Model Checking for
David Henriques*, Joâo Martins**, Paolo Zuliani,
This technical report is a more detailed version of a published paper:
Statistical Model Checking (SMC) is a computationally very efficient verification technique based on selective system sampling. One well identified shortcoming of SMC is that, unlike probabilistic model checking, it cannot be applied to systems featuring nondeterminism, such as Markov Decision Processes (MDP). We address this limitation by developing an algorithm that resolves nondeterminism probabilis- tically, and then uses multiple rounds of sampling and Reinforcement Learning to provably improve resolutions of nondeterminism with respect to satisfying a Bounded Linear Temporal Logic (BLTL) prop- erty. Our algorithm thus reduces an MDP to a fully probabilistic Markov chain on which SMC may be applied to give an approxi- mate solution to the problem of checking the probabilistic BLTL prop- erty. We integrate our algorithm in a parallelised modifiation of the PRISM simulation framework. Extensive validation with both new and PRISM benchmarks demonstrates that the approach scales very well in scenarios where symbolic algorithms fail to do so.