On the Race of Worms, Alerts and Patches

This paper, while math heavy (something like 65 or more equations), models the interplay between worm propagation and patching. Some heavy stuff, but study it closely. It's good work, and one of the more important studies I've seen on this question.

We study the efficacy of patching and filtering countermeasures in protecting a network against scanning worms. Recent work has addressed the question of detect- ing worm scans and generating self-certifying alerts, specif- ically in order to combat zero-day worms. Alerts need to be propagated in the network, and this is typically done us- ing an overlay of dedicated servers. Alerted servers are used for filtering worm traffic and for generating and distributing patches to end hosts within their subnet. Can alerts and patches be propagated fast enough to limit the spread of the worm? The answer will depend on the speeds of the different processes, namely, worm spread, alert spread, and downloading of patches from servers. We characterize the interplay between them and establish fundamental limits on the effectiveness of these countermeasures. Specifically, we show that (i) the number of nodes eventually infected grows approximately exponentially in the ratio of infection rate to patch rate, and (ii) the patch rate required to ensure a bound on the final number of infectives grows only loga- rithmically with the number of servers in the overlay. (iii) We introduce the concept of minimum broadcast curve as an abstraction of the alert dissemination process on over- lays, which unifies the analytical treatment of a variety of overlay networks. The results provide engineering guide- lines for the design of alert propagation and patching sys- tems. In particular, they specify the required frequency of automatic updates, and suggest that automatic patching is feasible provided that scan rates are limited to reasonable values. The results are obtained analytically, supplemented by simulations. The simulations demonstrate the accuracy of the analytical framework established in this paper.

Source: On the Race of Worms, Alerts, and Patches, Milan Vojnovic and Ayalvadi Ganesh, MSR Technical Report MSR-TR-2005-13, Feb 2005.