An Algorithm for Generation of Attack Signatures Based on Sequences Alignment

Nan Li, Chunhe Xia, Yi Yang, HaiQuan Wang

Beihang University.

DOI: 10.4236/jsea.2008.11011                

Abstract

This paper presents a new algorithm for generation of attack signatures based on sequence alignment. The algorithm is composed of two parts: a local alignment algorithm-GASBSLA (Generation of Attack Signatures Based on Sequence Local Alignment) and a multi-sequence alignment algorithm-TGMSA (Tri-stage Gradual Multi-Sequence Alignment). With the inspiration of sequence alignment used in Bioinformatics, GASBSLA replaces global alignment and constant weight penalty model by local alignment and affine penalty model to improve the generality of attack signatures. TGMSA presents a new pruning policy to make the algorithm more insensitive to noises in the generation of attack signatures. In this paper, GASBSLA and TGMSA are described in detail and validated by experiments.

Keywords

Attack Signatures Generation, Sequence Local Alignment, Affine Penalty, Intrusion Detection, Pruning Policy

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Idc. IDC Enterprise Security Survey, 2005.
[2]	M. V. Gundy, D. Balzarotti, and G. V. Fieldschema, “Catch me, if you can: Evading network signatures with web-based polymorphic worms,” Boston, MA: 2007.
[3]	Y. Tang, X. C. Lu, et al., “An automatic generation of attack signatures based on multi-sequence alignment [J],”Chinese Journal of Computers, 2006, 29 (9): 153321541.
[4]	J. Newsome, B. Karp, and D. Song, “Polygraph: Automatically generating signatures for polymorphic worms,” in: Proceedings of the IEEE S &P 2005, Oakland, California, pp. 226-241, 2005.
[5]	Z. Li, M. Sanghi, Y. Chen, et al., “Network-based and attack-resilient length signature generation for zero-day polymorphic worms[C],” 2007.
[6]	T. Smith and M. Waterman, “Identification of common molecular subsequences,” Journal of Molecular Biology,
[7]	S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” Journal of Molecular Biology, 48(3): pp. 443-453, 1970.
[8]	P. K. Murphy, “Biological sequence comparison: An overview of techniques,” Technical Report, University of Arizona, Department of Computer Science, 1994.
[9]	S. Uliel, A. Fliess, A. Amir, and R. Unger., “A simple algorithm for detecting circular permutations in proteins,” Bioinformatics, Vol. 15, No. 11: pp. 930-936, 1999.
[10]	J . R. Crandall, S. F. Wu, and F. T. Chong, “Experiences using Minos as a tool for capturing and analyzing novel worms for unknown vulnerabilities,” in: Proceedings of the GI SIG SIDAR Conference on Detection of Intrusions and Malware and Vulnerability Assessment, Vienna, pp. 32-50, 2005.
[11]	J. R. Crandall, Su Zhen Dong, S. F. Wu, and F. T. Chong, “On deriving unknown vulnerabilities from Zero Day polymorphic and metamorphic worm exploits,” in: Proceedings of the ACM CCS 2005, Alexandria, Virginia, pp. 235-248, 2005.
[12]	J. Xu, P. Ning, C. Kil, Y. Zhai, and C. Bookholt, “Automatic diagnosis and response to memory corruption vulnerabilities,” in: Proceedings of the ACM CCS 2005, Alexandria, Virginia, pp. 223-234, 2005.
[13]	Symantec Security Response: CodeRed Worm. http://www. sarc.com/avcenter/venc/data/codered.worm.html.
[14]	C. CAN-2003-0245. Apache apr-psprintf memory corruption vulnerability. http://www.securityfocus.com/bi-d/7723/ discussion/.
[15]	Viruslist.com: Net-Worm. Linux. Adm. http://www.viruslist.com/en/viruses/encyclopedia?virusid=23854.
[16]	SANS Institute: Lion worm. http://www.sans.o-rg/y2k/ lion.htm.
[17]	R. P. Lippmann, D. J. Fried, I. Graf, et al., “Evaluating intrusion detection systems: The 1998 DARPA offline intrusion detection evaluation,” in: Proceedings of the 2000 DARPA Information Survivability Conference and Exposition, Hilton Head, SC, 2: pp. 1012-1035, 2000.