MONAA: A Tool for Timed Pattern Matching with Automata-Based Acceleration

Masaki Waga, Ichiro Hasuo, Kohei Suenaga

Abstract

MONAA is a high-performance tool designed for timed pattern matching, a process used to identify specific sequences of events with timing constraints in large data logs. By adapting classic string-matching "skipping" techniques to timed automata, MONAA achieves significant speedups while maintaining a constant memory footprint. This paper presents the methodology behind MONAA, including its use of timed automata and pre-computed skip tables. Evaluation on automatic transmission system logs demonstrates that MONAA significantly outperforms existing state-of-the-art tools, offering linear scalability and high efficiency for both online and offline monitoring tasks.

Introduction

As systems like autonomous cars and industrial robots become more complex, monitoring their behavior for safety and performance is critical. Engineers often need to search through massive "timed words"—logs of events where each entry has a precise timestamp—to find segments that match specific requirements, such as: "The gear must shift from 1st to 4th while engine RPM is high, all within 10 seconds."

Existing tools for timed pattern matching often struggle with the volume of data, exhibiting slow performance or high memory requirements. Furthermore, live systems require "online" monitoring to detect patterns as data arrives, rather than waiting for the system to finish running. MONAA addresses these challenges by providing a scalable, memory-efficient solution.

Methods

MONAA implements a novel "timed FJS algorithm," inspired by classic string-searching algorithms like Knuth-Morris-Pratt (KMP) and Boyer-Moore. These algorithms speed up searches by "skipping" sections of text that cannot possibly contain a match.

To handle the continuous time domain of timed words, MONAA represents search patterns as Timed Automata (TA)—state machines that track time using clocks. Before the search begins, MONAA pre-computes a skip table by analyzing the pattern to determine how many events it can safely skip based on current observations. This process utilizes "zone constructions" to handle continuous timing constraints. MONAA offers two primary interfaces: a command-line tool for general use and a C++ API (libmonaa) that allows developers to hard-code specifications directly into software for maximum performance.

Evaluation

The researchers evaluated MONAA using logs generated from a Simulink model of an automatic transmission system. The input timed words ranged from 708 to over 1.7 million entries. The test specification involved complex gear changes ($g_1$ through $g_4$) and engine rotation speeds ($\omega$) within specific time windows. MONAA was benchmarked against Montre, a state-of-the-art tool for timed regular expression matching, in both online and offline modes.

Key Results and Discussion

Benchmarks demonstrate that MONAA significantly outperforms existing solutions in terms of execution speed and memory stability. For the largest log (1.7M entries), MONAA's command-line tool (using the TA interface) finished in approximately 4.5 seconds, compared to nearly 290 seconds for Montre's online mode. Using the libmonaa API with a hard-coded specification further reduced the execution time to just 1.07 seconds.

Table 3: Execution time comparison (seconds) across different tools and log lengths.

A critical advantage of MONAA is its constant memory footprint. While Montre's offline memory usage grew linearly with the log size, reaching over 166 MB for the largest dataset, MONAA's memory usage remained stable between 7 MB and 16 MB regardless of the data volume. This stability makes MONAA ideal for long-term monitoring of real-time systems.

Table 1: Memory usage comparison (KB) across different tools and log lengths.

Conclusion

MONAA provides a scalable solution for real-time monitoring of complex systems. While translation overhead from regular expressions to automata is a current bottleneck for very short logs, the tool's linear time complexity and stable memory usage make it ideal for large-scale data processing. Future work includes refining skipping logic with more sophisticated timing analysis and integrating libmonaa into live control loops for real-time safety enforcement.

Summary updated

Abstract

We present mmonaa, a monitoring tool over a real-time property specified by either a timed automaton or a timed regular expression. It implements a timed pattern matching algorithm that combines 1) features suited for online monitoring, and 2) acceleration by automata-based skipping. Our experiments demonstrate \monaa's performance advantage, especially in online usage.
BibTeX
@inproceedings{waga2018monaa,
  author = {Masaki Waga and Ichiro Hasuo and Kohei Suenaga},
  title = {{MONAA: A Tool for Timed Pattern Matching with Automata-Based Acceleration}},
  booktitle = {MT@CPSWeek},
  year = {2018},
  url = {https://openreview.net/forum?id=LX6iKBMjMA},
}
Figure