Abstract
This paper presents TAG (Timed Automata Generator), a novel passive learning algorithm designed to automatically infer deterministic Timed Automata from system event logs. By utilizing a single user-defined parameter $k$, TAG balances model complexity with high precision, addressing common challenges in automated modeling such as hyperparameter bloat and non-determinism. The algorithm produces human-understandable and mathematically rigorous models of temporal behavior in complex real-time systems.
Introduction
Understanding the behavior of complex physical or software systems often requires formal models. However, manual creation of these models is slow and error-prone. While modern systems generate massive amounts of event logs, converting these logs into a "global" model that describes the whole system's behavior over time remains a significant challenge.
Timed Automata (TA) are a standard formalism for such models, incorporating explicit clock constraints to define when events are allowed to occur. Figure 1 illustrates a simple TA for a lamp controller, where transitions depend on both discrete events and temporal guards.
Problem Statement
Existing techniques for learning Timed Automata from logs suffer from three primary issues:
- Hyperparameter Bloat: Many algorithms require numerous parameters that are difficult for non-experts to tune.
- Non-Determinism: Models may produce multiple possible states for the same event at the same time, making them hard to interpret.
- Imprecision: Over-generalization often leads to the loss of specific timing "guards" that define system logic.
The TAG Algorithm
TAG is designed to learn Deterministic Real-Time Automata (DRTA) using only one parameter: $k$, representing the "look-ahead" distance used to determine state equivalence. The algorithm follows a three-step pipeline:
- Automaton Initialization: A "prefix tree" is built where every unique sequence of events in the log is represented by a unique path.
- States Merging: Similar to the classic $k$-Tail algorithm, TAG merges states with identical future event sequences of length $k$ to shrink and generalize the model.
- Transitions Splitting: This novel refinement step ensures determinism. If logs show that an event leads to different future behaviors depending on when it occurred, TAG splits the transition into specific timing guards.
Experimental Evaluation
The researchers evaluated TAG using two primary sources:
- Synthetic Benchmarks: 200 Timed Automata were generated with varying complexities to establish a ground truth for accuracy and runtime testing.
- Real-World TV Logs: Logs from the Canadian TV channel CBC Windsor were used to test interpretability (small dataset) and scalability (two months of logs).
Key Results and Insights
- Superior Precision: In synthetic tests, TAG achieved an average precision of 0.92, significantly outperforming competitors like RTI+ (0.44) and Timed k-Tail (0.58).
- Balanced F1-Score: TAG achieved the best overall balance of precision and recall, ensuring it does not "hallucinate" behaviors absent from the real system.
- Real-World Utility: On TV log data, TAG produced a 6-state model reflecting the structure of morning broadcasts (News $\rightarrow$ Ads $\rightarrow$ Children's Programs). This model allowed researchers to calculate complex probabilities, such as the likelihood of watching an hour of children's programming without interruption (7-8%).
- Determinism and Interpretability: By forcing the output to be deterministic, TAG ensures the model remains visually inspectable and useful for engineers.
Conclusion
TAG provides a powerful, accessible tool for learning formal models from logs. By performing structural merging first and then "splitting" transitions based on temporal evidence, it effectively manages the trade-off between simplicity and specificity. Future work will focus on learning models composed of interacting subsystems and applying TAG to anomaly detection and predictive maintenance.
Summary updated