GPU-based NFA implementation for memory efficient high speed regular expression matching
Authors:
Open Access
- 25 February 2012
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 47 (8) , 129-140
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.Keywords
This publication has 24 references indexed in Scilit:
- iNFAntACM SIGCOMM Computer Communication Review, 2010
- OpenMP to GPGPU2009
- Regular Expression Matching on Graphics Hardware for Intrusion Detection2009
- Gnort: High Performance Network Intrusion Detection Using Graphics Processors2008
- XFA: Faster Signature Matching with Extended Automata2008 IEEE Symposium on Security and Privacy (SP 2008), 2008
- Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia2007
- An improved algorithm to accelerate regular expression evaluation2007
- A hybrid finite automaton for practical deep packet inspection2007
- Fast and memory-efficient regular expression matching for deep packet inspection2006
- Algorithms to accelerate multiple regular expressions matching for deep packet inspection2006