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 toq).
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