Symbolic Model Checking for Probabilistic Timed Automata

Marta Z. Kwiatkowska, Gethin Norman, Jeremy Sproston, Fuzhi WangFORMATS/FTRTFT 2004 · DOI

TL;DR

This paper introduces a symbolic model-checking approach for verifying probabilistic timed automata (PTAs) against properties expressed in PTCTL. By leveraging zones and difference bound matrices, it offers a more scalable verification method for complex real-time systems with both probabilistic and temporal aspects, outperforming traditional region-graph methods.

What Problem Does This Paper Address?

Many real-world systems, from embedded devices to communication protocols, exhibit both precise timing requirements and inherent randomness or uncertainty. Modeling these systems accurately requires formalisms that can capture both aspects. Probabilistic Timed Automata (PTAs) are one such formalism, extending traditional timed automata with discrete probability distributions. However, verifying properties of these PTAs, especially complex temporal logic formulas like PTCTL, can be computationally challenging. Traditional methods, like the region-graph construction, suffer from state-space explosion, making them impractical for larger systems. This paper aims to bridge this gap by developing a symbolic model-checking approach that avoids explicit state-space construction, thereby improving scalability.

Methods

The core contribution of this paper lies in developing symbolic model-checking algorithms for PTCTL properties over PTAs. The key ideas are:

  • Symbolic State Representation: Instead of explicit states (location, clock valuation), the paper uses symbolic states represented by a pair of a location and a zone. A zone is a convex set of clock valuations, which can be efficiently represented using Difference Bound Matrices (DBMs).
  • Zone-Based Operations: The algorithms operate on these zones, performing operations like time predecessors and discrete predecessors. To handle potential non-convexity arising from these operations, they represent non-convex zones as lists of DBMs.
  • PTCTL Model Checking: The paper adapts standard model-checking techniques to work with symbolic states. For PTCTL formulas, it recursively computes sets of symbolic states satisfying subformulas.
  • Handling Probabilistic and Temporal Modalities: Special attention is given to the probabilistic "Until" operator (P~x[φ U ψ]). The algorithms compute either the maximum probability (pmax) or minimum probability (pmin) of satisfying such properties.
  • Time Divergence: A crucial aspect is handling time divergence. The algorithms are designed to consider only "time-divergent" behaviors, which is essential for accurate probability calculations, especially for minimum probability properties. They also include a mechanism to check for and eliminate "zeno" states (states from which time cannot diverge with probability 1).
  • Algorithm for Maximum Probabilities (MaxU): This algorithm iteratively computes symbolic states satisfying "Until" properties by using timed and discrete predecessor operations and combining results from probabilistic edges.
  • Algorithm for Minimum Probabilities (MinU): This is achieved by leveraging duality: the minimum probability of a property is 1 minus the maximum probability of its negation. The paper also introduces algorithms to handle qualitative release formulas (e.g., P<1[φ V ψ]) which are crucial for the minimum probability computation.

Datasets

Not discussed in the paper. The paper uses case studies to evaluate its algorithms, but these are not presented as datasets in the traditional sense.

Key Insights and Ideas

  • Symbolic Approach for PTAs is Feasible: The paper demonstrates that symbolic techniques, successful for non-probabilistic timed systems, can be effectively extended to probabilistic timed automata, offering a path to overcome state-space explosion.
  • Zones as a Scalable Representation: Using zones and DBMs for representing sets of clock valuations is key to managing the complexity of timed systems symbolically. The handling of non-convex zones is a practical necessity.
  • Time Divergence is Critical for Minimum Probabilities: The distinction between considering all paths versus only time-divergent paths is crucial for correctly calculating minimum probabilities, as pathological non-divergent behaviors can artificially lower these probabilities.
  • Duality Simplifies Minimum Probability Calculations: The paper effectively uses the duality between "Until" and "Release" operators to reduce the problem of computing minimum probabilities to computing maximum probabilities, simplifying the overall verification process.
  • Case Studies Validate Scalability: The application to CSMA/CD and FireWire protocols shows that, in practice, the symbolic approach can handle significantly smaller state spaces compared to digital clock approaches, even though worst-case complexity remains high.

Key Results

  • Theoretical Foundation: The paper provides a formal theoretical framework for symbolic model checking of PTAs against PTCTL.
  • Prototype Implementation: A prototype implementation using DBMs was developed.
  • Case Study Performance:
    • For the CSMA/CD protocol, the symbolic approach resulted in significantly smaller model sizes compared to the digital clocks approach. For example, for a deadline of 2800ns, the symbolic model had 1263 states, while the digital clock model had 10,738,692 states.
  • For the FireWire root contention protocol, similar reductions in model size were observed. For a deadline of 20 * 10³ns, the symbolic approach generated models with 528 states, whereas the digital clock approach resulted in 1,462,165 states.
  • Algorithm Efficiency: While the worst-case complexity of the MaxU algorithm can be high, the case studies demonstrated practical feasibility with much smaller state spaces than theoretical upper bounds.

Limitations and Future Work

  • Worst-Case Complexity: The paper acknowledges that the MaxU algorithm can be expensive in the worst case, as it might construct a powerset of the region graph.
  • Implementation Efficiency: The current implementation is primarily for validation, and the authors state that future work will focus on developing an efficient symbolic implementation.
  • Non-Canonical Zone Representation: Representing non-convex zones as lists of DBMs is not canonical, which can lead to redundancy and potentially impact performance.
  • Future Directions:
    • Efficient symbolic implementation of the algorithms.
  • Adaptations to probabilistic polyhedral hybrid automata.
  • Symbolic probabilistic systems.
  • Comparison with state-partitioning techniques.

Summary updated

BibTeX
@inproceedings{kwiatkowska2004symbolic,
  author = {Marta Z. Kwiatkowska and Gethin Norman and Jeremy Sproston and Fuzhi Wang},
  title = {{Symbolic Model Checking for Probabilistic Timed Automata}},
  booktitle = {FORMATS/FTRTFT},
  year = {2004},
  doi = {10.1007/978-3-540-30206-3\_21},
}
Figure