快速兩階段多字元動態可重組正規表示式比對系統

網路安全近年來已經被當成一項重要的議題，隨著網路速度的發展，高速入侵偵測系統的需求變得格外的重要。這些偵測系統為了描述一些有可能造成安全威脅的特徵樣式，大部分都開始使用正規表示式。傳統上我們可以使用能力等同於這些正規表式的有限自動機來辨識網路封包的資訊。而在有限狀態機的實現方法中，通常分為確定性有限狀態機以及非確定性有限狀態機。確定性有限狀態機只需執行單次掃描來決定下次狀態轉移，但通常需要較大的狀態儲存空間。非確定性有限狀態機則需執行多次掃描來決定下次狀態轉移，但通常需要較小的狀態儲存空間。本論文將著重於探討現今網路的入侵偵測系統，討論造成狀態數目爆炸類型樣式的存在，以及造成狀態數劇烈增加的原因和將正比重複限制數N的指數複雜度化約成線性複雜度的方法。我們提出透過相當的狀態共用，使用兩階段的比對方法來結合確定性有限狀態機與非確定性有限狀態機，並將正規表示式前綴匹配共用並以硬體平行比對的方式建構，剩餘較大狀態資料則儲存於外部記憶體空間。此外，實作硬體非確定性有限狀態機可透過多工器的切換來動態重組正規表示式語法，以達成全系統可動態重組化的效果。我們使用可現場規劃的邏輯陣列來實作此兩階段比對架構，透過比對狀態平行化操作的方式，可實現工作在230 MHz，可達到1.84 Gbps的比對速度。若使用每時脈周期四個字元比對，可達到更高的比對速度。

關鍵字

入侵偵測；多字元；動態可重組；樣式比對；正規表示式；確定性有限狀態機；非確定性有限狀態機

並列摘要

Network security has recently become an important issue. With the growing of high-speed networks, there is a growing demand for high performance network intrusion detection systems (NIDSs). Some NIDSs may use regular expressions to describe the signatures of security threats. Traditionally, we can build finite-state automaton corresponding to these regular expressions to identify the suspicious packets. Deterministic finite-state automata (DFA) and non-deterministic finite-state automata (NFA) are commonly used for regular expressions matching. The DFA does one-pass scanning with a larger storage cost, while the NFA does multi-pass scanning with a less storage cost. This thesis focuses on the state explosion problem existing in the common signature patterns of an NIDS, and how to reduce the state storage cost from the exponential complexity to linear complexity. Through the common string states sharing, we propose a two-phases matching architecture combining DFA and NFA. This architecture constructs circuit-based parallel matching with prefix sharing, while the remains state transition tables stored in off-chip memory spaces. Furthermore, with multiplexers, fully system matching patterns are dynamically reconfigurable. We also implement the two-phase matching engine in a field programmable gate array (FPGA). Through parallel state operations, the optimized architecture will process four characters at 230 MHz, resulting in a concurrent throughput of 1.84 Gbps. If the 4-character processing module is implemented, higher throughput can be achieved.

並列關鍵字

Network Intrusion Detection ； Multi-Character ； Dynamically Reconfigurable ； Pattern Matching ； Regular Expressions ； DFA ； NFA

參考文獻

[2] Bro intrusion detection system. http://www.bro-ids.org/.

[3] R. M. J. E. Hopcroft, and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd ed.: Addison-Wesley, 2001.

[6] PCRE- perl compatible regular expressions. http://www.pcre.org/

[7] A. V. Aho and M. J. Corasick, "Efficient string matching: an aid to bibliographic search," Commun. ACM, vol. 18, pp. 333-340, 1975.

[10] T. Lin and T. Sherwood, "A high throughput string matching architecture for intrusion detection and prevention," in Computer Architecture, 2005. ISCA '05. Proceedings. 32nd International Symposium on, 2005, pp. 112-122.

國際替代計量

快速兩階段多字元動態可重組正規表示式比對系統

全文下載

主題瀏覽