Introduction
Modern Intrusion Detection Systems (IDS) are notoriously noisy, often triggering thousands of low-level alerts for a single network event. This phenomenon, known as "alert fatigue," overwhelms security administrators and obscures critical threats. To address this, alert correlation—the process of grouping related alerts into high-level attack scenarios—is essential.
Existing correlation methods typically face a trade-off: knowledge-based systems are fast but cannot detect novel attacks, while statistical or machine learning approaches often rely on computationally expensive pair-wise comparisons. In high-traffic environments where 5,000 alerts per minute is standard, these methods frequently fail to scale. This paper presents a high-performance framework designed to bridge this gap by combining automated pattern discovery with real-time stream processing capabilities.
System Architecture and Methodology
The proposed framework utilizes a multi-stage pipeline optimized for high throughput and incremental updates. The process begins with Aggregation and Virtual Patterns, where raw alerts are generalized into "Hyper Alerts." For instance, multiple probes from various sources targeting a single destination are abstracted into a single "Many-to-one" pattern. This abstraction reduces the complexity of the data stream before it reaches the mining engine.
At the heart of the system is the Frequent Structured Pattern Tree (FSP_Tree) and the associated FSP_Growth algorithm. Unlike traditional frequent itemset mining, which only tracks what items appear together, the FSP_Tree encodes the connectivity and topology of alerts (the "who talked to whom" graph structure) directly into its branches. This allows the system to identify recurring attack strategies, such as DDoS or multi-stage exploits, based on their structural signatures.
To manage the continuous nature of network data, the framework employs Tilted-Time Windows. This technique maintains fine-grained data for the most recent events while progressively aggregating older data into coarser summaries. This approach ensures the system remains memory-efficient while still allowing for historical queries and the detection of "concept drift" as attack patterns evolve over time.
Evaluation and Key Results
The framework was evaluated using both synthetic datasets (up to 60,000 graphs) and a massive real-world dataset consisting of 3.2 million alerts collected over one month from a public WiFi network in Fredericton, Canada.
Performance and Scalability
- High Throughput: The system demonstrated the ability to process over 400,000 alerts per minute on standard hardware, significantly exceeding the requirements of large-scale networks.
- Linear Scalability: Processing time grew linearly with dataset size, avoiding the exponential complexity traps of pair-wise statistical methods.
- Model Stability: The pattern tree was shown to stabilize after approximately two weeks of operation, indicating that the system effectively filters transient noise to focus on persistent, meaningful behaviors.
Pattern Discovery
The system successfully identified complex, multi-step attack sequences in real-world traffic, such as the progression from Host Query to ICMP Reconnaissance and finally to a Buffer Overflow attempt. By using structural abstraction, the system recognized these patterns even when the specific IP addresses involved changed.
Discussion and Future Work
While the framework offers significant advancements in speed and automated discovery, it is not without limitations. Currently, the system may identify frequent but non-malicious patterns caused by network maintenance or misconfigurations. Future work will focus on developing automated filters for these "false positive patterns."
Additionally, the system's reliance on a fixed activity threshold (e.g., 60 seconds) means that extremely "slow-burning" attacks—those with steps separated by hours or days—might be missed. The authors suggest that adaptive time windows, which adjust based on the type of pattern observed, represent a promising direction for enhancing the system's detection capabilities against sophisticated, long-term threats.
Summary updated