GPU Computation for Online Realtime Multi-Pattern Matching

Abstract:

Most applications of traditional full-text search, e.g., webpage search, are offline which exploit text search engine to preview the texts and set up related index. However, applications of online realtime full-text search, e.g., network Intrusion detection and prevention systems (IDPS) are too hard to implementation by using commodity hardware. They are expensive and inflexible for more and more occurrences of new virus patterns and the text cannot be previewed and the search must be complete realtime online. Additionally, IDPS needs multi-pattern matching, and then malicious packets can be removed immediately from normal ones without degrading the network performance. Considering the problem of realtime multi-pattern matching, we implement two sequential algorithms, Wu-Manber and Aho-Corasick, respectively over GPU parallel computation platform. Both pattern matching algorithms are quite suitable for the cases with a large amount of patterns. In addition, they are also easier extendable over GPU parallel computation platform to satisfy realtime requirement. Our experimental results show that the throughput of GPU implementation is about five to seven times faster than CPU. Therefore, pattern matching over GPU offers an attractive solution of IDPS to speed up malicious packets detection among the normal traffic by considering the lower cost, easy expansion and better performance.

• Periodical: Applied Mechanics and Materials (Volumes 284-287)
• Pages: 3428-3432
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.284-287.3428
• Online since: January 2013
• Authors: Yu Hsiu Huang, Richard Chun Hung Lin, Ying Chih Lin, Cheng Yi Lin
• Keywords: Aho-Corasick, Graphic Processing Unit (GPU), IDPS, Network Security, Pattern Matching, Real-Time, Wu-Manber

References

[1] M. Guimaraes, M. Murray. Overview of Intrusion Detection and Intrusion Prevention. In: Proceedings of the 5th annual conference on Information security curriculum development, (2008).

DOI: 10.1145/1456625.1456638

[2] C. Wu, J. Yin, Z. Cai, et al. An Efficient Pre-filtering Mechanism for Parallel Intrusion Detection Based on Many-Core GPU, Communications in Computer and Information Science 58:298-305, (2009).

DOI: 10.1007/978-3-642-10847-1_37

[3] S. Wu, U. Mamber. A Fast Algorithm for Multi-Pattern Searching, Technical Report TR-94-17, (1994).

[4] V. Aho, M. J. Corasick. Efficient String Matching: An Aid to Bibliographic Search, Communications of the ACM, 18:333-340, (1975).

DOI: 10.1145/360825.360855

[5] NVIDIA CUDA programming guide, Version 2.3.1.

[6] SNORT: Open-Source Network IDPS. http://www.snort.org

[7] R. S. Boyer, J. S. Moore. A Fast String Searching Algorithm. Communications of the ACM, 20(10):762-772, (1977).

DOI: 10.1145/359842.359859

[8] The OpenMP API Specification for Parallel Programming. http://openmp.org/wp/