MITL Model Checking via Generalized Timed Automata and a New Liveness Algorithm

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

TL;DR

This paper introduces a novel, more efficient way to check the correctness of real-time systems specified in Metric Interval Temporal Logic (MITL) by translating them into a richer model called Generalized Timed Automata (GTAs). Crucially, it also provides the first algorithm for checking "liveness" (whether a system can reach a desired state) in GTAs, overcoming a major theoretical hurdle.

What Problem Does This Paper Address?

Verifying real-time systems, especially those with complex timing requirements, is a significant challenge. Metric Interval Temporal Logic (MITL) is a powerful language for specifying these requirements, but translating MITL formulas into standard timed automata (which are the basis for many verification tools) often leads to very large and complex automata. Existing methods for this translation involve a "guess-and-check" approach, which typically requires introducing alternation into the automata, and then a subsequent, computationally expensive "de-alternation" step. Furthermore, while algorithms exist for checking liveness in standard timed automata, no such algorithms were known for the more expressive GTA model, which is better suited for representing MITL.

Methods

The authors propose two main contributions:

  1. MITL to GTA Translation: They present a new, more concise translation from MITL to Generalized Timed Automata (GTAs). GTAs are an extension of timed automata that include "future clocks." These future clocks act like timers that can "guess" a future event's timing and then check if that guess was correct. This feature naturally handles the "guess-and-check" aspect of MITL modalities, leading to a more direct and, for certain modalities like "until," an exponentially more succinct translation compared to prior methods.
  2. Liveness Algorithm for GTAs: A key challenge for GTAs is the absence of a finite "region equivalence," a crucial tool for developing liveness algorithms in standard timed automata. The authors develop a new zone-based algorithm for checking Büchi non-emptiness (a form of liveness) in GTAs. This algorithm circumvents the lack of a finite region equivalence by leveraging a new equivalence relation and carefully handling diagonal constraints, which are common in GTAs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Future Clocks as a Natural Fit: The introduction of "future clocks" in GTAs provides a more direct and elegant way to model the "guess-and-check" nature of temporal logic modalities like MITL's "next" and "until," avoiding the need for complex de-alternation steps.
  • Bypassing Region Equivalence: The lack of a finite region equivalence in GTAs is a significant obstacle for liveness checking. The authors demonstrate that it's possible to develop liveness algorithms by devising alternative equivalence relations and carefully managing the state space, particularly in the presence of diagonal constraints.
  • Compositional Translation: The paper outlines a compositional approach to translating MITL formulas into GTAs, building up complex formulas from simpler ones using standard transducer composition and product operations. This modularity is key to managing the complexity of the translation.

Key Results

  • Exponential Improvement: The proposed MITL to GTA translation offers an exponential improvement in the number of locations for the "timed until" modality compared to state-of-the-art methods.
  • First Liveness Algorithm for GTAs: The paper presents the first zone-based algorithm for checking Büchi non-emptiness (liveness) in GTAs, a significant theoretical advancement.
  • Safe GTA Construction: The translation results in "safe" GTAs, a restricted but still powerful class of GTAs for which the liveness problem is decidable.

Limitations and Future Work

  • Implementation and Performance: The authors acknowledge that implementing these algorithms and evaluating their practical performance, especially compared to existing tools, would require significant effort and optimization.
  • Scalability: Making the approach scalable for large real-time systems is identified as a major area for future work.
  • Generalizing Liveness: While the paper provides a liveness algorithm for safe GTAs, extending it to more general GTA models might be a future direction.

Summary updated

Abstract

The translation of Metric Interval Temporal Logic (MITL) to timed automata is a topic that has been extensively studied. A key challenge here is the conversion of future modalities into equivalent automata. Typical conversions equip the automata with a guess-and-check mechanism to ascertain the truth of future modalities. Guess-and-check can be naturally implemented via alternation. However, since timed automata tools do not handle alternation, existing methods perform an additional step of converting the alternating timed automata into timed automata. This de-alternation step proceeds by an intricate finite abstraction of the space of configurations of the alternating automaton. Recently, a model of generalized timed automata (GTA) has been proposed. The model comes with several powerful additional features, and yet, the best known zone-based reachability algorithms for timed automata have been extended to the GTA model, with the same complexity for all the zone operations. We provide a new concise translation from MITL to GTA. In particular, for the timed until modality, our translation offers an exponential improvement w.r.t. the state-of-the-art. Thanks to this conversion, MITL model checking reduces to checking liveness for GTAs. However, no liveness algorithm is known for GTAs. Due to the presence of future clocks, there is no finite time-abstract bisimulation (region equivalence) for GTAs, whereas liveness algorithms for timed automata crucially rely on the presence of the finite region equivalence. As our second contribution, we provide a new zone-based algorithm for checking Buchi non-emptiness in GTAs, which circumvents this fundamental challenge.
BibTeX
@inproceedings{akshay2024mitl,
  author = {S. Akshay and Paul Gastin and R. Govind and B. Srivathsan},
  title = {{MITL Model Checking via Generalized Timed Automata and a New Liveness Algorithm}},
  booktitle = {CONCUR},
  year = {2024},
  url = {https://openreview.net/forum?id=PVhyOFbZNg},
}
Figure