Abstract
In this paper we describe a new tool, SReach, which solves probabilistic bounded reachability problems for two classes of stochastic hybrid systems. The first one is (nonlinear) hybrid automata with parametric uncertainty. The second one is probabilistic hybrid automata with additional randomness for both transition probabilities and variable resets. Standard approaches to reachability problems for linear hybrid systems require numerical solutions for large optimization problems, and become infeasible for systems involving both nonlinear dynamics over the reals and stochasticity. Our approach encodes stochastic information by using random variables, and combines the randomized sampling, a $\delta$-complete decision procedure, and statistical tests. SReach utilizes the $\delta$-complete decision procedure to solve reachability problems in a sound manner, i.e., it always decides correctly if, for a given assignment to all random variables, the system actually reaches the unsafe region. The statistical tests adapted guarantee arbitrary small error bounds between probabilities estimated by SReach and real ones. Compared to standard simulation-based methods, our approach supports non-deterministic branching, increases the coverage of simulation, and avoids the zero-crossing problem. We demonstrate our method's feasibility by applying SReach to three representative biological models and to additional benchmarks for nonlinear hybrid systems with multiple probabilistic system parameters.
Introduction
Verifying the safety of Stochastic Hybrid Systems (SHSs) is a critical yet notoriously difficult task. These systems integrate discrete logic, continuous physical laws (often expressed as nonlinear ODEs), and inherent randomness, such as sensor noise or biological variability. Traditional formal verification tools typically struggle with nonlinearity and the mathematical undecidability of exact probability computation in stochastic settings. While simulation-based methods like Monte Carlo are common, they often fail to account for non-deterministic branching and may miss rare, high-impact failure states. SReach was developed to bridge this gap, providing a sound framework for analyzing complex, uncertain systems.
Methodology
SReach employs a hybrid approach that integrates formal verification within a statistical sampling framework. The process begins by encoding all sources of uncertainty—such as parametric variation or probabilistic transitions—as random variables with defined distributions.
The tool then performs randomized sampling. For each sample, the stochastic model is converted into a standard hybrid automaton. SReach utilizes the dReach engine, which employs $\delta$-complete bounded model checking. Unlike traditional solvers, dReach uses $\delta$-decidability to either prove unreachability or identify a path to an unsafe state within a specified numerical error margin ($\delta$). Finally, SReach aggregates these results using statistical tests, such as the Sequential Probability Ratio Test or Bayesian Interval Estimation, to calculate the overall probability of reachability with user-defined confidence levels and error bounds.
Evaluation and Key Results
The authors evaluated SReach on a variety of benchmarks, including biological models like Atrial Fibrillation and Prostate Cancer treatment, as well as control systems like quadcopter stabilization. The tool proved capable of handling high-dimensional systems, with some models involving up to 367 variables and 165 nonlinear ODEs.
A significant finding was the tool's utility in parameter estimation. For instance, in the prostate cancer model, SReach identified that specific treatment threshold combinations (e.g., $r_0=10, r_1=15$) resulted in a success probability near 1.0. Furthermore, the implementation of parallelization using OpenMP provided substantial performance gains, reducing analysis time for complex models from hours to minutes on multi-core machines.
Discussion and Limitations
SReach offers several advantages over traditional methods. By fixing probabilistic transitions during sampling, it creates a sound over-approximation of reachability, ensuring that safety guarantees are robust. It also avoids numerical instabilities like the "zero-crossing" problem by using SMT-based bounded model checking.
However, as a bounded model checker, SReach is limited to verifying behavior within a finite number of steps ($k$) and cannot currently prove infinite-time safety. Future work aims to extend the tool to handle Stochastic Differential Equations (SDEs), where noise continuously affects the system dynamics, and to further optimize the computational cost associated with high-dimensional SMT solving.
Summary updated