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

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

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

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

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

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

![CatastrophicBacktrackingError_ru/image1.png](https://import.viva64.com/docx/blog/CatastrophicBacktrackingError_ru/image1.png)

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

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

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

![CatastrophicBacktrackingError_ru/image2.png](https://import.viva64.com/docx/blog/CatastrophicBacktrackingError_ru/image2.png)

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

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