REDoS detection in “Domino” regular expressions by Ambiguity Analysis

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