A Fast Two-Phase Multi-Character Dynamically Reconfigurable Regular Expression Matching Architecture

網路安全近年來已經被當成一項重要的議題，隨著網路速度的發展，高速入侵偵測系統的需求變得格外的重要。這些偵測系統為了描述一些有可能造成安全威脅的特徵樣式，大部分都開始使用正規表示式。傳統上我們可以使用能力等同於這些正規表式的有限自動機來辨識網路封包的資訊。而在有限狀態機的實現方法中，通常分為確定性有限狀態機以及非確定性有限狀態機。確定性有限狀態機只需執行單次掃描來決定下次狀態轉移，但通常需要較大的狀態儲存空間。非確定性有限狀態機則需執行多次掃描來決定下次狀態轉移，但通常需要較小的狀態儲存空間。 本論文將著重於探討現今網路的入侵偵測系統，討論造成狀態數目爆炸類型樣式的存在，以及造成狀態數劇烈增加的原因和將正比重複限制數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. his 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.口試委員會審定書 i謝 ii要 iiibstract vontents viiigures ixables xiilgorithms xiiihapter 1 Introduction 1.1 Motivation 4.2 Contributions 6.3 Thesis organization 7hapter 2 Background and Problem Analysis 9.1 Regular Expression in Computing Theory 9.2 Syntax of Regular Expressions 12.3 Finite State Automaton 15.3.1 Deterministic Finite-State Automaton 17.3.2 Non-Deterministic Finite-State Automaton 18.4 Examples of Network Applications 20.5 Recognizer Design Consideration 21.6 Analysis of the Recognizer 22.7 The Prototype of Regular Expressions with DFA 24.8 The Prototype of Regular Expressions with NFA 28.9 Summary 30hapter 3 Related Works 32.1 String Pattern Matching 33.2 Patterns using Regular Expressions 34.3 String Matching Hardware Architectures 36.4 Recent Researches 45.5 Network Platform 49.6 Summary 50hapter 4 Two-Phase Matching Approach 51.1 Motivation of Hybrid Matching 52.2 Multi-Staged Partition 53.3 Hybrid Matching Solution 55.4 Introduction to Two-Phase Matching Approach 56.5 Grouping 59.6 Dynamically Reconfigurable NFA 64.7 Summary 71hapter 5 Multi-Character Matching Approach 73.1 Motivation 73.2 Multi-character Solution 74.3 Design Consideration 78.4 Dynamically Reconfigurable Matching Approach 78.5 Extended Structure 81.6 Summary 81hapter 6 Implementation 83.1 Pre-processing 83.1.1 Table Formats 84.1.2 Pre-processing Algorithm 86.1.3 NFA Table Translator 89.1.4 DFA Table Compression 95.2 NFA Matching Block 100.3 Run Time Recognizer 104.3.1 Evaluation Board 105.3.2 System architecture 106.3.3 Pipeline 112.3.4 Collision 112.4 Summary 113hapter 7 Experimental Results 114.1 Static NFA Matching Block 114.2 Dynamical NFA Matching Block 121.3 DFA Approach Comparisons 127.4 System Evaluations 132.5 Summary 134hapter 8 Conclusion and Future Work 135.1 Future Work 137eferences 138ppendix A 142ppendix B 14