AnKLe: détection automatique d'attaques par divergence d'information

Emmanuelle Anceaume, Yann Busnel, Sébastien GambsHAL 2012

TL;DR

This paper introduces AnKLe, a novel algorithm for automatically detecting attacks in massive data streams by estimating the divergence between observed and expected data patterns. AnKLe achieves high accuracy and robustness across various stream distributions, outperforming existing methods and offering a crucial tool for securing distributed systems.

What Problem Does This Paper Address?

In today's world of massive, distributed systems, nodes are constantly bombarded with data streams – think network traffic, sensor readings, or logs from distributed applications. The challenge is that these streams can be tampered with by adversaries. Detecting these malicious activities is crucial, but it's difficult because nodes have limited memory and can only process data in a single pass. Existing methods struggle to accurately estimate the "difference" between a normal data stream and a potentially compromised one, especially under strict resource constraints. This paper tackles this by proposing a method to accurately quantify this difference, making it easier to spot anomalies indicative of attacks.

Methods

The core of AnKLe lies in its ability to estimate the Kullback-Leibler (KL) divergence, a measure of how one probability distribution differs from another. The authors cleverly rewrite the KL divergence formula to make it amenable to stream processing. AnKLe combines two main techniques:

  • Sampling: Instead of processing every single data point, AnKLe strategically samples items from the stream. This is essential for managing the sheer volume of data and limited memory.
  • Information-Theoretic Methods: It leverages concepts like Shannon entropy and frequency moments to quantify the stream's characteristics.

AnKLe operates in two phases: an online phase where it processes incoming data, and a post-processing phase to compute the final KL divergence estimate. It uses specialized tasks to estimate the number of distinct items, identify frequent items, and sample random items to build its estimate. A key innovation is how it handles both frequent and infrequent items to ensure accuracy across diverse stream patterns.

Datasets

The paper evaluates AnKLe using synthetic traces generated from classical distributions that mimic various adversarial strategies: Uniform, Poisson, Zipf, and Pascal. These distributions are chosen to represent different types of data patterns and potential attack scenarios.

Key Insights and Ideas

  • KL Divergence as an Attack Indicator: The paper establishes that a high KL divergence between an observed stream and an expected, "ideal" stream is a strong indicator of adversarial activity.
  • Sampling for Efficiency: By using sampling techniques, AnKLe achieves efficiency in both time and space, making it suitable for resource-constrained environments.
  • Handling Diverse Distributions: AnKLe's design allows it to accurately estimate KL divergence even for streams with complex or unusual distributions, which is a significant advantage over methods that assume specific data patterns.
  • Robustness through Combined Estimation: The algorithm's ability to combine estimates for frequent and infrequent items is crucial for its overall accuracy and robustness.

Key Results

Experimental results demonstrate that AnKLe significantly outperforms existing algorithms (like those based on AMS and CCM) in estimating KL divergence. The paper shows that AnKLe's estimations closely align with the "exact" KL divergence values across various distributions and parameter settings. This high accuracy suggests AnKLe is a reliable tool for detecting deviations from expected behavior, even in the presence of sophisticated adversarial strategies.

Limitations and Future Work

The authors acknowledge that a theoretical analysis of AnKLe's behavior is a direction for future work. Specifically, they aim to conduct a detailed study on how different parameters (like the size of the estimator matrix and the number of frequent item counters) impact the estimation's precision and the algorithm's space complexity.

Summary updated

Abstract

4 pages
BibTeX
@inproceedings{anceaume2012ankle,
  author = {Emmanuelle Anceaume and Yann Busnel and Sébastien Gambs},
  title = {{AnKLe: détection automatique d'attaques par divergence d'information}},
  booktitle = {HAL},
  year = {2012},
}
Figure