Squashing Worms

When a new computer worm invades the Internet, system administrators start a race. Can they patch their computers before the worm attacks? Or if a system is infected, can they patch other systems before the infection spreads out of control?

Worms are especially difficult to contain. Unlike viruses, which infect computers only through user actions such as opening an attachment, worms spread on their own by taking advantage of vulnerabilities within an operating system. Because it takes time to apply a patch to each computer in a network, administrators usually can’t repair these vulnerabilities in all their systems simultaneously. So they have to prioritize by choosing the strategy most likely to contain the epidemic.

The problem gets even trickier for worms that mutate. Such a worm first exploits a single vulnerability in an operating system. Then, once the infection has spread throughout a network, the worm changes strategy and exploits another weakness, then another. Computers that have been patched to eliminate the first vulnerability are still susceptible to others, so the second attack is like a brand new worm. This second time, however, the worm gets launched from the millions of computers it’s already infected rather than from just a single computer or a small handful. Although mutating worms are not yet common, security experts worry that they may soon begin to create havoc.

Jennifer Tour Chayes, a mathematician and theoretical computer scientist at Microsoft Research in Redmond, Wash., has mathematically analyzed the question of which computers to patch first when a mutating worm is spreading through the Internet. The methods system administrators have typically used thus far won’t work, she and her team have found.

Tracking infections

System administrators have tended to imitate the strategies of epidemiologists who try to control the spread of human viruses. Epidemiologists usually rely on “contact tracing”: they ask the infected person for the names of everyone with whom he or she has had contact, and then attempt to either vaccinate or quarantine those individuals. Similarly, system administrators usually work first to protect the machines that are most closely connected to the initial “patients.”

Chayes’ research suggests that a worm may mutate so quickly that contact tracing can’t contain the infection. Therefore, she says, administrators should first patch the most highly connected systems, without regard to their proximity to other infected computers.

Chayes presented the results on Aug. 4 at MathFest 2007 in San Jose, Calif.

Modeling the internet

In lieu of launching experimental worms on the Internet itself, Chayes and her colleagues simulated the Internet as a mathematical network with nodes representing chunks of the Internet that can be isolated from the rest. Most of these nodes would correspond to Internet service providers, other large businesses, and universities.

To create a network with a structure similar to that of the Internet, Chayes used a model that starts with a small network and “grows” by linking in new nodes in accordance with certain rules. Since popularity on the Internet breeds further popularity, the model is designed so that if an existing node already has lots of connections to other nodes, new nodes are more likely to link to it than to more isolated ones.

This design produces a network with many of the same properties as the Internet. Service providers usually have a growing clientele, so acquire more and more connections over time. Similarly, in Chayes’ model, the oldest nodes tend to be the most connected. Also, both in the Internet and in Chayes’ model, it takes very few links, on average, to jump from one hub to any other hub. And like the Internet, Chayes’ model has a few nodes that are connected to many, many other nodes.

Worming through networks

Chayes then began to study how worms can spread through her model. To simulate the effects of a rapidly mutating worm, which beats defenses by constantly changing its strategy, she assumed that even patched computers remain susceptible to new attacks by the same worm.

First she analyzed the simplest strategy for distributing patches: giving each node the same chance of receiving treatment. This mimics what happens when users or system administrators apply patches, or fail to, in a roughly random way. In that case, she found, any worm, no matter how slowly it spreads, could possibly become an epidemic. “This is really scary,” she says.

The implications may extend beyond computer security to public health. Chayes says that as human societies become more and more interconnected through travel and communication, social networks increasingly display properties similar to those of the Internet and her model. Her result therefore suggests that someday, if we fail to adopt smart strategies for distributing vaccines, new human viruses might easily become epidemic. “Infections spread like wildfire on social and technological networks,” she says.

This means that finding effective vaccine distribution strategies is essential. So Chayes next studied the most common method of distributing patches or vaccines: administering them to nodes that are connected to infected nodes. This method does reduce the likelihood that a worm or virus will start an epidemic, she found, but eliminating the risk completely would require an absurd quantity of human vaccine or computer patching. “The problem with contact tracing is that by the time you’re trying to cure [the worm or virus],” she says, “it’s already out of control.”

In a third strategy, Chayes distributed patches to the nodes with the largest numbers of connections, regardless of whether the nodes connecting to them were themselves infected. That method brought the infestation under control with far fewer patches than the initial strategy had required.

For many kinds of networks, no other strategy could do significantly better, she showed. This finding probably applies to social networks, too.

Chayes cautions that her model is very simple. She plans to work with epidemiologists to explore the real-world implications of her research for human epidemics. She says, however, that her research “certainly suggests that sometimes if you use contact tracing and a virus is mutating too rapidly, you’re going to be in trouble.”

---

If you would like to comment on this article, please see the blog version.