metrica
Мы используем куки, чтобы пользоваться сайтом было удобно.
Хорошо
to the top
close form

Заполните форму в два простых шага ниже:

Ваши контактные данные:

Шаг 1
Поздравляем! У вас есть промокод!

Тип желаемой лицензии:

Шаг 2
Team license
Enterprise license
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности
close form
Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Бесплатная лицензия PVS‑Studio для специалистов Microsoft MVP
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Мне интересно попробовать плагин на:
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
check circle
Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

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

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

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+)+').

Популярные статьи по теме


Комментарии (0)

Следующие комментарии next comments
close comment form