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

Популярные статьи по теме
5 причин, почему статический анализ кода важен для бизнеса

Дата: 20 Апр 2023

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

В статье разбираются 5 основных причин, почему статический анализ кода будет полезен бизнесу, связанному с разработкой программного обеспечения. Статья поможет принять решение, стоит ли познакомиться…
Можно автоматизировать обзор кода?

Дата: 18 Апр 2023

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

Автоматизация обзоров кода возможна с помощью инструментов статического анализа. Следует учитывать, что разовые проверки непродуктивны, поэтому очень важно, чтобы статический анализ кода стал неотъем…
Личный кабинет PVS-Studio

Дата: 31 Мар 2023

Автор: Тимур Макаев

В этой заметке предлагаем познакомиться с новым веб-сервисом от PVS-Studio. Речь идёт о личном кабинете пользователя. Он будет полезен всем активным читателям нашего блога, а также тем, кто решит поп…
Reddit для программистов

Дата: 27 Мар 2023

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

Эта статья посвящена одной популярной и активной площадке на просторах Интернета — Reddit. Кто не в курсе, Reddit — это платформа, где сосуществуют тысячи сообществ по интересам. Мы любим Reddit за ч…
Хорошо ли ChatGPT ищет ошибки в коде?

Дата: 02 Мар 2023

Автор: Артём Ровенский

Нейросети всё больше вливаются в привычный мир, пытаясь упростить нам жизнь. Тот же ChatGPT вызвал бурю обсуждений в интернете. Чат бот способен писать тексты, код, рефераты и песни. Он даже умеет ис…


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

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