A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation

S. Akshay, Paul Gastin, R. Govind, Aniruddha R. Joshi, B. Srivathsan

Abstract

In this paper, we consider a model of generalized timed automata (GTA) with two kinds of clocks, history and future, that can express many timed features succinctly, including timed automata, event-clock automata with and without diagonal constraints, and automata with timers. Our main contribution is a new simulation-based zone algorithm for checking reachability in this unified model. While such algorithms are known to exist for timed automata, and have recently been shown for event-clock automata without diagonal constraints, this is the first result that can handle event-clock automata with diagonal constraints and automata with timers. We also provide a prototype implementation for our model and show experimental results on several benchmarks. To the best of our knowledge, this is the first effective implementation not just for our unified model, but even just for automata with timers or for event-clock automata (with predicting clocks) without going through a costly translation via timed automata. Last but not least, beyond being interesting in their own right, generalized timed automata can be used for model-checking event-clock specifications over timed automata models.

1. Introduction

The formal verification of real-time systems has traditionally relied on Timed Automata (TA) as the primary modeling formalism. However, as system complexity grows, the need for more expressive features—such as timers that count down to zero or event-clocks that predict the time until a future event—has become apparent. While specialized models like Event-Clock Automata (ECA) exist, they often lack direct verification support. Practitioners are frequently forced to translate these models into standard TA, a process that typically results in a state-space explosion, rendering verification computationally prohibitive.

Furthermore, the inclusion of diagonal constraints (e.g., $x - y \le 5$) introduces significant theoretical challenges, particularly regarding the termination of verification algorithms. This paper addresses these gaps by introducing Generalized Timed Automata (GTA), a unified framework that encompasses TA, ECA, and timers, supported by a direct, simulation-based verification algorithm.

2. The Generalized Timed Automata (GTA) Framework

The core of our approach is the classification of clock variables into two distinct categories:

  1. History Clocks: These measure the time elapsed since a past event, encompassing standard TA clocks and event-recording clocks.
  2. Future Clocks: These measure the time remaining until a future event, generalizing timers and event-predicting clocks.

2.1 Decidability and the $X_D$-Safe Subclass

A significant theoretical finding of this work is that reachability in the most general GTA model is undecidable. The combination of future clocks and diagonal constraints allows the system to simulate a counter machine. To maintain decidability while preserving practical expressivity, we identify the $X_D$-safe subclass. This subclass restricts the interaction between future clocks and diagonal guards just enough to ensure termination while still covering the requirements of TA, ECA, and timer-based models.

3. Symbolic Verification: The Zone Algorithm

To check reachability efficiently, we propose a simulation-based zone algorithm. Standard verification techniques often struggle with the infinite state space of timed systems. Our algorithm leverages the $\mathcal{G}$-simulation framework, which groups infinite sets of clock valuations into symbolic "zones."

The primary innovation here is a new termination analysis specifically designed to handle diagonal constraints. By using simulation relations that allow larger zones to "subsume" smaller ones, the algorithm effectively prunes the search tree, ensuring that the exploration of the state space remains finite without sacrificing accuracy.

4. Implementation and Experimental Results

We implemented the GTA model and the zone algorithm within Tchecker, an open-source library for timed systems. This represents the first implementation capable of handling ECA with diagonal constraints and timers directly, without an intermediate translation to TA.

4.1 Performance Benchmarks

The prototype was evaluated against several benchmarks, including standard TA protocols (Fischer, FDDI) and synthetic ECA suites (ToyECA).

  • Direct vs. Translated Performance: In the ToyECA benchmarks, the GTA approach achieved near-instantaneous verification (approx. 0.0003 seconds). In contrast, the traditional method of translating ECA to TA resulted in timeouts (exceeding 60 seconds) or significantly higher latency.
  • Overhead Analysis: When applied to standard TA models, where the additional features of GTA are not utilized, the tool demonstrated performance comparable to specialized TA verifiers. This indicates that the unified model does not impose a significant "flexibility tax" on simpler models.

5. Conclusion and Future Work

The GTA framework provides a powerful, unified solution for the verification of real-time systems. By treating predicting clocks and timers as first-class citizens, we avoid the overhead of translation and enable the verification of models previously considered too complex for standard tools.

While the current work focuses on reachability analysis within the $X_D$-safe subclass, future research will explore extending these techniques to liveness properties and investigating the limits of the EXPSPACE-complete complexity in larger industrial applications.

Summary updated

Abstract

In this paper, we consider a model of generalized timed automata (GTA) with two kinds of clocks, history and future, that can express many timed features succinctly, including timed automata, event-clock automata with and without diagonal constraints, and automata with timers. Our main contribution is a new simulation-based zone algorithm for checking reachability in this unified model. While such algorithms are known to exist for timed automata, and have recently been shown for event-clock automata without diagonal constraints, this is the first result that can handle event-clock automata with diagonal constraints and automata with timers. We also provide a prototype implementation for our model and show experimental results on several benchmarks. To the best of our knowledge, this is the first effective implementation not just for our unified model, but even just for automata with timers or for event-clock automata (with predicting clocks) without going through a costly translation via timed automata. Last but not least, beyond being interesting in their own right, generalized timed automata can be used for model-checking event-clock specifications over timed automata models.
BibTeX
@inproceedings{akshay2023unified,
  author = {S. Akshay and Paul Gastin and R. Govind and Aniruddha R. Joshi and B. Srivathsan},
  title = {{A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation}},
  booktitle = {CAV},
  year = {2023},
  url = {https://openreview.net/forum?id=AiMHBVKJlq},
}
Figure