Network Immunology

Overview

Can automatic patching be effective and practical in containing worms? Effective is meant to contain a worm to a small factor of the size of the population of infected hosts at worm detection time. Practical is meant that the frequency of client patch updates is reasonably small (client patch updates at regular intervals of minutes may be acceptable, while that of a fraction of second may not). We consider how effective and practical is reactive patching to contain a typical, random scanning worm. We show that already for the simple scanning strategy of random scanning worms, automatic patching system is effective, only under a lower bound on the patching rate (of the same order as the worm infection rate)---other worm scanning strategies such as that of topological worms would impose even more severe constraints.

 

We consider automatic patching system where a population of hosts is partitioned into subnets. In each subnet, a patching server patches hosts in its subnets, only if in alerted state. At worm detection time, a patching server becomes alerted. Alert is distributed to other patching servers after some positive alert broadcast time. We assume patch can be automatically generated—a problem of its own and not the scope of our work. It takes some positive time for a host to become patched from the time its patch server became alerted. How fast alerts and patches need to be to contain the worm?

 

The problem is of interest in view of existing automatic patch distribution systems (e.g. Microsoft Automatic Updates and SMS) and recent proposals to automate patch generation and distribution (see a limited sample of the references below). Our work addresses the question of the limits and effectiveness of automatic patching.

 

Publications

• Sampling Strategies for Epidemic-Style Information Dissemination, M. Vojnovic, V. Gupta, T. Karagiannis, and C. Gkantsidis, accepted for IEEE INFOCOM 2008, Phoenix, AZ, Apri, 2008. MSR Technical Report version with proofs: MSR-2007-82, July 2007.
• Planet Scale Software Updates, C. Gkantsidis, T. Karagiannis, P. Rodriguez, and M. Vojnovic, ACM SIGCOMM 2006, Pisa, Italy, Apri, 2008. MSR Technical Report version with proofs: MSR-2006-85, Jan 2006.
• On the Race of Worms, Alerts and Patches, M. Vojnovic and A. J. Ganesh, to appear IEEE Trans. on Networking, 2008. Conference version presented at ACM WORM 2005, The 3^rd Workshop on Rapid Malcode, George Mason University, Fairfax, VA, USA, Nov 11, 2005. MSR Technical Report version with proofs: MSR-2005-13
• Model of the Spread of Randomly Scanning Internet Worms that Saturate Access Links, G. Kesidis, M. Vojnovic, I. Hamadeh, Y. Jin, and S. Jiwasurat, accepted ACM TOMACS, 2008.
• Reactive Patching: a viable worm defense strategy?, M. Vojnovic and A. J. Ganesh, Tutorial, Performance 2005, Juan-les-Pins, France, Oct 2005, slides.

Related work

The following articles make several claims on effectiveness of on-demand patching:

• William A. Arbaugh, A Patch in Nine Saves Time?, IEEE Computer Magazine, Jun 2004.
• Angelos D. Keromytis, "Patch on Demand" Saves Even More Time?, IEEE Computer Magazine, Aug 2004.

Tutorials

• Addressing the Threat of Internet Worms, Paxson, 2005.
• Internet Outbreaks: Epidemiology and Defenses, Savage, 2005.
• Models of Internet Worm Defense, Nicol & Liljenstam, 2004.
• Mitigating the Risk of Cyber Attack, Alderson, 2004.

Taxonomy

• A Taxonomy of Computer Worms, Weaver, Paxson, Staniford, Cunningham, ACM CCS WORM, Oct 2003.
• How to Own Internet in your Spare Time, Staniford, Paxson, Weaver, 11th USENIX Security Symposium, 2002.

Worm forensics

• The Spread of the Witty Worm, Shannon, Moore, 2004.
• Reflections on Witty: Analyzing the Attacker, Weaver, Ellis, 2004.
• Inside the Slammer Worm, Moore, Paxson, Savage, Shannon, Staniford, Weaver, IEEE Security & Privacy, 2004.
• The Spread of the Sapphire/Slammer Worm, Moore, Paxson, Savage, Shannon, Staniford, Weaver, Technical Report 2003.

Topological worms

• The Effect of Network Topology on the Spread of Epidemics, Ganesh, Massoulie, Towsley, IEEE Infocom 2005, Miami, FL, 2005..

Containment

• Countering Network Worms Through Automatic Patch Generation, Sidiroglou, Keromytis, IEEE Security & Privacy, 2005.
• Very Fast Containment of Scanning Worms, Weaver, Staniford, Paxson, 13th USENIX Security Symposium, Aug 2004.
• Can we Contain Internet Worms?, Costa, Crowcroft, Castro, Rowstron, HotNets III, San Diego, CA, Nov 2004.
• Implementing and Testing a Virus Trottle, Twycross, Williamson, 12th USENIX Security Symposium, 2003.
• Throttling Viruses: Restricting Propagation to Defeat Malicious Mobile Code, Williamson, ACSAC 2002.
• Internet Quarantine: Requirements for Containing Self-Propagating Code, Moore, Shannon, Voelker, Savage, IEEE Infocom 2003.
• Dynamic Quarantine of Internet Worms, Wong, Wang, Song, Bielski, Ganger, DSN-2004.
• Cooperative Response Strategies for Large Scale Attack Mitigation, Nojiri, Rowe, Levitt, DARPA DISCEX III Conference, 2003.

Worst-case worms

• The Top Speed of Flash Worms, Staniford, Moore, Paxson, Weaver, ACM CCS WORM, Oct 2004.
• A Worst-Case Worm, Weaver, Paxson, The Third Annual Workshop on Economics and Information Security (WEIS04), May 2004.

Detection

• The Monitoring and Early Detection of Internet Worms, Zou, Gong, Towsley, Gao, to appear in IEEE/ACM Trans. on Networking, 2005.
• Toward Understanding Distributed Blackhole Placement, Cooke, Bailey, Mao, McPherson, WORM 2004, Oct 2004.

Models

• Coupled Kermack-McKendrick Models for Randomly Scanning and Bandwidth-saturating Internet Worms, Kesidis, Hamadeh, Jiwasurat, QoS-IP, Sicily, Feb 2005.
• Preliminary Results Using ScaleDown to Explore Worm Dynamics, Weaver, Hamadeh, Kesidis, Paxson, ACM CCS WORM, Oct 2004.
• Modeling the Spread of Active Worms, Chen, Gao, Kwait, IEEE Infocom 2003, San Francisco, CA, 2003.
• Code Red Worm Propagation Modeling and Analysis, Zou, Gong, Towsley, ACM CCS, 2002.