Катастрофический возврат в регулярных выражениях
Катастрофический возврат возникает при оценке уязвимым регулярным выражением строк определённого формата. В результате этой ошибки время вычисления регулярного выражения увеличивается экспоненциально, в зависимости от длины входной строки.
Катастрофический возврат в регулярных выражениях становится возможным из-за "наивной" природы алгоритма вычисления регулярного выражения.
Наивность алгоритма заключается в необходимости проверки абсолютно всех вариантов сопоставлений строки с шаблоном для того, чтобы сделать вывод об отсутствии совпадений.
В случае если таких вариантов окажется огромное количество и при этом среди них не будет ни одного верного сопоставления, проверка всех вариантов займет неоправданно много времени. Этот процесс и называется катастрофическим возвратом.
Так, например, несколько вариантов сопоставлений строки 'xxxxy' с шаблоном '(x+)+y' продемонстрированы в таблице ниже:
При обработке строки 'xxxxy' регулярным выражением '(x+)+y' никаких проблем не возникнет, т. к. она полностью соответствует паттерну и количество символов в строке незначительно.
Однако если удалить символ 'y' и увеличить количество символов 'x', например, в 6 раз, время вычисления регулярного выражения заметно увеличится.
График зависимости времени вычисления регулярного выражения '(x+)+y' от длины входной строки вида 'xx....xx' представлен ниже:
Регулярное выражение является уязвимым к катастрофическому возврату, если соответствует следующим условиям:
- Существует два подвыражения, при этом одно из них включено в другое и к каждому из них применяется один из следующих кванторов: '*', '+', '*?', '+?', '{...}' (в предыдущем примере подвыражение 'x+' включено в '(x+)+');
- Существует такая строка, которую можно было бы сопоставить с обоими этими подвыражениями (строку 'xxxx' можно сопоставить как с шаблоном 'x+', так и с '(x+)+').
0