Data Reduction in Intrusion Alert Correlation

Gianni Tedesco, Uwe AickelinSsrn 2006 · DOI · OpenReview

Abstract: Network intrusion detection sensors are usually built around low level models of network traffic. This means that their output is of a similarly low level and as a consequence, is difficult to analyze. Intrusion alert correlation is the task of automating some of this analysis by grouping related alerts together. Attack graphs provide an intuitive model for such analysis. Unfortunately alert flooding attacks can still cause a loss of service on sensors, and when performing attack graph correlation, there can be a large number of extraneous alerts included in the output graph. This obscures the fine structure of genuine attacks and makes them more difficult for human operators to discern. This paper explores modified correlation algorithms which attempt to minimize the impact of this attack.

Introduction

Network Intrusion Detection Systems (NIDS) are notoriously "noisy." Operating at a low level, they generate alerts for every suspicious packet, a characteristic that attackers exploit via alert flooding. Tools like Stick or Snot can generate thousands of bogus alerts, creating a three-pronged Denial of Service (DoS) attack against security infrastructure: storage exhaustion, processing bottlenecks, and cognitive overload for human analysts. While existing tools use TCP state tracking to filter some noise, they remain vulnerable to stateless protocols or single-packet exploits.

Methodology: Strategic Correlation

This research proposes a "strategic" approach to defending IDS against alert-flooding. The core innovation lies in integrating a Token Bucket Filter (TBF) directly into an attack-graph correlation engine.

Attack Graphs and Queue Graphs

Rather than analyzing alerts in isolation, the system maps them to a Directed Acyclic Graph (DAG). In this model, vertices represent vulnerabilities or states, and edges represent the logical steps an attacker must take to progress toward a goal.

An attack graph illustrating multiple exploit paths (Sadmind AMSLVerify or Sendmail Buffer Overflow) leading to root privileges.

The authors utilize a "Queue Graph" (QG) structure where each exploit vertex acts as a queue for incoming alerts. By placing a TBF at each queue, the system can rate-limit alerts based on their strategic context. If an attacker floods a specific exploit path, the TBF discards the excess while maintaining the overall graph structure.

Data Preservation and Fallbacks

To ensure analysts are aware of dropped alerts, the system employs Run Length Encoding (RLE), using counters to indicate repeated messages. For alerts that do not map to the known attack graph, a per-signature TBF fallback prevents "unknown" floods from crashing the system while still allowing a low-volume trickle of potentially novel attack strategies to reach the operator.

Experimental Evaluation

The approach was evaluated using the Firestorm IDS and tcpdump data from a Defcon Capture The Flag event. The test scenario involved a repeated ICMP flood at approximately 7,343 packets per second against a signature base of 1,600 Snort-style rules.

Results

The integration of context-aware throttling yielded dramatic improvements in system stability and data clarity.

Experimental results comparing control and throttled runs.

As shown in the results, the throttled run achieved a ~435x reduction in data size and a ~432x reduction in alert count. Crucially, the system was ~30% faster in terms of elapsed time. The primary performance gain came from reducing I/O operations—writing fewer alerts to disk—rather than just CPU savings.

Conclusion

By moving the throttle inside the correlation engine, the system makes strategic decisions about data retention. This ensures that even under extreme alert flooding, the IDS remains functional and provides a clear, manageable attack scenario to the human operator. Future work will focus on optimizing TBF parameters and refining the handling of alerts that fall outside known attack graphs.

Summary updated

Abstract

Network intrusion detection sensors are usually built around low level models of network traffic. This means that their output is of a similarly low level and as a consequence, is difficult to analyze. Intrusion alert correlation is the task of automating some of this analysis by grouping related alerts together. Attack graphs provide an intuitive model for such analysis. Unfortunately alert flooding attacks can still cause a loss of service on sensors, and when performing attack graph correlation, there can be a large number of extraneous alerts included in the output graph. This obscures the fine structure of genuine attacks and makes them more difficult for human operators to discern. This paper explores modified correlation algorithms which attempt to minimize the impact of this attack.
BibTeX
@misc{tedesco2006data,
  author = {Gianni Tedesco and Uwe Aickelin},
  title = {{Data Reduction in Intrusion Alert Correlation}},
  year = {2006},
  eprint = {0804.1281},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0804.1281},
  howpublished = {Ssrn},
}
Figure