Worm Origin Identification Using Random Walks

We propose a novel technique for determining the origin of a quickly propagating worm or the worm’s entry point to an intranet, for law enforcement or diagnostic purposes. Our technique rests upon an architecture in which network routers or end hosts record flow records and make them available for querying. Querying these records, our search then walks backward randomly along paths of flows. Due to the “wide tree” shape of a worm propagation emanating from the source, those edges near the top of the tree emerge as edges more frequently traversed in random walks, thereby aiding in identifying the source. We detail the effectiveness of this approach using both analysis and simulation, and argue the feasibility of the architecture needed to implement it.

Source: Worm Origin Identification Using Random Walks, Yinglian Xie Vyas Sekar, David A. Maltz, Michael K. Reiter, and Hui Zhang.

An interesting paper, and one of the more interesting methods I've seen in a long time for worm host detetcion.