Efficient Pattern Matching Algorithm for Intrusion Detection Systems

Abstract:

To overcome the defects of low efficiency of pattern matching in intrusion detection systems (IDS), an efficient pattern matching algorithm is proposed. The proposed algorithm first preprocesses pattern to record pattern information, then it recursive compares the nodes to find the most common part of pattern to improve efficiency. The proposed algorithm also appends auxiliary structure of m nodes in pattern to reduce time and space complexity. Theoretical analysis shows that for the subject with n nodes, the time complexity of the proposed algorithm is, and space complexity is . Detailed experimental results and comparisons with existed algorithms show that the proposed algorithm outperforms current state-of-the-art algorithms in terms of time efficiency, space efficiency and matching ratio.

• Periodical: Applied Mechanics and Materials (Volumes 511-512)
• Pages: 1178-1184
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.511-512.1178
• Online since: February 2014
• Authors: Wen Jun Yang
• Keywords: Complexity, Efficiency, Information Security, Intrusion Detection, Pattern Matching

References

[1] Su Ming-Yang, Yu Gwo-Jong, Lin Chun-Yuen. A real-time network intrusion detection system for large-scale attacks based on an incremental mining approach [J]. Computers and Security, 2009, 28(5): 301-309.

DOI: 10.1016/j.cose.2008.12.001

[2] Li Zhuowei, Das Amitabha, Zhou Jianying, et al. Variable-length signatures for intrusion detection [J]. Computer Systems Science and Engineering, 2008, 23(3): 183-192.

[3] Tarakanov Alexander. Immunocomputing for intelligent intrusion detection [J]. IEEE Computational Intelligence Magazine, 2008, 3(2): 22-30.

DOI: 10.1109/mci.2008.919069

[4] Ryu Young U, Rhee Hyeun-Suk. Evaluation of intrusion detection systems under a resource constraint [J]. ACM Transactions on Information and System Security, 2008, 11(4): 1-25.

DOI: 10.1145/1380564.1380566

[5] Sung Jung-Sik, Kang Seok-Min, Kwon Taeck-Geun. A fast pattern-matching algorithm for network intrusion detection system [J]. Lecture Notes in Computer Science, 2006, 3976: 1157-1162.

DOI: 10.1007/11753810_102

[6] Liu Rong-Tai, Huang Nen-Fu, Kao Chia-Nan, et al. A fast pattern matching algorithm for network processor-based intrusion detection system [C]. Proceedings of IEEE International Performance, Computing and Communications Conference, 2004, 271-275.

DOI: 10.1109/pccc.2004.1301087

[7] Antonatos S., K.G. Anagnostakis. Generating realistic workloads for network intrusion detection systems [J]. ACM SIGSOFT Software Engineering Notes archive, 2004, 29(1): 207-215.

DOI: 10.1145/974043.974078

[8] Dharmapurikar Sarang, Lockwood John W. Fast and scalable pattern matching for network intrusion detection systems [J]. IEEE Journal on Selected Areas in Communications, 2006, 24(10): 1781-1791.

DOI: 10.1109/jsac.2006.877131

[9] Mu Yong-min, Li Mei-gui, Liang Qi. The survey of the pattern matching algorithm in intrusion detection system [J]. ACTA Electronica Sinica, 2006, 34(12A): 2488-2490.

[10] Lu Hongwei, Wei Kai, Kong Huafeng. An improved high-effective KMP pattern matching algorithm [J]. Journal of Huazhong Universiy of Science and Technoloyg (Nature Science Edition), 2006, 34(10): 41-43.