Design and Evaluation of a Fast and Robust Worm Detection Algorithm

Fast spreading worms are a reality, as amply demonstrated by worms such as Slammer, which reached its peak propagation in a matter of minutes. With these kinds of fast spreading worms, the traditional approach of signature-based detection is no longer sufficient. Specifically, these worms can infect all vulnerable hosts well before a signature is available. To counter them, we must devise fast detection algorithm that can detect new worms appearing the first time without a signature. We present the design and evaluation of such an algorithm in this paper. The key to our algorithm design is the identification of certain invariant characteristics of worm propagation. Specifically, we are able to demonstrate using real network traces how worm propagation can perturb the arrival process distribution of unsolicited packets. Our algorithm employs a novel two-step procedure that combines a first stage change point detection with a second stage growth rate interference to confirm the existence of a worm. To evaluate our algorithm, we have applied it to multi-year network traces that cover many of the major worm outbreaks in recent years, including Slammer, Witty, Nimda and Blaster. In all cases, our algorithm is able to detect the worm within a very short time, well before significant infection has taken place.