正規表示式比對在網路入侵偵測系統中扮演著不可或缺的角色，隨著網路流量快速地成長，正規表示式已經被廣泛運用在網路入侵偵測系統中，因為正規表示式的彈性與簡潔，近年來，繪圖處理器 (GPU) 經常被使用來加速正規表示式比對，經典的正規表示式比對方法有DFA，然而，DFA遭遇到狀態數爆炸的問題，它需要大量的記憶體空間。
在這篇論文中，我們提出一個基於GPU的方法叫作MB-DFA，為了加速正規表示式比對他可以一次處理多個字元，並且解決了狀態數爆炸的問題，此外，我們也提出了一個壓縮的方案，可以壓縮default transition，基於我們的實驗結果，我們所提出的MB-DFA可以達到有效地降低記憶體的使用量，而且最好的效能在GPU可以達到83 Gbps.

Regular expression matching plays an important role in Network Intrusion Detection System (NIDS). As the Internet traffic grows rapidly, regular expression have been widely used in NIDS due to its flexibility and conciseness. Recently, graphics processing unit (GPU) is often used to accelerate regular expression matching. The classical matching approach for regular expression matching uses deterministic finite automata (DFA). However, DFA suffers from the problem of state explosion because it needs a lot of memory space.
In this thesis, we propose a GPU-based approach called Multi-Byte DFA (MB-DFA) which can process multiple characters per cycle in order to accelerate regular expression matching and solve the problem of state explosion. In addition, we also propose a compression scheme based on default transition. Our experimental results show that the proposed MB-DFA can achieve significant reductions in memory usage and the best performance of throughput is 83 Gbps on GPU.

[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] 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.
[3] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no 10, pp.762-772, 1977.
[4] Sun Wu, Udi Manber, “A fast algorithm For Multi-Pattern Searching,” Technical Report TR 94-17, University of Arizona at Tuscon, 1994
[5] Ken Thompson, “Programming Techniques: Regular expression search algorithm.” Communications of the ACM Volume 11 Issue 6 (1968) pp. 419-422.
[6] V-M. Glushkov, “The abstract theory of automata.” Russian Mathematical Surveys 16-5 (1961) pp.1–53.
[7] NVIDIA Corporation, “Whitepaper NVIDIA’s Next Generation CUDA Compute Architecture: Kepler GK110/210,” 2012
[8] Martin, John, “Introduction to Languages and the Theory of Computation.” McGraw Hill (2010) pp.108.
[9] N. Yamagaki, R. Sidhu, S. Kamiya, “High-Speed Regular Expression Matching Engine Using Multi-Character NFA,” in Proc. Intl. Conf. FPL, Aug. 2008, pp. 697–701.
[10] C.-H. Lin, C.-H. Liu, L.-S. Chien, S.C. Chang, “Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs,” IEEE Transactions on Computers, vol. PP, p.1, 2012.
[11] S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner, “Algorithms to accelerate multiple regular expressions matching for deep packet inspection,” ACM SIGCOMM Computer Communication Review, vol. 36, no. 4, pp. 339–350, 2006.
[12] D. Ficara, S. Giordano, G. Procissi, F. Vitucci, G. Antichi, and A. Di Pietro, “An improved dfa for fast regular expression matching,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 5, pp. 29–40, 2008.
[13] D. Ficara, A. Di Pietro, S. Giordano, G. Procissi, F. Vitucci, and G. Antichi, “Differential encoding of dfas for fast regular expression matching,” IEEE/ACM Transactions on Networking (TON), vol. 19, no. 3, pp. 683–694, 2011.
[14] M. Becchi and P. Crowley, “A-dfa: A time- and space-efficient dfa compression algorithm for fast regular expression evaluation,” ACM Trans. Archit. Code Optim., vol. 10, no. 1, pp. 4:1–4:26, Apr. 2013.
[15] CUDA. [Online]. Available : http://www.nvidia.com/object/cuda_home_new.html
[16] OpenCL. [Online]. Available: https://developer.nvidia.com/opencl
[17] Kepler. [Online]. Available : http://www.nvidia.com/object/nvidia-kepler.html
[18] Fermi. [Online]. Available : http://www.nvidia.com/object/fermi-architecture.html
[19] Snort. [Online]. Available : http://www.snort.org
[20] Bro. [Online]. Available : http://www.bro.org
[21] C.-H. Lin, C.-H. Liu, and S.-C. Chang, "Accelerating regular expression matching using hierarchical parallel machines on GPU," in Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE. IEEE, 2011, pp. 1-5