💻 computer science

Verification of Parametric Markov Automata under Time-bounded Reachability

This paper introduces parametric Markov Automata to handle uncertainty in model rates and presents a two-step discretization approach, implemented in the Storm model checker, to solve time-bounded reachability synthesis problems by partitioning parameter spaces into satisfying and violating regions with arbitrary precision.

Original authors: Kevin van de Glind, Matthias Volk, Tim Willemse

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kevin van de Glind, Matthias Volk, Tim Willemse

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 the engineer in charge of a complex, automated factory. This factory has machines that run on electricity (probabilistic choices) and machines that run on a timer (continuous time). Your job is to make sure the factory never crashes and always finishes its jobs on time.

In the past, to check if your factory was safe, you had to know the exact speed of every timer and the exact odds of every coin flip. If you didn't know these numbers precisely, you couldn't run the safety check. It was like trying to drive a car blindfolded because you didn't know the exact speed limit.

This paper introduces a new way to check these factories even when you don't know the exact numbers. Instead of needing a single number for a timer (like "5 seconds"), you can use a range (like "between 4 and 6 seconds"). The authors call this a Parametric Markov Automaton (pMA). Think of it as a factory blueprint where the speeds and odds are written as variables (like $x$ and $y$ ) instead of fixed numbers.

Here is how their solution works, broken down into simple steps:

1. The Problem: Too Many Unknowns

Real-world systems are messy. Environmental changes might make a machine faster or slower. You might not know the exact probability of a part failing. The old tools said, "We can't check this until you give us exact numbers." This paper says, "We can check it while the numbers are still ranges."

2. The Solution: A Two-Step "Freezing" Process

The authors developed a method to handle these fuzzy ranges. They do it in two main steps:

Step A: The "Stop-Motion" Trick (Discretization)
Imagine watching a fast-moving video. It's hard to analyze every single frame of continuous motion. So, you turn the video into a "stop-motion" animation where you only look at the scene every tiny fraction of a second (like every 0.01 seconds).

What they do: They take the continuous, flowing time of the factory and chop it up into tiny, discrete steps.
The Catch: This introduces a tiny bit of error, like a blurry photo. But the authors prove that if you make the steps small enough, the blur is so tiny it doesn't matter. They can make this error as small as you want.

Step B: The "What-If" Game (Parameter Lifting)
Now that the factory is a stop-motion animation, they have to deal with the unknown ranges (the variables).

The Analogy: Imagine you are playing a board game against an opponent. You don't know exactly what cards they hold (the parameters).
- Scenario 1 (The "Angel" Player): You assume your opponent is trying to help you win. You ask, "Is there any set of cards they could hold that lets me win?"
- Scenario 2 (The "Demon" Player): You assume your opponent is trying to make you lose. You ask, "Is there any set of cards they could hold that makes me lose?"
What they do: They turn the unknown ranges into a game between a "Player" (who controls the factory's choices) and "Nature" (who controls the unknown numbers). They calculate the best and worst-case scenarios. If the factory is safe even in the worst-case scenario, then it's safe for sure.

3. The Results: Mapping the Safe Zones

The paper doesn't just say "Yes" or "No." It creates a map.

Imagine a map of the factory's possible settings. Some areas are Green (Safe: The factory works no matter what the exact numbers are). Some areas are Red (Unsafe: The factory crashes).
The authors' tool draws the lines between these Green and Red zones. It tells you exactly which combinations of speeds and odds are safe and which are dangerous.

4. The Bottleneck: The "Stop-Motion" Cost

The authors tested their method on many different factory models. They found that while the math works perfectly, the computer has to work very hard to create those tiny "stop-motion" steps.

The Analogy: It's like trying to analyze a high-speed race by taking a photo every millimeter. The more precise you want to be, the more photos you need to take, and the longer it takes to process them.
Conclusion: The biggest slowdown in their system comes from that first step (chopping time into tiny pieces).

Summary

This paper gives us a new tool to verify systems where we don't know the exact numbers. Instead of needing perfect data, we can work with ranges. The tool turns continuous time into tiny steps and plays a "best-case vs. worst-case" game to draw a map of what is safe and what is dangerous. While it requires a lot of computer power to be super precise, it successfully solves a problem that was previously impossible to handle without exact data.

Technical Summary: Verification of Parametric Markov Automata under Time-bounded Reachability

Problem Statement
Markov Automata (MA) are a compositional model for nondeterministic, continuously timed stochastic systems, serving as semantics for models like Generalized Stochastic Petri Nets and Dynamic Fault Trees. However, existing model checking algorithms for MA require fully specified models, where all transition rates and probabilities are known precisely. This assumption is often unrealistic for real-world systems where parameters may be subject to environmental uncertainty or unknown.

This paper addresses the verification of Parametric Markov Automata (pMA), where transition rates and probabilistic successor distributions are defined by parametric functions rather than fixed constants. The authors focus on time-bounded reachability properties (e.g., "Is the probability of reaching a goal state within time $t$ greater than $\theta$ ?"). Two specific problems are tackled:

Satisfaction Verification: Determining if there exists a parameter valuation within a given region that satisfies or violates a property.
Synthesis: Partitioning the parameter space into regions that satisfy the property and regions that violate it.

The analysis must account for four distinct satisfaction relations based on the interaction between the system's scheduler (making nondeterministic choices) and "nature" (assigning parameter values): Feasibility, Angelic-aid, Robust, and Demonic.

Methodology
The proposed approach solves these problems via a two-step process that transforms the continuous parametric model into a discrete one amenable to existing synthesis techniques, while bounding the introduced errors.

Discretization and Transformation:
- The pMA is first discretized using a step size $\delta$ , converting the continuous-time model into a Parametric Markov Decision Process (pMDP). This step generalizes previous discretization results for non-parametric MAs.
- To handle the immediate transitions of probabilistic states (which occur without time elapse), the authors employ a state-elimination technique. Probabilistic states (PS) are collapsed into Markovian states (MS), transforming the model into a standard step-bounded reachability problem on a pMDP.
- Since the discretization introduces exponential terms ( $e^{-\lambda \delta}$ ) which are difficult to handle in symbolic parameter synthesis, the authors approximate these terms using partial Taylor expansions. This yields an "approximate discretized pMA" where transition probabilities are represented by rational functions, bounded by over- and under-approximations.
Parameter Lifting (PL) and Verification:
- The transformed pMDP is analyzed using Parameter Lifting (PL). This technique abstracts inter-state dependencies by treating parameter choices as nondeterministic choices made by a second player ("Nature") in a stochastic game.
- The PL method computes upper and lower bounds for the reachability probability. These bounds are compared against the user-specified threshold $\theta$ .
- The approach utilizes a refinement scheme: if the bounds are inconclusive (i.e., the interval straddles the threshold), the parameter region is partitioned, and the process is repeated.
- The total error is governed by three terms: the discretization error ( $\epsilon_\delta$ ), the error from the Taylor approximation, and the error introduced by the PL abstraction. The authors demonstrate that the discretization error is the dominant factor.

Key Contributions

Definition of pMA: The paper formally introduces Parametric Markov Automata, extending MAs with parametric rate and probabilistic functions.
Algorithm for Time-bounded Reachability: The authors present the first algorithm capable of performing satisfaction verification and parameter synthesis for pMAs under time-bounded reachability constraints.
Generalized Discretization: They generalize the discretization results of Guck et al. [17] to the parametric setting, proving that the discretized pMA bounds the true reachability probability of the pMA.
Approximate Discretization: A method is introduced to handle exponential terms in the discretized model via Taylor expansion, allowing the use of rational function-based synthesis tools.
Implementation: The approach is implemented using the Storm model checker (via the Stormpy interface) and supports both pMAs and parametric CTMCs.

Experimental Results
The authors evaluated their implementation on a suite of benchmarks from the QCOMP benchmark set, including models like flexible-manufacturing, polling, and kanban.

Verification: For satisfaction verification, the tool successfully provided conclusive answers for all tested benchmarks, often within seconds.
Synthesis: For parameter synthesis, the tool successfully partitioned parameter spaces for smaller models. However, for larger or more complex models, the process frequently reached the 15-minute timeout.
Performance Bottlenecks: The experimental analysis identifies discretization as the primary performance bottleneck. The computational cost increases significantly as the discretization step $\delta$ decreases (to reduce error) or as the maximum sojourn rate in the model increases.
Comparison: When compared to PRISM-PSY on parametric CTMCs (where PRISM-PSY does not require discretization), the proposed method was slower. However, the method succeeds where PRISM-PSY fails: it can analyze pMAs and models with parametric transition probabilities (not just rates), such as the tandem benchmark.

Significance and Claims
The paper claims to bridge a gap in formal verification by enabling the analysis of uncertainty in Markov Automata, a model class widely used for reliability engineering but previously restricted to fully specified instances. The authors emphasize that their approach solves the verification and synthesis problems up to arbitrary precision, provided the discretization step is sufficiently small.

The authors remain modest regarding scalability, acknowledging that the current implementation is limited by the cost of discretization. They explicitly state that the main performance bottlenecks originate from the discretization of the pMA. Consequently, they suggest that future work should investigate approaches that avoid discretization entirely, such as analyzing continuous-time stochastic games directly or utilizing uniformization techniques, though they note these alternatives may introduce their own computational challenges. The work establishes a foundational framework for parametric analysis of continuous-time nondeterministic systems, extending the capabilities of existing tools like Storm to handle parametric uncertainty in a broader class of models.

1. The Problem: Too Many Unknowns

2. The Solution: A Two-Step "Freezing" Process

3. The Results: Mapping the Safe Zones

4. The Bottleneck: The "Stop-Motion" Cost

Summary

More like this