Perl Compatible Regular Expressions PCRE 是一個開源的正規表達式引擎，PCRE經常用於網路入侵偵測系統( 例如. Snort, Suricate)中來檢測封包Payload中的可疑字串，但過去正規表達式的研究都沒提及複雜的PCRE語法及PCRE的攻擊問題。PCRE使用的資料結構與比對演算法讓它可能成為網路入侵偵測系統的漏洞. 攻擊者透過在封包中加入精心設計過的Payload來達成RE-DOS (Regular expression-Denial of Service)攻擊, RE-DOS攻擊消耗網路入侵偵測系統的運算效能以此來降低檢測的throughput. Regular Expression Matching有兩種常見的實現方法, Non-Deterministic Finite Automata (NFA)和Deterministic Finite Automata (DFA). NFA跟DFA都不會受到RE-DOS攻擊，但兩種方法皆無法支援PCRE中的語法。
PCRE 的語法在NIDS的pattern set中經常用來描述不同特徵的攻擊，PCRE提供了使用者更有彈性的描述方法，所以PCRE的功能是有必要的，為了解決PCRE的RE-DOS攻擊，此篇論文提出名為labeled NFA的有限狀態機方法，labeled NFA基於Glushkov NFA且支援PCRE語法，我們根據PCRE不同的語法標記NFA state的標籤來建構出labeled NFA，我們定義了labeled NFA上的標籤以及標籤對應的比對方法來支援PCRE語法，從而避免網路入侵偵測系統中的RE-DOS攻擊。

Perl Compatible Regular Expressions (PCRE) [1] is an open-source regular expression engine, it is often used in network intrusion detection systems (NIDS) (eq. snort, suricate) to detect suspicious strings in the packet payload, but the past regular expression research has not mentioned the complicated PCRE syntax and PCRE attacks. the data structure and comparison algorithm used by PCRE make it possible to become a vulnerability in the network intrusion detection system. Attackers can achieve RE-DOS (Regular Expression-Denial of Service) attacks by adding a carefully designed payload to the packet. RE-DOS consumes the computational performance of the network intrusion detection system to reduce the detection throughput. Regular Expression Matching has two common implementation methods, Non-Deterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA). NFA and DFA will not be attacked by RE-DOS, but they cannot support PCRE syntax.
The grammar of PCRE is often used to describe attacks with different characteristics in the pattern set of NIDS. PCRE provides users with a more flexible description method, so the function of PCRE is necessary. In this thesis, we propose a finite state machine method called labeled NFA. labeled NFA is based on Glushkov NFA and supports PCRE syntax. We modify the construction algorithm of Glushkov NFA, which labeled NFA state to constructs labeled NFA according to the different meta-character of PCRE. We define flags and their match process to support PCRE syntax to avoid RE-DOS attacks in NIDS.

[1] PCRE —[Online]. Available: https://www.pcre.org/
[2] S. Wu and U. Manber, “A fast algorithm for multi-pattern searching,” Dept. Comput. Sci., Univ. Arizona, Tucson, AZ, USA, Tech. Rep. TR-94-17, 1994
[3] 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
[4] V. Aho and M. J. Corasick, “Efficient string matching: An aid to bibliographic search,” Commun. ACM, vol. 18, no. 6, pp. 330-340, 1975
[5] Snort—a open-source network intrusion detection system. [Online]. Available: http://www.snort.org/.
[6] Bro Intrusion Detection System. (2014). [Online]. Available: https://www.bro.org/
[7] Suricate. (2018) [Online]. Available: https://suricata.io/
[8] ClamAV 0.100.1 (2018) [Online]. Available: https://www.clamav.net/
[9] F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz, “Fast and memory-efficient regular expression matching for deep packet inspection,” in Proc. ACM/IEEE Symp. Archit. Netw. Commun. Syst., San Jose, CA, USA, pp. 93–102, 2006.
[10] M. Becchi and P. Crowley, “A hybrid finite automaton for practical deep packet inspection,” in Proc. ACM CoNEXT Conf., New York, NY, USA, 2007, Art. no. 1.
[11] V. M. Glushkov, “The Abstract Theory of Automata,” Russian Mathematical Surveys, Vol. 16, No. 5, pp. 1-53, 1961.
[12] M. O. Rabin, D. Scott. “ Finite automata and their decision problems,” IBM Journal of Research and Development, 3(2): 114-125, 1959.
[13] Xiang Wang, Yang Hong, Harry Chang, KyoungSoo Park, Geoff Langdale, Jiayu Hu and Heqing Zhu, “Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs” 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’19)
[14] SMITH, R., ESTAN, C., AND JHA, S. “Xfa: Faster signature matching with extended automata”. In Security and Privacy, 2008. SP 2008. IEEE Symposium on (2008), IEEE, pp. 187–201.
[15] Ken Thompson, “Programming Techniques: Regular expression search algorithm.” Communications of the ACM Volume 11 Issue 6 (1968) pp. 419-422
[16] Valentin W¨ustholz, Oswaldo Olivo, Marijn J.H. Heule, and Isil Dillig, “Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions” 2017 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 3-20.
[17] Yuju Shen, Yanyan Jiang, Chang Xu, Ping Yu, Xiaoxing Ma and Jian Lu, “ReScue: Crafting Regular Expression DoS Attacks” 2018 33rd ACM/IEEE International Conference on Automated Software Engineering, pp. 225-235
[18] Victor C. Valgenti, Min Sik Kim, Sung-Il Oh and Inbok Lee, “REduce: Removing Redundancy from Regular Expression Matching in Network Security” 2015 24th International Conference on Computer Communication and Networks (ICCCN)
[19] James C. Davis, “On the Impact and Defeat of Regular Expression Denial of Service” 2020
[20] Yehuda Afek, Anat Bremler-Barr, Yotam Harchol, David Hay, Yaron Koral, “Making DPI Engines Resilient to Algorithmic Complexity Attacks” 2016 IEEE/ACM Transactions on Networking
[21] Asiri Rathnayake and Hayo Thielecke, “Static Analysis for Regular Expression Exponential Runtime via Substructural Logics”, May 2014
[22] M. Becchi and S. Cadambi, “Memory-efficient regular expression search using state merging,” in Proc. 26th IEEE Int. Conf. Comput. Commun. (INFOCOM), Anchorage, AK, USA, pp. 1064–1072, 2007.
[23] S. Kong, R. Smith, and C. Estan, “Efficient signature matching with multiple alphabet compression tables,” in Proc. 4th Int. Conf. Security Privacy Commun. Netow., Istanbul, Turkey, 2008, Art. no. 1.
[24] M. Becchi and P. Crowley, “Efficient regular expression evaluation: Theory to practice,” in Proc. 4th ACM/IEEE Symp. Archit. Netw. Commun. Syst., San Jose, CA, USA, pp. 50–59, 2008.
[25] S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner, “Algorithms to accelerate multiple regular expressions matching for deep packet inspection,” ACM SIGCOMM Comput. Commun. Rev., vol. 36, no. 4, pp. 339–350, 2006.
[26] M. Becchi and P. Crowley, “An improved algorithm to accelerate regular expression evaluation,” in Proc. 3rd ACM/IEEE Symp. Architect. Netw. Commun. Syst., Orlando, FL, USA, pp. 145–154, 2007.
[27] Regular Expression Processor. Accessed on Apr. 5, 2012. [Online]. Available: http://regex.wustl.edu/index.php/Regular_Expression_Processor
[28] Online Random Tools — [Online]. Available: https://onlinerandomtools.com/generate-random-data-from-regexp
[29] Random String Generator based on Regular Expression — [Online]. Available: https://github.com/daidodo/regxstring
[30] Online tool to test Regular Expressions — [Online]. Available: https://regexr.com/