近年來，隨著網路規模快速成長，惡意封包與網路攻擊的問題日趨嚴重。因此，我們需要憑藉有效的網路入侵偵測系統(NIDS)來保護電腦免於來自網路上的惡意攻擊。網路入侵偵測系統需要由事先定義的規則來檢查網路封包內容，而隨著這些惡意攻擊越來越多樣化，著名的網路入侵偵測系統如:Snort及ClamAV所提供的規則數量也越來越多。而隨著網路發展，軟體方法已經不足以應付現今的網路速度，因此我們使用這些規則並且將系統建立在較有速度優勢的硬體FPGA上以達到較佳的效能。然而當我們所使用的規則越多，我們所使用的硬體資源也會越多。
早期由Prasanna et. Al所提出的基於NFA設計的硬體架構，能夠有效將正規表示式實作在FPGA上。然而這樣的架構在使用大量規則的情況下，其輸入方式會導致High fanout電路產生，以至於效能不佳、增加耗能。在這篇論文中，我們試著改善輸入的方式，使用傳統單一字元字串比對處理器陣列的架構，並且透過Block RAM及暫存器集合來增加處理器陣列架構的效能且減少硬體資源的使用。而這樣的架構同樣能夠套用正規表示式，並且透過BlockRAM以及Global Counter來改善正規表示式中會造成電路更加複雜的Kleene star以及Constrained Repetition等問題。
我們將提出的兩階段式管線化架構實作在Xilinx Virtex-7 XC7V2000T上。當我們將架構套用在字串比對上，和原來管線化輸入方式的處理器陣列架構(design 4.a)相比，我們只需要使用3%至6%的block RAM便能夠減少將近80%的成本，並且和暴力法架構相比仍然保有較佳的時脈週期。當我們實作在正規表示式比對上，我們能夠藉由prefix duplication以及Global Counter，在一個規則表內消除最多90%的constrained repetition，並且和原始架構相比下最多使用2.3%的block RAM便能夠減少近80%的硬體資源使用率，同時和NFA-based架構相比也能夠有更好的效能。

In recent years, as the scale of Internet grows rapidly, considerable malicious packets and attacks are increasingly serious problem nowadays. As a result, we need to rely on a effective Network Intrusion Detection System (NIDS) to prevent our computers from malicious attack. NIDS use predefined rules to suspect the payload of internet packets. While the malicious attack becomes various and numerous, Snort and ClamAV, the famous NIDS, have a tendency to release more rules. Trandtional NIDS using software-based method is not enough to meet the speed of current Internet, so we implement these rules on hardware FPGA to achieve higher throughput. However, the more rules we use to bulid in the system, the more hardware resource we have to use.
A NFA-based architecture that Prasanna et. al. proposed [11] can implement regular expression on FPGA. Nevertheless, with massive rules, the way of input broadcast in NFA-based architecture may cause high fan-out circuit which result in low throughput and high power consumption. In this thesis, we propose an architecture based on processor array design for single-character pattern matching to prevent a high fan-out circuit, and use block RAM and Register Set to reduce hardware resource. Also, regular expression can implement on our architecture, and we can use Block RAM and Global Counter to improve some problem caused by Kleene star, constraint repetitions in original architecture.
We implement our improved architecture on device Xilinx Virtex-7 XC7V2000T. For string matching with two phase architecture, we can reduce nearly 80% area cost compared to original input pipeline architecture (design 4.a) with 3% to 6% block RAMs, and still have a better clock period compared to brute-force architecture. For regular expression matching, we can eliminate almost 90% constrained repetitions with prefix duplication and Global Counter in a rule set, and thus reduce nearly 80% hardware resource utilization with at most 2.3% block RAMs compared to original input pipeline architecture, and also have a shorter clock period in comparison with NFA-based architectures.

[1] Snort. [Online]. Available: https://www.snort.org
[2] ClamAV [Online]. Available: https://www.clamav.net
[3] E. Knuth, J. H. M. Jr., and V. R. Pratt, “Fast pattern matching in strings,” SIAM Journal on Computing, vol. 6, on 2, pp. 323-350, June 1977.
[4] Alfred V. Aho and Margaret J. Corasick, “Efficient string Matching: An Aid to Bibliographic Search,” Commun. ACM, vol.18, no 6, pp. 333-340, 1975.
[5] Sun Wu, Udi Manber, “A fast algorithm for Multi-Pattern Searching,” Technical Report TR 94-17, University of Arizona at Tuscon, May 1994.
[6] V. M. Glushkov, “The Abstract Theory of Automata,” Russian Mathematical Surveys, Vol. 16, No. 5, 1961, pp. 1-53.
[7] M. O. Rabin, D. Scott. “Finite automata and their decision problems,” IBM Journal of Research and Development, 3(2): 114-125, 1959.
[8] Fayez Gebali, Senior Member and A.N.M. Ehtesham Rafiq, “Processor Array Architecture for Deep Packet Classfication”, In IEEE Transactions on Parallel and Distributed Systems, Vol. 17, No. 3, March 2006.
[9] F. El-Guibaly and A. Tawfik, “Mapping 3D IIR Digital Filter onto Systolic Arrays,” Multidimensional Systems and Signal Processing, vol. 7, no. 1, pp. 7-26, Jan 1996.
[10] Yeim-Kuan Chang and Kai-Tso Chang, “Processor Array Architecture for Intrusion Detection System,” Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, July 2009.
[11] 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
[12] Bispo, J.C., Sourdis, I., Cardoso, J.M., Vassiliadis, S. “Regular expression matching for reconfigurable packet inspection,” IEEE Field Programmable Technology (FPT), pp. 119–126 (2006)
[13] Sourdis, I., Vassiliadis, S., Bispo, J.C., Cardoso, J.M. “Regular expression matching in reconfigurable hardware,” J. Signal Processing Systems 51(1), 99–121 (2008)
[14] SangKyun Yun and KyuHee Lee, “Regular Expression Pattern Matching Supporting
Constrained Repetitions,” Reconfigurable Computing: Architectures, Tools and Applications, ARC 2009, LNCS 5453, pp. 300-305, 2009
[15] Derek Pao, Nga Lam Or, and Ray C. C. Cheung, “A memory-based NFA regular expression match engine for signature-based intrusion detection” Computer Communications, Vol 36, Issue. 10-11, pp. 1255-1267, June 2013.
[16] Lianhua Ji and V. P. Heuring, “Impact of Gate fan-in and fan-out Limits on Optoelectronic digital circuits,” National Center for Biotechnology Information (NCBI), Appl Opt., 36(17):3927-40, June 10 1997
[17] M. Becchi and P. Crowley, “A hybrid finite automaton for practical deep packet inspection,” ACM Conf. on Emerging Network Experiment and Technology (CoNext), pp. 1-12, 2007.
[18] R. Smith, C. Estan, and S. Jha, “XFA: Faster Signature Matching with Extended Automata,” in IEEE Symposium on Security and Privacy, 2008, pp. 187-201
[19] Xiaodong Yu, Bill Lin, Michela Becchi, “Revisiting State Blow-Up: Automatically Building Augmented-FA While Preserving Functional Equivalence,” IEEE Journal on Selected Areas in Communications 32(10): 1822-1833, 2014
[20] C. H. Lin, C. T. Huang, C. P. Jiang and S. C. Chang “Optimization of Pattern Matching Circuits for Regular Expression on FPGA” In IEEE Transactions on Very Scale Integration (VLSI) System, Vol. 15, No. 12, December 2007.
[21] Zachary K. Baker, Hong-Jip Jung, and Viktor K. Prasanna, “Regular expression software deceleration for intrusion detection systems” in Proc. 16th Int’l Conference on Field Programmable Logic and Applications (FPL’06), Madrid, 2006, pp. 418-125.
[22] C. R. Clark and D. E. Schimmel. “Scalable Pattern Matching for High Speed Networks” In IEEE Symposium in Field-Programmable Custom Computing Machines,(FCCM), Napa, CA, Apr. 2004.
[23] Y.-H.E. Yang and V.K. Prasanna, ‘‘High-Performance and Compact Architecture for Regular Expression Matching on FPGA,’’ IEEE Trans. Comput., vol. 61, no. 7, pp. 1013-1025, July 2012
[24] 7 Series FPGAs Overview. [Online]. Available: http://www.xilinx.com/support/