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. Оказывается, на Хабре уже есть статья о бэктрекинге и атомарных групировках, там описанная проблема рассмотрена глубже и суровей — Атомарная группировка, или Ни шагу назад!:)