Hypergraph-Guided Regex Filter Synthesis for Event-Based Anomaly Detection
Margarida Ferreira, Victor Nicolet, Luan Pham, Joey Dodds, Daniel Kroening, Ines Lynce, Ruben Martins · 2025
Read Hypergraph-Guided Regex Filter Synthesis for Event-Based Anomaly Detection by Margarida Ferreira, Victor Nicolet, Luan Pham, Joey Dodds, Daniel Kroening, Ines Lynce, Ruben Martins (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06911.txt.
Introduction
Readable patterns, written as regular expressions, that flag strange events are synthesized by Margarida Ferreira and six co-authors in a 2025 anomaly detection paper. In a stationary system, any deviation from past behavior may signal malicious activity. Deep learning detectors work, but their alarms are hard to explain.
Their algorithm, HyGLAD, first infers groups of entities that behave alike, using a hypergraph view of the events. It then builds regular expressions capturing the values those entities take. Because the patterns are readable, the anomalies they catch are interpretable too. Against seven unsupervised deep-learning detectors from a standard library, across five real-world datasets, HyGLAD improved precision and recall over the second-best method. It also trained and ran about ten times faster, on a single CPU rather than a graphics processor.
Catalog record
| CREATOR | Margarida Ferreira, Victor Nicolet, Luan Pham, Joey Dodds, Daniel Kroening, Ines Lynce, Ruben Martins |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06911
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hypergraph-Guided Regex Filter Synthesis for Event-Based Anomaly Detection Margarida Ferreira, Victor Nicolet, Luan Pham, Joey Dodds, Daniel Kroening, Ines Lynce, Ruben Martins Abstract . We propose HyGLAD , a novel algorithm that automatically builds a set of interpretable patterns that model event data. These patterns can then be used to detect event-based anomalies in a stationary system, where any deviation from past behavior may indicate malicious activity. The algorithm infers equivalence classes of entities with similar behavior observed from the events, and then builds regular expressions that capture the values of those entities. As opposed to deep-learning approaches, the regular expressions are directly interpretable, which also translates to interpretable anomalies. We evaluate HyGLAD against all 7 unsupervised anomaly detection methods from DeepOD ( Zuo 2021 ) on five datasets from real-world systems. The experimental results show that on average HyGLAD outperforms existing deep-learning methods while being an order of magnitude more efficient in training and inference (single CPU vs GPU). Precision is improved by 1.2 × \times and recall by 1.3 × \times compared to the second-best baseline. 1. Introduction Event-based anomaly detection focuses on identifying irregularities in events 1 1 1 https://opentelemetry.io/docs/specs/semconv/general/events/ , a type of machine-generated data that captures system activity in a predefined schema (e.g., time, actor, operation) ( Amazon Web Services 2024 ; Google Cloud 2024 ; Microsoft Corporation 2024 ) . These events are ubiquitous in cloud platforms and applications, where they serve as rich sources of data for understanding system behavior. Unlike unstructured logs ( Le and Zhang 2021 ; Du et al. 2017 ) , which contain free-text messages, events such as the one given in Figure 1 are suitable for systematic mining and modeling. ⬇ { "actor" : { "id" : "AttrService-InstanceRole-BTDN", ... }, "api" : { "operation" : "GetInstanceStatus", "request.data" : { "instanceID" : "i-12345", "asnDesc": "AMAZON-AES"} } } Figure 1. Example of an event in OCSF schema ( The OCSF Community 2024 ) . Recent studies ( He et al. 2021 ; He et al. 2022 ; He et al. 2016 ; Landauer et al. 2023 ; Le and Zhang 2022 ; Zhu et al. 2023 ) report that despite interest in log- and event-based anomaly detection, several key challenges remain unresolved and block adoption. Because unsupervised approaches are less accurate than supervised approaches ( He et al. 2021 ; He et al. 2022 ) and real-world labeled anomaly data is scarce, users must choose between generating labeled data for their unique system and relying on less powerful unsupervised techniques. In addition to accuracy, existing systems are not interpretable ( Landauer et al. 2023 ) or efficient ( He et al. 2021 ) enough for wide use. If an event is identified as an anomaly, it is crucial that this information is available to the user immediately, along with additional context to support further diagnosis and mitigation. Some systems generate billions of events per day, requiring fast and incremental detection techniques. While deep learning approaches fit the requirements on accuracy ( Landauer et al. 2023 ) , they are not interpretable and are computationally expensive. Deep learning approaches take an all-in view on anomaly detection where all of their processing is encoded in an uninterpretable statistical model. This gives them flexibility because they can be trained on almost any input, but the statistical models might be hiding many sub-problems in anomaly detection that can be tackled with efficient and interpretable algorithmic approaches. Our work identifies event categorization as a sub-problem that can be solved in an efficient and interpretable manner. In event categorization, the goal is to dynamically generate a set of general equivalence classes that covers the normal events in a system. Our approach is unconventional in that it solves the event categorization problem first and then uses the equivalence classes to detect anomalies: any event that does not fall into a known class is anomalous. We show that the resulting anomaly detection approach is more accurate than existing deep-learning methods. The key to building these equivalence classes is generalizing correctly over entities in the system. For example, imagine a system where three usernames appear in events, System-Read-QCHXY , System-Read-RBLEA and System-Admin-DFGRD . The two System-Read users can be observed to behave in the same way in event data. If these two users fall into different equivalence classes, a third System-Read user that is created later will always appear as anomalous, even if it behaves the same as the other read accounts. The pattern we want is System-Read-* . On the other hand, if we generalize more, we run into another problem. The pattern System-*-* is too general, because it also captures our admin user, which can be observed behaving in ways that the read users don’t. We present HyGLAD , which synthesizes regular expression-based equivalence classes from a baseline of normal system behavior recorded in events. A key benefit of our regex-based equivalence model is that the model itself can be directly understood by humans. These benefits carry through to the anomaly detection method, which amounts to matching a few regexes per event (27 MB/s on a single CPU core), and where each anomaly is easily explained by comparing it to our known equivalence classes. Our equivalence classes are a set of filters consisting of regular expressions, where each filter matches events. The regexes in the filters are a generalization of string values that appear in the events: they match at least those values and may additionally match other similar-looking values representing entities that behave similarly. Generalizing solely based on the values themselves would introduce rules that accept potentially anomalous behavior. The key insight of our approach is that events record the underlying relations between entities in a system, and these relations can safely guide the generalization over the observed values. In other words, we combine and generalize entities that we observe acting in the same way with respect to other entities. We use this information to decide when to synthesize regexes that generalize over multiple entities. In summary, we make the following contributions in this paper: • We propose a new algorithm, HyGLAD , that builds interpretable regex-based equivalence classes for events using a graph-based similarity metric to group entities. • We release three novel datasets with a total of 8.5 million events to benchmark event-based anomaly detection algorithms. Our datasets are collected from three large-scale cloud service systems containing thousands of resources and interacting actors, with labeled anomalous events. • We extensively benchmark HyGLAD against seven state-of-the-art anomaly detection methods from DeepOD ( Zuo 2021 ) on five real-world datasets. Our results show HyGLAD is efficient and accurate: HyGLAD can scan 27 MB/s of events on a single CPU core with 93% recall and 81% precision. 2. Related Work Event-based anomaly detection is less explored than log-based detection. In this section, we review related studies and insights on their limitations that motivate our approach. Surveys. Recent surveys ( He et al. 2021 ; He et al. 2022 ; He et al. 2016 ; Landauer et al. 2023 ; Le and Zhang 2022 ; Zhu et al. 2023 ) highlight three key limitations of existing methods. First, many high-performing techniques lack interpretability and explainability , making it