Tracing online propagation paths when worm breaks out on a large scale can improve the network’s anti-attackability. The existing tracing approaches to obtain worm propagation path are all based on off-line analysis and usually have a lower accuracy. This paper proposes an online Accumulation Algorithm with sliding detection windows, which can fleetly and efficiently trace the origin and initial causal edges of the worm. The algorithm solves the conflicts in choosing causal edges and tackles the problem of merging propagation paths in the consecutive reconstruction phase. The algorithm’s accuracy and performance have been analyzed. Experimental results reveal that the online Accumulation Algorithm can dig out causal edge even at the initial stage, and the Accumulation Algorithm can achieve detection accuracy higher than 90% while its running time is only 1% of related works.