以圖形處理器為基礎加速正規表示法比較之多執行緒演算法設計

Accelerating Regular Expression Matching Using Multi-threaded Algorithm on GPU

蔡昇宇(Sheng-Yu Tsai)

指導教授 ： 張世杰

國立清華大學/電機資訊學院/資訊工程學系/碩士(2010年)

https://doi.org/10.6843/NTHU.2010.00469

摘要

網路威脅偵測系統(Network Intrusion Detection Systems)已經被廣泛地使用來偵測網路上的病毒，並且保護我們的電腦。其中最主要的核心，就是字串比對(Pattern Matching)的引擎，而正規表示法(Regular Expression)就是最常被採用的表示方法，因為他簡潔而有力的演繹能力，同時，使用上非常具有彈性。不過，雖然使用上非常方便，相對地，它運算量大又複雜，實做上也有許多問題。因此，正規表示法的字串比對是整個網路威脅偵測系統效能的瓶頸。這篇論文中，我們提出一個創新的階層式有限狀態機(Hierarchical Finite State Machine)，他是一個特別適合應用在圖形處理器(GPU)的一個平行演算法，並且能夠解決並加速一般無法處理的複雜正規表示法，同時，依然能過有效處理一般的固定字串(Exact String)。

關鍵字

圖形處理器 ； 正規表示法 ； 字串比對 ； 加速

並列摘要

Abstract
In terms of flexibility and scalability, regular expression has been widely adopted in Network Intrusion Detection Systems (NIDS) to represent network attack patterns. To accommodate the increasing number of attack patterns, several recent researches adopt Graphic Processor Units (GPUs) to accelerate the matching process. However, all of them cannot deal with complex regular expressions which have become an important representation in virus database. In this paper, we propose a novel parallel algorithm to accelerate regular expression matching performed on GPUs. We also propose an innovative state machine for complex regular expression matching, the state machine of which is more suitable for performing in the parallel algorithm. The experimental results show that the novel approach not only achieves a significant speedup on performing complex regular expression matching but also are faster on the simple regular expression matching than other GPU approaches.

參考文獻

[5] B.L. Hutchings, R. Franklin, and D. Carver, “Assisting Network Intrusion Detection with Reconfigurable Hardware,” in Proc.10th Ann. IEEE Symp. Field-Program. Custom Comput. Mach. (FCCM), 2002, pp. 111-120.

[6] C. R. Clark and D. E. Schimmel, “Scalable Pattern Matching for High Speed Networks,” in Proc. 12th Ann. IEEE Symp. Field-Program. Custom Comput. Mach. (FCCM), 2004, pp. 249-257

[7] J. Moscola, J. Lockwood, R. P. Loui, and M. Pachos, “Implementation of a Content-Scanning Module for an Internet Firewall,” in Proc. 11th Ann. IEEE Symp. Field-Program. Custom Comput. Mach. (FCCM), 2003, pp. 31–38.

[8] M. Aldwairi*, T. Conte, and P. Franzon, “Configurable String Matching Hardware for Speeding up Intrusion Detection,” in ACM SIGARCH Computer Architecture News, 2005, pp. 99–107

[9] S. Dharmapurikar and J. Lockwood, “Fast and Scalable Pattern Matching for Content Filtering,” in Proc. of Symp. Architectures Netw. Commun. Syst. (ANCS), 2005, pp. 183-192