GPU-based NFA implementation for memory efficient high speed regular expression matching
GPU-based NFA implementation for memory efficient high speed regular expression matching
复制标题
基于 GPU 的 NFA 实现，可实现内存高效的高速正则表达式匹配
DOI：
10.1145/2145816.2145833
复制
发表时间：
2012
影响因子：
35.6
通讯作者：
["Yuan Zu
中科院分区：
文献类型：
--
作者：
["Yuan Zu
正则表达式模式匹配是网络入侵检测、蠕虫检测、流量分析、Web应用等诸多网络功能的基础和核心引擎，基于DFA的解决方案存在状态空间呈指数级爆炸的问题，无法在不牺牲匹配速度的前提下进行补救。鉴于基于DFA的方法的这种可扩展性问题，人们对基于NFA的用于存储器高效的正则表达式匹配的方法越来越感兴趣。为了使用NFA实现高匹配速度，它需要潜在的大规模并行处理，因此代表了在图形处理器单元（GPU）上的理想编程任务。在深入理解NFA特性和GPU体系结构的基础上，通过合理的数据结构和并行编程设计，提出了将NFA适配到GPU体系结构中的有效方法，从而更好地利用GPU的并行处理能力实现高速正则表达式匹配。实验结果表明，与现有的基于GPU的NFA实现方法[9]相比，我们提出的方法可以将匹配速度提高29~46倍，在NVIDIA GTX-460 GPU上始终获得10 Gbps以上的匹配速度。同时，我们的设计只需要少量的内存空间，比DFA大小呈指数级增长更慢。这些结果使我们的设计成为一个有效的解决方案，内存高效的高速正则表达式匹配，并清楚地证明了GPU作为一个平台，内存高效的高速正则表达式匹配的权力和潜力。
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.