Skip to Main content Skip to Navigation
Conference papers

Importance Splitting for Statistical Model Checking Rare Properties

Cyrille Jegourel 1 Axel Legay 1 Sean Sedwards 1 
1 ESTASYS - Efficient STAtistical methods in SYstems of systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Statistical model checking avoids the intractable growth of states associated with probabilistic model checking by estimating the probability of a property from simulations. Rare properties are often important, but pose a challenge for simulation-based approaches: the relative error of the estimate is unbounded. A key objective for statistical model checking rare events is thus to reduce the variance of the estimator. Importance splitting achieves this by estimating a sequence of conditional probabilities, whose product is the required result. To apply this idea to model checking it is necessary to define a score function based on logical properties, and a set of levels that delimit the conditional probabilities. In this paper we motivate the use of importance splitting for statistical model checking and describe the necessary and desirable properties of score functions and levels. We illustrate how a score function may be derived from a property and give two importance splitting algorithms: one that uses fixed levels and one that discovers optimal levels adaptively.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Cyrille Jegourel Connect in order to contact the contributor
Submitted on : Wednesday, November 26, 2014 - 5:24:12 PM
Last modification on : Monday, July 25, 2022 - 3:28:32 AM
Long-term archiving on: : Friday, April 14, 2017 - 7:53:18 PM


Files produced by the author(s)



Cyrille Jegourel, Axel Legay, Sean Sedwards. Importance Splitting for Statistical Model Checking Rare Properties. Computer Aided Verification, Jul 2013, Saint-Pétersbourg, Russia. pp.576 - 591, ⟨10.1007/978-3-642-39799-8_38⟩. ⟨hal-01087826⟩



Record views


Files downloads