In this paper, an effective algorithm for early detection of worms is proposed. The early detection algorithm based on multi-similarity integrates the worms? behavior attributes with their traffic distribution and detects abnormal behavior by their similarity distribution change of some attributes. Three groups of experiments are conducted to evaluate the effectiveness of the algorithm. The results show that the multi-similarity owning the specialty of higher true positive, lower false positive and false negative. It can be conclude that the algorithm can detect the worm attack ahead of its overspreading on the large-scale network.