Regex на практике: PCRE, RE2 и Rust regex

2 июля 2019 года. Cloudflare получает инцидент P0: их WAF (Web Application Firewall) начинает потреблять 100% CPU на всех edge nodes по всему миру. За 27 минут ~20% всего трафика Cloudflare недоступно. Причина: один уязвимый regex в новом правиле WAF. Один паттерн с nested quantifiers. Один HTTP-запрос. Результат: глобальный outage. Это ReDoS.

• **Cloudflare outage 2019:** причина - regex в WAF правиле с nested quantifiers `(?:...|...|...)+` где альтернативы могли матчиться overlapping способами. На специально подобранном входе - exponential backtracking. 27 минут глобального outage, ~20% трафика. После: переход на RE2 (linear-time engine).
• **Stack Overflow outage 2016:** regex для парсинга markdown-подобного синтаксиса. Пользователь отправил строку из 20 000 пробелов. CPU spike, site down на несколько минут. После этого SO перешёл на регулярный анализ паттернов перед деплоем
• **Node.js express-validator:** множество уязвимых regex в валидации email, URL, ISBN. Исправлено в версии 5.x заменой на специализированные библиотеки. Уроки: не писать regex для валидации email вручную
• **Hyperscan (Intel DPDK):** промышленный multi-pattern regex движок для сетевых пакетов. Используется в Snort IDS, Suricata. Компилирует сотни паттернов в NFA и обрабатывает параллельно. O(n) при O(k) паттернах одновременно

PCRE: backtracking движок

**PCRE** (Perl Compatible Regular Expressions) - самый распространённый движок regex: Python `re`, PHP, Nginx, Apache, большинство языков. Работает через **backtracking**: пробует все варианты сопоставления, откатываясь при неудаче. Мощный (поддерживает обратные ссылки), но уязвим к катастрофическому backtracking - **ReDoS**.

**CloudFlare outage 2019:** один уязвимый regex в WAF правиле положил все edge nodes глобально на 27 минут. Pattern с nested quantifiers на специально crafted HTTP-запросе. Экспоненциальный backtracking блокировал CPU на 100%. Реальная атака ReDoS в промышленном масштабе. Решение: использовать RE2 или Rust regex в критических путях.

Lookaheads и lookaheads: мощь без backtracking

**Lookahead** `(?=...)` и **lookbehind** `(?<=...)` - нулевой ширины утверждения: проверяют контекст без поглощения символов. `(?!...)` - отрицательный lookahead. Lookaheads позволяют выражать условия без backtracking во многих случаях и значительно упрощают сложные паттерны.

Важное ограничение Python `re`: lookbehind должен иметь **фиксированную ширину**. `(?<=\d{3})` работает, `(?<=\d+)` нет - переменная ширина запрещена. Perl и PCRE2 поддерживают переменную ширину. Rust regex и RE2 не поддерживают lookbehind вообще - цена за гарантированный O(n).

Backreferences: выход за пределы регулярных языков

**Backreference** `\1`, `\2` - ссылка на содержимое ранее захваченной группы. `(\w+)\s+\1` находит повторяющиеся слова. Backreferences выходят за пределы регулярных языков! Язык {ww : w ∈ Σ*} (палиндромная удвоенная строка) не является регулярным, но описывается `(.*)\1` в PCRE. RE2 и Rust regex не поддерживают backreferences - они остаются в границах регулярных языков.

Практическое правило: если задача требует backreferences - это сигнал, что задача потенциально не является регулярной. Для валидации XML использовать XML-парсер, не regex. Для HTML - BeautifulSoup или lxml. Backreferences в конфигурации Nginx или WAF - потенциальная уязвимость ReDoS.

RE2 и Rust regex: гарантированный O(n)

**RE2** (Google, 2007) и **Rust regex** (2014) - движки на основе NFA/DFA симуляции. Гарантируют O(n) по длине строки. Компилируют regex в NFA, симулируют NFA детерминированно (все ветви параллельно). Ценой: нет backreferences, нет lookbehind переменной ширины, нет атомарных групп.

Итоги

• **PCRE (Python re):** backtracking, поддерживает backreferences и lookahead. Уязвим к ReDoS при nested quantifiers на специальных входах
• **RE2 и Rust regex:** NFA/DFA симуляция, O(n) гарантировано. Нет backreferences. Используются в критических путях с untrusted input
• **Backreferences** выходят за рамки регулярных языков - это сигнал что задача возможно нерегулярная. Для XML/HTML использовать парсер
• **Lookahead:** нулевая ширина, не поглощает символы. Может усложнять backtracking паттерны - проверять на ReDoS-уязвимость

Связанные темы

Regex - практическое воплощение теории регулярных языков:

• Регулярные языки и DFA — RE2 и Rust regex реализуют теоретическую конструкцию: regex -> NFA -> DFA -> O(n) симуляция
• Формальная верификация — Верификация regex паттернов на ReDoS - статический анализ безопасности
• Автоматы в коде — Regex движки - конечные автоматы; та же теория в state machines приложений

Вопросы для размышления

• Regex для валидации email адресов: RFC 5322 полный паттерн занимает несколько страниц. Почему разработчики используют упрощённые версии и какие риски это создаёт?
• RE2 не поддерживает backreferences, но поддерживает lookahead (ограниченно). Почему lookahead без backreferences не нарушает O(n) гарантию?
• Cloudflare перешёл на RE2 после инцидента. Но RE2 не поддерживает некоторые полезные паттерны. Как организовать проверку regex паттернов на ReDoS-уязвимость перед деплоем?

Связанные уроки

• comp-07-regex-in-lexer