Importance Sampling for Stochastic Timed Automata

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

5 Citationer (Scopus)
123 Downloads (Pure)

Resumé

We present an importance sampling framework that combines symbolic analysis and simulation to estimate the probability of rare reachability properties in stochastic timed automata. By means of symbolic exploration, our framework first identifies states that cannot reach the goal. A state-wise change of measure is then applied on-the-fly during simulations, ensuring that dead ends are never reached. The change of measure is guaranteed by construction to reduce the variance of the estimator with respect to crude Monte Carlo, while experimental results demonstrate that we can achieve substantial computational gains.
OriginalsprogEngelsk
TitelDependable Software Engineering : Theories, Tools, and Applications
RedaktørerMartin Fränzle, Deepak Kapur, Naijin Zhan
Antal sider16
ForlagSpringer
Publikationsdato2016
Sider163-178
ISBN (Trykt)978-3-319-47676-6
ISBN (Elektronisk)978-3-319-47677-3
DOI
StatusUdgivet - 2016
BegivenhedSymposium on Dependable Software Engineering Theories, Tools and Applications - Beijing, China, Beijing, Kina
Varighed: 9 nov. 201610 nov. 2016
http://lcs.ios.ac.cn/setta/

Konference

KonferenceSymposium on Dependable Software Engineering Theories, Tools and Applications
LokationBeijing, China
LandKina
ByBeijing
Periode09/11/201610/11/2016
Internetadresse
NavnLecture Notes in Computer Science
Vol/bind9984
ISSN0302-9743

Fingerprint

Importance sampling

Citer dette

Jegourel, C., Larsen, K. G., Legay, A., Mikučionis, M., Poulsen, D. B., & Sedwards, S. (2016). Importance Sampling for Stochastic Timed Automata. I M. Fränzle, D. Kapur, & N. Zhan (red.), Dependable Software Engineering: Theories, Tools, and Applications (s. 163-178). Springer. Lecture Notes in Computer Science, Bind. 9984 https://doi.org/10.1007/978-3-319-47677-3_11
Jegourel, Cyrille ; Larsen, Kim Guldstrand ; Legay, Axel ; Mikučionis, Marius ; Poulsen, Danny Bøgsted ; Sedwards, Sean. / Importance Sampling for Stochastic Timed Automata. Dependable Software Engineering: Theories, Tools, and Applications. red. / Martin Fränzle ; Deepak Kapur ; Naijin Zhan. Springer, 2016. s. 163-178 (Lecture Notes in Computer Science, Bind 9984).
@inproceedings{b980856eef094af89851df0fb5ac2528,
title = "Importance Sampling for Stochastic Timed Automata",
abstract = "We present an importance sampling framework that combines symbolic analysis and simulation to estimate the probability of rare reachability properties in stochastic timed automata. By means of symbolic exploration, our framework first identifies states that cannot reach the goal. A state-wise change of measure is then applied on-the-fly during simulations, ensuring that dead ends are never reached. The change of measure is guaranteed by construction to reduce the variance of the estimator with respect to crude Monte Carlo, while experimental results demonstrate that we can achieve substantial computational gains.",
keywords = "importance sampling, rare events, stochastic timed automata, verification, model checking",
author = "Cyrille Jegourel and Larsen, {Kim Guldstrand} and Axel Legay and Marius Mikučionis and Poulsen, {Danny B{\o}gsted} and Sean Sedwards",
year = "2016",
doi = "10.1007/978-3-319-47677-3_11",
language = "English",
isbn = "978-3-319-47676-6",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "163--178",
editor = "Martin Fr{\"a}nzle and Deepak Kapur and Naijin Zhan",
booktitle = "Dependable Software Engineering",
address = "Germany",

}

Jegourel, C, Larsen, KG, Legay, A, Mikučionis, M, Poulsen, DB & Sedwards, S 2016, Importance Sampling for Stochastic Timed Automata. i M Fränzle, D Kapur & N Zhan (red), Dependable Software Engineering: Theories, Tools, and Applications. Springer, Lecture Notes in Computer Science, bind 9984, s. 163-178, Symposium on Dependable Software Engineering Theories, Tools and Applications, Beijing, Kina, 09/11/2016. https://doi.org/10.1007/978-3-319-47677-3_11

Importance Sampling for Stochastic Timed Automata. / Jegourel, Cyrille; Larsen, Kim Guldstrand; Legay, Axel; Mikučionis, Marius; Poulsen, Danny Bøgsted; Sedwards, Sean.

Dependable Software Engineering: Theories, Tools, and Applications. red. / Martin Fränzle; Deepak Kapur; Naijin Zhan. Springer, 2016. s. 163-178 (Lecture Notes in Computer Science, Bind 9984).

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

TY - GEN

T1 - Importance Sampling for Stochastic Timed Automata

AU - Jegourel, Cyrille

AU - Larsen, Kim Guldstrand

AU - Legay, Axel

AU - Mikučionis, Marius

AU - Poulsen, Danny Bøgsted

AU - Sedwards, Sean

PY - 2016

Y1 - 2016

N2 - We present an importance sampling framework that combines symbolic analysis and simulation to estimate the probability of rare reachability properties in stochastic timed automata. By means of symbolic exploration, our framework first identifies states that cannot reach the goal. A state-wise change of measure is then applied on-the-fly during simulations, ensuring that dead ends are never reached. The change of measure is guaranteed by construction to reduce the variance of the estimator with respect to crude Monte Carlo, while experimental results demonstrate that we can achieve substantial computational gains.

AB - We present an importance sampling framework that combines symbolic analysis and simulation to estimate the probability of rare reachability properties in stochastic timed automata. By means of symbolic exploration, our framework first identifies states that cannot reach the goal. A state-wise change of measure is then applied on-the-fly during simulations, ensuring that dead ends are never reached. The change of measure is guaranteed by construction to reduce the variance of the estimator with respect to crude Monte Carlo, while experimental results demonstrate that we can achieve substantial computational gains.

KW - importance sampling

KW - rare events

KW - stochastic timed automata

KW - verification

KW - model checking

UR - http://people.cs.aau.dk/~marius/stratego/rare.html

U2 - 10.1007/978-3-319-47677-3_11

DO - 10.1007/978-3-319-47677-3_11

M3 - Article in proceeding

SN - 978-3-319-47676-6

T3 - Lecture Notes in Computer Science

SP - 163

EP - 178

BT - Dependable Software Engineering

A2 - Fränzle, Martin

A2 - Kapur, Deepak

A2 - Zhan, Naijin

PB - Springer

ER -

Jegourel C, Larsen KG, Legay A, Mikučionis M, Poulsen DB, Sedwards S. Importance Sampling for Stochastic Timed Automata. I Fränzle M, Kapur D, Zhan N, red., Dependable Software Engineering: Theories, Tools, and Applications. Springer. 2016. s. 163-178. (Lecture Notes in Computer Science, Bind 9984). https://doi.org/10.1007/978-3-319-47677-3_11