近年來，隨著網路發展快速，大量的惡意封包在網際網路之間傳播。惡意封包包含有病毒(virus)、惡意郵件(malware)…等。網路入侵偵測系統則是一套被設計來監測網路上是否含有這些惡意攻擊。在此系統中，我們常使用字串比對技術去保護我們的系統，所以字串比對技術是不可或缺的。藉由事先定義的病毒碼，網路入侵偵測系統能找出封包內容中是否為包含已定義的病毒碼。有限狀態自動機是一種常被使用在網路入侵偵測系統的比對技術，例如：NFA及DFA。由於網路的迅速膨脹，使得單一執行緒演算法已經不能負荷我們的高需求，所以我們需要藉由硬體協助來加速字串比對的效能。 GPU繪圖處理器常被利用來執行平行運算，有效地加速了字串比對的速度。
在這篇論文中，我們提出以NFA比對的方式為基礎並且有效利用GPU上的有限的記憶體空間存放更多更複雜的正規表示式。我們基於相似於NFA轉DFA的子集構造法轉換原先的NFA變成我們提出的CNFA。相較於原先的NFA與DFA，新提出的CNFA強加了一個限制。這個限制是每個狀態自動機只能擁有最多兩條相同字元的路徑，分別是對self-loop的路徑與non-self-loop的路徑兩種去做轉換。根據我們的實驗結果，新提出的CNFA在GPU上最佳表現可達大約100 Gbps。還有，CNFA只花費相對於iNFAnt使用量的18%。甚至對於iNFAnt無法處理的複雜規則集，CNFA可以勝任。

With the rapid development of networks, a large number of malicious packets, such as virus and malware, are spreading in recent years. Network intrusion detection system (NIDS) is mainly designed for monitoring whether there are some malicious packets over the Internet. The technique of pattern matching plays an important role because we often use it to protect our systems. With pre-defined virus signatures called patterns, NIDS can find out whether these pre-defined patterns exist in the payload of packets. Finite state automata (FSA), such as NFA and DFA, are one of pattern matching techniques in NIDS. Because processing a large amount of network packets only on a single thread cannot satisfy our high-speed demand, we need hardware to accelerate the performance of pattern matching. GPU can be used to effectively accelerate the performance of pattern matching because abundant parallel hardware threads are supported.
In this thesis, we propose a new NFA-based method to store more complex regular expressions in limited memory of GPU effectively. The proposed constrained NFA (CNFA) is constructed from the original NFA based on the method used in the subset construction algorithm that converts NFA to DFA. Compared to original NFA and DFA, the proposed CNFA imposes a constraint that each state can only have at most two transitions for each character, namely self-loop and non-self-loop transitions. Based on our experimental results, the proposed CNFA can achieve the performance of about 100 Gbps at the best case on GPU. Also, the proposed CNFA only needs 18% of memory usage, used in iNFAnt. In addition, the proposed CNFA can be used for more complex rule sets that is not possible to be implemented in iNFAnt.

[1] E. Knuth, J. H. M. Jr., and V. R. Pratt, “Fast pattern matching in strings,” SIAM Journal on Computing, vol. 6, no. 2, pp.323–350, 1977.
[2] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no 10, pp.762-772, 1977.
[3] V. Aho and M. J. Corasick, “Efficient string matching: An aid to bibliography search,” Communications of the ACM, vol. 18, no.6, pp.333-340, 1975.
[4] Z. K. Baker and V. K. Prasanna, “Time and Area Efficient Pattern Matching on FPGAs,” Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, pp.223-232, 2004.
[5] X. Zha and S. Sahni, “GPU-to-GPU and Host-to-Host Multipattern String Matching On A GPU,” IEEE Transactions on Computers, vol.62, pp.1156-1169, 2013.
[6] C.-H. Lin, C.-H. Liu, L.-S. Chien and S.C. Chang, “Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs,” IEEE Transactions on Computers, vol.PP, p.1, 2012.
[7] R. Nigel Horspool, “Practical Fast Searching in Strings.” Software-Practice & Experience 10-6 (1980) pp.501-506.
[8] Andrew Hume & Daniel Sunday, “Fast String Searching.” Software-Practice & Experience 21-11 (1991) pp.1221-1248.
[9] Ken Thompson, “Programming Techniques: Regular expression search algorithm.” Communications of the ACM Volume 11 Issue 6 (1968) pp. 419-422.
[10] V-M. Glushkov, “The abstract theory of automata.” Russian Mathematical Surveys 16-5 (1961) pp.1–53.
[11] Martin, John, “Introduction to Languages and the Theory of Computation.” McGraw Hill (2010) pp.108.
[12] CUDA. [Online]. Available : http://www.nvidia.com/object/cuda_home_new.html
[13] Niccolo’Cascarano et al., “iNFAnt: NFA Pattern Matching on GPGPU Devices,” ACM SIGCOMM Computer Communication Review, vol. 40 Num. 5, pp. 21-26, 2010.
[14] Kepler. [Online]. Available : http://www.nvidia.com/object/nvidia-kepler.html
[15] NVIDIA Corporation, “Whitepaper NVIDIA’s Next Generation CUDA Compute Architecture: Fermi,” 2009
[16] M. Becchi, C. Wiseman, and P. Crowley, “Evaluating Regular Expression Matching Engines on Network and General Purpose Processors,” the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, 2009.
[17] L7-filter. [Online]. Available : http://l7-filter.sourceforge.net/
[18] Emerging Threats. [Online]. Available : http://emergingthreats.net/
[19] Suricata. [Online]. Available : http://suricata-ids.org/
[20] VRT. [Online]. Available : https://www.snort.org/vrt/
[21] Oinkmaster. [Online]. Available : http://oinkmaster.sourceforge.net/
[22] Suricata Rule Set. [Online]. Available:
https://rules.emergingthreats.net/open/suricata/emerging-all.rules
[23] PCRE. [Online]. Available: http://www.pcre.org/
[24] Defcon. [Online]. Available : http://www.defcon.org/
[25] ClamAV. [Online]. Available : http://www.clamav.net/