Worm Origin Identification Using Random Moonwalks

We propose a novel technique that can determine both the host responsible for originating a propagating worm attack and the set of attack flows that make up the ini-tial stages of the attack tree via which the worm infected successive generations of victims. We argue that knowl-edge of both is important for combating worms: knowl-edge of the origin supports law enforcement, and knowledge of the causal flows that advance the attack supports diag-nosis of how network defenses were breached. Our tech-nique exploits the “wide tree” shape of a worm propagation emanating from the source by performing random “moon-walks” backward in time along paths of flows. Correlating the repeated walks reveals the initial causal flows, thereby aiding in identifying the source. Using analysis, simula-tion, and experiments with real world traces, we show how the technique works against both today’s fast propagating worms and stealthy worms that attempt to hide their attack flows among background traffic.