REDoS Detection in “Domino” Regular Expressions by Ambiguity Analysis
Antonina Nepeivoda, Yulia Andreevna Belikova, Kirill Konstantinovich Shevchenko, Mikhail Romanovich Teriukha, Danila Pavlovich Knyazihin, Aleksandr Dmitrievich Delman, Anna Sergeevna Terentyeva · Proceedings of the Institute for System Programming of RAS · 2023
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.