Importance Splitting for Statistical Model Checking Rare Properties - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Importance Splitting for Statistical Model Checking Rare Properties

Résumé

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.
Fichier principal
Vignette du fichier
CAV2013.pdf (352.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01087826 , version 1 (26-11-2014)

Identifiants

Citer

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⟩
210 Consultations
711 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More