隨著網際網路的快速成長，隨之而來的大量惡意攻擊和電腦病毒嚴重影響到網路的安全。網路入侵偵測系統(NIDS)藉由事先定義好的規則來找出這些惡意攻擊。在NIDS中，同時比對多個字串是計算量最多的也最昂貴的一項工作。而傳統以軟體為基礎的NIDS解決方法通常並無法滿足日益成長的網路攻擊所需的高速需求。
　　在此篇論文中，我們提出兩個不同架構的字串比對方法來達到在一個時脈週期處理多個字元。我們提出的第一個方法擁有模組化的設計並且可以節省不必要的計算。而第二個方法，我們提出兩個改進使用TCAM當作事先過濾的技術來提升效能。在第一個改進方法中 我們比對字串的最後w字元而非字串的前w字元來達到事先過濾。為了能同時處理多個字元最後，在第二個改進方法中我們採用所有群組的比對結果，而非只採用第一個群組的結果。最後，我們使用Snort規則中的字串和DEFCON的封包來當作我們模擬效能的評估方式。我們的模擬結果顯示第一個方法能較傳統的暴力法減少約83%的運算，而第二個方法能得到比FTSE更好的效能。

With the growth of the Internet, the explosion of attacks and viruses affects the network security significantly. Network Intrusion Detection System (NIDS) is a system developed for identifying attacks by using a set of rules. Searching for multiple patterns is a computationally expensive task in NIDS. Traditional software-based NIDS solutions usually can not achieve a high-speed required for ever growing Internet attacks.
In this thesis, we propose two pattern matching approaches that can process multiple characters per clock cycle. The first approach is modular and computationally efficient. The second approach provides two techniques to improve the performance of FTSE proposed in [16] that utilizes TCAM as a pre-filter to achieve gigabit performance. The first technique matches the w-byte suffixes of the patterns instead of matching w-byte prefixes. The second technique finds the matching results from all groups rather than the first group in order to process multiple characters at a time. We finally perform the simulations by using Snort pattern sets and DEFCON packet traces. Our performance results show that the first approach can reduce 83% unnecessary computations in the exhaustive search proposed in [5] and the second approach has a better throughput than the original FTSE scheme.

[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] 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.
[3] Mansoor Alicherry, M.Muthuprasanna, Vijay Kumar, “High Speed Pattern Matching for Network IDS/IPS,” in Proceeding of 14th IEEE International Conference on Network Protocols (ICNP’06)
[4] 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.
[5] 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.
[6] Young H. Cho, W.H. Mangione-Smith, “Fast reconfiguring deep packet filter for 1+ Gigabit network,” In IEEE Symposium on Field-Programmable Custom Computing Machines, (FCCM), Napa, CA, Apr. 2005.
[7] 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.
[8] DEFCON. http://www.shmoo.com/, http://cctf.shmoo.com/data/cctf-defcon8/
[9] 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.
[10] M. Fisk and G. Varghese. “An analysis of fast string matching applied to content-based forwarding and intrusion detection,” Technical Report CS2001-0670 (updated version), University of California - San Diego, 2002.
[11] Fayez Gebali, A. N. M. Ehtesham Rafiq, “Processor Array Architectures for Deep Packet Classification,” IEEE Trans. Parallel Distrib. Syst. 17(3): 241-252 (2006)
[12] R. M. Karp and M. O. Rabin, “Efficient randomized pattern-matching algorithms,” IBM J. Res. Dev., vol. 31, no. 2, pp. 249–260, 1987.
[13] 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.
[14] Po-Ching Lin, Zhi-Xiang Li, Ying-Dar Lin, Yuan-Cheng Lai, Profiling and Accelerating String Matching Algorithms in Three Network Content Security Applications , IEEE Communications Surveys and Tutorials, 2nd quarter, 2006.
[15] R.T. Liu, N.F. Huang, C.H. Chen, C.N. Kao, “A Fast String Matching Algorithm for Network Processor-Based Intrusion Detection System”, ACM Transactions on Embedded Computing Systems, Vol. 3, No. 3, Aug. 2004, pp.614-633.
[16] R.T. Liu, C.N. Kao, H.S. Wu, M.C. Shih and N.F. Huang, “FTSE: The FNP-Like TCAM Searching Engine,” in IEEE Symposium on Computers and Communications, pp 863-868, June 2005.
[17] R.T. Liu, N.F. Huang, C.H. Chen, C.N. Kao, “A Fast String Matching Algorithm for Network Processor-Based Intrusion Detection System,” ACM Transactions on Embedded Computing Systems, Vol. 3, No. 3, Aug. 2004, pp. 614-633.
[18] J. Moscola, J. Lockwood, RP. Loui, M. Pachos, “Implementation of a content-scanning module for an Internet firewall, ” In: Pocek KL, ed. Proc. of the 11th Annual IEEE Symp. on Field-Programmable Custom Computing Machines (FCCM), pp.31-38, 2003.
[19] R. Sidhu and V. K. Prasanna, “Fast Regular Expression Matching Using FPGAs,“ In Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’01), pages 227–238, Rohnert Park, CA, USA, May 2001.
[20] Snort-the de Facto Standard for Intrusion Detection/Prevention, [Online]. Available: www.snort.org
[21] 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.
[22] Jung-Sik Sung*, Seok-Min Kang†, Youngseok Lee†, Taeck-Geun Kwon†, and Bong-Tae Kim* “A Multi-gigabit Rate Deep Packet Inspection Algorithm using TCAM,” IEEE Globecom 2005
[23] L. Tan and T. Sherwood, “A high throughput string matching architecture for intrusion detection and prevention,” in ISCA, 2005.
[24] Lin Tan, Timothy Sherwood, “A High Throughput String Matching Architecture for Intrusion Detection and Prevention," isca, pp. 112-122, 32nd Annual International Symposium on Computer Architecture (ISCA'05), 2005
[25] S. Wu and U. Manber, “A fast algorithm for multi-pattern searching,” Tech. Report, TR94-17, U of Arizona, May 1994.
[26] 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.