Understanding Regular Expression Denial of Service (ReDoS): Insights from LLM-Generated Regexes and Developer Forums
Authors: 
Mohammed Latif Siddiq, Jiahao Zhang, and Joanna Cecilia Da Silva SantosAuthors Info & Claims
April 2024
Pages 190 - 201
Abstract
Regular expression Denial of Service (ReDoS) represents an algorithmic complexity attack that exploits the processing of regular expressions (regexes) to produce a denial-of-service attack. This attack occurs when a regex's evaluation time scales polynomially or exponentially with input length, posing significant challenges for software developers. The advent of Large Language Models (LLMs) has revolutionized the generation of regexes from natural language prompts, but not without its risks. Prior works showed that LLMs can generate code with vulnerabilities and security smells. In this paper, we examined the correctness and security of regexes generated by LLMs as well as the characteristics of LLM-generated vulnerable regexes. Our study also examined ReDoS patterns in actual software projects, aligning them with corresponding regex equivalence classes and algorithmic complexity. Moreover, we analyzed developer discussions on GitHub and StackOverflow, constructing a taxonomy to investigate their experiences and perspectives on ReDoS. In this study, we found that GPT-3.5 was the best LLM to generate regexes that are both correct and secure. We also observed that LLM-generated regexes mainly have polynomial ReDoS vulnerability patterns, and it is consistent with vulnerable regexes found in open source projects. We also found that developers' main discussions around insecure regexes is related to mitigation strategies to remove vulnerable regexes.
References
[1]
2022. GitHub Copilot. Accessed Dec 7, 2022. https://github.com/features/copilot
[2]
2023. Chat completions. Accessed Mar 25, 2023. https://platform.openai.com/docs/guides/chat
[3]
2023. Common Vulnerabilities and Exposures (CVE). https://cve.mitre.org/index.html [Online; accessed 11. Sep. 2023].
[4]
2023. CWE - CWE-1333: Inefficient Regular Expression Complexity (4.13). https://cwe.mitre.org/data/definitions/1333.html [Online; accessed 6. Nov. 2023].
[5]
2023. GPT-3.5. https://platform.openai.com/docs/models/gpt-3-5 [Online; accessed 11. Sep. 2023].
[6]
2023. re2. https://github.com/google/re2 [Online; accessed 5. Nov. 2023].
[7]
2023. ReDoS checker | Devina.io. https://devina.io/redos-checker [Online; accessed 5. Nov. 2023].
[8]
2023. Regular Expression Library. https://regexlib.com [Online; accessed 11. Sep. 2023].
[9]
2023. Stack Exchange API. https://api.stackexchange.com [Online; accessed 11. Sep. 2023].
[10]
2024. Outage Postmortem - July 20, 2016. https://stackstatus.tumblr.com/post/147710624694/outage-postmortem-july-20-2016 [Online; accessed 23. Jan. 2024].
[11]
Ahmad Abdellatif, Mairieli Wessel, Igor Steinmacher, Marco A. Gerosa, and Emad Shihab. 2022. BotHunter: An Approach to Detect Software Bots in GitHub. In 2022 IEEE/ACM 19th International Conference on Mining Software Repositories (MSR). 6--17.
[12]
Owura Asare, Meiyappan Nagappan, and N Asokan. 2022. Is GitHub's copilot as bad as humans at introducing vulnerabilities in code? arXiv preprint arXiv:2204.04741 (2022).
[13]
Efe Barlas, Xin Du, and James C Davis. 2022. Exploiting input sanitization for regex denial of service. In Proceedings of the 44th International Conference on Software Engineering. 883--895.
[14]
Martin Berglund, Frank Drewes, and Brink Van Der Merwe. 2014. Analyzing catastrophic backtracking behavior in practical regular expression matching. arXiv preprint arXiv:1405.5599 (2014).
[15]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 1877--1901.
[16]
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 (Saarbrücken, Germany) (ISSTA 2016). Association for Computing Machinery, New York, NY, USA, 282--293.
[17]
Carl Chapman, Peipei Wang, and Kathryn T Stolee. 2017. Exploring regular expression comprehension. In 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 405--416.
[18]
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 (2021).
[19]
Nariyoshi Chida and Tachio Terauchi. 2022. Repairing dos vulnerability of real-world regexes. In 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2060--2077.
[20]
Scott Crosby. 2003. Denial of service through regular expressions. (2003).
[21]
Scott A. Crosby and Dan S. Wallach. 2003. Denial of Service via Algorithmic Complexity Attacks. In 12th USENIX Security Symposium (USENIX Security 03). USENIX Association, Washington, D.C. https://www.usenix.org/conference/12th-usenix-security-symposium/denial-service-algorithmic-complexity-attacks
[22]
James C Davis, Christy A Coghlan, Francisco Servant, and Dongyoon Lee. 2018. The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale. In Proceedings of the 2018 26th ACM joint meeting on european software engineering conference and symposium on the foundations of software engineering. 246--256.
[23]
James C. Davis, Eric R. Williamson, and Dongyoon Lee. 2018. A Sense of Time for JavaScript and Node.js: First-Class Timeouts as a Cure for Event Handler Poisoning. In 27th USENIX Security Symposium (USENIX Security 18). USENIX Association, Baltimore, MD, 343--359. https://www.usenix.org/conference/usenixsecurity18/presentation/davis
[24]
James Finnie-Ansley, Paul Denny, Brett A Becker, Andrew Luxton-Reilly, and James Prather. 2022. The robots are coming: Exploring the implications of openai codex on introductory programming. In Proceedings of the 24th Australasian Computing Education Conference. 10--19.
[25]
Sk Adnan Hassan, Zainab Aamir, Dongyoon Lee, James C Davis, and Francisco Servant. 2023. Improving Developers' Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies. In 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 1238--1255.
[26]
John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. 2001. Introduction to automata theory, languages, and computation. Acm Sigact News 32, 1 (2001), 60--65.
[27]
Kelvin Jiang, Ronak Pradeep, and Jimmy Lin. 2021. Exploring listwise evidence reasoning with t5 for fact verification. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers). 402--410.
[28]
Nate Kushman and Regina Barzilay. 2013. Using semantic unification to generate regular expressions from natural language. North American Chapter of the Association for Computational Linguistics (NAACL).
[29]
Eric Larson and Anna Kirk. 2016. Generating evil test strings for regular expressions. In 2016 IEEE International Conference on Software Testing, Verification and Validation (ICST). IEEE, 309--319.
[30]
Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee. 2023. Textbooks Are All You Need II: phi-1.5 technical report. arXiv:2309.05463 [cs.CL]
[31]
Yeting Li, Zixuan Chen, Jialun Cao, Zhiwu Xu, Qiancheng Peng, Haiming Chen, Liyuan Chen, and Shing-Chi Cheung. 2021. ReDoSHunter: A Combined Static and Dynamic Approach for Regular Expression DoS Detection. In 30th USENIX Security Symposium (USENIX Security 21). 3847--3864.
[32]
Yeting Li, Yecheng Sun, Zhiwu Xu, Jialun Cao, Yuekang Li, Rongchen Li, Haiming Chen, Shing-Chi Cheung, Yang Liu, and Yang Xiao. 2022. RegexScalpel: Regular Expression Denial of Service (ReDoS) Defense by Localize-and-Fix. In 31st USENIX Security Symposium (USENIX Security 22). 4183--4200.
[33]
Yeting Li, Zhiwu Xu, Jialun Cao, Haiming Chen, Tingjian Ge, Shing-Chi Cheung, and Haoren Zhao. 2020. Flashregex: Deducing anti-redos regexes from examples. In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering. 659--671.
[34]
Yinxi Liu, Mingxue Zhang, and Wei Meng. 2021. Revealer: Detecting and exploiting regular expression denial-of-service vulnerabilities. In 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 1468--1484.
[35]
Nicholas Locascio, Karthik Narasimhan, Eduardo DeLeon, Nate Kushman, and Regina Barzilay. 2016. Neural Generation of Regular Expressions from Natural Language with Minimal Domain Knowledge. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, Jian Su, Kevin Duh, and Xavier Carreras (Eds.). Association for Computational Linguistics, Austin, Texas, 1918--1923.
[36]
Louis G Michael, James Donohue, James C Davis, Dongyoon Lee, and Francisco Servant. 2019. Regexes are hard: Decision-making, difficulties, and risks in programming regular expressions. In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 415--426.
[37]
Arghavan Moradi Dakhel, Vahid Majdinasab, Amin Nikanjam, Foutse Khomh, Michel C. Desmarais, and Zhen Ming (Jack) Jiang. 2023. GitHub Copilot AI Pair Programmer: Asset or Liability? J. Syst. Softw. 203, C (sep 2023), 23 pages.
[38]
Nadim Nachar et al. 2008. The Mann-Whitney U: A test for assessing whether two independent samples come from the same distribution. Tutorials in quantitative Methods for Psychology 4, 1 (2008), 13--20.
[39]
Nhan Nguyen and Sarah Nadi. 2022. An Empirical Evaluation of GitHub Copilot's Code Suggestions. In Proceedings of the 19th International Conference on Mining Software Repositories (Pittsburgh, Pennsylvania) (MSR '22). Association for Computing Machinery, New York, NY, USA, 1--5.
[40]
Jun-U Park, Sang-Ki Ko, Marco Cognetta, and Yo-Sub Han. 2019. Softregex: Generating regex from natural language descriptions using softened regex equivalence. In Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP). 6425--6431.
[41]
Rishov Paul, Md. Mohib Hossain, Mohammed Latif Siddiq, Masum Hasan, Anindya Iqbal, and Joanna C. S. Santos. 2023. Enhancing Automated Program Repair through Fine-tuning and Prompt Engineering. arXiv:2304.07840 [cs.LG]
[42]
Hammond Pearce, Baleegh Ahmad, Benjamin Tan, Brendan Dolan-Gavitt, and Ramesh Karri. 2022. Asleep at the Keyboard? Assessing the Security of GitHub Copilot's Code Contributions. In 2022 IEEE Symposium on Security and Privacy (SP). 754--768.
[43]
Sida Peng, Eirini Kalliamvakou, Peter Cihon, and Mert Demirer. 2023. The impact of AI on developer productivity: Evidence from GitHub copilot. arXiv preprint arXiv:2302.06590 (2023).
[44]
Neil Perry, Megha Srivastava, Deepak Kumar, and Dan Boneh. 2022. Do Users Write More Insecure Code with AI Assistants? arXiv preprint arXiv:2211.03622 (2022).
[45]
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer. Journal of Machine Learning Research 21, 140 (2020), 1--67. http://jmlr.org/papers/v21/20-074.html
[46]
Denise Rey and Markus Neuhäuser. 2011. Wilcoxon-Signed-Rank Test. In International Encyclopedia of Statistical Science. https://api.semanticscholar.org/CorpusID:30088448
[47]
June Sallou, Thomas Durieux, and Annibale Panichella. 2024. Breaking the Silence: the Threats of Using LLMs in Software Engineering. In ACM/IEEE 46th International Conference on Software Engineering-New Ideas and Emerging Results. ACM/IEEE.
[48]
Gustavo Sandoval, Hammond Pearce, Teo Nys, Ramesh Karri, Brendan Dolan-Gavitt, and Siddharth Garg. 2022. Security Implications of Large Language Model Code Assistants: A User Study. arXiv preprint arXiv:2208.09727 (2022).
[49]
Inbal Shani. 2023. Survey reveals AI's impact on the developer experience | The GitHub Blog. GitHub Blog (June 2023). https://github.blog/2023-06-13-survey-reveals-ais-impact-on-the-developer-experience/#methodology
[50]
Yuju Shen, Yanyan Jiang, Chang Xu, Ping Yu, Xiaoxing Ma, and Jian Lu. 2018. ReScue: crafting regular expression DoS attacks. In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering. ACM, Montpellier France, 225--235.
[51]
Mohammed Latif Siddiq, Beatrice Casey, and Joanna Santos. 2023. A Lightweight Framework for High-Quality Code Generation. arXiv preprint arXiv:2307.08220 (2023).
[52]
Mohammed Latif Siddiq, Shafayat H Majumder, Maisha R Mim, Sourov Jajodia, and Joanna CS Santos. 2022. An Empirical Study of Code Smells in Transformer-based Code Generation Techniques. In 2022 IEEE 22nd International Working Conference on Source Code Analysis and Manipulation (SCAM). IEEE, 71--82.
[53]
Mohammed Latif Siddiq, Joanna Santos, Ridwanul Hasan Tanvir, Noshin Ulfat, Fahmid Al Rifat, and Vinicius Carvalho Lopes. 2023. Exploring the Effectiveness of Large Language Models in Generating Unit Tests. arXiv preprint arXiv:2305.00418 (2023).
[54]
Mohammed Latif Siddiq and Joanna C. S. Santos. 2023. Generate and Pray: Using SALLMS to Evaluate the Security of LLM Generated Code. arXiv:2311.00889 [cs.SE]
[55]
Dominik Sobania, Martin Briesch, and Franz Rothlauf. 2022. Choose Your Programming Copilot: A Comparison of the Program Synthesis Performance of Github Copilot and Genetic Programming. In Proceedings of the Genetic and Evolutionary Computation Conference (Boston, Massachusetts) (GECCO '22). Association for Computing Machinery, New York, NY, USA, 1019--1027.
[56]
Eric Spishak, Werner Dietl, and Michael D. Ernst. 2012. A Type System for Regular Expressions. In Proceedings of the 14th Workshop on Formal Techniques for Java-like Programs (Beijing, China) (FTfJP '12). Association for Computing Machinery, New York, NY, USA, 20--26.
[57]
Cristian-Alexandru Staicu and Michael Pradel. 2018. Freezing the Web: A Study of {ReDoS} Vulnerabilities in {JavaScript-based} Web Servers. In 27th USENIX Security Symposium (USENIX Security 18). 361--376.
[58]
Lenka Turoňová, Lukáš Holík, Ivan Homoliak, Ondřej Lengál, Margus Veanes, and Tomáš Vojnar. 2022. Counting in Regexes Considered Harmful: Exposing {ReDoS} Vulnerability of Nonbacktracking Matchers. In 31st USENIX Security Symposium (USENIX Security 22). 4165--4182.
[59]
Sri Lakshmi Vadlamani and Olga Baysal. 2020. Studying Software Developer Expertise and Contributions in Stack Overflow and GitHub. In 2020 IEEE International Conference on Software Maintenance and Evolution (ICSME). 312--323.
[60]
Priyan Vaithilingam, Tianyi Zhang, and Elena L Glassman. 2022. Expectation vs. experience: Evaluating the usability of code generation tools powered by large language models. In Chi conference on human factors in computing systems extended abstracts. 1--7.
[61]
Tim Valicenti, Justice Vidal, and Ritik Patnaik. 2023. Mini-GPTs: Efficient Large Language Models through Contextual Pruning. arXiv preprint arXiv:2312.12682 (2023).
[62]
Brink Van Der Merwe, Nicolaas Weideman, and Martin Berglund. 2017. Turning evil regexes harmless. In Proceedings of the South African Institute of Computer Scientists and Information Technologists. 1--10.
[63]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is All You Need. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS'17). Curran Associates Inc., Red Hook, NY, USA, 6000--6010.
[64]
Shangwen Wang, Mingyang Geng, Bo Lin, Zhensu Sun, Ming Wen, Yepang Liu, Li Li, Tegawendé F. Bissyandé, and Xiaoguang Mao. 2023. Natural Language to Code: How Far are We?. In Proceedings of the 31st ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). ACM.
[65]
Cody Watson, Nathan Cooper, David Nader Palacio, Kevin Moran, and Denys Poshyvanyk. 2021. A Systematic Literature Review on the Use of Deep Learning in Software Engineering Research. arXiv:2009.06520 [cs.SE]
[66]
Adar Weidman. 2022. Regular expression denial of service - redos. https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
[67]
Jiarong Wu, Lili Wei, Yanyan Jiang, Shing-Chi Cheung, Luyao Ren, and Chang Xu. 2023. Programming by Example Made Easy. ACM Transactions on Software Engineering and Methodology (jul 2023).
[68]
Valentin Wüstholz, Oswaldo Olivo, Marijn JH Heule, and Isil Dillig. 2017. Static detection of DoS vulnerabilities in programs that use regular expressions. In Tools and Algorithms for the Construction and Analysis of Systems: 23rd International Conference, TACAS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22--29, 2017, Proceedings, Part II 23. Springer, 3--20.
[69]
Shuai Zhang, Xiaodong Gu, Yuting Chen, and Beijun Shen. 2023. InfeRE: Step-by-Step Regex Generation via Chain of Inference.
[70]
Zexuan Zhong, Jiaqi Guo, Wei Yang, Tao Xie, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. 2018. Generating regular expressions from natural language specifications: Are we there yet?. In AAAI Workshops. 791--794.
[71]
Honglei Zhuang, Zhen Qin, Rolf Jagerman, Kai Hui, Ji Ma, Jing Lu, Jianmo Ni, Xuanhui Wang, and Michael Bendersky. 2023. Rankt5: Fine-tuning T5 for text ranking with ranking losses. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2308--2313.
[72]
Albert Ziegler, Eirini Kalliamvakou, X. Alice Li, Andrew Rice, Devon Rifkin, Shawn Simister, Ganesh Sittampalam, and Edward Aftandilian. 2022. Productivity Assessment of Neural Code Completion. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming (San Diego, CA, USA) (MAPS 2022). Association for Computing Machinery, New York, NY, USA, 21--29.
Index Terms
- Understanding Regular Expression Denial of Service (ReDoS): Insights from LLM-Generated Regexes and Developer Forums
Recommendations
Re(gEx|DoS)Eval: Evaluating Generated Regular Expressions and their Proneness to DoS Attacks
ICSE-NIER'24: Proceedings of the 2024 ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging ResultsWith the recent advances of code generation techniques based on Large Language Models (LLMs), developers are using them for a vast range of tasks, including regex generation. Despite the efforts to generate regexes from natural language, there is no ...
The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale
ESEC/FSE 2018: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software EngineeringRegular expressions (regexes) are a popular and powerful means of automatically manipulating text. Regexes are also an understudied denial of service vector (ReDoS). If a regex has super-linear worst-case complexity, an attacker may be able to trigger ...
ReScue: crafting regular expression DoS attacks
ASE '18: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software EngineeringRegular expression (regex) with modern extensions is one of the most popular string processing tools. However, poorly-designed regexes can yield exponentially many matching steps, and lead to regex Denial-of-Service (ReDoS) attacks under well-conceived ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2024
487 pages
ISBN:9798400705861
DOI:10.1145/3643916
- Chair:
- Igor Steinmacher,
- Co-chair:
- Mario Linares-Vasquez,
- Program Chair:
- Kevin Patrick Moran,
- Program Co-chair:
- Olga Baysal
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ICPC '24
Sponsor:
ICPC '24: 32nd IEEE/ACM International Conference on Program Comprehension
April 15 - 16, 2024
Lisbon, Portugal
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 34Total Downloads
- Downloads (Last 12 months)34
- Downloads (Last 6 weeks)35
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in