Для получения триального ключа
заполните форму ниже
Team license
Enterprise license
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

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

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

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

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

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

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


Если вы так и не получили ответ, пожалуйста, проверьте папку
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+)+').

Последние статьи:

Опрос:

Популярные статьи по теме
Как Apple и другие крупные компании настиг программный баг

Дата: 09 Ноя 2022

Автор: Ульяна Гришина

Сегодня мы отобрали свежие случаи программных ошибок, чтобы вы могли немного отвлечься и, возможно, узнать что-то новенькое. Если вам интересно узнать, как программисту удалось сломать Интернет по вс…
Единороги компании PVS-Studio

Дата: 30 Авг 2022

Автор: Андрей Карпов

Скорее всего вы перешли на эту статью, заинтересовавшись одним из наших рисунков единорогов. Приятно видеть ваш интерес. Сейчас мы расскажем, почему рисуем этих единорогов, что они означают и чем воо…
Обрабатывать ли в PVS-Studio вывод других инструментов?

Дата: 26 Май 2022

Автор: Андрей Карпов

Анализатор PVS-Studio умеет "схлопывать" повторяющиеся предупреждения. Предоставляет возможность задать baseline, что позволяет легко внедрять статический анализ в legacy-проекты. Стоит ли предостави…
15000 ошибок в открытых проектах

Дата: 24 Май 2022

Автор: Андрей Карпов

Количество багов в нашей коллекции перевалило за отметку 15000. Именно такое количество ошибок обнаружила команда PVS-Studio в различных открытых проектах. Особенно интересно, что это всего лишь побо…
Комментарии в коде как вид искусства

Дата: 04 Май 2022

Автор: Сергей Хренов

Приветствую всех программистов, а также сочувствующих. Кто из нас хотя бы раз в жизни не оставлял комментарии в коде? Был ли это ваш код, а может, чужой? Что за комментарии вы написали: полезные или …

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

Следующие комментарии
Unicorn with delicious cookie
Мы используем куки, чтобы пользоваться сайтом было удобно.
Хорошо