We present two light-weight worm detection algorithms that offer significant advantages over fixed-threshold methods. The
first algorithm, RBS (
rate-based sequential hypothesis testing), aims at the large class of worms that attempts to quickly propagate, thus exhibiting abnormal levels of the rate at which
hosts initiate connections to new destinations. The foundation of RBS derives from the theory of sequential hypothesis testing,
the use of which for detecting randomly scanning hosts was first introduced by our previous work developing TRW [6]. The sequential
hypothesis testing methodology enables us to engineer detectors to meet specific targets for false-positive and false-negative
rates, rather than triggering when fixed thresholds are crossed. In this sense, the detectors that we introduce are truly
adaptive.
We then introduce RBS+TRW, an algorithm that combines fan-out rate (RBS) and probability of failure (TRW) of connections to
new destinations. RBS+TRW provides a unified framework that at one end acts as pure RBS and at the other end as pure TRW.
Selecting an operating point that includes both mechanisms extends RBS’s power in detecting worms that scan randomly selected
IP addresses. Using four traces from three qualitatively different sites, we evaluate RBS and RBS+TRW in terms of false positives,
false negatives, and detection speed, finding that RBS+TRW provides good detection of high-profile worms as well as internal
Web crawlers that we use as proxies for targeting worms. In doing so, RBS+TRW generates fewer than 1 false alarm per hour
for wide range of parameter choices.