Выявление REDoS cитуаций в регулярных выражениях структуры «домино»

Ситуация отказа в обслуживания регулярных выражений (REDoS) возникает в случае высокой вычислительной сложности сопоставления строки с выражением и встречается во многих библиотеках регулярных выражений таких языков, как PYTHON, JAVASCRIPT, C++. В данной статье рассматривается класс регулярных выражений, которые создают угрозу возникновения REDoS, однако не распознаются как уязвимые рядом существующих программных систем. Предлагается производить оценку степени неоднозначности таких выражений посредством комбинирования проверки на строгую звёздную нормальную форму и анализа трансформационного моноида автомата Глушкова, построенного по входному регулярному выражению. Эксперименты показывают, что данный подход оказывается эффективен при оценке полиномиальных неоднозначностей в регулярных выражениях со сложной структурой перекрытий.

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.