Optimal worm-scanning method using vulnerable-host distributions

Most internet worms use random scanning. The distribution of vulnerable hosts on the internet, however, is highly non-uniform over the IP-address space. This implies that random scanning wastes many scans on invulnerable addresses and more virulent scanning schemes may take advantage of the non-uniformity of a vulnerable-host distribution. Questions then arise as to how attackers may exploit such information and how virulent the resulting worm may be. These issues provide 'worst-case scenarios'for defenders and 'best-case scenarios'for attackers when the vulnerable-host distribution is available. This work develops such a scenario, called importance scanning, which results from importance sampling in statistics. Importance scanning scans the IP-address space according to an empirical distribution of vulnerable hosts. An analytical model is developed to relate the infection rate of worms with the Importance-Scanning (IS) strategies. Based on parameters chosen from Witty and Code Red worms, the experimental results show that an IS worm can spread much faster than either a random-scanning worm or a routing worm. In addition, a game-theoretical approach suggests that the best strategy for defenders is to scatter applications uniformly in the entire IP-address space.