Guided Importance Sampling for Safety and Reliability: A Pragmatic Comparison of Symbolic and Simulation-Based Approaches
- 3 November 2025
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-11
Abstract
Statistical Model Checking (SMC) becomes imprac-tical for hazards with probabilities as small as 10−9. Importance Sampling (IS) can help, but its effectiveness hinges on a good sampling distribution. We present a symbolic-simulation method that constructs such a distribution for Discrete-Time Markov Chains (DTMCs) used in model-based safety assessment. First, we partition all first-passage executions to the hazard into Path-Influence Regions (PIRs), repair-aware classes induced by minimal critical failure mode sets. For each PIR, we encode cut sequences with Bounded Model Checking (BMC) and use Opti-mization Modulo Theories (OMT) to synthesize two probabilistic extremal witnesses (most and least likely). We then solve a convex fitting problem over locally normalized IS weights to equalize (or tightly bound) the likelihood ratios on these extremals, which by affinity controls the entire PIR and is sufficient for computing the optimal distribution. The resulting estimator is unbiased and, under mild conditions, enjoys Bounded Relative Error (BRE) for which we provide a proof sketch and rare-event preliminaries. In experiments on nine benchmarks, our method improves accuracy, reduces relative error, and increases robustness compared to IS baselines (PLASMA and PathZVA), especially for large models and long horizons.Keywords
This publication has 30 references indexed in Scilit:
- $\mathcal {S}$BIP 2.0: Statistical Model Checking Stochastic Real-Time Systems2018
- (Stochastic) Model Checking in GreatSPN2014
- Simulation and Statistical Model Checking for Modestly Nondeterministic ModelsLecture Notes in Computer Science, 2012
- PRISM 4.0: Verification of Probabilistic Real-Time Systems2011
- Statistical Model Checking for Cyber-Physical Systems2011
- Importance Sampling in Rare Event Simulation2009
- Ymer: A Statistical Model Checker2005
- Introduction to Rare Event Simulation2004
- Approximate Probabilistic Model Checking2004
- The Cross-Entropy Method2004