Passive learning of Timed Automata from logs (Student Abstract)

Lénaïg CornanguerAAAI 2021 · DOI

Introduction

Reverse-engineering the "hidden logic" of time-sensitive systems is a critical task in modern engineering. At AAAI-21, a new approach was presented to learn these models directly from event logs. The proposed algorithm, TAG (Timed Automata Generator), learns deterministic Timed Automata by combining state-merging with a novel "transition division" strategy. This method achieves a superior balance between model simplicity and temporal precision compared to existing state-of-the-art (SOTA) methods.

The Challenge of Passive Learning

Many complex systems—ranging from industrial controllers to biological ecosystems—generate logs of timestamped events. To understand or verify these systems, researchers often use Timed Automata (TA). These are state-transition diagrams where transitions are gated by "clocks" and "guards." For example, a system might only transition to a new state if an event occurs within a specific time window.

Example of a Timed Automaton (TA) with states and temporal guards.

Learning these models "passively"—using only logs without the ability to probe the system—is an NP-hard problem. Existing algorithms typically struggle with two issues:

  1. Over-generalization: Creating guards that are too broad, leading to high False Positive Rates (FPR).
  2. Over-complexity: Producing massive, non-deterministic models that are difficult for humans to interpret.

The TAG Algorithm

TAG addresses these issues through a two-phase process:

1. Conciseness and Determinism

The algorithm begins by constructing a prefix tree from the logs. It then merges states that exhibit the same "k-future" (identical behavior for the next $k$ steps). If a merge introduces non-determinism—where a single event could lead to multiple states—TAG continues merging until the model is deterministic.

2. Temporal Precision via Transition Division

The core innovation of TAG is "transition division." The algorithm identifies instances where the timing of an event alters subsequent behavior. If an event at time $t_1$ leads to a different future than the same event at time $t_2$, TAG splits the transition and its target state into distinct paths. This allows the model to capture precise temporal constraints that standard merging algorithms often overlook.

The resulting model is a PDRTA (Probabilistic Deterministic Real-Time Automaton) that remains concise while maintaining high sensitivity to timing.

Experimental Evaluation

The authors evaluated TAG using a synthetic benchmarking approach. A known Timed Automaton served as the ground truth to generate 1,000 positive event sequences (70% training, 30% testing). Additionally, 300 negative sequences were designed to test the False Positive Rate.

Key Results

In head-to-head testing against SOTA algorithms, TAG was the only one to achieve a perfect score across all metrics.

Performance comparison of TAG against SOTA algorithms GenProgTA and RTI+.

While RTI+ exhibited a high FPR (accepting 66 "illegal" sequences) and GenProgTA failed to recognize some "legal" sequences, TAG successfully reconstructed the exact target automaton with the optimal number of states.

Conclusion and Future Work

TAG demonstrates that selectively "splitting" transitions is as vital as merging states for learning accurate Timed Automata. By enforcing determinism, the algorithm ensures the resulting models are practical for formal verification and controller synthesis. Future work will focus on scaling the algorithm for massive real-world datasets and developing better distance metrics for model validation.

Summary updated

BibTeX
@inproceedings{cornanguer2021passive,
  author = {Lénaïg Cornanguer},
  title = {{Passive learning of Timed Automata from logs (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17883},
}
Figure