Regular expression attack technique on ReDoS vulnerability
DOI:
https://doi.org/10.54654/isj.v1i21.1030Keywords:
regex, fuzzing, automaton, ambiguity, ReDoSTóm tắt
Abstract— Regular expressions, or regexes, have become an integral part of modern software development, seamlessly woven into the fabric of countless applications. From validating user input in web forms to parsing complex log files for data analysis, regexes are employed across a vast spectrum of tasks. Their ability to precisely define and match patterns within text makes them invaluable tools for tasks ranging from simple data extraction to sophisticated security measures. However, this widespread reliance on regexes also introduces a significant security vulnerability: ReDoS (Regular Expression Denial of Service) attacks. These attacks exploit the inherent complexity of regex matching by crafting malicious input that triggers an exponentially long processing time, effectively bringing the application to a standstill. The potential for ReDoS attacks highlights the crucial need for developers to exercise extreme caution when designing and implementing regex-based components within their applications. This paper explores the inherent ambiguity of regular expressions, fuzzing with static analysis and proposes a novel fuzzing technique to generate effective attack patterns. By analyzing the potential interpretations of ambiguous regex constructs, our method identifies and exploits weaknesses in software implementations that rely on regex for input validation. The proposed fuzzing algorithm generates test cases that systematically explore the ambiguity space, maximizing the likelihood of uncovering vulnerabilities related to unexpected regex behavior. This approach aims to enhance software security by proactively detecting and mitigating potential attack vectors stemming from the misinterpretation of regular expression patterns.
Downloads
References
OWASP (2010-02-10). "Regex Denial of Service". Retrieved 2010-04-16.
Son, D. T., Tram, N. T. K., & Thu, T. T. . (2022). Machine learning approach detects DDoS attacks. Journal of Science and Technology on Information Security, 1(15), 102-108. https://doi.org/10.54654/isj.v1i15.850.
Martin Berglund, Frank Drewes, Brink van der Merwe. 2014. Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching. Electronic Proceedings in Theoretical Computer Science 151(Proc. AFL 2014).
Efe Barla, Xin Du, James C. Davis. 2023. Exploiting Input Sanitization for Regex Denial of Service. Proceedings of the ACM/IEEE 44th International Conference on Software Engineering (ICSE) 2022. https://arxiv.org/abs/2303.01996.
"Backtracking in .NET regular expressions - .NET". learn.microsoft.com. 11 August 2023. When using System.Text.RegularExpressions to process untrusted input, pass a timeout. A malicious user can provide input to RegularExpressions, causing a Denial-of-Service attack. ASP.NET Core framework APIs that use RegularExpressions pass a timeout.
Li, Yeting, et al. "ReDoSHunter: A Combined Static and Dynamic Approach for Regular Expression DoS Detection." 30th USENIX Security Symposium (USENIX Security 21). 2021.
Davis, James C., Francisco Servant, and Dongyoon Lee. 2021. "Using selective memoization to defeat regular expression denial of service (ReDoS)." 2021 IEEE Symposium on Security and Privacy (SP), Los Alamitos, CA, USA.
Paul Wilton. Beginning JavaScript. John Wiley & Sons, 2004.
Pieter Hooimeijer, Benjamin Livshits, David Molnar, Prateek Saxena, and Margus Veanes. Fast and precise sanitizer analysis with BEK. In USENIX Security Symposium, pages 1–16, August 2011.
https://en.wikipedia.org/wiki/Thompson's_construction.
Sugiyama, Satoshi, and Yasuhiko Minamide. "Checking time linearity of regular expression matching based on backtracking." Information and Media Technologies 9.3 (2014): 222-232.
Shen, Yuju, et al. "ReScue: crafting regular expression DoS attacks." 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2018.
Chida, Nariyoshi, and Tachio Terauchi. 2020."Automatic repair of vulnerable regular expressions." arXiv preprint arXiv:2010.12450.
Theofilos Petsios, Jason Zhao, Angelos D Keromytis, and Suman Jana. 2017. Slowfuzz: Automated domain-independent detection of algorithmic complexity vulnerabilities. In Proceedings of the International Conference on Computer and Communications Security (CCS ’17). 2155–2168. https://doi.org/10.1145/3133956. 3134073.
James Kirrage, Asiri Rathnayake, and Hayo Thielecke. 2013. Static analysis for regular expression denial-of-service attacks. In Proceedings of the 7th International Conference on Network and System Security (NSS ’13). 135–148. https://doi.org/ 10.1007/978-3-642-38631-2_11.
Valentin Wüstholz, Oswaldo Olivo, Marijn JH Heule, and Isil Dillig. 2017. Static detection of DoS vulnerabilities in programs that use regular expressions. In Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS ’17). 3–20. https://doi.org/10.1007/ 978-3-662-54580-5_1.
Nicolaas Weideman, Brink van der Merwe, Martin Berglund, and Bruce Watson. 2016. Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA. In Proceedings of the International Conference on Implementation and Application of Automata (CIAA ’16). 322–334. https: //doi.org/10.1007/978-3-319-40946-7_27.
Weber, Andreas, and Helmut Seidl. 1991. "On the degree of ambiguity of finite automata." Theoretical Computer Science 88.2 (1991): 325-349.
Asiri Rathnayake and Hayo Thielecke. 2014. Static analysis for regular expression exponential runtime via substructural logics. (2014). arXiv:arXiv:1405.7058.
Carl Chapman and Kathryn T Stolee. 2016. Exploring regular expression usage and context in Python. In Proceedings of the 25th International Symposium on Software Testing and Analysis (ISSTA ’16). 282–293. https://doi.org/10.1145/ 2931037.2931073.
Downloads
Published
How to Cite
Issue
Section
License
Proposed Policy for Journals That Offer Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Proposed Policy for Journals That Offer Delayed Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication, with the work [SPECIFY PERIOD OF TIME] after publication simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
