Abstract
A computer worm is a self-replicating and self-propagating program designed to spread through the network by exploiting security holes; moreover, with its malicious behaviors, it has caused much inconvenience to computer users. We believe that detection is the first step to fight against worms. In this thesis we provide some guidance for sensor placement in worm detection. Because of the popularity for peer-to-peer systems, it is conceivable that worms may be created to fail such systems. The question then is: given a network with a special topology, how can one put sensors to help detect worms? To answer this question, we introduce the concept of distance-k dominating sets for sensor placement. In this thesis we consider two types of structured peer-to-peer systems [17]: Chord [19] and CAN [16]. Since Chord and CAN use one-way hash function for node joining and their topologies behave as a random graph, our simulation results then provide the guidance on the number of the sensors needed for worm detection. That is, if we wish to approximate the effect of the distance-(k+1) dominating set for worm detection, the number of the randomly chosen sensors needed for P2P systems should be at least larger than the size of the distance-k dominating set obtained from the greedy approximation algorithm with the reduction rule.