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 complex systems is a significant challenge, particularly when they involve both nonlinear continuous dynamics (e.g., robotic flight) and discrete stochastic events (e.g., sensor failures or biological state changes). These "Stochastic Hybrid Systems" (SHSs) are prevalent in fields ranging from aerospace to synthetic biology. Traditional reachability analysis—determining if a system will ever enter an unsafe state—is mathematically undecidable for these systems. Numerical methods often struggle with nonlinearities, while pure Monte Carlo simulations may miss rare critical events or fail to account for non-deterministic branching.
Stochastic Hybrid Systems
SHSs combine continuous change, often described by differential equations, with discrete jumps triggered by probabilistic transitions or parameter uncertainties.
As shown in Figure 1, these systems can be modeled as automata where each mode contains specific invariants and differential equations. Transitions between modes can be guarded by complex conditions and may involve probabilistic outcomes, making the state space exceptionally difficult to explore exhaustively.
Methodology: The SReach Approach
SReach addresses these challenges by integrating formal logic with statistical sampling through a three-stage pipeline:
- Randomized Sampling: Stochastic elements, such as uncertain physical parameters, are treated as random variables. SReach samples these variables to generate a set of deterministic "intermediate" models.
- $\delta$-Complete Decision Procedures: For each sampled model, SReach employs
dReach, a tool that uses symbolic logic to verify if any valid path within that specific configuration reaches the target region. Unlike standard simulators,dReachprovides a sound answer within a user-defined precision factor ($\delta$). - Statistical Aggregation: The results from individual samples are aggregated using advanced statistical tests, such as Bayesian Interval Estimation or Sequential Probability Ratio Tests. This allows SReach to provide high-confidence probability estimates with rigorous error bounds.
To ensure practical performance, the implementation includes parallel processing and a caching mechanism to avoid redundant symbolic checks for identical model configurations.
Experimental Evaluation
The authors evaluated SReach across a diverse suite of benchmarks, including biological models (e.g., prostate cancer therapy), standard control problems (e.g., quadcopter stabilization), and large-scale synthetic systems with up to 367 variables and 165 nonlinear ODEs.
As illustrated in Figure 2, the tool's performance and the resulting probability estimates vary with the bounded horizon $k$. The data demonstrates that while computational time increases with complexity, SReach remains capable of providing precise estimates for systems that are beyond the reach of traditional tools.
Key Insights and Results
- Non-Deterministic Branching: By applying symbolic solvers to sampled models, SReach handles non-determinism that pure simulation typically ignores.
- The Zero-Crossing Problem: Logic-based interval analysis allows SReach to reliably "bracket" boundary events, such as a physical collision, which often cause numerical issues in standard simulators.
- Parameter Estimation: The tool can be used to identify parameter ranges that satisfy reachability goals, such as determining optimal PSA thresholds in cancer treatment models to maximize the probability of preventing relapse.
Conclusion and Future Work
SReach represents a significant step forward in the verification of nonlinear stochastic hybrid systems. While currently limited to bounded horizons ($k$), it provides a robust framework for safety analysis and parameter tuning. Future work aims to extend the tool's capabilities to support Stochastic Differential Equations (SDEs), where randomness is continuous and affects the system dynamics at every time step.
Summary updated