infected by permutation scanning would start at a ran- dom point 300.000 This has the effect of providing a self-coordinated, com- prehensive scan while maintaining the benefits of ran- 200.000 dom probing. Each worm looks like it is conducting a random scan, but it attempts to minimize duplication of effort. Any time an instance of the worm, W, encounters already-infected host, it knows that w, the original infector of the host, is already working along the cur rent sequence in the permutation, and is further ahead 0 Hence, there's no need for w to continue working 5678 Time(hours) the current sequence in addition to w K=26,T=5.52 Self-coordination keeps the infection rate high and guar antees an eventual comprehensive scan. Furthermore, it allows the worm to make a local decision that further Figure 6: The spread of a simulated worm capable of 10 scanning is of little benefit. After any particular copy scans/second in a population of 300,000 vulnerable machines of the worm sees several infected machines without dis- and its comparison to the model developed in Section 2. The covering new vulnerable targets, the worm assumes that simulation and theoretical results overlap completely. effectively complete infection has occurred and stops the canning process. lished itself on the network A timer could then induce the worms to wake up, change It may seem that the permutation scanning algorithm is the permutation key to the next one in a prespecified se- spoofable, but only to a very limited degree. If an unin- quence, and begin scanning through the new permuta- fected machine responds to the scan in the same way as tion, starting at its own index and halting when another a worm, by falsely claiming to be infected, it will tem- instance is discovered. This process insures that every porarily protect those machines which exist later in the address would be efficiently rescanned at regular inte vals, detecting any machines which came onto the net However, since the permutation itself changes on ev- or were reinstalled but not patched, greatly increasing a ery rescan, the set of machines protected is constantly worm's staying power. Otherwise, the worms are silent changing. The result is that unless a very large number ind difficult to detect, until they receive attack orders of uninfected machines respond to probes like an actual (see Section 6) worm, the protection is almost nonexistent A further optimization is a partitioned permutation scan In this scheme, the worm has a range of the permutation 4.3 Simulation of a Warhol Worm that it is initially responsible for. When it infects another machine, it reduces its range in half, with the newly in- fected worm taking the other section. When the range A combination of hit-list and permutation scanning can gets below a certain level, it switches to simple permu- create what we term a Warhol worm, capable of attack tation scanning and otherwise behaves like a permuta- ing most vulnerable targets in well under an hour, possi- tion scan. This scheme offers a slight but noticeable bly less than 15 minutes. Hit-list scanning greatly im- increase in scanning efficiency, by dividing up the ini- proves the initial spread, while permutation scanning tial workload using an approximate divide-and-conquer keeps the worm's infection rate high for much longer when compared with random scanning Permutation scanning interacts particularly well with a In order to evaluate the effects of hit-list and permuta- worm which attacks multiple security holes: after de- tion scanning, we wrote a small, abstract simulator of a ciding that the initial exploit is exhausted, the worm re- Warhol worms spread. The simulator assumes complete sets the permutation to its current address changes the connectivity within a 2 entry address space using a permutation key, and exploits the second security hole Thus, even relatively rare secondary holes can be effi- pseudo-random permutation to ddresses to a sub- ciently and quickly scanned once the worm has estab- If a machine is not reachable from an arbit rary point on the externalinfected by permutation scanning would start at a ran￾dom point. This has the effect of providing a self-coordinated, com￾prehensive scan while maintaining the benefits of ran￾dom probing. Each worm looks like it is conducting a random scan, but it attempts to minimize duplication of effort. Any time an instance of the worm, W, encounters an already-infected host, it knows that W0 , the original infector of the host, is already working along the cur￾rent sequence in the permutation, and is further ahead. Hence, there’s no need for W to continue working on the current sequence in addition to W0 . Self-coordination keeps the infection rate high and guar￾antees an eventual comprehensive scan. Furthermore, it allows the worm to make a local decision that further scanning is of little benefit. After any particular copy of the worm sees several infected machines without dis￾covering new vulnerable targets, the worm assumes that effectively complete infection has occurred and stops the scanning process. A timer could then induce the worms to wake up, change the permutation key to the next one in a prespecified se￾quence, and begin scanning through the new permuta￾tion, starting at its own index and halting when another instance is discovered. This process insures that every address would be efficiently rescanned at regular inter￾vals, detecting any machines which came onto the net or were reinstalled but not patched, greatly increasing a worm’s staying power. Otherwise, the worms are silent and difficult to detect, until they receive attack orders (see Section 6). A further optimization is a partitioned permutation scan. In this scheme, the worm has a range of the permutation that it is initially responsible for. When it infects another machine, it reduces its range in half, with the newly in￾fected worm taking the other section. When the range gets below a certain level, it switches to simple permu￾tation scanning and otherwise behaves like a permuta￾tion scan. This scheme offers a slight but noticeable increase in scanning efficiency, by dividing up the ini￾tial workload using an approximate divide-and-conquer technique. Permutation scanning interacts particularly well with a worm which attacks multiple security holes: after de￾ciding that the initial exploit is exhausted, the worm re￾sets the permutation to its current address, changes the permutation key, and exploits the second security hole. Thus, even relatively rare secondary holes can be effi- ciently and quickly scanned once the worm has estab- 0 100,000 200,000 300,000 0 1 2 3 4 5 6 7 8 Time (hours) Number of Instances Simulation K = 2.6, T = 5.52 Figure 6: The spread of a simulated worm capable of 10 scans/second in a population of 300,000 vulnerable machines and its comparison to the model developed in Section 2. The simulation and theoretical results overlap completely. lished itself on the network. It may seem that the permutation scanning algorithm is spoofable, but only to a very limited degree. If an unin￾fected machine responds to the scan in the same way as a worm, by falsely claiming to be infected, it will tem￾porarily protect those machines which exist later in the current permutation from being scanned by the worm. However, since the permutation itself changes on ev￾ery rescan, the set of machines protected is constantly changing. The result is that unless a very large number of uninfected machines respond to probes like an actual worm, the protection is almost nonexistent. 4.3 Simulation of a Warhol Worm A combination of hit-list and permutation scanning can create what we term a Warhol worm, capable of attack￾ing most vulnerable targets in well under an hour, possi￾bly less than 15 minutes. Hit-list scanning greatly im￾proves the initial spread, while permutation scanning keeps the worm’s infection rate high for much longer when compared with random scanning. In order to evaluate the effects of hit-list and permuta￾tion scanning, we wrote a small, abstract simulator of a Warhol worm’s spread. The simulator assumes complete connectivity within a 2 32 entry address space4 using a pseudo-random permutation to map addresses to a sub- 4 In general, the Internet address space isn’t completely connected. If a machine is not reachable from an arbitrary point on the external