網路安全近年來已經被當成一項重要的議題，隨著網路速度的發展，高速入侵偵測系統的需求變得格外的重要。這些偵測系統為了描述一些有可能造成安全威脅的特徵樣式，大部分都開始使用正規表示式。傳統上我們可以使用能力等同於這些正規表式的有限自動機來辨識網路封包的資訊。而在有限狀態機的實現方法中，通常分為確定性有限狀態機以及非確定性有限狀態機。確定性有限狀態機只需執行單次掃描來決定下次狀態轉移，但通常需要較大的狀態儲存空間。非確定性有限狀態機則需執行多次掃描來決定下次狀態轉移，但通常需要較小的狀態儲存空間。
本論文將著重於探討現今網路的入侵偵測系統，討論造成狀態數目爆炸類型樣式的存在，以及造成狀態數劇烈增加的原因和將正比重複限制數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.

口試委員會審定書 i
誌謝 ii
摘要 iii
Abstract v
Contents vii
Figures ix
Tables xii
Algorithms xiii
Chapter 1 Introduction 1
1.1 Motivation 4
1.2 Contributions 6
1.3 Thesis organization 7
Chapter 2 Background and Problem Analysis 9
2.1 Regular Expression in Computing Theory 9
2.2 Syntax of Regular Expressions 12
2.3 Finite State Automaton 15
2.3.1 Deterministic Finite-State Automaton 17
2.3.2 Non-Deterministic Finite-State Automaton 18
2.4 Examples of Network Applications 20
2.5 Recognizer Design Consideration 21
2.6 Analysis of the Recognizer 22
2.7 The Prototype of Regular Expressions with DFA 24
2.8 The Prototype of Regular Expressions with NFA 28
2.9 Summary 30
Chapter 3 Related Works 32
3.1 String Pattern Matching 33
3.2 Patterns using Regular Expressions 34
3.3 String Matching Hardware Architectures 36
3.4 Recent Researches 45
3.5 Network Platform 49
3.6 Summary 50
Chapter 4 Two-Phase Matching Approach 51
4.1 Motivation of Hybrid Matching 52
4.2 Multi-Staged Partition 53
4.3 Hybrid Matching Solution 55
4.4 Introduction to Two-Phase Matching Approach 56
4.5 Grouping 59
4.6 Dynamically Reconfigurable NFA 64
4.7 Summary 71
Chapter 5 Multi-Character Matching Approach 73
5.1 Motivation 73
5.2 Multi-character Solution 74
5.3 Design Consideration 78
5.4 Dynamically Reconfigurable Matching Approach 78
5.5 Extended Structure 81
5.6 Summary 81
Chapter 6 Implementation 83
6.1 Pre-processing 83
6.1.1 Table Formats 84
6.1.2 Pre-processing Algorithm 86
6.1.3 NFA Table Translator 89
6.1.4 DFA Table Compression 95
6.2 NFA Matching Block 100
6.3 Run Time Recognizer 104
6.3.1 Evaluation Board 105
6.3.2 System architecture 106
6.3.3 Pipeline 112
6.3.4 Collision 112
6.4 Summary 113
Chapter 7 Experimental Results 114
7.1 Static NFA Matching Block 114
7.2 Dynamical NFA Matching Block 121
7.3 DFA Approach Comparisons 127
7.4 System Evaluations 132
7.5 Summary 134
Chapter 8 Conclusion and Future Work 135
8.1 Future Work 137
References 138
Appendix A 142
Appendix B 144

[1]Snort official web site. http://www.snort.org/.
[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.
[4]Chomsky_hierarchy in Wikipedia, http://en.wikipedia.org/wiki/Chomsky_hierarchy.
[5]Flex: The fast lexical analyzer. http://flex.sourceforge.net/.
[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.
[8]S. Wu and U. Manber. "A fast algorithm for multi-pattern searching, " Technical Report TR-94-17, Dept. of Comp. Science, Univ of Arizona, 1994.
[9]N. Tuck, T. Sherwood, B. Calder, and G. Varghese, "Deterministic memory-efficient string matching algorithms for intrusion detection," in INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004, pp. 2628-2639 vol.4.
[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.
[11]S. Dharmapurikar and J. W. Lockwood, "Fast and Scalable Pattern Matching for Network Intrusion Detection Systems," Selected Areas in Communications, IEEE Journal on, vol. 24, pp. 1781-1792, 2006.
[12]M. Aldwairi, T. Conte, and P. Franzon, “Configurable string matching hardware for speeding up intrusion detection,” SIGARCH Comput. Archit. News, 33(1):99–107, 2005.
[13]Z. K. Baker and V. K. Prasanna, "A methodology for synthesis of efficient intrusion detection systems on FPGAs," in Field-Programmable Custom Computing Machines, 2004. FCCM 2004. 12th Annual IEEE Symposium on, 2004, pp. 135-144.
[14]J. Moscola, J. Lockwood, R. P. Loui, and M. Pachos, "Implementation of a content-scanning module for an Internet firewall," in Field-Programmable Custom Computing Machines, 2003. FCCM 2003. 11th Annual IEEE Symposium on, 2003, pp. 31-38.
[15]F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz, "Fast and memory-efficient regular expression matching for deep packet inspection," in Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems San Jose, California, USA: ACM, 2006.
[16]S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner, "Algorithms to accelerate multiple regular expressions matching for deep packet inspection," in Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications Pisa, Italy: ACM, 2006.
[17]S. Kumar, J. Turner, and J. Williams, "Advanced algorithms for fast and scalable deep packet inspection," in Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems San Jose, California, USA: ACM, 2006.
[18]B. C. Brodie, D. E. Taylor, and R. K. Cytron, “A scalable architecture for high-throughput regular-expression pattern matching,” SIGARCH Comput. Archit. News, 34(2):191–202, 2006.
[19]M. Becchi and P. Crowley, "A hybrid finite automaton for practical deep packet inspection," in Proceedings of the 2007 ACM CoNEXT conference New York, New York: ACM, 2007.
[20]R. Smith, C. Estan, and S. Jha, "XFA: Faster Signature Matching with Extended Automata," in Security and Privacy, 2008. SP 2008. IEEE Symposium on, 2008, pp. 187-201.
[21]R. W. Floyd and J. D. Ullman, "The Compilation of Regular Expressions into Integrated Circuits," J. ACM, vol. 29, pp. 603-622, 1982.
[22]R. Sidhu and V. K. Prasanna, "Fast Regular Expression Matching Using FPGAs," in Field-Programmable Custom Computing Machines, 2001. FCCM ''01. The 9th Annual IEEE Symposium on, 2001, pp. 227-238.
[23]L. Cheng-Hung, H. Chih-Tsun, J. Chang-Ping, and C. Shih-Chieh, "Optimization of Pattern Matching Circuits for Regular Expression on FPGA," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol. 15, pp. 1303-1310, 2007.
[24]B. Joao, S. Ioannis, M. P. C. Joao, and V. Stamatis, "Regular expression matching for reconfigurable packet inspection," in Field Programmable Technology, 2006. FPT 2006. IEEE International Conference on, 2006, pp. 119-126.
[25]C. R. Clark and D. E. Schimmel, "Efficient Reconfigurable Logic Circuits for Matching Complex Network Intrusion Detection Patterns, " in Field-Programmable Logic and Applications: 956-959, 2003.
[26]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.
[27]J. Moscola, Y. H. Cho, and J. W. Lockwood, "A Scalable Hybrid Regular Expression Pattern Matcher," in Field-Programmable Custom Computing Machines, 2006. FCCM ''06. 14th Annual IEEE Symposium on, 2006, pp. 337-338.
[28]Y.-H. E. Yang, W. Jiang, and V. K. Prasanna, "Compact architecture for high-throughput regular expression matching on FPGA," in Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems San Jose, California: ACM, 2008.
[29]N. Yamagaki, R. Sidhu, and S. Kamiya, "High-speed regular expression matching engine using multi-character NFA," in Field Programmable Logic and Applications, 2008. FPL 2008. International Conference on, 2008, pp. 131-136.
[30]J. Divyasree, H. Rajashekar, and K. Varghese, "Dynamically reconfigurable regular expression matching architecture," in Application-Specific Systems, Architectures and Processors, 2008. ASAP 2008. International Conference on, 2008, pp. 120-125.
[31]S. Antonatos, K. G. Anagnostakis, and E. P. Markatos, "Generating realistic workloads for network intrusion detection systems, " SIGSOFT Softw. Eng. Notes, 29(1):207–215, 2004.
[32]C.-T. D. Lo, Y.-G. Tai, and K. Psarris, "Hardware implementation for network intrusion detection rules with regular expression support," in Proceedings of the 2008 ACM symposium on Applied computing Fortaleza, Ceara, Brazil: ACM, 2008.
[33]C.-T. D. Lo, and Y.-G. Tai, “Highly Space Efficient Counters for Perl Compatible Regular Expressions in FPGAs,” in the International Workshop on Applied Reconfigurable Computing, Imperial College London, U.K., March 26-28, 2008.
[34]C.-C. Yang, "Two phase pattern matching algorithm and architecture for regular expression," in Department of Graduate Institute of Electrical Engineering, College of Electrical Engineering and Computer Science. vol. Master: National Taiwan University, 2008.
[35]C.-L. Chang, "The design and implementation of a perl compatible regular expression pattern matching engine with pipeline architecture using FPGAs," in Department of Graduate Institute of Electrical Engineering, Master Thesis of College of Electrical Engineering and Computer Science: National Taiwan University, 2008.
[36]Altera Inc, “DE2 Development and Education Board User Manual,” (v1.4.1), 2007.