Как одна кривая регулярка может «положить» ваш сервер: разбираем уязвимость ReDoS

Алерты кричат о 100% загрузке CPU, API лежит, сыплются таймауты и 502 ошибки. Первая мысль — DDoS. Но графики сети абсолютно спокойны. Вы смотрите логи и видите, что перед падением пришел всего один странный POST-запрос с email чуть длиннее обычного. Никаких инъекций, просто пара лишних символов.

И этого хватило, чтобы наглухо парализовать бэкенд.

Что произошло? (TL;DR)

Это классический ReDoS (Regular Expression Denial of Service). В отличие от сетевого DDoS, здесь бьют не по ширине канала, а по алгоритмической сложности.

Суть кроется в движках регулярных выражений (включая стандартный модуль re в Python), которые используют механизм бэктрекинга (поиска с возвратом). Если регулярка содержит логические изъяны — например, вложенные квантификаторы (a+)+ — специально подобранная строка заставляет парсер зайти в тупик. Он начинает возвращаться назад и перебирать все возможные комбинации символов.

Сложность вычислений растет экспоненциально: каждый лишний символ во входной строке удваивает время работы. В итоге строка длиной всего в 30–40 символов заставит процессор уйти в вычисления на десятилетия.

Регулярные выражения — мощнейший инструмент, но алгоритмические ошибки в них обходятся очень дорого. Если вы хотите понимать логику работы парсера под капотом и научиться сразу писать оптимальные, безопасные паттерны — приглашаю на мой авторский БЕСПЛАТНЫЙ курс «Python: Регулярные выражения (RegEx) с нуля».

Далее мы препарируем эту уязвимость под капотом Python, напишем эксплойт для зависания собственного процессора и разберем, как защитить свой код от подобных катастроф.

2. Под капотом Python: Как работает модуль re

В мире регулярных выражений бал правят два основных архитектурных подхода: DFA (детерминированные конечные автоматы) и NFA (недетерминированные конечные автоматы).

DFA работает предсказуемо и быстро. Он проходит по строке строго один раз слева направо, всегда точно зная, в каком состоянии находится. Ему требуется ровно столько шагов, сколько символов в тексте, поэтому он гарантирует выполнение за линейное время . Однако из-за своей прямолинейности DFA ограничен в возможностях и не поддерживает многие продвинутые функции.

Встроенный в Python модуль re (как и движки регулярных выражений в Perl, Java, JavaScript и PHP) использует NFA-движок.

Почему разработчики выбрали именно его? NFA дает огромную гибкость. Именно благодаря ему работают такие мощные конструкции, как «жадные» и «ленивые» квантификаторы, заглядывания (lookarounds) и, что самое главное, обратные ссылки (backreferences). Это механизм, позволяющий захватить кусок текста в группу и сослаться на него же дальше в выражении (например, для поиска повторяющихся слов).

Но за эту мощь приходится платить. Главная архитектурная особенность и одновременно уязвимое место NFA — механизм бэктрекинга (backtracking), или поиска с возвратом.

Суть бэктрекинга

Как это работает на практике? NFA-движок пытается сопоставить паттерн, читая входную строку. Встречая квантификаторы вроде * (ноль или более) или + (один или более), он по умолчанию ведет себя «жадно»: захватывает максимально возможный кусок текста.

Если после такого захвата оставшаяся часть строки не совпадает с хвостом регулярного выражения, движок фиксирует, что зашел в тупик. Тогда он делает шаг назад: откатывается по строке, «отдает» один символ из захваченного куска и пробует применить оставшуюся часть регулярки снова. Если снова неудача — откатывается еще на один символ назад. Движок методично перебирает возможные ветвления, пока не найдет полное совпадение или не исчерпает абсолютно все варианты возврата.

В нормальных условиях, при адекватном регулярном выражении и типичных входных данных, эти возвраты происходят мгновенно. Движок быстро понимает, что совпадения нет, отбрасывает неверные ветки за микросекунды и выдает результат. Проблема возникает только тогда, когда логика паттерна при определенных строках генерирует огромное количество таких тупиковых ветвей.

3.Что такое Catastrophic Backtracking

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

Классические уязвимые конструкции, из-за которых падают серверы, обычно сводятся к двум паттернам:

Вложенные квантификаторы: (a+)+, ([a-zA-Z]+)*, (a*)*.
Пересекающиеся альтернативы: (a|a)+, ([a-z]|[a-zA-Z])+.

Проблема этих выражений в том, что они предоставляют движку слишком много свободы. В паттерне (a+)+ символ “a” может быть поглощен как внутренним плюсом, так и внешним. Для NFA-движка это означает, что если совпадение сразу не нашлось, он будет обязан проверить абсолютно все возможные комбинации распределения символов между внешними и внутренними группами.

Почему происходит взрыв (Трассировка)

Давайте посмотрим, как парсер сходит с ума при попытке сопоставить регулярку ^(a+)+$ со строкой aaaa! (символ ! в конце здесь критичен — именно он обламывает полное совпадение и заставляет движок искать обходные пути).

Вот как выглядят шаги бэктрекинга:

Движок идет по строке. Внутренний квантификатор a+ жадно забирает все 4 буквы: (aaaa). Затем он смотрит на следующий символ и упирается в !. Конец строки $ не достигнут. Совпадения нет.
Запускается бэктрекинг. Движок делает шаг назад, и внутренний a+ «отдает» одну букву. Первая группа становится (aaa). Оставшуюся букву a подхватывает внешнее условие (начинается вторая итерация группы): (aaa)(a). Движок снова упирается в !. Совпадения нет.
Очередной откат. Первая группа отдает еще одну букву: (aa). Теперь остаток aa нужно как-то распределить. Движок пробует (aa)(aa), а затем (aa)(a)(a). Обе ветки упираются в !.
Откаты продолжаются, перебирая все доступные комбинации:

(a)(aaa)
(a)(aa)(a)
(a)(a)(aa)
(a)(a)(a)(a)

Движок методично перебирает все возможные варианты разбиения строки. Только исчерпав их до самого последнего, он сдается и возвращает None.

Математика зависания

С точки зрения математики, при несовпадении движок решает задачу комбинаторики: сколькими способами можно расставить границы подгрупп между одинаковыми символами. Для строки из подходящих символов, за которыми следует несовпадающий символ, количество вариантов разбиения пропорционально $2^{N-1}$ .

Алгоритмическая сложность (время выполнения) деградирует с линейного до экспоненциального . Что это значит на практике?

Каждый новый символ, добавленный во входную строку, увеличивает время валидации в два раза.

Если строка из 15 символов парсится за безопасные доли секунды, то дальше начинается катастрофа:

Строка из 25 символов потребует уже около 33 миллионов шагов бэктрекинга.
Строка из 30 символов — больше миллиарда шагов (ваш сервер повиснет на несколько минут).
Строка из 40 символов — заблокирует процесс на годы.

Именно поэтому ReDoS так опасен: чтобы положить бэкенд, атакующему не нужен ботнет. Ему нужен один HTTP-запрос со строкой длиной всего в 40-50 символов.

4. Практика на Python: Вешаем свой процессор

Давайте отвлечемся от сухой теории и посмотрим, как эта уязвимость выглядит в реальном коде.

«Безобидный» код

Представьте банальную задачу: нам нужно написать валидатор для поля ввода, где пользователь указывает свои навыки или теги через пробел. Разработчик решает задачу «в лоб» и пишет регулярку: строка должна состоять из букв и цифр, после которых может идти необязательный пробел, и все это повторяется до конца строки.

Получается вот такой паттерн: ^([a-zA-Z0-9]+\s?)+$

На первый взгляд, все отлично. Прогоняем валидные данные — регулярка работает без нареканий. Но в ней заложена бомба замедленного действия: вложенный квантификатор + внутри группы, которая сама закрыта квантификатором +.

Код эксплойта

Давайте напишем небольшой скрипт и посмотрим, что произойдет, если мы подадим на вход строку, состоящую только из подходящих букв a, но в самом конце добавим символ !, который сломает совпадение.

Вы можете скопировать этот код и запустить локально (спойлер: кулер вашего ноутбука начнет шуметь).

import reimport time# Наша «безобидная» регулярка для валидации слов с пробеламиvulnerable_regex = re.compile(r'^([a-zA-Z0-9]+\s?)+$')# Нормальный ввод — отрабатывает за микросекундыprint("Valid input:", bool(vulnerable_regex.match("Habr is awesome"))) # Функция для тестирования злонамеренного вводаdef test_redos(payload_length):    # Формируем зловредную строку: много 'a' и один '!' в конце    payload = "a" * payload_length + "!"        start = time.time()    vulnerable_regex.match(payload)    elapsed = time.time() - start        print(f"Length: {payload_length} | Time: {elapsed:.4f} sec")# Показываем экспоненциальный рост времени обработкиfor i in range(20, 31):    test_redos(i)

Анализ результатов

Запустив скрипт, вы увидите примерно такую картину в консоли:

Valid input: TrueLength: 20 | Time: 0.0412 secLength: 21 | Time: 0.0825 secLength: 22 | Time: 0.1651 secLength: 23 | Time: 0.3304 sec...Length: 28 | Time: 10.5123 secLength: 29 | Time: 21.0345 secLength: 30 | Time: 42.1051 sec

Обратите внимание на цифры. При длине строки в 20 символов регулярка тупит, но еще справляется за сотые доли секунды. Однако с каждым добавленным символом время выполнения удваивается.

При 30 символах скрипт будет «думать» почти минуту. А теперь давайте посчитаем последствия для реального веб-сервера. Если злоумышленник отправит payload длиной всего в 50 символов (что легко помещается в любое стандартное поле ввода):

Разница между 30 и 50 символами — 20 шагов.
Это означает увеличение времени в $2^{20}$ раз (примерно в миллион раз).
40 секунд $\times$ 1 000 000 = 40 000 000 секунд.
Это около 1.2 лет непрерывной 100% загрузки одного ядра процессора на парсинг коротенькой строки.

Если ваше приложение написано на синхронном фреймворке (например, классический Django или Flask), из-за GIL (Global Interpreter Lock) этот процесс заблокирует рабочий поток. Парочка таких запросов — и все воркеры вашего веб-сервера (Gunicorn/uWSGI) будут заняты исключительно перебором букв «а». Легитимные пользователи начнут получать 502 Bad Gateway, а ваш сервер официально «ляжет».

5. Как защитить свой Python-код (и сервер)

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

Правило №1: Ограничение длины ввода (Sanity Check)

Это самое банальное, самое скучное и одновременно самое эффективное правило. ReDoS невозможен, если злоумышленник не может передать вам достаточно длинную строку для раскачки бэктрекинга.

Никогда не скармливайте регуляркам сырой, не проверенный по длине пользовательский ввод. Если вы ждете на вход username, проверьте его длину до вызова модуля re:

def validate_username(username):    if len(username) > 50:        return False # Отсекаем на подлете    return bool(vulnerable_regex.match(username))

Это защитит вас от 99% брутфорс-атак на регулярки и сэкономит процессорное время.

Правило №2: Правильное написание регулярных выражений

Если вам все же нужно парсить длинные тексты, придется избавляться от «зла» — двусмысленности в паттернах.

Давайте починим нашу уязвимую регулярку из предыдущего примера: ^([a-zA-Z0-9]+\s?)+$

Проблема была в том, что пробел опционален, и движок не понимал, где заканчивается одно слово и начинается другое, если пробела нет. Правильный подход — описать структуру строго: «слово, за которым может следовать ноль или более повторений конструкции (пробел + слово)».

Безопасный вариант:

safe_regex = re.compile(r'^[a-zA-Z0-9]+(\s[a-zA-Z0-9]+)*$')

Здесь нет пересекающихся альтернатив. Если движок встречает пробел, он точно знает, что дальше обязано идти слово. Если слова нет — это гарантированный провал без попыток отката. Эта регулярка распарсит хоть мегабайт текста за доли секунды.

Правило №3: Использование альтернативных библиотек

Стандартный re в Python не обновлялся архитектурно очень давно. Если безопасность критична, стоит посмотреть в сторону сторонних решений.

1. Библиотека regex (Drop-in замена для re) Это мощный модуль, который поддерживает продвинутые фичи, отсутствующие в стандарте. Самая важная для нас — атомарные группировки (?>...) и посессивные квантификаторы ++. Суть атомарной группы в том, что как только движок нашел совпадение внутри нее, он «забывает» все точки возврата. Бэктрекинг для этой группы запрещается намертво.

2. Библиотека google-re2 (Абсолютная защита) Если вы парсите гигантские объемы неконтролируемого текста, используйте биндинги к C++ библиотеке re2 от Google. Это чистый DFA-движок. В нем физически нет механизма бэктрекинга, поэтому время выполнения строго гарантировано как . С re2 уязвимость ReDoS невозможна по определению. Минус: DFA не поддерживает заглядывания (lookarounds) и обратные ссылки (backreferences). Если ваша регулярка завязана на них, re2 выдаст ошибку компиляции паттерна.

Правило №4: Не полагайтесь на тайм-ауты в Python

У многих разработчиков возникает резонная мысль: «А давайте просто обернем вызов re.match() в try/except с тайм-аутом! Если думает дольше секунды — убиваем».

В Python с модулем re это работает из рук вон плохо. Парсинг регулярного выражения происходит на уровне C-кода, который в процессе захватывает GIL (Global Interpreter Lock). Стандартные питоновские механизмы асинхронных тайм-аутов (например, asyncio.wait_for) просто не смогут прервать этот синхронный C-цикл. Поток будет заблокирован, пока регулярка не доработает.

Единственный способ гарантированно прервать зависшую регулярку в Python — это вынести ее в отдельный процесс через multiprocessing и убить процесс по тайм-ауту (или использовать signal.alarm, что работает только на Unix-системах и может привести к непредсказуемым побочным эффектам в многопоточных приложениях).

Но порождать тяжеловесный процесс ОС ради валидации одного email-адреса — это архитектурный «костыль», который сам по себе может положить сервер из-за исчерпания памяти (своеобразный самодельный DDoS). Поэтому решайте проблему на уровне алгоритма (Правило 2) или движка (Правило 3), а не пытайтесь бороться с последствиями.

6. Заключение

Регулярные выражения — это невероятно мощный и выразительный инструмент, без которого сложно представить современную бэкенд-разработку. Но классическое правило «с большой силой приходит большая ответственность» работает здесь на все сто процентов.

Мы часто привыкаем доверять стандартным библиотекам, воспринимая встроенный модуль re как безопасный черный ящик. Однако архитектурные особенности NFA-движков таковы, что малейшая алгоритмическая небрежность в написании паттерна способна превратить валидацию короткой строки в вычислительную катастрофу, которая положит вашу инфраструктуру.

Что стоит сделать прямо сейчас? Проведите аудит своих сервисов. Откройте код и посмотрите, как именно вы проверяете пользовательский ввод. Особое внимание уделите регуляркам, которые парсят:

Email-адреса (в сети гуляют сотни «универсальных» паттернов для email, многие из которых уязвимы к ReDoS).
Длинные URL-ссылки.
Номера телефонов и адреса.
Различные парсеры разметки (например, самописные конвертеры Markdown).

Убедитесь, что перед каждым вызовом регулярного выражения стоит банальный, но спасительный if len(input_string) > MAX_LENGTH.

Анонсы новых статей, полезные материалы, а так же если в процессе у вас возникнут сложности, обсудить их или задать вопрос по этой статье можно в моём Telegram‑сообществе. Смело заходите, если что‑то пойдет не так, — постараемся разобраться вместе.

ссылка на оригинал статьи https://habr.com/ru/articles/1044496/