ABSTRACT
Regular expression pattern matching is the foundation and core engine of many network functions, such as network intrusion detection, worm detection, traffic analysis, web applications and so on. DFA-based solutions suffer exponentially exploding state space and cannot be remedied without sacrificing matching speed. Given this scalability problem of DFA-based methods, there has been increasing interest in NFA-based methods for memory efficient regular expression matching. To achieve high matching speed using NFA, it requires potentially massive parallel processing, and hence represents an ideal programming task on Graphic Processor Unit (GPU). Based on in-depth understanding of NFA properties as well as GPU architecture, we propose effective methods for fitting NFAs into GPU architecture through proper data structure and parallel programming design, so that GPU's parallel processing power can be better utilized to achieve high speed regular expression matching. Experiment results demonstrate that, compared with the existing GPU-based NFA implementation method [9], our proposed methods can boost matching speed by 29~46 times, consistently yielding above 10Gbps matching speed on NVIDIA GTX-460 GPU. Meanwhile, our design only needs a small amount of memory space, growing exponentially more slowly than DFA size. These results make our design an effective solution for memory efficient high speed regular expression matching, and clearly demonstrate the power and potential of GPU as a platform for memory efficient high speed regular expression matching.
- PCRE - Perl Compatible Regular Expressions. http://www.pcre.org/.Google Scholar
- Snort intrusion detection system. http://www.snort.org/.Google Scholar
- S. S. Baghsorkhi, M. Delahaye, S. J. Patel, W. D. Gropp, and W. mei W. Hwu. An adaptive performance modeling tool for GPU architectures. In Proceedings of ACM PPoPP, 2010. Google ScholarDigital Library
- M. Becchi and P. Crowley. A hybrid finite automaton for practical deep packet inspection. In Proceedings of CoNext, 2007. Google ScholarDigital Library
- M. Becchi and P. Crowley. An improved algorithm to accelerate regular expression evaluation. In Proceedings of ANCS, 2007. Google ScholarDigital Library
- M. Becchi and P. Crowley. Efficient regular expression evaluation: Theory to practice. In Proceedings of ANCS, 2008. Google ScholarDigital Library
- M. Becchi and P. Crowley. Extending finite automata to efficient match perl-compatible regular expressions. In Proceedings of CoNext, 2008. Google ScholarDigital Library
- M. Becchi, M. Franklin, and P. Crowley. A workload for evaluating deep packet inspection architectures. In Proceedings of IISWC, 2008.Google ScholarCross Ref
- N. Cascarano, P. Rolando, F. Risso, and R. Sisto. iNFAnt: NFA pattern matching on GPGPU devices. SIGCOMM CCR, 40 (5): 21--26, 2010. Google ScholarDigital Library
- M. Chen. TCAM-based high speed regular expression matching. Bachelor thesis, Institute of Networked Systems (IONS), University of Science and Technology of China, June 2010.Google Scholar
- M. Chen, Q. Dong, and K. Peng. TCAM-based DFA implementation: A novel approach to efficient regular expression matching. Technical report, Institute of Networked Systems (IONS), University of Science and Technology of China.Google Scholar
- J. W. Choi, A. Singh, and R. W. Vuduc. Model-driven autotuning of sparse matrix-vector multiply on GPUs. In Proceedings of ACM PPoPP, 2010. Google ScholarDigital Library
- Y. Dotsenko, S. S. Baghsorkhi, B. Lloyd, and N. K. Govindaraju. Auto-tuning of fast fourier transform on graphics processors. In Proceedings of PPOPP, 2011. Google ScholarDigital Library
- S. Hong, S. K. Kim, T. Oguntebi, and K. Olukotun. Accelerating CUDA graph algorithms at maximum warp. In Proceedings of ACM PPoPP, 2011. Google ScholarDigital Library
- J. Kim, H. Kim, J. H. Lee, and J. Lee. Achieving a single compute device image in OpenCL for multiple GPUs. In Proceedings of ACM PPoPP, 2011. Google ScholarDigital Library
- S. Kumar, B. Chandrasekaran, J. Turner, and G. Varghese. Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia. In Proceedings of ANCS, 2007. Google ScholarDigital Library
- S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In Proceedings of ACM SIGCOMM, 2006. Google ScholarDigital Library
- S. Lee, S.-J. Min, and R. Eigenmann. OpenMP to GPGPU: a compiler framework for automatic translation and optimization. In Proceedings of ACM PPoPP, 2009. Google ScholarDigital Library
- C. R. Meiners, J. Patel, E. Norige, E. Torng, and A. X. Liu. Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems. In Proceedings of USENIX Security, August 2010. Google ScholarDigital Library
- Peng, Dong, and Chen}peng2011iwqosK. Peng, Q. Dong, and M. Chen. TCAM-based DFA deflation: A novel approach to fast and scalable regular expression matching. In Proceedings of ACM/IEEE IWQoS, 2011. Google ScholarDigital Library
- K. Peng, S. Tang, Q. Dong, and M. Chen. Chain-based DFA deflation for fast and scalable regular expression matching using TCAM. In Proceedings of ANCS, 2011. Google ScholarDigital Library
- E. F. O. Sandes and A. C. M. de Melo. CUDAlign: using GPU to accelerate the comparison of megabase genomic sequences. In Proceedings of ACM PPoPP, 2010. Google ScholarDigital Library
- R. Smith, C. Estan, and S. Jha. XFA: Faster signature matching with extended automata. In Proceedings of IEEE Symposium on Security and Privacy, 2008. Google ScholarDigital Library
- R. Smith, C. Estan, S. Jha, and S. Kong. Deflating the big bang: fast and scalable deep packet inspection with extended finite automata. In Proceedings of ACM SIGCOMM, 2008. Google ScholarDigital Library
- R. Smith, N. Goyal, J. Ormont, K. Sankaralingam, and C. Estan. Evaluating GPUs for network packet signature matching. In Proceedings of ISPASS, 2009.Google ScholarCross Ref
- G. Vasiliadis, S. Antonatos, M. Polychronakis, E. P. Markatos, and S. Ioannidis. Gnort: High performance network intrusion detection using graphics processors. In Proceedings of RAID, 2008. Google ScholarDigital Library
- G. Vasiliadis, M. Polychronakis, S. Antonatos, E. P. Markatos, and S. Ioannidis. Regular expression matching on graphics hardware for intrusion detection. In Proceedings of RAID, 2009. Google ScholarDigital Library
- F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz. Fast and memory-efficient regular expression matching for deep packet inspection. In Proceedings of ANCS, 2006. Google ScholarDigital Library
- Y. Zhang, J. Cohen, and J. D. Owens. Fast tridiagonal solvers on the GPU. In Proceedings of ACM PPoPP, 2010. Google ScholarDigital Library
- M. Zheng, V. T. Ravi, F. Qin, and G. Agrawal. GRace: a low-overhead mechanism for detecting data races in GPU programs. In Proceedings of ACM PPoPP, 2011. Google ScholarDigital Library
Index Terms
- GPU-based NFA implementation for memory efficient high speed regular expression matching
Recommendations
GPU acceleration of regular expression matching for large datasets: exploring the implementation space
CF '13: Proceedings of the ACM International Conference on Computing FrontiersRegular expression matching is a central task in several networking (and search) applications and has been accelerated on a variety of parallel architectures, including general purpose multi-core processors, network processors, field programmable gate ...
GPU-based NFA implementation for memory efficient high speed regular expression matching
PPOPP '12Regular expression pattern matching is the foundation and core engine of many network functions, such as network intrusion detection, worm detection, traffic analysis, web applications and so on. DFA-based solutions suffer exponentially exploding state ...
Exploring different automata representations for efficient regular expression matching on GPUs
PPoPP '13: Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programmingRegular expression matching is a central task in several networking (and search) applications and has been accelerated on a variety of parallel architectures. All solutions are based on finite automata (either in deterministic or non-deterministic form),...
Comments