REDoS Detection in “Domino” Regular Expressions by Ambiguity Analysis

The Regular Expression Denial of Service (REDoS) problem refers to a time explosion caused by the high computational complexity of matching a string against a regex pattern. This issue is prevalent in popular regex engines, such as Python, JavaScript, and C++. In this paper, we examine several existing open-source tools for detecting REDoS and identify a class of regexes that can create REDoS situations in popular regex engines but are not detected by these tools. To address this gap, we propose a new approach based on ambiguity analysis, which combines a strong star-normal form test with an analysis of the transformation monoids of Glushkov automata orbits. Our experiments demonstrate that our implementation outperforms the existing tools on regexes with polynomial matching complexity and complex subexpression overlap structures. 

1. Davis J. C., Coghlan C. A., Servant F., and Lee D. The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale. In Proc. of the 2018 ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2018. pp. 246-256. DOI: 10.1145/3236024.3236027.

2. Liu Y., Zhang M., and Meng W. Revealer: Detecting and exploiting regular expression denial-of-service vulnerabilities. In Proc. of the 2021 IEEE Symposium on Security and Privacy (SP), 2021. pp. 1468-1484. DOI: 10.1109/SP40001.2021.00062.

3. Van der Merwe B., Weideman N., and Berglund M. Turning evil regexes harmless. In Proc. of the South African Institute of Computer Scientists and Information Technologists, 2017. pp. 1-10. DOI: 10.1145/3129416.3129440.

4. Weideman N., van der Merwe B., Berglund M., Watson B. W. Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA. In Proc. of the Implementation and Application of Automata - 21st International Conference. 2016. pp. 322-334. DOI: 10.1007/978-3-319-40946-7_27.

5. Shen Y., Jiang Y., Xu C., Yu P., Ma X., Lu J. ReScue: Crafting regular expression DoS attacks. In Proc. of the 33rd ACM/IEEE International Conference on Automated Software Engineering, 2018. pp. 225-235. DOI: 10.1145/3238147.3238159.

6. Li Y., Sun Y., Xu Z., Cao J., Li Y., Li R., Chen H., Cheung S.-C., Liu Y., Xiao Y. RegexScalpel: Regular expression denial of service (ReDoS) defense by Localize-and-Fix. In Proc. of the 31st USENIX Security Symposium (USENIX Security 22), 2022. pp. 4183-4200.

7. Li Y., Chen Z., Cao J., Xu Z., Peng Q., Chen H., Chen L., Cheung S. ReDoSHunter: A combined static and dynamic approach for regular expression DoS detection. In Proc. of the 30th USENIX Security Symposium (USENIX Security 21), 2021. pp. 3847-3864.

8. Google. Official public repository of RE2 library. Available at: https://github.com/google/re2, accessed 01.07.2023.

9. Bruggemann-Klein A. and Wood D. One-unambiguous regular languages. Information and Computation, vol. 140, no. 2, 1998. pp. 229-253. DOI: 10.1006/inco.1997.2688.

10. Freydenberger D. D., Schmid M. L. Deterministic regular expressions with back-references. Journal of Computer and System Sciences, vol. 105, 2019. pp. 1-39. DOI: 10.1016/j.jcss.2019.04.001.

11. Allauzen C., Mohri M. A unified construction of the Glushkov, Follow, and Antimirov automata. In Proc. of the Mathematical Foundations of Computer Science, 2006. pp. 110-121. DOI: 10.1007/11821069_10.

12. Eric Pin J. Mathematical foundations of automata theory. Available at: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf, accessed 01.07.2023.

13. Weber A., Seidl H. On the degree of ambiguity of finite automata. Theoretical Computer Science, vol. 88, no. 2, 1991. pp. 325-349. DOI: 10.1016/0304-3975(91)90381-B.

14. Allauzen C., Mohri M., Rastogi A. General algorithms for testing the ambiguity of finite automata. In Proc. of the Developments in Language Theory, 2008. pp. 108-120. DOI: 10.1007/978-3-540-85780-8_8.

15. Bruggemann-Klein A. Regular expressions into finite automata. Theoretical Computer Science, vol. 120, no. 2, 1993. pp. 197-213. DOI: 10.1016/0304-3975(93)90287-4.

16. Almeida M., Moreira N., Reis R. On the performance of automata minimization algorithms. In Proc. of the 4th Conference on Computability in Europe, 2008. pp. 3-14.

17. Weideman N. Regex static analyzer. Available at: https://github.com/NicolaasWeideman/RegexStaticAnalysis, accessed 01.07.2023.

18. Shen Y., Jiang Y., Xu C., Yu P., Ma X., Lu J. Rescue. Available at: https://github.com/2bdenny/ReScue, accessed 01.07.2023.

19. Liu Y., Zhang M., Meng W. Revealer. Available at: https://github.com/cuhkseclab/Revealer, accessed 01.07.2023.

20. Gelade W., Neven F. Succinctness of the Complement and Intersection of Regular Expressions. In Proc. of the 25th International Symposium on Theoretical Aspects of Computer Science, 2008. pp. 325-336. DOI: 10.4230/LIPIcs.STACS.2008.1354.

21. Birget J., Margolis S. W., Meakin J. C., Weil P. Pspace-complete problems for subgroups of free groups and inverse finite automata. Theoretical Computer Science, vol. 242, no. 1-2, 2000. pp. 247-281. DOI: 10.1016/S0304-3975(98)00225-4.