Reversible sketches for efficient and accurate change detection over network data streams

Robert Schweller, Ashish Gupta, Elliot Parsons, Yan Chen2004 · DOI

TL;DR

This paper introduces "reversible sketches," a novel technique that allows for efficient and accurate detection of significant changes in network traffic without needing to store individual flow information. This overcomes a major hurdle in using sketch-based methods for real-time anomaly detection in high-speed networks, enabling faster identification of problematic flows.

What Problem Does This Paper Address?

Network operators face a growing challenge in detecting traffic anomalies like failures and attacks. While sketch-based methods offer a scalable way to monitor massive data streams at high speeds, they typically lose the original "keys" (like source IP addresses) of the traffic flows. This makes it difficult to pinpoint which specific flows are causing anomalies, even if the anomaly itself is detected. Storing all flow keys is infeasible due to the sheer volume. This paper tackles the problem of how to identify the specific "culprit" flows responsible for detected heavy changes in network traffic, without the prohibitive cost of storing per-flow state.

Methods

The core innovation is the concept of reversible sketches. The authors build upon the k-ary sketch, a probabilistic data structure that summarizes network traffic with minimal memory. The key challenge with standard k-ary sketches is their irreversibility – you can estimate aggregate changes but not identify the contributing keys.

To address this, they introduce two main techniques:

  • Modular Hashing: Instead of hashing the entire key (e.g., a 32-bit IP address) directly, the key is broken into smaller "words." Each word is then hashed independently using separate hash functions. These individual hashes are then combined to form the final hash. This increases the update time slightly but is crucial for the reversibility mechanism.
  • IP Mangling: To combat the issue of correlated IP addresses (e.g., many flows sharing the same network prefix), they employ a reversible transformation (like an OLE transformation, f(x) = ax mod n) to "mangle" the input keys. This randomization helps ensure that the modular hashing distributes keys more uniformly, mimicking the behavior of truly random hash functions and improving sketch accuracy.

The "reversal" process then involves a Reverse Sketch Problem. Given the sketch and information about which buckets are "heavy" (indicating a significant change), the system reconstructs the set of original keys that likely contributed to these heavy buckets. For single heavy buckets, this involves intersecting sets of potential keys. For multiple heavy buckets, they propose more complex graph-based approaches and optimizations to efficiently find the suspect keys.

Datasets

The evaluation was performed using Netflow traffic traces from a large edge router at Northwestern University. These traces represent real-world network traffic. The authors divided the data into five-minute intervals and used the volume change of the top-x IPs as a ground truth for comparison. No new benchmarks were introduced; rather, existing real-world data was used.

Key Insights and Ideas

  • The "Key" is Crucial for Actionable Anomaly Detection: Detecting an anomaly is only half the battle; identifying the source is essential for mitigation. Sketches are great for detection but poor for identification.
  • Reversibility is the Missing Link: By making sketches reversible, we can bridge the gap between aggregate anomaly detection and actionable flow-level identification.
  • Modular Hashing and IP Mangling are Synergistic: Modular hashing breaks down the problem, while IP mangling ensures that the input data is sufficiently randomized for the modular hashing to work effectively and avoid skewed distributions.
  • Efficiency Trade-offs: While modular hashing and IP mangling add some overhead, they are designed to be sub-linear in the key space size, making them scalable for massive networks. The paper highlights a trade-off between the size of the sketch (related to m) and the efficiency of reverse hashing (related to q).

Key Results

  • The proposed reversible sketch system can quickly infer the keys of culprit flows with high accuracy.
  • Evaluated on real Netflow data, the system achieved over 95% true positive rate and less than 2% false positive rate for detecting heavy changes, with results reported in 0.42 seconds for up to 100 heavy changes.
  • The streaming data recording used less than 200KB of memory.
  • The IP mangling technique effectively randomized input keys, leading to a distribution of keys per bucket comparable to direct hashing, unlike standard modular hashing which resulted in highly skewed distributions.
  • For single heavy changes, the system achieved 100% real positive and zero false positive rates.
  • For multiple heavy changes, with parameters like H=6 and k=212 (using 192KB for sketches), the system achieved over 95% true positive rates for up to 140 heavy changes with negligible false positives.

Limitations and Future Work

  • Hierarchical vs. Non-Hierarchical Keys: The IP mangling scheme discussed is particularly effective for hierarchical keys like IP addresses. The paper notes that for non-hierarchical keys (e.g., source/destination IP pairs), an alternative, slightly less efficient scheme is needed (detailed in [23]).
  • False Positives with Multiple Heavy Buckets: The paper acknowledges that generalizing to multiple heavy buckets per hash table can lead to a higher number of false positives, and the proposed verification methods are only applicable for small numbers of heavy buckets.
  • Future Work: The paper refers to a more detailed technical report [23] for optimized algorithms, further evaluations, and more comprehensive discussions on reducing false positives and negatives, as well as improving efficiency for multiple heavy changes. This includes exploring a new IP-mangling scheme with better statistical properties for non-hierarchical keys and using a second verifier sketch with 4-universal hash functions to reduce false positives.

Summary updated

Abstract

Traffic anomalies such as failures and attacks are increasing in frequency and severity, and thus identifying them rapidly and accurately is critical for large network operators. The detection typically treats the traffic as a collection of flows and looks for heavy changes in traffic patterns (<i>e.g.</i>, volume, number of connections). However, as link speeds and the number of flows increase, keeping per-flow state is not scalable. The recently proposed sketch-based schemes [14] are among the very few that can detect heavy changes and anomalies over massive data streams at network traffic speeds. However, sketches do not preserve the key (<i>e.g.</i>, source IP address) of the flows. Hence, even if anomalies are detected, it is difficult to infer the culprit flows, making it a big practical hurdle for online deployment. Meanwhile, the number of keys is too large to record.
BibTeX
@misc{schweller2004reversible,
  author = {Robert Schweller and Ashish Gupta and Elliot Parsons and Yan Chen},
  title = {{Reversible sketches for efficient and accurate change detection over network data streams}},
  year = {2004},
  doi = {10.1145/1028788.1028814},
}

Loading related content...

Figure