網路的使用量在近年內呈現巨大的成長，許多的病毒與惡意攻擊影響網路安全甚鉅，網路入侵偵測系統(NIDS)是一種藉由事先定義好的規則來找出這些惡意攻擊。這些規則是被一個被廣泛應用的偵測系統之一─Snort定義的，在網路入侵偵測系統中，搜尋多個字串是一個計算量很高也很昂貴的一項工作，我們需要找到更有效率且成本更低的字串搜尋方式。傳統的軟體演算法無法應付如此高速的網路惡意攻擊的成長，因此在硬體資源上實做IDS系統逐漸變成一個重要的議題。
　　在本篇論文中，我們提出了一個架構在KMP演算法上的有效率的架構，我們的主要想法是設計一個可以在一個時脈處理n個字元的架構，這個變數代表一個時脈裡可以處理的字元數，為了確保我們的架構的效率，我們討論了所有可能的狀況，雖然這樣可能造成許多複雜的結果，但是我們設計出來的架構可以選取正確的下一個字串可能的比較位置，並且在下一個時脈裡重複同樣的比較程序。根據我們的觀察，我們設計的架構可以運行到每秒十億位元以上的速度。

The usage of the Internet has grown enormously in recent years. There are many viruses affect the network security significantly. Network Intrusion Detection System (NIDS) is a system developed for identifying attacks by using a set of rules. These rules are defined by Snort; one of the most often applied NIDS in the world. Searching for multiple patterns is a computationally expensive task in NIDS. We want to find a method to search patterns more efficiently and have cheaper cost. However, the traditional software-based NIDS solutions usually can not achieve a high-speed required for ever growing Internet attacks. Therefore, the issue of the implement in hardware for preventing the malicious attack from intruders has became more significantly.
In this thesis, we proposed an efficient architecture based on KMP algorithm. Our main idea is design an architecture that always processes n characters per clock cycle. Here the variable, n, means the amount of the input characters we could process in each clock cycle. To ensure our proposed scheme could always process efficiently, we discuss all possible circumstances and compare at most two potential matching prefix at the same clock cycle. Although there will be many complex compare results, our design will find the correct index of the pattern and repeat the comparisons in next clock cycle. According to our observation, our approach could process in giga-bit ratio and use a small quantity of hardware resource.

Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Snort NIDS 2
1.3 Overview of Our Thesis 3
Chapter 2 Related Work 5
2.1 Software-based solutions 6
2.1.1 KMP algorithm 6
2.1.2 Boyer-Moore algorithm 7
2.1.3 Aho-Corasick algorithm 10
2.2 FPGA-based solutions 12
2.3 Bloom Filter-based solutions 14
2.4 TCAM based solutions 16
Chapter 3 Proposed Architecture 19
3.1 Preliminaries 19
3.2 Multi-Character KMP Algorithm 22
3.2.1 Multi-KMP Algorithm 23
3.2.2 Backtrack Function 26
3.3 Architecture Description 28
3.3.1 Case Discussion 29
3.3.2 Detail of Control Units 36
3.3.3 Data Flow of our Architecture 39
3.4 Fibonacci String 43
3.5 Pattern Parsing Strategy 45
3.5.1 SRL-16 Shift Register 45
3.5.2 Pattern Parsing 46
3.6 Extensions 47
Chapter 4 Performance 51
4.1 Environment 51
4.2 Performance Metrics 52
4.3 Performance Evaluation 53
4.3.1 Pattern Set Distribution 53
4.3.2 Compare with our design in different degrees 55
4.3.3 Compare with other FPGA designs 57
Chapter 5 Conclusions 59
References 60

[1]A. Aho and M. Corasick, “Efficient string matching: An aid to bibliographic search,” Communications of the ACM, vol. 18, no. 6, pp.333-343, June 1975.
[2]Z. K. Baker and V. K. Prasanna, “A Computationally Efficient Engine for Flexible Intrusion Detection.” in Proceedings of IEEE Transactions on Very Large Scale Integration (VLSI), 2005
[3]R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no 10, pp.762-772, Oct. 1977.
[4]Young H. Cho, W.H. Mangione-Smith, “Deep packet filter with dedicated logic and read only memories,” in Proceedings of the 12th IEEE Symposium of Field-Programmable Custom Computing Machines, 2004.
[5]C. R. Clark and D. E. Schimmel. “Scalable Pattern Matching for High Speed Networks,” In IEEE Symposium on Field-Programmable Custom Computing Machines, (FCCM), Napa, CA, Apr. 2004.
[6]S. Dharmapurikar, P. Krishnamurthy, T. S. Sproull and J. W. Lockwood, “Deep Packet Inspection using Parallel Bloom Filters”, IEEE Micro, vol. 24, no. 1, pp. 52-61, Jan. 2004.
[7]D. E. Knuth, J. H. M. Jr., and V. R. Pratt, “Fast pattern matching in strings,” SIAM J. Comput., vol. 6, no. 2, pp. 323–350, June 1977.
[8]M. Gokhale, D.Dubois, A. Dubois, M. Boorman, S. Poole, and V. Hogsett. “Granidt: Towards gigabit rate network intrusion detection techolory.” In Proceedings of International Conference on Field Programmable Logic and Applications, pages 404–413, 2002.
[9]R. Nigel Horspool, “Practical fast searching in strings.” Software–Practice & Experience 10–6 (1980) 501–506.
[10]Andrew Hume & Daniel Sunday, “Fast string searching.” Software–Practice &Experience 21–11 (1991) 1221–1248.
[11]J. Singaraju, L. Bu and J. A. Chandy, “A Signature Match Processor Architecture for Network Intrusion Detection.” In Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2005.
[12]Snort-the de Facto Standard for Intrusion Detection/Prevention, [Online]. Available: www.snort.org
[13]I. Sourdis and D. Pnevmatikatos. “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching.” In IEEE Symposium on Field-Programmable Custom Computing Machines, (FCCM), Napa, CA, Apr. 2004.
[14]F. Yu, R. H. Katz, T. V. Lakshman, “Gigabit Rate Packet Pattern-Matching Using TCAM,” in Proceeding of 12th IEEE International Conference on Network Protocols (ICNP’04), Berlin, Germany, Oct. 2004, pp. 174-183.