[Paper] TAPAAL SMC: Statistical Model Checking of Stochastic Timed-Arc Petri Nets

Source: arXiv - 2606.02007v1

Overview

The paper introduces TAPAAL SMC, the first tool that brings statistical model checking (SMC) to stochastic timed‑arc Petri nets (TAPNs). By giving TAPNs a rigorous stochastic semantics and coupling it with scalable SMC algorithms, the authors make it possible to analyze realistic, time‑ and probability‑aware models that were previously out of reach for automated verification.

Key Contributions

• First stochastic semantics for TAPNs – a mathematically sound way to assign probabilities to timed‑arc Petri net executions.
• Integration of quantitative & qualitative SMC into the open‑source TAPAAL model checker, enabling “run‑time” verification of complex models.
• Proof of well‑behaved semantics (e.g., measurability, finiteness of execution probabilities) that guarantees the statistical estimators are valid.
• Extensive case‑study evaluation (manufacturing pipelines, communication protocols, embedded controllers) showing that the approach scales to models with thousands of places and transitions.
• User‑friendly modeling extensions (inhibitor arcs, transport arcs, place invariants) that preserve the expressive power of TAPNs while remaining amenable to SMC.

Methodology

1. Modeling Layer – The authors start from the classic TAPN formalism (tokens carry ages, arcs have time intervals, places may have invariants). They extend it with stochastic firing delays: each enabled transition draws a random delay from a user‑specified distribution (e.g., exponential, uniform).
2. Semantic Construction – They define a continuous‑time Markov decision process (CTMDP) that captures both the timing constraints and the probabilistic choices. Key technical steps include:
   • Mapping token ages to clock valuations.
   • Ensuring that the set of enabled transitions is measurable at every instant.
   • Proving that the resulting stochastic process is non‑Zeno (time always progresses).
3. Statistical Model Checking – Two SMC engines are built on top of the CTMDP:
   • Qualitative SMC (hypothesis testing) to answer “does the property hold with probability ≥ p?”.
   • Quantitative SMC (Monte‑Carlo estimation) to compute an approximate probability with confidence bounds.
     Both engines reuse TAPAAL’s existing simulation engine, adding a lightweight wrapper that records property satisfaction over many random runs.
4. Implementation – The extensions are integrated into the TAPAAL GUI, allowing users to annotate transitions with distributions, select properties in a temporal‑logic style (e.g., P≥0.9 [ F≤10 s goal ]), and launch SMC experiments with a single click.

Results & Findings

• Performance: For a benchmark of a stochastic manufacturing line (≈ 2 k places, 1.8 k transitions), quantitative SMC converged to a 95 % confidence interval within ≈ 30 s using 10 k simulation runs—orders of magnitude faster than exact model checking, which timed out.
• Expressiveness: The stochastic TAPN model could capture both hard real‑time constraints (via place invariants) and soft probabilistic behaviours (via exponential delays) in a single formalism, something not achievable with pure timed automata or pure stochastic Petri nets alone.
• Accuracy: In a communication protocol case study, the estimated probability of a deadline miss (≤ 5 ms) was 0.012 ± 0.001, matching analytical results obtained by hand‑derived Markov chains, confirming the statistical estimates are reliable.
• Scalability: Across five diverse case studies, the number of required simulation runs grew sub‑linearly with model size, thanks to the variance‑reduction techniques (e.g., importance sampling) built into the SMC engine.

Practical Implications

• Rapid prototyping: Engineers can now model time‑critical, probabilistic systems (e.g., IoT edge devices, autonomous vehicle controllers) in TAPN and get quick, statistically sound feedback on reliability or performance without waiting for exhaustive verification.
• Design‑space exploration: By tweaking distribution parameters (e.g., sensor latency) and re‑running SMC, developers can perform “what‑if” analyses to guide hardware sizing or scheduling policies.
• Integration with CI pipelines: Since SMC runs are just simulations, they can be scripted and automated, enabling continuous verification of safety‑critical properties as code evolves.
• Bridging the gap between formal methods and industry: The familiar Petri‑net notation lowers the entry barrier for system architects, while the statistical guarantees provide the rigor required for certification (e.g., ISO 26262, IEC 61508).

Limitations & Future Work

• Statistical uncertainty: Results are always approximations; rare‑event properties (probability < 10⁻⁴) may need prohibitively many simulations or specialized rare‑event techniques.
• Distribution support: The current implementation focuses on exponential and uniform distributions; extending to arbitrary PDFs (e.g., Weibull, log‑normal) would broaden applicability.
• State‑space explosion in simulation: Extremely large nets can still cause memory pressure during simulation, suggesting the need for on‑the‑fly abstraction or compositional SMC.
• Toolchain integration: Future work includes exposing a REST API for TAPAAL SMC so that it can be called from other development environments (e.g., ROS, MATLAB).

Bottom line: TAPAAL SMC equips developers with a practical, statistically rigorous way to verify stochastic timed‑arc Petri net models, opening the door to faster, more reliable design cycles for time‑sensitive, probabilistic systems.

Authors

• Tanguy Dubois
• Kim G. Larsen
• Jiri Srba

Paper Information

• arXiv ID: 2606.02007v1
• Categories: cs.DC
• Published: June 1, 2026
• PDF: Download PDF