具字串共用之正規表示法樣式比對架構

A Regular Expression Pattern Matching Architecture with Common String Sharing Scheme

王彥凱(Yen-Kai Wang)

指導教授 ： 王勝德

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00673

摘要

在入侵偵測系統中，正規表示法非常適合用來描述網路攻擊特徵。使用NFA架構硬體實作正規表式法，常會產生兩大問題，1.所佔用的硬體資料過大，2.不能新增新的rule的問題。
本篇論文著重於兩大問題的解決，對於硬體資料過大的問題，我們提出共用字串機制來解決，並改善其硬體架構，使其達到高速比對，最小化電路空間的設計。實驗結果顯示，我們的正規表示法樣式比對器，在Altera DE2上實作，速度可達到2.4 Gbps，且不影響速度情況下，可以使原設計架構有23.51%的空間改善(For snort 2.8)。
對於問題2對面不斷更新的樣式規則，我們也提出一種動態支援的比較器，以解決產品化後，未來要支援的新樣式規則。

關鍵字

正規表示法 ； Snort ； 樣式比對 ； 共用字串

並列摘要

Regular expressions are very suitable to describe the features of network attacks in an Intrusion Detection System (IDS). NFA-based hardware architectures might cause two problems. 1. NFA-based architectures occupy too much hardware area.2. NFA-based architecture can not add new rule dynamically.
This paper focus on these two issues .For the first one, we propose a string mechanism to improve the hardware area of NFA circuit. The experiment results of the proposed Regular Expression matching engine can scan the payload up to the rate of 2.4 Gbps, and have 23.51% space improvement (for the snort 2.8)
For the second one, we also propose a matching architecture that can support dynamic updating of new rule sets.this comparator is going to support new rule in the future.

並列關鍵字

Regular Expression ； Snort ； Pattern match ； Common string

參考文獻

[5] C. R. Clark and D. E. Schimmel, "Scalable pattern matching for high speed networks," in Field-Programmable Custom Computing Machines, 2004. FCCM 2004. 12th Annual IEEE Symposium on, 2004, pp. 249-257.

[7] M. Faezipour and M. Nourani, "Constraint Repetition Inspection for Regular Expression on FPGA," in High Performance Interconnects, 2008. HOTI '08. 16th IEEE Symposium on, 2008, pp. 111-118.

[9] P. Sutton, "Partial character decoding for improved regular expression matching in FPGAs," in Field-Programmable Technology, 2004. Proceedings. 2004 IEEE International Conference on, 2004, pp. 25-32.

[11] James, M., H. C. Young, et al. (2006). A Scalable Hybrid Regular Expression Pattern Matcher. Field-Programmable Custom Computing Machines, 2006. FCCM '06. 14th Annual IEEE Symposium on.

[12]B. C. Brodie, R. K. Cytron, and D. E. Taylor, "A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching," in Computer Architecture, 2006. ISCA '06. 33rd International Symposium on, 2006, pp. 191-202.