Online Anomaly Detection under Adversarial Impact

Marius Kloft, Pavel LaskovAISTATS 2010 · OpenReview

Abstract

Security analysis of learning algorithms is gaining increasing importance, especially since they have become targets of deliberate obstruction in certain applications. Some security-hardened algorithms have been developed for specific tasks, but a general framework for assessing the security of learning algorithms is still missing. This work investigates the vulnerability of online anomaly detection systems to poisoning attacks, specifically focusing on the impact of finite training windows versus theoretical infinite-window models.

Introduction

Anomaly detection is a cornerstone of computer security, used to identify network intrusions, credit card fraud, and other malicious activities. To remain effective against evolving threats, these systems must be "online," updating their model of "normal" behavior as new data arrives. However, this adaptability introduces a significant vulnerability: poisoning attacks. An adversary can inject carefully crafted data points that appear nearly normal to gradually "drag" the system's model toward a malicious target, eventually causing the system to accept an actual attack as legitimate.

Prior research suggested that subverting these systems required an exponential amount of data, implying practical security. However, this conclusion relied on the assumption of an infinite training window. In practice, systems utilize finite sliding windows to accommodate changing data patterns. This paper explores whether the security of these systems holds when memory is finite.

Methodology

The study focuses on Centroid Anomaly Detection, which flags data points based on their Euclidean distance from the training set's mean. The authors analyze three common strategies for updating a finite sliding window of size $n$ when a new point arrives:

  1. Average-out: The oldest point is replaced.
  2. Random-out: A random existing point is discarded.
  3. Nearest-out: The point closest to the new incoming point is discarded to preserve data diversity.

The authors derive the optimal attack policy for each strategy. For the "Nearest-out" learner, the attack is formulated as a Quadratically Constrained Linear Program (QCLP) to maximize centroid shift while remaining within the "normal" boundary. These findings were validated using high-dimensional Gaussian artificial data and real-world HTTP traffic (2,950 benign requests and 69 malicious instances from Metasploit), with raw byte strings converted into numerical vectors using a 3-gram spectrum kernel.

Theoretical and Empirical Insights

The transition from an infinite to a finite window significantly degrades security. While infinite windows require exponential effort to subvert, finite windows (Average-out/Random-out) can be compromised with linear effort. Specifically, for Average-out learners, the displacement of the centroid ($D_i$) is exactly $i/n$, where $i$ is the number of attack points.

Comparison of centroid displacement ($D_i$) for different update strategies and data dimensions ($d$).

As shown in Figure 3, the "Nearest-out" strategy—intended to be more robust—actually becomes easier to attack as the dimensionality ($d$) of the data increases. In high-dimensional spaces, the Voronoi-like cells around data points grow, providing the attacker more room to maneuver. This "curse of dimensionality" for the defender means that more complex feature sets can inadvertently aid an adversary.

The Critical Ratio and Security Guarantees

A pivotal discovery of this research is the "critical ratio" ($\nu_{crit}$). If an attacker controls less than a specific percentage of the total traffic, the progress of the poisoning attack is strictly bounded. Regardless of the attack duration, the centroid can never be pushed to the malicious target.

Empirical validation of the critical ratio ($\nu_{crit}$) on real HTTP traffic.

Experiments using real-world HTTP traffic confirmed the accuracy of this theoretical bound. For a WebDAV exploit, the theory predicted a $\nu_{crit}$ of 0.152. As illustrated in Figure 5, the attack successfully reached the target when the attacker controlled 16% of the traffic ($\nu=0.16$) but failed when the fraction was reduced to 14% ($\nu=0.14$), staying below the critical threshold $D_{crit}$.

Conclusion

This work demonstrates that real-world online anomaly detection implementations using finite sliding windows are significantly more vulnerable to poisoning attacks than previously theorized. However, it also provides a constructive path for defense: by maintaining the attacker's influence on total network traffic below a calculated critical ratio, defenders can provide hard security guarantees. Future work may involve developing auto-tuning filters that leverage these insights to prevent rapid model drift.

Summary updated

Abstract

Security analysis of learning algorithms is gaining increasing importance, especially since they have become target of deliberate obstruction in certain applications. Some security-hardened algorit...
BibTeX
@inproceedings{kloft2010online,
  author = {Marius Kloft and Pavel Laskov},
  title = {{Online Anomaly Detection under Adversarial Impact}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=-9Y2lMdGj5},
}
Figure