Sound Statistical Model Checking for Probabilities and Expected Rewards (extended version)

Carlos E. Budde, Arnd Hartmanns, Tobias Meggendorfer, Maximilian Weininger, Patrick WienhöftarXiv 2024 · DOI · arXiv

Here is a blog-style summary of the paper.

TL;DR

Statistical model checking (SMC) is widely used to verify probabilistic systems, but many state-of-the-art tools rely on unsound statistical methods that violate their own confidence guarantees. This paper provides a comprehensive framework for sound SMC, introducing the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality to provide rigorous, sample-efficient guarantees for expected rewards. The authors implement these methods in the modes tool, demonstrating empirically that standard methods frequently fail while their sound alternatives deliver on their mathematical promises.

What Problem Does This Paper Address?

Statistical model checking (SMC) estimates system properties—such as the probability of a critical failure or the expected energy consumption—by running a large number of random simulations. To be trustworthy, these estimates must be Probably Approximately Correct (PAC). This means that if you ask for 95% confidence, the calculated confidence interval must actually contain the true value at least 95% of the time.

The authors reveal a troubling gap in the field: many popular SMC tools use approximations based on the Central Limit Theorem (like the textbook Wald interval). These methods are fundamentally unsound for finite sample sizes and frequently under-deliver on coverage, especially for edge cases where probabilities are close to 0 or 1. Furthermore, estimating expected rewards (e.g., expected execution time) has remained an open problem because system paths can theoretically be infinitely long with unbounded rewards, making standard PAC guarantees mathematically impossible without extra structural assumptions.

Methods

The paper systematically tackles soundness for both probabilities and expected rewards:

  • For Probabilities: The authors evaluate various binomial proportion estimators. They recommend the Clopper-Pearson interval over the commonly used Okamoto (Hoeffding) bound, showing it achieves exact soundness with far fewer samples.
  • For Bounded Expected Rewards: The authors introduce the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality to the SMC community. DKW constructs a confidence band around the entire empirical cumulative distribution function (cdf), allowing researchers to derive tight, sound confidence intervals for the mean.
  • For Unbounded Expected Rewards: The authors prove that "bounding sets" can theoretically truncate extreme path rewards with negligible error. For practical applications, they formalize limit-PAC procedures and introduce DKW-E-Lower, a method that provides guaranteed lower bounds that provably converge to the true expected reward as the number of samples increases.

Datasets

The authors evaluated their methods using the Quantitative Verification Benchmark Set (QVBS), a standard open-source collection of probabilistic models (DTMCs and MDPs). They selected 44 distinct benchmark instances containing expected-reward properties, including well-known protocols and systems like coupon, egl, csma, wlan, and firewire.

Key Insights and Ideas

  • The Illusion of Textbook Safety: Standard normal approximations (like the Wald interval) are dangerously unreliable for verification. On real-world models, a method claiming 95% confidence can drop to an actual coverage probability as low as 39%.
  • DKW is a Hidden Gem: The DKW inequality has been largely ignored in verification but is vastly superior to Hoeffding's inequality for expected rewards. It naturally exploits the distribution of observed samples to yield intervals up to 2x narrower when loose a priori bounds are used.
  • Lower Bounds are Practical: While a true mathematical upper bound on unbounded reachability rewards is practically impossible to compute purely from sampling, a sound, converging lower bound (limit-PAC) is highly achievable and useful for proving minimum performance thresholds.

Key Results

  • Widespread Tool Unsoundness: The authors surveyed 10 state-of-the-art SMC tools (including PRISM, Uppaal SMC, and Plasma Lab) and found that none originally implemented a sound and efficient method for both probabilities and rewards across fixed and sequential settings.
  • Empirical Failures: In tests across the 44 QVBS benchmark instances with a target 95% confidence level, the standard Normal interval failed to meet the threshold in 31 instances.

![Fig.

  1. Coverage for fixed (top, k = 50) and sequential methods (bottom, ε = 0.05).](/figures/art_895d6bbeac3642029d1bc13dbbca44d1)
  2. DKW Efficiency: DKW consistently outperformed Hoeffding's inequality, producing confidence intervals that were on average 1.72x narrower, approaching the theoretical maximum efficiency gain of 2x.
  3. DKW-E-Lower Convergence: The novel DKW-E-Lower method demonstrated strong practical convergence, with the distance to the true expected reward decreasing by an average factor of 2.6x for every 10x increase in sample size ($k$).

Limitations and Future Work

While the authors proved that unbounded reachability rewards can be fully bounded in theory, the structural parameters required (like the minimum transition probability $p_{min}$) lead to astronomically large, impractical sample sizes ($q > 10^8$ even for tiny 5-state models). Thus, true two-sided PAC guarantees for unbounded rewards remain a challenge.

As immediate future work, the authors suggest extending these sound statistical methods to rare-event simulations (where probabilities are extremely small) and continuous-time Markov chains (CTMCs).

Summary updated

Abstract

Statistical model checking estimates probabilities and expectations of interest in probabilistic system models by using random simulations. Its results come with statistical guarantees. However, many tools use unsound statistical methods that produce incorrect results more often than they claim. In this paper, we provide a comprehensive overview of tools and their correctness, as well as of sound methods available for estimating probabilities from the literature. For expected rewards, we investigate how to bound the path reward distribution to apply sound statistical methods for bounded distributions, of which we recommend the Dvoretzky-Kiefer-Wolfowitz inequality that has not been used in SMC so far. We prove that even reachability rewards can be bounded in theory, and formalise the concept of limit-PAC procedures for a practical solution. The 'modes' SMC tool implements our methods and recommendations, which we use to experimentally confirm our results.
BibTeX
@misc{budde2024sound,
  author = {Carlos E. Budde and Arnd Hartmanns and Tobias Meggendorfer and Maximilian Weininger and Patrick Wienhöft},
  title = {{Sound Statistical Model Checking for Probabilities and Expected Rewards (extended version)}},
  year = {2024},
  eprint = {2411.00559},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.00559},
}

Loading related content...

Figure