부산대학교 도서관

Inspired by the Flash worm paper [1], we formulate and investigate the problem of finding a fast and resilient propagation topology and propagation schedule for Flash worms and similar malcodes. Resiliency means a very large proportion of infectable targets are still infected no matter which fraction of targets are not infectable. There is an intrinsic tradeoff between speed and resiliency, since resiliency requires transmission redundancy which slows down themalcode. To investigate this problem formally, we need an analytical model. We first show that, under a moderately general analytical model, the problem of optimizing propagation time isNP-hard. This fact justifies the need for a simpler model, which we present next. In this simplified model, we present an optimal propagation topology and schedule, which is then shown by simulationto be even faster than the Flash worm. Moreover, our worm is faster even when the source has much less bandwidth capability. We also show that for every preemptive schedule there exists a nonpreemptive schedule which is just as effective. This fact greatly simplifies the optimization proble In terms of the aforementioned tradeoff, we give a propagation topology based on extractor graphs which can reduce the infection time linearly while keeping the expected number of infected nodes exponentially close to optimal.