State of the Art for String Analysis and Pattern Search Using CPU and GPU Based Programming

Mario Góngora-Blandón, Miguel Vargas-Lombardo

Centro de Investigación, Desarrollo e Innovación en Tecnologías de la Información y las Comunicaciones (CIDITIC) Grupo de Investigación en Salud Electrónica y Supercomputación (GISES), Technological University of Panama, Panama City, Panama.

DOI: 10.4236/jis.2012.34038                

Abstract

String matching algorithms are an important piece in the network intrusion detection systems. In these systems, the chain coincidence algorithms occupy more than half the CPU process time. The GPU technology has showed in the past years to have a superior performance on these types of applications than the CPU. In this article we perform a review of the state of the art of the different string matching algorithms used in network intrusion detection systems; and also some research done about CPU and GPU on this area.

Keywords

GPU; String Matching; Pattern Matching

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Tomov, J. Dongarra and M. Baboulin, “Towards Dense Linear Algebra for Hybrid GPU Accelerated Manycore Systems,” Parallel Computing, Vol. 36, 2010, pp. 232-240.
[2]	NVIDIA, “What is GPU Computing,” 2012. http://www.nvidia.com/object/what-is-gpu-computing.html
[3]	D. Gusfield, “Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology,” Cambridge University, Cambridge, 1997.
[4]	G. Vasiliadis, S. Antonatos, M. Polychronakis, E. P. Markatos and S. Ioannidis, “Gnort: High Performance Network Intrusion Detection Using Graphics Processors,” Proceedings of the 11th International Symposium on Recent Advances in Intrusion Detection, Cambridge, 2008, pp. 116-134.
[5]	D. E. Knuth, J. H. Morris Jr and V. R. Pratt, “Fast Pattern Matching in Strings,” SIAM Journal on Computing, Vol. 6, 1977, p. 323.
[6]	R. S. Boyer and J. S. Moore, “A Fast String Searching Algorithm,” Commun. ACM, Vol. 20, 1977, pp. 762-772.
[7]	A. V. Aho and M. J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search,” Commun. ACM, Vol. 18, 1975, pp. 333-340.
[8]	S. Wu and U. Manber, “A Fast Algorithm for Multi-Pattern Searching,” Technical Report TR-94-17, University of Arizona, Tucson, 1994.
[9]	B. Commentz-Walter, “A String Matching Algorithm Fast on the Average,” Automata, Languages and Programming, 1979, pp. 118-132.
[10]	R. M. Karp and M. O. Rabin, “Efficient Randomized Pattern-Matching Algorithms,” IBM Journal of Research and Development, Vol. 31, 1987, pp. 249-260.
[11]	M. Fisk and G. Varghese, “Applying Fast String Matching to Intrusion Detection,” University of California, San Diego, 2004.
[12]	C. J. Coit, S. Staniford and J. McAlerney, “Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort,” DARPA Information Survivability Conference and Exposition, Vol. 1, 2001, p. 367.
[13]	M. Roesch et al., “Snort-Lightweight Intrusion Detection for Networks,” Proceedings of the 13th USENIX Conference on System Administration, 1999, pp. 229-238.
[14]	N. Tuck, T. Sherwood, B. Calder and G. Varghese, “Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection,” INFOCOM, 2004.
[15]	N. Jacob and C. Brodley, “Offloading IDS Computation to the GPU,” Proceedings of the 22nd Annual Computer Security Applications Conference, Washington DC, 2006, pp. 371-380.
[16]	L. Marziale, G. G. Richard III and V. Roussev, “Massive Threading: Using GPUs to Increase the Performance of Digital Forensics Tools,” Digital Investigation, Vol. 4, 2007, pp. 73-81.
[17]	A. T. Nottingham and B. Irwin, “gPF: A GPU Accelerated Packet Classification Tool,” Southern African Telecommunications Networks and Applications Conference, 2009, pp. 339-344.
[18]	R. Smith, N. Goyal, J. Ormont, K. Sankaralingam and C. Estan, “Evaluating GPUs for Network Packet Signature Matching,” IEEE International Symposium on Performance Analysis of Systems and Software, 2009, pp. 175-184.
[19]	F. Yu, Z. Chen, Y. Diao, T. V. Lakshman and R. H. Katz, “Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection,” Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems, California, 2006, pp. 93-102.
[20]	R. Smith, C. Estan, S. Jha and S. Kong, “Deflating the Big Bang: Fast and Scalable Deep Packet Inspection with Extended Finite Automata,” SIGCOMM Computer Communication Review, Vol. 38, 2008, pp. 207-218.
[21]	G. Vasiliadis and S. Ioannidis, “Gravity: A Massively Parallel Antivirus Engine,” Recent Advances in Intrusion Detection, 2011, pp. 79-96.
[22]	E. Seamans and E. Alexander, “Fast Virus Signature Matching on the GPU,” GPU Gems, Vol. 3, 2007, pp. 771-783.
[23]	J. Owens, “GPU Architecture Overview,” ACM SIGGRAPH, 2007, pp. 5-9.
[24]	R. Smith, C. Estan and S. Jha, “XFA: Faster Signature Matching with Extended Automata,” Proceedings of the 2008 IEEE Symposium on Security and Privacy, Washington DC, 2008, pp. 187-201.
[25]	T. Kojm, “ClamAV,” 2004. http://www. clamav. Net
[26]	M. Pharr and R. Fernando, “2: Programming Techniques for High-Performance Graphics and General-Purpose Computation (Gpu Gems),” Addison-Wesley Professional, Boston, 2005.