💻 computer science

Effective Stochastic Automata Model Checking by Interval Abstraction (extended version)

This paper introduces the first general and effective model checking approach for stochastic automata with general probability distributions by combining refinable interval abstraction with "big time steps" semantics to compute reachability probability bounds, supported by extensions to Modest and Jani formalisms and a Rust prototype implementation.

Original authors: Pedro R. D'Argenio, Arnd Hartmanns, Annabell Petri

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pedro R. D'Argenio, Arnd Hartmanns, Annabell Petri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict the future of a complex machine, like a self-driving car or a hospital's power grid. You know that things go wrong randomly: a sensor might fail, a battery might drain, or a network might get clogged. To keep these systems safe, engineers need to calculate the odds of a disaster happening.

For a long time, the best tools for this job had a major limitation: they could only handle "exponential" randomness. Think of this like rolling a die where the odds of stopping are the same every second, no matter how long you've been waiting. But in the real world, things aren't that simple. A lightbulb doesn't just have a constant chance of burning out; it gets more likely to fail the longer it's been on. A repair crew might arrive at a specific time, not just "sometime soon."

This paper introduces a new way to model these real-world, messy probabilities using something called Stochastic Automata. Think of a Stochastic Automaton as a flowchart for a machine where every step has a "timer" attached to it. These timers don't just tick down; they are set by rolling dice with complex shapes (like a bell curve or a skewed line) to decide exactly when the next event happens.

The Problem: The "Infinite" Maze

The problem is that because these timers can be set to any real number (like 3.14159 seconds or 10.00001 seconds), the number of possible scenarios is infinite. It's like trying to map a maze where every turn could lead to an infinite number of different paths. Traditional math tools get stuck here, and the only other tools that could handle this were limited to very simple, predictable machines.

The Solution: The "Interval" Map

The authors of this paper created a new method called Interval Abstraction. Here is the analogy:

Imagine you are trying to guess where a dart will land on a giant, continuous wall. Instead of trying to predict the exact millimeter (which is impossible), you divide the wall into large, colored zones (intervals).

The Roll: You roll a die to decide which zone the dart lands in (e.g., "The Red Zone").
The Guess: Once you know it's in the Red Zone, you don't pick a specific spot yet. Instead, you say, "It could be anywhere in the Red Zone."

In the paper's method, they replace the complex, continuous "dice rolls" of the machine with a list of these zones. They then build a simplified map (called a Markov Decision Process) that tracks which zones the timers are in.

The Magic: Because they treat the exact position within a zone as a "wildcard" (nondeterministic choice), they can calculate the best-case and worst-case scenarios.
The Result: They get a "safety net." They can say, "The chance of failure is at least X% and at most Y%." If the worst-case number is still safe, the system is safe.

Refining the Picture

The authors realized that if the zones are too big, the answer is too vague (like saying "The dart is somewhere in the whole building"). But if they make the zones smaller and smaller, the answer gets more precise. They showed that by splitting these zones into smaller pieces, their tool can get very close to the true answer, even for complex machines with many timers racing against each other.

The New Tool

The team built a prototype software tool (written in a language called Rust) that does this automatically.

Input: You give it a model of your system (using a language called Modest).
Process: It chops the continuous time into zones, builds the "safety net" map, and runs a calculation to find the best and worst odds.
Output: It tells you the range of probabilities for reaching a specific goal (like "the system crashes" or "the job gets done").

What They Found

They tested their tool on several examples, including:

Simple puzzles: Small models where they knew the exact answer. Their tool got very close, proving the math works.
Queueing lines: Simulating lines of customers (like at a bank) where arrival times vary. Even with millions of possible states, the tool finished the calculation in minutes on a standard laptop.
File Servers: A complex model of a computer server handling requests. They compared their tool to an existing, famous tool. Their new tool was often faster and more accurate, especially when they used smaller zones to get a better picture.

The Bottom Line

This paper presents the first "general purpose" tool that can analyze complex, real-world timing systems without forcing engineers to simplify their models too much. It trades the impossible task of finding the exact number for a highly accurate range (a lower and upper bound), giving engineers a powerful way to prove their systems are dependable even when time behaves unpredictably.

Problem Statement
Stochastic Automata (SA) are a formalism for modeling dependable and high-performance systems where component faults, maintenance, and service times follow general continuous probability distributions (e.g., Weibull, uniform) rather than the exponential distributions required by Continuous-Time Markov Chains (CTMCs) or Generalized Stochastic Petri Nets (GSPNs). While SA offer a more realistic representation of non-Markovian systems, their analysis is challenging due to the combination of continuous time, general distributions, and nondeterministic choices.

Existing analysis approaches face significant limitations:

Statistical Model Checking (SMC): Tools like Fig employ Monte Carlo simulation but are restricted to (weakly) deterministic SA, where minimum and maximum reachability probabilities coincide. They cannot handle general nondeterministic SA.
Analytical Methods: Previous algorithms for general SA (e.g., by Bryans et al.) rely on "region trees" requiring nested integrals that become infeasible as model depth increases, or they use discretization that lacks tool support. Other formalisms like Stochastic Hybrid Automata (SHA) or Stochastic Timed Automata (STA) exist, but their model checking often suffers from scalability issues due to the complexity of hybrid reachability or the rigidity of digital clock semantics (fixed time steps).

Methodology
The paper proposes the first dedicated, general, and effective model checking approach for SA based on interval abstraction. The core methodology involves transforming an infinite-state SA into a finite Markov Decision Process (MDP) that overapproximates the original semantics.

Interval Abstraction: Instead of discretizing the outcome of sampling from a continuous probability distribution (CPD), the method partitions the support of each distribution into a finite set of intervals.
- Sampling a value from a CPD is replaced by a two-step process: (1) a discrete probabilistic choice of an interval (based on the probability mass of that interval), followed by (2) a continuous nondeterministic choice of a specific value within that interval.
- This transforms the SA into an MDP where states track the current location and the intervals containing the possible values of active timers.
Big Time Steps Semantics: The approach utilizes the "big time steps" semantics of SA. Transitions occur only when a timer expires or a guard set is satisfied, rather than at every infinitesimal time step. This avoids the "dense time" complexity found in other semantics.
- The abstraction propagates intervals symbolically. When a timer expires, the system transitions to a new state where the timer's interval is updated or reset.
- The resulting MDP is finite because the number of locations is finite and the number of interval combinations is fixed by the user-defined partition.
Overapproximation and Bounds:
- The MDP strategy can choose the precise value within an interval, whereas the original SA semantics involves a random choice. This introduces nondeterminism that overapproximates the original system.
- Consequently, computing the maximum reachability probability on the MDP yields an upper bound for the SA, and the minimum reachability probability yields a lower bound.
- The paper proves that as the intervals become smaller, the approximation error is expected to decrease, though monotonicity is not guaranteed with all partitioning strategies.
Tooling and Formalisms:
- The authors extended the Modest modeling language and the Jani interchange format to support SA, including timer declarations and guard sets.
- A prototype tool implemented in Rust performs the interval abstraction, constructs the MDP, and computes bounds using Value Iteration (VI).

Key Contributions

First Dedicated SA Model Checker: The paper presents the first tool-based approach for model checking general SA that is not limited to deterministic subclasses.
Interval Abstraction for SA: It adapts interval abstraction (previously used for SHA) specifically for SA, replacing continuous probabilistic choices with discrete probabilistic followed by continuous nondeterministic choices, resulting in a finite MDP.
Formal Correctness: The authors provide a formal proof (Theorem 1) establishing that the MDP's reachability probabilities bound the SA's true probabilities ( $p_{min}^{MDP} \le p_{min}^{SA} \le p_{max}^{SA} \le p_{max}^{MDP}$ ).
Language Extensions: The extension of Modest and Jani to support SA provides a user-friendly high-level modeling interface and a standard for model exchange.
Prototype Implementation: A Rust-based prototype demonstrates the feasibility of the approach.

Experimental Results
The authors evaluated the prototype on three sets of examples:

Small SA Models: Including the running example and models from literature distinguishing strategy classes. The tool successfully computed bounds that closely approximated true probabilities (e.g., approximating 0.25 and 0.75 with bounds [0.245, 0.755] using 0.0125 per-interval probability).
Queueing Models: Non-Markovian M/M/1 and Weibull/E6/1 queues with buffer limits. Despite generating MDPs with millions of states (e.g., ~3.3 million states), the tool completed analysis in under 3 minutes on a standard laptop.
File Server Model: A comparison with the mcsta tool (which uses digital clocks for STA).
- For uniform distributions, the SA approach achieved higher accuracy in less than 30% of the runtime compared to mcsta, largely because the "big time steps" semantics resulted in significantly smaller MDPs than the digital clock approach (which forces time steps of duration 1).
- For exponential distributions, the fixed-width intervals of mcsta performed better than the equal-probability intervals used in the prototype, highlighting that interval generation strategies impact performance. The authors note that refining intervals per timer is possible in their approach, unlike the fixed-width constraint of digital clocks.

Significance and Claims
The paper claims to introduce a general and effective model checking approach for SA that places few restrictions on input models.

Scalability: The experimental results suggest the approach scales well for nontrivial examples, handling models with hundreds of thousands to millions of MDP states, which previous analytical techniques could not manage.
Practicality: Despite being a prototype, the tool works well for reasonably-sized SA and provides useful bounds for safety and performance analysis.
Flexibility: The approach supports various continuous distributions (Uniform, Exponential, Erlang, Weibull) and complex features like timer races and nondeterministic choices.

The authors remain modest regarding the refinement process, noting that while smaller intervals generally improve accuracy, the relationship is not strictly monotonic with their current partitioning strategy, and a formal convergence proof remains an open challenge. They position this work as a foundation for future performance-optimized tools and extensions to dynamic fault trees and time-bounded properties.