Optimal Worm Propagation Topologies and Schedules

Introduction

Since the first Internet worm incident in 1988, network worms have evolved considerably. Current worms are very speedy and destructive, posing a major problem to security researchers. As a matter of fact, the recent years since 2001 have arguably been the golden age of worms, with notorious representatives such as CodeRed, Nimda, Slapper and Slammer. As a consequence, the security research community has spent a considerable amount of effort to study different aspects of worms: mechanics, dynamics, monitoring, detection, etc. However, there is little research on worms with certain extreme properties. One example is the flash worm, so called by its extreme speed, which was first studied by Staniford et al [2]. This type of worm, if unleashed in a right moment and within the right environment, can be capable of infecting the whole population of a million nodes by a fraction of a second.

Though such worm has yet to fully materialize, several actual worms have evolved towards this caliber. In particular, Slammer is able to infect at an unprecedented rate: 90% of the susceptible population within 10 minutes; Witty infects 110 hosts within 10 seconds. Such worms remind us that the flash worms are looming in the wild, perhaps just waiting for the right conditions. One may then ask: what are those conditions that stand between us and such monsters? Can one day they will be met and all hell breaks loose ?

These questions have motivated our project.  In our preliminary work [1], we have shown that theoretically, this scenario is possible even when the attacker has limited resource. Unlike the flash worm in Staniford’s work, which requires an enormous bandwidth at the source, our worm can achieve extreme speed with normal bandwidth. Using an optimal propagation structure, its efficiency is similar, if not better than the flash worm. We also analyzed the trade-off between the expected infection time of the worm and the expected number of nodes it can infect when infection is not perfect. This happens due to lost in worm code transmission, or when nodes become “healthy” (patched).

It is also important to note that, the worm problem is indeed a special broadcast problem in other contexts, for example, in overlay or P2P networks. In this setting, a special node needs to broadcast a message a few times, and thus there is no need to maintain a routing table for each intermediate node. The intermediate nodes also don’t have to keep track of their local neighbors’ connectivity. To this end, the worm problem can certainly find similar applications in the P2P domains.

In the future, we hope to explore  the following topics:

• The performance of our optimal topology versus the 3-level topology on actual networks. To measure this, we intend to employ a test-bed that functions at  a global scale.

• The optimal propagation topologies and schedules for attackers under different contexts. In particular, for botnet, the attacker doesn't communicate directly with each bot, but instead relies on a set of communication centers. Investigating the best strategy for the attacker will definitely help system analysts to  seek an effective mechanism to disrupt the botnet.

• The effectiveness of existing worm detection and prevention systems under the optimal attack schedules. Could we come up with a new preventive system specifically tailored to defeat these optimal strategies?

Bibliography (more can be found in [1])

[1] On the trade-off  between the expected number of infected nodes and expected propagation time of malcodes. DUC T. HA, HUNG Q. NGO, Technical Report: TR- 2007-005, Department of Computer Science and Engineering, SUNY at Buffalo. [pdf]

[2] The top speed of flash worms S. STANIFORD, D. MOORE, V. PAXSON, AND N. WEAVER, in WORM ’04: Proceedings of the 2004 ACM workshop on Rapid malcode, New York, NY, USA, 2004, ACM Press, pp. 33–42.[pdf]

People

Publications and Simulation Software

On the trade-off  between the expected number of infected nodes and expected propagation time of malcodes. Duc T. Ha, Hung Q. Ngo, Technical Report: TR- 2007-005, Department of Computer Science and Engineering, SUNY at Buffalo.

Simulation Software for this work is available upon request.