比對正規表示式之硬體設計

Hardware Design of Regular Expression Matching

江長平(Chang-Ping Jiang)

指導教授 ： 張世杰

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

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

摘要

正規表示式在網路入侵偵測系統被廣泛地使用來表示攻擊的病毒碼。之前已經有許多的硬體架構被提出來加速比對正規表示式。在這篇論文裡，我們專注在兩種硬體架構上，一種使用可程式化邏輯閘陣列，其上之邏輯單元的可重新設計功能可用來更新病毒碼。另一種硬體架構是使用以記憶體為基礎的演算法。在第一種邏輯單元為基礎的架構，雖然縮小邏輯方程式在電腦輔助設計領域已經被深入的研究，但是，研究如何縮小多個正規表示式卻被忽略。這篇論文提出了一個新的分享架構允許我們的演算法去取出共同的正規表示式部份以及分享共同部份。實驗結果顯示我們的分享架構可以有效地降低比對正規表示式之電路的面積。在第二種使用記憶體為基礎之演算法的架構，這篇論文也提出了一個新的演算法，可以有效地分享共同的部分字串，實驗結果也顯示我們的演算法可以降低記憶體的使用。

關鍵字

正規表示式 ； 硬體設計

並列摘要

Regular expressions are widely used in Network Intrusion Detection System (NIDS) to represent attack patterns. Previously, many hardware architectures have been proposed to accelerate regular expression matching. In this thesis, we concentrate on two hardware architectures. One uses reconfigurable logic module on FPGA because FPGA allows for updating new attack patterns. The other uses memory-based algorithm. For the first logic-based architecture, because of increasing number of attacks, we need to accommodate large number of regular expressions on FPGA. Although the minimization of logic equations has been studied intensively in the area of computer-aided design (CAD), the minimization of multiple regular expressions has been largely neglected. This thesis presents a novel sharing architecture allowing our algorithm to extract and share common sub-regular expressions. Experimental results show that our sharing scheme significantly reduces the area of regular expression pattern matching circuits. For the second memory-based architecture, this thesis presents a novel sharing mechanism allowing our algorithm to share common sub-patterns resulting in the significant reduction of memory.

並列關鍵字

regular expression ； hardware design

參考文獻

[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), Apr. 2001, pp. 227-238.

[2] B. L. Hutchings, R. Franklin and D. Carver, “Assisting Network Intrusion Detection with Reconfigurable Hardware,” in Proc. of the10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’02), Sep. 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.

[6] S. Dharmapurikar and J. W. Lockwood. “Fast and Scalable Pattern Matching for Content Filtering,” Proceedings of Symposium on Architectures for Networking and Communications Systems (ANCS), Oct 2005.

[7] F. Yu, R. Katz, and T. V. Lakshman, “Gigabit Rate Multiple-Pattern Matching with TCAM,” (ICNP 2004)