Катастрофический бэктрекинг (ReDoS)

Узнаём, почему «безобидная» регулярка может зависнуть на секунды и как этого избежать.

Катастрофический бэктрекинг — лавинообразный рост числа вариантов перебора, из-за которого регулярка работает экспоненциально долго на коротком вводе.

Как движок ищет совпадение

Классический движок регулярок (как в Python, JS, Java) работает с возвратами (backtracking): если выбранный вариант не привёл к совпадению, он откатывается и пробует другой. Обычно это незаметно. Но при неудачных паттернах число вариантов растёт экспоненциально, и поиск зависает.

Опасный шаблон

Беда возникает, когда квантор стоит над группой, которая сама содержит квантор и допускает один и тот же текст многими способами. Классический пример (НЕ запускайте на длинном вводе):

^(a+)+$

Здесь a+ внутри (...)+ — текст вроде aaaa можно разбить на группы десятками способов: (aaaa), (a)(aaa), (aa)(aa) и так далее. Пока совпадение есть, всё хорошо. Но если в конец добавить символ, ломающий совпадение, — например "aaaaaaaaaaaaaaaaaaaa!", — движок переберёт все разбиения, прежде чем сдаться. Для 30 символов это миллиарды вариантов и зависание на секунды.

ReDoS — это уязвимость

Если такой паттерн применяется к пользовательскому вводу (например, валидация поля на сервере), злоумышленник пришлёт короткую «ядовитую» строку и повесит процесс. Это называется ReDoS (Regular expression Denial of Service) — отказ в обслуживании через регулярку. Реальные инциденты случались у крупных сервисов.

Безопасная демонстрация

Чтобы прочувствовать рост без зависания, посчитаем, на сколько способов можно разбить строку из n одинаковых букв на непустые группы — это число Фибоначчи-подобной природы, и оно растёт стремительно. Именно столько вариантов перебирает уязвимый паттерн:

def splits(n):
    # число способов разбить n символов на непустые подряд группы = 2**(n-1)
    return 2 ** (n - 1)

for n in [5, 10, 20, 30]:
    print(n, "символов ->", splits(n), "вариантов разбиения")

Вывод:

5 символов -> 16 вариантов разбиения
10 символов -> 512 вариантов разбиения
20 символов -> 524288 вариантов разбиения
30 символов -> 536870912 вариантов разбиения

Полмиллиарда вариантов для 30 символов — вот почему движок «думает» секундами. Каждый лишний символ удваивает работу.

Как защититься

• Избегайте вложенных кванторов: (a+)+, (a*)*, (.*)* — красные флаги.
• Уточняйте классы: вместо жадной .* используйте конкретный класс, который не пересекается с соседями, например [^"]* вместо .* между кавычками.
• Якорьте паттерн (^...$) и ограничивайте длину ввода до применения регулярки.
• Для проверки паттернов на уязвимость есть онлайн-анализаторы и линтеры.

Итог

• Backtracking-движок при плохих паттернах перебирает экспоненциально много вариантов.
• Вложенные кванторы вроде (a+)+ на «ядовитом» вводе вешают поиск — это ReDoS.
• Избегайте вложенных кванторов, уточняйте классы, якорьте паттерн и ограничивайте длину ввода.