Research ArticleOpen AccessGoogle Scholar indexed
State of the Art for String Analysis and Pattern Search Using CPU and GPU Based Programming
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
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
- 1 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
- 2 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
Journal of Information Security·Volume 03 (2012)·Pages 314–318·Published 31 October 2012·DOI10.4236/jis.2012.34038
Copy link · social · email
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.
KeywordsGPUString MatchingPattern Matching
- 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.
- NVIDIA, “What is GPU Computing,” 2012. http://www.nvidia.com/object/what-is-gpu-computing.html
- D. Gusfield, “Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology,” Cambridge University, Cambridge, 1997.
- 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.
- 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.
- R. S. Boyer and J. S. Moore, “A Fast String Searching Algorithm,” Commun. ACM, Vol. 20, 1977, pp. 762-772.
- A. V. Aho and M. J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search,” Commun. ACM, Vol. 18, 1975, pp. 333-340.
- S. Wu and U. Manber, “A Fast Algorithm for Multi-Pattern Searching,” Technical Report TR-94-17, University of Arizona, Tucson, 1994.
- B. Commentz-Walter, “A String Matching Algorithm Fast on the Average,” Automata, Languages and Programming, 1979, pp. 118-132.
- R. M. Karp and M. O. Rabin, “Efficient Randomized Pattern-Matching Algorithms,” IBM Journal of Research and Development, Vol. 31, 1987, pp. 249-260.
- M. Fisk and G. Varghese, “Applying Fast String Matching to Intrusion Detection,” University of California, San Diego, 2004.
- 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.
- M. Roesch et al., “Snort-Lightweight Intrusion Detection for Networks,” Proceedings of the 13th USENIX Conference on System Administration, 1999, pp. 229-238.
- N. Tuck, T. Sherwood, B. Calder and G. Varghese, “Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection,” INFOCOM, 2004.
- 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.