High-Performance Pattern Matching Algorithm on GPU

以圖形處理器為基礎之高效能樣式比對演算法

林群裕(Chum-Yu Lin)

指導教授 ： 張世杰

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

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

摘要

中文摘要
網路侵入偵測系統已經被廣泛地使用在保護電腦受到網路病毒攻擊上這方面一段時間了，然而由於現在網路上的攻擊種類漸多，並且網路的複雜度也增加，傳統上在單一處理器的軟體的方法已經不適合在這高速網路環境裡了。最近圖形處理器已經受到很多人的注意，最主要的原因是他的強大的資料平行處理運算能力。而圖形處理器除了在圖形應用程式上，也其他各個領域上有突破性的發展，像是科學物理計算、電子設計自動化、生物技術上等方面。
在這篇論文裡，我們提出新的演算法可以加速樣式比對，並且實作在圖形處理器上，這個使用Snort樣式的實驗結果證明了，我們新的演算法執行在圖形處理器上，相較於將傳統的演算法執行在運算處理器上，可以成功的大幅度加速樣式比對， 配合這個演算法，我們在記憶體使用量也有妥善的改良。

關鍵字

圖形處理器 ； 多執行緒

並列摘要

Abstract
Network Intrusion Detection System (NIDS) has been widely used to protect computer systems from network attacks. Due to the ever-increasing number of attacks and network complexity, traditional software approaches on uni-processor become inadequate for the high-speed network.
Graphics Processor Unit (GPU) has attracted a lot of attention due to its dramatic power of massive data parallel computing. In addition to graphic applications, GPU has achieved substantial progress than general-purpose CPUs for a range of non-graphical applications such as science and physics computations, electronic design automation, bioinformatics, and so on.
In this paper, we propose a novel algorithm to speedup pattern matching on GPU. The experimental results show the new algorithm on GPU can achieve a significant speedup compared to the conventional Aho-Corasick algorithm on CPU for total Snort string patterns. In addition, the new algorithm also has improvement on memory requirements.

參考文獻

[1] R. Sidhu and V. K. Prasanna. Fast regular expression matching using FPGAs. In Proc. of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '01), pp. 227-238, 2001.

[2] R. Franklin, D. Carver, and B.L. Hutchings. Assisting Network Intrusion Detection with Reconfigurable Hardware. In Proceedings of IEEE FCCM 2002, pp. 111-120, Apr. 2002.

[3] J. Moscola, J. Lockwood, R. P. Loui and M. Pachos. Implementation of a Content-Scanning Module for an Internet Firewall. In Proc. of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’03), Apr. 2003.

[4] C. R. Clark and D. E. Schimmel. “Scalable Parallel Pattern Matching on High Speed Networks,” in Proceedings of the Twelfth Annual IEEE Symposium on Field Programmable Custom Computing Machines 2004 (FCCM '04), 2004.

[6] M. Aldwairi*, T. Conte, and P. Franzon. Configurable String Matching Hardware for Speeding up Intrusion Detection. In ACM SIGARCH Computer Architecture News, 33(1):99–107, 2005.