On the Race of Worms, Alerts and Patches

We study the efficacy of patching and filtering countermeasures in protecting a network against scanning worms. Recent work has addressed the question of detecting worm scans and generating self-certifying alerts, specifically in order to combat zero-day worms. Alerts need to be propagated in the network, and this is typically done using 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 logarithmically 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 overlays, which unifies the analytical treatment of a variety of overlay networks. The results provide engineering guidelines for the design of alert propagation and patching systems. 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.