adam.oliner.net

Authors: A. J. Oliner, A. V. Kulkarni, and A. Aiken

Title: Community Epidemic Detection using Time-Correlated Anomalies [pdf] [slides]

Published: International Symposium on Recent Advances in Intrusion Detection (RAID), 2010.

Consider a set of instances of an application, which we call a community. Two examples of communities are all the mail servers in an organization or all the browsers on a cluster of workstations. Assume some subset of these instances, or clients, are compromised and are running malicious code. The initial breach (or breaches) went undetected and the existence of the exploit is unknown, so the malicious code may continue running indefinitely, perhaps quietly stealing computing resources (as in a zombie network), spoofing content, denying service, etc. We present a method for detecting such situations by using properties of the aggregate behavior of the community to reliably identify when a subset of the community is not behaving properly.

We describe an implementation of an epidemic detector, called Syzygy, that applies two main insights:

1. Even if a single noisy model cannot reliably judge the health of a client, we can reduce the noise by averaging the judgements of many independent models and
2. Epidemics exhibit time-correlated behavior that is impossible to detect on a single client.

Our method effectively leverages the statistical properties of a large community to turn noisy models into reliable community detectors and uses the temporal properties of an epidemic as a means for better detecting it.

Syzygy monitors each client’s behavior and reports anomaly scores, which quantify the divergence of recent behavior from the model. For example, a client whose recent response times are unusually high may report a score that is above average (anomalous). Syzygy then computes the numerical average of all clients’ scores and checks whether this community score exceeds a threshold. By doing these computations properly, we can make strong theoretical guarantees about our ability to overcome model noise and detect epidemics. Intuitively, we expect anomalies on individual clients in a large community to be common, but we do not expect anomaly scores from multiple clients to be strongly correlated in time, absent an epidemic. Throughout the paper—using math, deployments, and simulations—we show that, in a large community, even simple, noisy models are sufficient for reliable epidemic detection.

This entry was posted on Thursday, June 10th, 2010 at 1:51 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.