Monitoring Timed Properties (Revisited)

Thomas Møller Grosen, Sean Kauffman, Kim Guldstrand Larsen, Martin Zimmermann

Abstract

In this paper we study monitoring of real-time systems with respect to properties expressed either in Metric Interval Temporal Logic or as Timed Büchi Automata. We offer efficient symbolic online monitoring algorithms in a number of settings, exploiting so-called zones well-known from efficient model checking of Timed Automata. Our contributions include a new, much simplified treatment of time divergence and monitoring under timing uncertainty. The online monitoring procedure that handles time divergence, as well as uncertain timing, is implemented in the tool MoniTAal, and shown to effectively monitor properties over long traces.

Introduction

Runtime monitoring is a critical technique for ensuring that a running system adheres to its formal specifications. In the context of real-time systems, these specifications often involve strict temporal constraints, such as "a response must occur within 20 milliseconds of a request." While theoretical frameworks for monitoring exist, practical application faces two significant hurdles: time divergence and timing uncertainty.

Time divergence refers to the fundamental physical reality that time always progresses toward infinity. Many existing monitoring algorithms fail to account for this, often resulting in "unknown" verdicts for properties that would be clearly violated if time were allowed to pass. Timing uncertainty, on the other hand, stems from the imprecision of real-world sensors and logging mechanisms. Instead of a precise timestamp, events are often observed within a time interval (e.g., "between 10.1 and 10.2 seconds").

This paper introduces an efficient symbolic online monitoring algorithm that addresses these challenges by leveraging "zones"—a symbolic representation technique borrowed from the field of model checking. The resulting tool, MoniTAal, provides a high-performance solution for verifying complex temporal properties in realistic, imprecise environments.

Methodology

The proposed monitoring framework follows a symbolic approach to handle the infinite state space of timed systems.

Formalism: From Logic to Automata

The process begins by expressing system properties in Metric Interval Temporal Logic (MITL), which are then translated into Timed Büchi Automata (TBA). A TBA extends standard finite automata with a set of real-valued clocks that track elapsed time. Transitions between states are guarded by clock constraints and can include clock resets.

Figure 1: A Timed Büchi Automaton (TBA) representing a bounded response property: "whenever 'a' is observed, 'b' should be observed within 30 time units."

Symbolic Reachability with Zones

To avoid the state-space explosion associated with exact timing (the "region" problem), the algorithm utilizes zones. Zones are sets of clock constraints represented as Difference Bounded Matrices (DBMs). This symbolic representation allows the monitor to track a finite number of symbolic states, each representing an infinite set of concrete clock valuations. This shift from regions to zones provides an order-of-magnitude improvement in computational performance.

Addressing Divergence and Uncertainty

A key contribution of this work is the simplified treatment of time divergence. By intersecting the property automaton with a specialized "time-divergent" automaton, the monitor is forced to consider only those future paths where time progresses to infinity. This allows the monitor to proactively identify violations that would occur simply by the passage of time.

Furthermore, the algorithm is extended to handle symbolic timed words, where event times are provided as intervals $[l, u]$. The symbolic successor computation is adapted to account for all possible concrete timings within these intervals, ensuring that the monitor remains sound even under timing uncertainty.

Experimental Evaluation

The effectiveness of the proposed approach and the MoniTAal tool was evaluated using both synthetic benchmarks and an industrial case study.

Industrial Case Study: Gear Controller

The tool was tested against a verified model of a gear controller developed in collaboration with an automotive company. This model includes complex timing requirements for gear shifting under various failure conditions. MoniTAal demonstrated exceptional performance, with a maximum response time—the time taken to provide a verdict after an observation—typically under 100 microseconds, even for traces containing 10,000 events.

Scalability and Robustness

In synthetic benchmarks, the tool successfully monitored traces with up to 200,000 observations. Memory growth remained negligible due to the implementation of "inactive clock abstraction," which prunes timing data that is no longer relevant to future transitions. Crucially, the monitor correctly identified property satisfaction and violation even when event timings were imprecise, a feature missing from most contemporary monitoring tools.

Conclusion and Future Work

This research demonstrates that symbolic monitoring using zones is a viable and highly efficient approach for real-time systems. By treating time divergence as a reachability problem and incorporating interval-based timing, the authors have bridged the gap between theoretical monitoring and practical application.

Future work will focus on extending the framework to handle unobservable symbols (silent transitions) and input mutations, where the sequence of events itself might be noisy or permuted. Additionally, the authors aim to further optimize the handling of highly non-deterministic specifications to ensure consistent performance across all property types.

Summary updated

BibTeX
@inproceedings{grosen2022monitoring,
  author = {Thomas Møller Grosen and Sean Kauffman and Kim Guldstrand Larsen and Martin Zimmermann},
  title = {{Monitoring Timed Properties (Revisited)}},
  booktitle = {FORMATS},
  year = {2022},
  doi = {10.1007/978-3-031-15839-1\_3},
}
Figure