The following is an analysis of a worst case virulence for a computer
worm, using existing mechanisms and a modified infection strategy. Such
a "Warhol Worm" could infect every vulnerable machine in a 15 minute time
period, outpacing human defense. It is important to understand the possible
threat, in order to develop better defenses.
"In the future, everybody will have 15 minutes of fame"
The recent outbreak of the Code Red active worm has demonstrated how
vulnerable our infrastructure is. But the worm could have been a thousand
times worse. It could have contained a malicious payload: corrupting data,
reflashing BIOSes, and potentially destroying machines. It could have
included attacks for different servers, or a secondary email component,
to increase its reach.
But although it was fast, the 12 hours it took to reach epidemic levels
still allows for an organized response. But by simply changing the infection
pattern, it is possible for a malicious programmer to build a "Warhol
Worm", able to attack all vulnerable machines, worldwide, in 15 minutes.
A reactive, human defense would fail before such an onslaught. It is an
important exercise to realize just how vulnerable we are.
An active worm such as Code Red or the original Morris worm takes advantage
of a security hole in a server. It scans through the Internet, looking
for machines running that service. Then it tries to break into that service.
If successful, it infects the target machine with another copy of itself.
Over a period of several hours, it goes from an initial machine to Internet
wide contamination. The difference between an active worm and a Warhol
worm is minor, just a different strategy of choosing hosts to infect.
There are 4 billion Internet addresses, and let us assume that 1 million
machines are vulnerable a particular Warhol Worm. Assume that the worm
is under 100k in size and is multithreaded, allowing it to probe and attack
many machines simultaneously. Further assume that the targeted servers
have good network connections, allowing a running copy of the worm to
scan 100 machines per second, probe and infect 10 machines per second,
and it takes 1 second to actually transfer over the worm to a new target.
Finally, assume that a Warhol Worm author has planned ahead and quietly
constructed a list of 50,000 computers with good network connections and
a running copy of the targeted server, of which an unknown 25% are actually
infectible by the worm.
The worm starts out on a single machine, with its list of 50,000 targets.
The worm goes through the list in order, and probes and infects the machines.
When it successfully takes over another machine, it divides the list in
half, sends half over to the newly infected machine and keeps the other
half. This quick division of labor allows the worm to infect every vulnerable
machine on the list in under a minute.
Now roughly 12,000 machines will be infected, and the second stage begins.
The worm first attempts to infect all the hosts on its subnet, before
beginning to choose new targets in the general Internet. But instead of
just picking random machines, or scanning through the net in a linear
order, the worms use a pseudo-random order.
A Warhol worm contains a generator for a pseudo-random permutation of
all 4 billion Internet addresses. Each worm infected during the hitlist
phase starts at its address and goes through the permutation, looking
for new targets to infect, while each worm infected during the second
phase starts at a random location. If it finds another copy of itself
running, it picks a new, random address and starts from there. This will
have the worm behave with both the features of a random probe (scattering
through the net) and a sequential probe (minimizing duplication of effort
and guaranteeing that the entire Internet will be efficiently scanned).
Even if the worms did not infect any other machines during this phase,
they would take about 50-100 hours to scan the entire internet at 100
scans/machine/second. If the computers on the hit list are chosen for
speed and connectivity, this would be significantly lower.
But with 1 million vulnerable machines, any given scan and probe has
a .025% chance of being a vulnerable machine. Thus, with the 1.2 million
scans per second the initial worms send out, 300 will reveal new targets.
By the second minute after release, the worm will have infected a total
of 30,000 machines. After the third minute, there will be over 70,000
infected machines. It becomes quite obvious that complete infection will
be achieved within the 15 minute timeframe.
Normally, once a worm which uses random probes infects about 1/2 of the
available hosts, the rate of new infections slows down considerably. A
fully coordinated worm, where the tasks of scanning the internet are perfectly
divided, will only slow down once every target is infected. The pseudo
random/random combination is a compromise, allowing the worm to do a comprehensive
scan of the internet without relying on transmitting information between
worms, just the ability to check to see if a potential target is already
The Internet will slow down during this process, but not as much as may
be expected. With only a few bytes to scan a target to see if a server
is running, roughly 5k to infect a target, and 100k to transfer on successful
infection, the amount of data involved is surprisingly small: Even at
the peak of infection with a million infested machines, this represents
only a hundred million scans per second worldwide, a network load not
significantly higher than Code Red employed.
There is no current defense against a malicious Warhol worm. The author
of a Warhol worm could easily cause hundreds of billions in real damage,
through corrupted data, destroyed machines, and lost time. By the time
the world realizes what is happening, all the damage would be done.
Appendix 1: Justification of assumptions
100k worm size: 100 kilobytes of data is a reasonable size for
a worm: It is sufficient for the infection code and a small but effective
malicious payload. With some patience and cleverness, the size could probably
be reduced to 50k or less.
100 scans/second: Scanning a single machine to see if it is running
the vulnerable service requires only about a kilobit of data to be sent
and received, this only requires about a 100kbps link for each active
worm. Since server machines targeted by active worms tend to have good
network, this is easily achievable. Many machines should be capable of
1000 scans per second.
10 attacks/second: 10 attacks per second requires transfering
the whole worm over. For servers, 1 megabyte/second of data is a little
high for some but many machines do have that level of bandwidth. A lower
limit of one attack per second would still be sufficient, as it would
only slow the initial phase of expansion, perhaps to slightly more than
a minute. During the second phase, infection rates are limited by the
rate of probing, not the rate of attacking.
1 second to infect a machine: Taking over and infecting a machine
requires that the probe be successful, the worm transfered over, and the
worm to start running. Since the worm is only 100k, this can easily be
accomplished in a second for machines connected through broadband links.
Note that a latency of several seconds will not significantly slow down
the propagation during the permutation scanning phase, but only slows
down the hitlist phase.
1M vulnerable hosts: Code Red I and II seem to have infected somewhere
between 500,000 and 1,000,000 machines on the net. A fewer number of potential
hosts would slow down the rate of infection slightly, but even with only
500,000 vulnerable machines, the spread would still take roughly 15 minutes:
it would double every 2 minutes instead of every minute, until all vulnerable
machines are infected.
Initial hit list scan: The initial hit-list scan is a slow scan
which is done in advance, just to determine a set of potentially vulnerable
machines. In the case of a web server, a simple web-crawler could be used.
For a different service, another form of scanner. Such scans, since they
only are used to detect the program running, not the existence of the
vulnerability, can be done weeks in advance and would not attract notice.
Much of the information may already be publicly available.
In practice, it would be very hard to detect and trace the scan used
to create such a hitlist. The Honeynet project has revealed just how many
scans occur all the time. A slow, advanced scan just to determine the
version of a web-server and its response time would be nearly undetectable
amid all the noise generated by script kiddies.
Also, the hitlist can be created long before an actual vulnerability
is discovered. The attacker simply collects a catalog of machines running
potential targeted services, and constructs the worm with the exception
of the actual exploitation code. Once an exploit is available is the final
worm compiled and released, using the premade hitlist.
Pseudo random scanning: The pseudo-random-permutation is easy
to construct: Just use a 32 bit block cipher and a key selected in advance.
To generate the Nth entry in the permutation, just encrypt N. To get the
index of a given machine K, just decrypt K.
This does result in some redundancy in scanning, as multiple worms may
probe a range in the permutation until an already infected machine is
found. However, this is a comparatively minor loss, and the rapid expansion
of the worm will cause a loss in efficiency, this is a comparatively minor
loss. Complete efficiency of scanning could be accomplished by having
the worms communicate with each other. Such communication would make such
a worm even more virulent, possibly allowing complete infection in 5 minutes.
Normally, a worm like Code Red has its infection rate start to slow as
it reaches saturation, as random probing becomes less effective. Because
this combines the effects of random and comprehensive probes, the rate
stay higher, longer.
Coordinated worms, and worms which exploit the structure of the net in
dividing the workload, would be even faster. The point of this exercise,
however, is to show that even very simple modifications to random infection
strategies can produce super virulence. Once you get a worm which propagates
in under an hour, what difference is there between 5 minutes and 15?
Appendix 2: Possible defenses
Unfortunately, Warhol worms are very fast, so human mediated defenses
fail. A transition to IPv6 would work wonders, since it eliminates the
random probing as a viable means of finding new hosts. Short of that,
more variation in applications, so individual flaws would affect fewer
hosts would help, since fewer vulnerable machines will slow the spread
of such worms.
Getting programmers to write their servers in bounds checked languages
would help, as this would eliminate roughly half of the security flaws.
But it isn't a panacea, there is nothing in a Warhol worm which requires
that the exploit used be a buffer overflow.
One factor which may slow the spread is the ability for routers to process
ARP requests. This will result in the effects of network congestion for
the worm, which will slow the spread. I have no current estimates on how
much this will affect things.
Thanks to Michael Constant for his assistance in helping design the
strategies used by such a worm.
I am currently writing an abstract simulator to model the virulence of
an abstract Warhol Worm for various parameters. I AM NOT, AND WILL NOT,
EVER WRITE SUCH A WORM! "I have no need to destroy things, just to prove
My math is deliberately sloppy when it comes to evaluating the point
where the geometric growth slows down. But the simulator confirms these
times. I will be releasing initial code for the simulator in a couple
of days, as well as data runs, but initial results say that it takes roughly
7 minutes and 30 seconds for 1M vulnerable hosts, 12 minutes and 45 seconds
if there are only 500k potential hosts in the network, as expected.
Why I'm keeping this page up!
Unfortunately, the results are too simple: Any reasonably intelligent
programmer who thinks about the problem will come up with a similar solution,
or a coordinated worm which efficiently divides the search space. Coordinated
worms are even faster but do require a level of worm to worm communication.
The point of this was to just demonstrate that coordinated worms are NOT
a prerequisite for truly fast propagation.
Secondly, the current worms, taking 12 hours to a day, are still fast
enough to foil most human reaction: Look at the continued spread of the
code red variants, roughly 3 weeks after initial infection. Changing this
to under an hour would only slightly increase the reach in the current
Finally, I am a personal believer in the doctrine of full disclosure,
especially when the "bad guys" (skilled, malicious programmers) could
easily come up with the same results without documentation. It is important
for the rest of us to consider and evaluate what the realistic threat
is. Saying nothing would help nobody.
We have always known, even before the Morris worm, that connected, homogeneous
computer networks are vulnerable to fast moving, active worms. This, however,
is an important result because it is a reminder of just HOW vulnerable
it is. Human mediated defenses can not stop a fast active worm.
I will not remove this page.
Copyright 2001 by Nicholas C Weaver, email@example.com. It may
be reproduced only in its entirety and with credit to its author.
The term "Warhol Worm" is an original term coined by the author.
If you mirror this article, please let me know where it is and from where
you got it. I am interested in how this article gets spread around.