07 Окт 2022

Катастрофический возврат в регулярных выражениях

07 Окт 2022

Катастрофический возврат возникает при оценке уязвимым регулярным выражением строк определённого формата. В результате этой ошибки время вычисления регулярного выражения увеличивается экспоненциально, в зависимости от длины входной строки.

Катастрофический возврат в регулярных выражениях становится возможным из-за "наивной" природы алгоритма вычисления регулярного выражения.

Наивность алгоритма заключается в необходимости проверки абсолютно всех вариантов сопоставлений строки с шаблоном для того, чтобы сделать вывод об отсутствии совпадений.

В случае если таких вариантов окажется огромное количество и при этом среди них не будет ни одного верного сопоставления, проверка всех вариантов займет неоправданно много времени. Этот процесс и называется катастрофическим возвратом.

Так, например, несколько вариантов сопоставлений строки 'xxxxy' с шаблоном '(x+)+y' продемонстрированы в таблице ниже:

CatastrophicBacktrackingError_ru/image1.png

При обработке строки 'xxxxy' регулярным выражением '(x+)+y' никаких проблем не возникнет, т. к. она полностью соответствует паттерну и количество символов в строке незначительно.

Однако если удалить символ 'y' и увеличить количество символов 'x', например, в 6 раз, время вычисления регулярного выражения заметно увеличится.

График зависимости времени вычисления регулярного выражения '(x+)+y' от длины входной строки вида 'xx....xx' представлен ниже:

CatastrophicBacktrackingError_ru/image2.png

Регулярное выражение является уязвимым к катастрофическому возврату, если соответствует следующим условиям:

Существует два подвыражения, при этом одно из них включено в другое и к каждому из них применяется один из следующих кванторов: '*', '+', '*?', '+?', '{...}' (в предыдущем примере подвыражение 'x+' включено в '(x+)+');
Существует такая строка, которую можно было бы сопоставить с обоими этими подвыражениями (строку 'xxxx' можно сопоставить как с шаблоном 'x+', так и с '(x+)+').