An Efficient Sequence Alignment Algorithm of Network Traffic

Sequence alignment algorithms, inspired by methods used in bioinformatics, have recently gained popularity in network applications. Smith-Waterman (SW) algorithm is one of the widely used alignment algorithm, but it has deficiency in alignment of network flows. In this paper, we propose an algorithm named ESW (Extended Smith Waterman) and a combinatorial reduction algorithm. Through combining merge clustering, special data structure and ESW, the combinatorial reduction algorithm can extract signatures from network flows containing worms more efficiently. The algorithms keep the accurate property of SW and have a low complexity. Our software implementation shows that the algorithms are suitable for network traffic and has remarkable superiority in dealing with background noise and cross infection.