隨著網路技術的進步，現今的網路設備除了具備依據封包標頭欄位作為選徑及封包分類的技術之外，尚需可以檢測封包內容的能力，以提供更進ㄧ步的應用及加值服務。檢測封包內容的關鍵技術在於ㄧ個多樣式字串匹配演算法，其根據事先定義的樣式資料庫搜尋封包內容找出所有吻合的樣式值及其出現位置。在以 Gpbs 為吞吐量的網路環境之下，此演算法如何滴水不漏檢測每秒通過動輒幾百萬的封包數量將是ㄧ大挑戰。本論文提出一個多樣式字串匹配演算法並衡量其純軟體實作及整合到 SoC 系統的可行性與效能。此一演算法結合了用以縮小搜尋範圍的濾除技術並利用樣式字串間字首、字尾可能交互重疊的關係以加速整體匹配速度。在ㄧ般的網路資料流情況下，前端的濾除技術可以大幅過濾不需要匹配的封包因而提高系統的吞吐量；然而在封包中ㄧ但發現了任何匹配的樣式之後，預先分析的樣式字串字首、字尾重疊關係將可派上用場，其效率可分兩方面來討論：若目前匹配的樣式字串其字尾與其他樣式字串有重疊關係時，這些與目前匹配樣式有重疊關係的其他樣式將有可能是下一個可能匹配的候選者，此時則逐一檢視這些樣式；另ㄧ方面，若在檢視所有可能匹配樣式之後仍沒有找到任何配，則搜尋引擎可以停在目前正在掃描的封包內容位置，而不像其他演算法需要向後倒退(bask shift)以重新開始下ㄧ輪的搜尋動作。此演算法在記憶體使用量及匹配速度均有不錯的表現，當使用最新的 Snort 版本作為樣式資料庫時，此演算法的記憶體消耗量只有 500 KB；另ㄧ方面，其效能與在平均狀況(average-case)下公認最好的Wu-Manber 演算法相接近，並在最糟狀況下(worst-case)擁有更佳的效能。因此，以實作的觀點而言，整個演算法的資料結構可以放到高速的 cache 或是 on-chip memory 以達到單一的記憶體存取而提升匹配速度，而在最糟狀況下效能的改善則可使系統避免針對演算法弱點的攻擊(algorithmic attack)。

Index of Figures and Tables
Abstract
中文摘要
Chapter1. Introduction
Chapter2. Related Works
2.1 Searching filters
2.1.1 Bloom Filter
2.2 Multi-pattern String matching algorithms
2.2.1 The Aho-Corasick Algorithm (AC)
2.2.2 The Wu-Manber Algorithm (WM)
2.2.3 The Keyword Trie Algorithm (Ktrie)
2.3 Hardware String Matching Approaches
Chapter3. The Proposed Algorithm
3.1 Introduction
3.2 The preprocessing stage
3.3 The matching algorithm
3.4 A Simple Example
Chapter4. Implementation
4.1 Bloom Filter Implementation
4.1.1 False Positive
4.1.2 Hash Function
4.1.3 Architecture and Memory Planning
4.2 The SoC System
4.2.1 System Architecture
4.2.2 Memory Planning
Chapter5. Performance Evaluation
5.1 Memory Consumption
5.2 Matching Efficiency
Chapter6. Conclusion
Reference

Searching Filters
[1] Burton H. Bloom, “Space time tradeoffs in hash coding with allowable errors,” Communications of the ACM, 13(7):422-426, 1970
[2] Chang, F.; Wu-chang Feng; Kang Li, “Approximate caches for packet classification.” INFOCOM2004, Volume 4, Page(s):2196 - 2207 vol.4, 2004
[3] S. Dharmapurikar, P. Krishnamurthy, TS Sproull, and JW Lockwood. “Deep Packet Inspection using. Parallel Bloom Filters.” IEEE Micro, 24(1):52–61, 2004
[4] L. Fan, P. Cao, J. Almeida, and A. Z. Broder. ”Summary cache: A scalable wide-area web cache sharing protocol.” IEEE/ACM Transactions on Networking, 8(3):281-293, June 2000.
[5] Michael Mitzenmacher, “Compressed Bloom Filters,” IEEE/ACM Transaction on networking, Volume 10, Issue 5, Oct. 2002 Page(s):604 - 612
[6] Saar Cohen,Yossi Matias, “Spectral Bloom Filter,” Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pp. 241-252, 2003.
[7] J. C. R. Tseng and W. P. Yang, “New Search Filter and Analysis,” Proc. of National Computer Symposium, Taiwan, R.O.C., Dec. 1991.
[8] C. Y. Wang, W. P. Yang, J. C. R. Tzeng and M. Hsu, “Random Filter and its Analysis,” International Journal of Computer Mathematics, vol. 33, pp. 181-194, 1990.
[9] C.R. Tseng and W. P. Yang, “2D Random Filter and Analysis,” International Journal of Computer Mathematics, vol. 42, pp. 33-45, 1992.
[10] Chang CC, Leu JJ, “Two 2D Search Filter and Their Performance Analyses,” International Journal Computer Mathematics, Vol. 60, pp. 183-203, 1995.
[11] Chang, CC, Lee, TF, and Leu, JJ , “Partition Search Filter and Its Performance Analysis,” The Journal of Systems and Software, Vol. 47, pp.35-43, 1999
[12] “A non-Computation Intensive Pre-filter for String Pattern Matching in Fast Deep Packet Inspection”, accepted for publication in IEEE Globecom 2006
[13] Mishina, Y.and Kojima, K. “String matching on IDP: a string matching algorithm for vector processors and its implementation,” in IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1993. (ICCD '93.), 3-6 Oct. 1993 Page(s):394 – 401.
Multi-pattern Matching Algorithms
[14] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no. 10, Oct. 1977, pp. 762-772.
[15] A. V. Aho and M. J. Corasick. “Efficient string matching: An aid to bibliographic search.” Communications of the ACM, 18(6):333–340, 1975.
[16] Sun Wu and Udi Manber, “A fast algorithm for multi-pattern searching,” Tech. Rep. TR94-17, Department of Computer Science, University of Arizona, May 1994
[17] Sun Wu and Udi Manber, “Fast Text Searching Allowing Errors.”, Communications of the ACM, pp. 83-91, Vol. 35, No. 10, Oct. 1992, USA.
[18] Steffen Heinz, Justin Zobel, and Hugn E. Williams, “Burst tries: a fast, efficient data structure for string keys.” ACM Transactions on Information Systems (TOIS), pp. 192 - 223 Vol. 20 , Issue 2, 2002
[19] Baeza-Yates, R., & Gonnet, G.. “Fast text searching for regular expressions or automaton searching on tries.” Journal of the ACM, 43(6), 915-936, 1996
[20] B. Commentz-Walter. “A string matching algorithm fast on the average”. In Proceedings of ICALP’79, pages 118–132,July 1979
[21] C. J. Coit, S. Staniford, and J. McAlerney. “Towards faster pattern matching for intrusion detection, or exceeding the speed of Snort.” In Proceedings of the 2nd DARPA Information Survivability Conference and Exposition (DISCEX II),June 2002
[22] Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection. In proceedings of the IEEE INFOCOM conference, Page(s):2628 - 2639 vol.4, 2004
[23] Lin Tan, Brett Brotherton and Timothy Sherwood, “Bit-split string-matching engines for intrusion detection and prevention.” ACM Transactions on Architecture and Code Optimization (TACO), pp. 3 – 34, Vol. 3 , Issue 1, 2006

Pattern Matching in Hardware
[24] R.T. Liu, N.F. Huang, C.H. Chen, C.N. Kao, “A Fast String Matching Algorithm for Network Processor-based Intrusion Detection Systems”, ACM Transactions on Embedded Computer Systems, Vol. 3, No. 3, August 2004, pp. 614 – 633.
[25] Gokhale, M., et al, “Towards Gigabit Rate Network Intrusion Detection.” Proceedings of FPL 2002
[26] Sourdis, I., Pnevmatikatos, D. “Fast, Large-Scale String Match for a 10Gbps FPGA-Based Network Intrusion Detection System.” Proceedings of FPL '03, 2003
[27] Z. K. Baker and V. K. Prasanna. “Time and Area Efficient Pattern Matching on FPGAs.” ACM International Symposium on Field-Programmable Gate Arrays (FPGA '04), 2004
[28] R. Sidhu and VK Prasanna, “Fast Regular Expression Matching using FPGAs”, IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM01), April 2001
[29] D. Carver, R. Franklin, BL Hutchings, “Assisting Network Intrusion Detection with Reconfigurable Hardware”, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines (FCCM02), April 2002
[30] J. Moscola, J. Lockwood, and RP Loui. “Implementation of a Content-Scanning Module for an Internet Firewall.” IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), Apr. 2003
[31] Ioannis Sourdis and Dionisios Pnevmatikatos, “Pre-decoded CAMs for Efficient and High-Speed NIDS Pattern Matching”, IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'04), April 2004, Napa CA, USA. July 16, 2004
[32] Fang Yu , Randy H. Katz , T. V. Lakshman, “Gigabit Rate Packet Pattern-Matching Using TCAM”, 12th IEEE Proceedings of the Network Protocols (ICNP'04), p.174-183, October 05-08, 2004

Miscellaneous
[33] Robin Sommer, Vern Paxson, “Enhancing Byte-Level Network Intrusion Detection Signatures with Context.”, Proceedings 10th ACM Conference on Computer and Communications Security, 2003
[34] Sun Wu and Udi Manber. “AGREP - A Fast Approximate Pattern-matching Tool.” Proceedings of the Winter 1992 USENIX Conference San Francisco, USA, 20.-24. Jan. 1992, pp. 153-162, Berkeley, USA, 1991.
[35] agrep, http://www.tgries.de/agrep/
[36] U. Manber and S. Wu. “GLIMPSE: A tool to search through entire file systems.”, Winter 1994 USENIX Conference.
[37] WebGlimse, http://webglimpse.net/
[38] M. Roesch. “Snort - Lightweight Intrusion Detection for Networks.” In Proceedings of the USENIX LISA '99 Conference, November 1999
[39] (on-line) Snort official site, http://www.snort.org
[40] (on-line) Clam AntiVirus, http://www.clamav.net
[41] (on-line) SpamAssassin project, http://spamassassin.apache.org/
Implementation
[42] George Marsaglia and Arif Zaman, "Toward a Universal C Random Number Generator." Florida State University Report: FSU-SCRI-87-50, 1987
[43] F. James, "A review of pseudorandom number generators", Computer Physics Communications 60 (1990), 329-344.
[44] M. Ramakrishna, E. Fu, and E. Bahcekapili. “A performance study of hashing functions for hardware applications.” In Proc. of Int. Conf. on Computing and Information, pages 1621-1636, 1994.
[45] Fowler / Noll / Vo (FNV) Hash, http://www.isthe.com/chongo/tech/comp/fnv/
[46] LM hash (LAN Manager hash),
http://en.wikipedia.org/wiki/LM_hash
[47] “The Database File System: Implementing a File System with the Berkeley DB”, http://www-128.ibm.com/developerworks/cn/linux/l-embdb/?ca
= dwcn-newsletter-linux
[48] DJB hash, http://cr.yp.to/djb.html
[49] Altera AN 207: TriMatrix Memory Selection Using the Quartus II Software
[50] Memory Initialization File (.mif) Definition, http://www.altera.com/support/software/nativelink/quartus2/glossary/def_mif.html
[51] Convert memory initialization file (.mif) to a .hex file format
http://www.altera.com/support/kdb/solutions/1430.html
[52] Nios Development Board Reference Manual, Stratix II Edition
[53] Nios II Processor Reference Handbook
[54] Nios II Software Developer's Handbook
[55] Quartus II Handbook Volume 5: Altera Embedded Peripherals
[56] Nios II Processor Literature, http://www.altera.com/literature/lit-nio2.jsp
[57] Nios forum, http://www.niosforum.com
[58] Eclipse project, http://www.eclipse.org/