Comments 16
Андрей, а неужели "(x+)+y" не оптимизируется в просто "x+y" стандартной техникой на конечных автоматах?
Зависит от движка. Например, если брать js, то в Хроме плохие регулярки зависают, а в Сафари всё норм.
Для js, кстати, тема хорошо разобрана здесь
Честно говоря, мне эта статья не понравилась. Ну рассказывается про детали некоторого неназванного алгоритма разбора регулярных выражений. При этом заметается под ковёр то, что алгоритмов этих много.
Привет! В этой статье я сделал акцент на самой проблеме и принципах её обнаружения и исправления. Таким образом, я хотел поделиться опытом с теми разработчиками, кто как и я столкнулся с проблемой катастрофического возврата и хочет понять почему это произошло и как этого можно было-бы избежать. При этом я старался максимально абстрагироваться от подробностей о принципе работы какого-либо конкретного алгоритма.
Однако, мне действительно стоило упомянуть, что эта проблема актуальна только для алгоритмов, основанных на недетерминированном конечном автомате.
Погонял https://cyberzhg.github.io/toolbox/nfa2dfa — если подставить "(x+)+y", то будет только один цикл, хотя, конечно, DFA сложнее "x+y". То есть, если делать конечный автомат, то никаких таких проблем не будет.
То есть, проблемы такого рода только для регулярных выражений, которые в обычный конечный автомат не укладываются => движок делается на других принципах. Занятно.
Привет, зависит от того, какой автомат используется в алгоритме. Проблема катастрофического возврата актуальна только для недетерминированных конечных автоматов.
Только это не проблема регулярных выражений, которые задаются регулярной грамматикой. Если не втаскивать всяких расширений, то взорваться при правильной реализации они не могут. Одна из подобных реализаций - https://github.com/google/re2
Емнип, было что-то про детерминированные движки регулярных выражений, они к этому уязвимы?
Нельзя ли это проиллюстрировать примером? Смутило слово «точность». Регулярное выражение всегда вычисляется точно, вопрос лишь в том, если есть более 1 соответствия — какое из них взять. Есть еще режимы greedy/ungreedy, задающие как сопоставлять — по максимально длинному или минимально длинному совпадению.
Атомарные группы не используют бэктрекинг, и потому не смогут найти то, что ищется бэктрекингом.
Пример: надо разменять 11 рублей монетами номиналом 5 и 2. Подобную задачу можно решить регуляркой на строке из 11 символов
^((?:.{5})*)((?:.{2})*)$Но если первую группу заменить на атомарную, регулярка бессильна - сожрав на первую группу 10 символов, она не пробует другие варианты
Отличная статья. Спасибо
Что такое катастрофический возврат и как регулярное выражение может стать причиной ReDoS-уязвимости?