An Effective Heuristic for Adaptive Importance Splitting in Statistical Model Checking - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

An Effective Heuristic for Adaptive Importance Splitting in Statistical Model Checking

Résumé

Statistical model checking avoids the intractable growth of states associated with numerical model checking by estimating the prob-ability of a property from simulations. Rare properties pose a challenge because the relative error of the estimate is unbounded. In [13] we de-scribe how importance splitting may be used with SMC to overcome this problem. The basic idea is to decompose a logical property into nested properties whose probabilities are easier to estimate. To improve perfor-mance it is desirable to decompose the property into many equi-probable levels, but logical decomposition alone may be too coarse. In this article we make use of the notion of a score function to improve the granularity of a logical property. We show that such a score function may take advantage of heuristics, so long as it also rigorously respects certain properties. To demonstrate our importance splitting approach we present an optimal adaptive importance splitting algorithm and an heuristic score function. We give experimental results that demonstrate a significant improvement in performance over alternative approaches.
Fichier principal
Vignette du fichier
ISOLA2014_v3.pdf (276.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

Cyrille Jegourel, Axel Legay, Sean Sedwards. An Effective Heuristic for Adaptive Importance Splitting in Statistical Model Checking. International Symposium On Leveraging Applications of Formal Methods, Verification and Validation, Oct 2014, Corfou, Greece. pp.143 - 159, ⟨10.1007/978-3-662-45231-8_11⟩. ⟨hal-01087828⟩
209 Consultations
195 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More