Slammer). Moreover, during our experiments Earlybird age worm outbreaks. Staniford et al.s landmark paper detected and extracted a signature for the Blaster, My- anticipated the development of far faster worms and ex- Doom and Kibuv B worms- significantly before they trapolated their growth analytically [42]-foreshadow- had been publicly disclosed and hours or days before any ing the release of the Slammer worm in 2002. Moore public detection signatures were distributed. Finally, in et al. subsequently analyzed the Slammer outbreak and our testing over a period of eight months, we have ex- estimated that almost all of the Internet address space perienced relatively few false positives and exceptions was scanned by the worm in under 10 minutes-limited are typically due to structural properties of a few popu- only by bandwidth constraints at the infected sites [21] lar protocols(SPAM via SMTP and NetBlOS) that recur This experience also motivates the need for fast and au- consistently and can be procedurally"white-listed tomated reaction times. Finally, based on these results, The remainder of this paper is structured as follows. Moore et al. analyzed the engineering requirements for In Section 2 we survey the field of worm research that reactive defenses-exploring the tradeoffs between reac. re have built upon and describe how it motivates our tion time, deployment and the granularity of containment work. Section 3 describes how we define worm behav- mechanisms(signature based vs. IP address based)[23] ior. Section 4 outlines a naive approach to detecting such Two of their key findings motivate our work. behaviors, followed by a concrete description of practi- First, they demonstrated that signature-based methods cal content sifting algorithms in Section 5. Section 6 can be an order of magnitude more effective than simply describes the implementation of the Earlybird prototype quarantining infected hosts piecemeal. The rough intu and an analysis of our live experiments using it. We de- ition for this is simple: if a worm can compromise a new scribe limitations and extensions in Section 7. Finally, host with an average latency of a seconds, then an ad- in Section 8 we summarize our findings and conclude dress based quarantine can must react more quickly than I seconds to prevent the worm from spreading. By con- 2 Background and related Work trast, a signature based system can, in principle, halt all Worms are simply small programs. They spread by ex- subsequent spreading once a signature is identified. The ploiting a latent software vulnerability in some popular second important result was their derivation, via simu network service-such as email. Web or terminal access tion, of"benchmarks"for how quickly such signatures 9 Seizing control of program execution and then sending must be generated to offer effective containment. Slow copy of themselves to other susceptible hosts spreading worms, such as CodeRe ffectively While the potential threat posed by network worms contained if signatures are generated within 60 minutes, has a long past -originating with fictional accounts while containing high-speed worms, such as Slammer in gerrold's"When harlie was One" and Brunner's may require signature generation in well under 5 minutes "Shockwave Rider"-it is only recently that this threat -perhaps as little as 60 seconds. Our principal contribu- has enjoyed significant research attention. Fred Co- tion is demonstrating practical mechanisms for achieving hen first lay the theoretical foundations for understand- this requirement. ing computer viruses in 198414, 5], and the Internet In the remainder of this section we examine existing worm of 1988 demonstrated that self-replication via a techniques for detecting worm outbreaks, characteriz- network could dramatically amplify the virulence of such ing worms and proposed countermeasures for mitigating pathogens [33, 39]. However, the analysis and under- worm spread standing of network worms did not advance substantially until the Code Red outbreak of 2001. In this section. we 2.1 Worm Detection attempt to summarize the contemporary research litera- Three current classes of methods are used for detecting ure-especially in its relation to our own work. detection, honeypots, and behavioral The first research papers in the"modern worm era" techniques at end hosts. We consider each of these in focused on characterizations and analyses of particu lar worm outbreaks. For example, Moore et al. pub Worms spread by selecting susceptible target hosts, in- lished one of the first empirical analyses of the CodeRed fecting them over the network, and then repeating this worms growth, based on unsolicited scans passively ob- process in a distributed recursive fashion. Many existing served on an unused network [22]. Further, the authors worms, excepting email viruses, will select targets using estimated the operational"repair"rate by actively prob- a random process. For instance, CodeRed selected target ng a subsample of the 360,000 infected sites over time. IP addresses uniformly from the entire address space. As They found that, despite unprecedented media coverage, a result, a worm may will be highly unusual in the num- the repair rate during the initial outbreak averaged under ber, frequency and distribution of addresses that it scans 2 percent per day. This reinforces our belief that fully This can be leveraged to detect worms in several ways ated intervention is necessary to effectively To monitor random scanning worms from a global pSlammer). Moreover, during our experiments Earlybird detected and extracted a signature for the Blaster, My￾Doom and Kibuv.B worms – significantly before they had been publicly disclosed and hours or days before any public detection signatures were distributed. Finally, in our testing over a period of eight months, we have ex￾perienced relatively few false positives and exceptions are typically due to structural properties of a few popu￾lar protocols (SPAM via SMTP and NetBIOS) that recur consistently and can be procedurally “white-listed”. The remainder of this paper is structured as follows. In Section 2 we survey the field of worm research that we have built upon and describe how it motivates our work. Section 3 describes how we define worm behav￾ior. Section 4 outlines a naive approach to detecting such behaviors, followed by a concrete description of practi￾cal content sifting algorithms in Section 5. Section 6 describes the implementation of the Earlybird prototype and an analysis of our live experiments using it. We de￾scribe limitations and extensions in Section 7. Finally, in Section 8 we summarize our findings and conclude. 2 Background and Related Work Worms are simply small programs. They spread by ex￾ploiting a latent software vulnerability in some popular network service – such as email, Web or terminal access – seizing control of program execution and then sending a copy of themselves to other susceptible hosts. While the potential threat posed by network worms has a long past – originating with fictional accounts in Gerrold’s “When Harlie was One” and Brunner’s “Shockwave Rider” – it is only recently that this threat has enjoyed significant research attention. Fred Co￾hen first lay the theoretical foundations for understand￾ing computer viruses in 1984 [4, 5], and the Internet worm of 1988 demonstrated that self-replication via a network could dramatically amplify the virulence of such pathogens [33, 39]. However, the analysis and under￾standing of network worms did not advance substantially until the CodeRed outbreak of 2001. In this section, we attempt to summarize the contemporary research litera￾ture – especially in its relation to our own work. The first research papers in the “modern worm era” focused on characterizations and analyses of particu￾lar worm outbreaks. For example, Moore et al. pub￾lished one of the first empirical analyses of the CodeRed worm’s growth, based on unsolicited scans passively ob￾served on an unused network [22]. Further, the authors estimated the operational “repair” rate by actively prob￾ing a subsample of the 360,000 infected sites over time. They found that, despite unprecedented media coverage, the repair rate during the initial outbreak averaged under 2 percent per day. This reinforces our belief that fully automated intervention is necessary to effectively man￾age worm outbreaks. Staniford et al.’s landmark paper anticipated the development of far faster worms and ex￾trapolated their growth analytically [42] – foreshadow￾ing the release of the Slammer worm in 2002. Moore et al. subsequently analyzed the Slammer outbreak and estimated that almost all of the Internet address space was scanned by the worm in under 10 minutes – limited only by bandwidth constraints at the infected sites [21]. This experience also motivates the need for fast and au￾tomated reaction times. Finally, based on these results, Moore et al. analyzed the engineering requirements for reactive defenses – exploring the tradeoffs between reac￾tion time, deployment and the granularity of containment mechanisms (signature based vs. IP address based) [23]. Two of their key findings motivate our work. First, they demonstrated that signature-based methods can be an order of magnitude more effective than simply quarantining infected hosts piecemeal. The rough intu￾ition for this is simple: if a worm can compromise a new host with an average latency of x seconds, then an ad￾dress based quarantine can must react more quickly than x seconds to prevent the worm from spreading. By con￾trast, a signature based system can, in principle, halt all subsequent spreading once a signature is identified. The second important result was their derivation, via simula￾tion, of “benchmarks” for how quickly such signatures must be generated to offer effective containment. Slow￾spreading worms, such as CodeRed can be effectively contained if signatures are generated within 60 minutes, while containing high-speed worms, such as Slammer, may require signature generation in well under 5 minutes – perhaps as little as 60 seconds. Our principal contribu￾tion is demonstrating practical mechanisms for achieving this requirement. In the remainder of this section we examine existing techniques for detecting worm outbreaks, characteriz￾ing worms and proposed countermeasures for mitigating worm spread. 2.1 Worm Detection Three current classes of methods are used for detecting new worms: scan detection, honeypots, and behavioral techniques at end hosts. We consider each of these in turn. Worms spread by selecting susceptible target hosts, in￾fecting them over the network, and then repeating this process in a distributed recursive fashion. Many existing worms, excepting email viruses, will select targets using a random process. For instance, CodeRed selected target IP addresses uniformly from the entire address space. As a result, a worm may will be highly unusual in the num￾ber, frequency and distribution of addresses that it scans. This can be leveraged to detect worms in several ways. To monitor random scanning worms from a global per-