Catastrophic backtracking в регулярных выражениях

    Можно ли простой и вроде невинной регуляркой убить систему? Да, можно.

    Например:

    >>> r = '(a+)*b'
    

    Просто — да. Невинно — вроде да. Конечно неумно, потому что скобки и звездочка лишние, но должно работать. Попробуем:

    >>> re.findall('(a+)*b', 'aaaaaab')
    ['aaaaaa']
    

    Круто, работает, пошли пить пиво.

    А нет…

    Если строка, в которой ищем, не будет содержать искомого паттерна, например просто 'aaaaaa', компилятор будет пробовать найти её следующим алгоритмом:

    1. Вся стока удовлетворяет 'a+', но мы не находим 'b', шаг назад.
    2. Теперь 'a+' удовлетворяет только 'aaaaa' (все, кроме последней), последняя удовлетворяет повтору '*', 'b' все равно не находим, шаг назад.
    3. Первое 'a+' удовлетворяет только 'aaaa', последние два 'aa' удовлетворяют повтору '*', 'b' все равно не находим, шаг назад.
    4. Первое 'a+' удовлетворяет 'aaaa', предпоследняя 'a' удовлетворяет одному повтору '*', следующая 'a' еще одному повтору '*', 'b' так и не находиться…

    Ну Вы поняли — и так далее. Вплоть до полного перебора строки.

    Немного статистики:
    >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*20)", number=1)
    0.24741506576538086
    >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*22)", number=1)
    0.99283289909362793
    >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*24)", number=1)
    3.9849259853363037
    

    Как видим, время исполнения растет экспоненциально. Для бОльших строк Python 2.6 на FreeBSD своевременно выкидывает RuntimeError, но на Windows тот самый Python бодренько перебирает все комбинации. Строки больше 30 символов не рискнул тестировать :)

    Пост навеяно сегодняшним вопросом на stackoverflow и давно прочитанной и успешно забытой заметкой Runaway Regular Expressions: Catastrophic Backtracking.

    P.S. Оказывается, на Хабре уже есть статья о бэктрекинге и атомарных групировках, там описанная проблема рассмотрена глубже и суровей — Атомарная группировка, или Ни шагу назад!:)
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 23

      0
      Полезное напоминание, спасибо. Как раз недавно «нырял» в регулярки, после праздников опять :)
        0
        Вот очень классная статья по регекспам. Рассматривается, в частности, и описанная проблема, а также имплементация регекспов с помощью конечного автомата: swtch.com/~rsc/regexp/regexp1.html
          +3
          И вот заодно дико классная классическая книжка по регекспам и не только. Помимо прочего, рассказывают, почему нельзя парсить Html с помощью regex: en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation
            +3
            Почему нельзя парсить html регулярками — это сюда stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 :)
              +1
              Спасибо за ссылку, это великолепно :)
                0
                интересно, есть где-нибудь перевод? а то тыкать новичков в английский текст бесполезно…
                0
                Можете ли вы в двух словах сказать почему?
                  +4
                  Если строго, то html по классификации Хомского принадлежыт к типу 2 (контекстно-свободные), в тоже время регулярки — 3 тип. То есть html нельзя описать (а значит и пропарсить) с помощью regexp.
                    –1
                    Я так понимаю, здесь потерялась частица не?

                    Любая контекстно-свободная грамматика может быть легко преобразована в вид, в котором правила состоят только из лево-регулярных или право-регулярных (для контекстно-свободных грамматик допустимо наличие тех и других одновременно). Следовательно, такие грамматики могут выразить все контекстно-свободные языки. Регулярные грамматики могут содержать либо лево-регулярные правила, либо право-регулярные, но не оба вида одновременно. Поэтому они могут описать лишь подмножество языков, называемых регулярными языками.
                      +1
                      А, нет, википедия не врёт, просто неправильно прочитал.
                      +3
                      Я думаю что regexp применяют к html в случае когда нужно выкусить кусок текста, а не пропарсить весь документ. В таком применении он бывает удобнее чем html/xml парсеры.
                      –1
                      другой инструмент.
                  +5
                  Было на Хабре с подробными объяснения, что плохо и как надо.
                  Атомарная группировка, или Ни шагу назад!

                  Вот несколько цитат оттуда, чтобы показать, что речь о том же.

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

                  Однако, регекс не должен матчить такую часть цепочки, в которой скобки не сбалансированы (открытые скобки не закрываются или, наоборот, закрываются скобки, которые вовсе не были открыты).
                  Далее выписываются рассуждения гипотетического Ивана и составленное им регулярное выражение.
                  Иван проверяет регекс на нескольких примерах цепочек (благо, на интервью разрешено прогонять тестовые программы, нельзя лишь заходить в Интернет и читать документацию)

                  и регекс с ними со всеми справляется как положено. Довольный, Иван показывает решение интервьюеру. Happy end, занавес? Но почему статья названа так, как она названа??
                  Интервьюер спрашивает, что должен (если должен) найти регекс в следующей цепочке:
                  (you're gonna fail sonny unless you correct it (your regex)
                  Прочитав и побледнев, Ванюша, тем не менее, не моргнув глазом отвечает, что, раз 1-я скобка нигде не закрывается, регекс должен найти 2-ю пару скобок: (your regex). Его просят проверить. Иван вбивает эту цепочку в свой проверочный скрипт

                  Проверив синтаксис, Иван запускает скрипт и… и ничего не происходит, скрипт как будто «зависает». Не говорит ни «да», ни «нет». Иван и интервьюер молча смотрят на это секунд 10. За это время Иван из бледного становится ярко-розовым: он уже явно чувствует подвох. Но чтО он сделал не так?? В этот момент лэптоп, на котором был запущен (и до сих пор почему-то не завершился) скрипт, начинает отчетливо гудеть, хотя до тех пор работал бесшумно.

                  А далее объясняется, как на самом деле работает это регулярное выражение (постоянно отступая назад), и повествуется о пользе атомарных группировок.
                    0
                    Спасибо за линк. Добавил в пост.
                    +5
                    Some people, when confronted with a problem, think «I know, I'll use regular expressions.» Now they have two problems.

                    © Jamie Zawinski

                    Хотя иногда, конечно, без регулярных выражений не обойтись.
                      0
                      Не обойтись? А чем не устраивает PEG?
                        0
                        Тем, что я не знаю (с настоящего момента — не знал) о его существовании.
                        Спасибо за наводку — добавил в readlater.
                      –1
                      А если взять какой-нибудь BusyBeaver в 6 состояний и конвертнуть в регэкспу? :) Надо будет посчитать на досуге.
                        0
                        Мне кажется, это не сразу получится: busy beaver--это пример машины тьюринга; а регекспы описываются конечными автоматами, и уступают в мощности машинам тьюринга. Вот тут про это есть.
                        0
                        Сначала, хотел написать WTF? Запустил на Java проверил различные варианты и мда… действительно не работает.

                        Вопрос как же так? Обычная регулярка. Простой Недетерминированный автомат => Детерминированный.
                        Причем тут бэктрекинг??? В автоматах.

                          +3
                          Как видим, время исполнения растет экспоненциально.

                          только если нет оптимизации для такого случая)
                          $ time perl -E 'my $s = "a" x 1_000_000; say $s =~ /(a+)*b/'
                          
                          perl -E 'my $s = "a" x 1_000_000; say $s =~ /(a+)*b/'  0.01s user 0.01s system 85% cpu 0.016 total
                          
                          • UFO just landed and posted this here
                            • UFO just landed and posted this here

                            Only users with full accounts can post comments. Log in, please.