Салют, Хабр!

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

Можно не писать самому регулярные выражения. Вообще не использовать их в коде. Но они всё равно там окажутся. Допустим, мы хотим написать проверку email-адреса, чтобы пускать людей с нужным корпоративным аккаунтом. Написали заглушку на FastAPI:

from fastapi import FastAPI
from pydantic import EmailStr

app = FastAPI()

@app.get("/")
async def validate_domains(email: EmailStr):
   return {"valid": True}

Выглядит легитимно, но, если выкатить, прод упадёт. Причина в ReDoS. Почему он возникает? Смотри ниже.

Откуда берётся backtracking? 

Проблема в так называемых возвратах регулярных выражений — backtracking. На некоторых текстах одни и те же символы обрабатываются очень много раз. В 2019 году эта невинная особенность регулярок на 27 минут положила CloudFlare. Вот он, преступник:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

Паттерн .*.*=.*. породил бесконечный backtracking и обрушил систему. Полная история тут.

Причину возвратов нельзя понять без небольшого погружения в теорию. Регулярные выражения почти без изменений можно перерисовать в виде схем; для этого есть множество инструментов, например, regexper.com. И де‑факто эти схемы очень похожи на реальную математическую модель регулярок, недетерминированные конечные автоматы (НКА). НКА можно представить в виде графа, где каждая вершина — это некоторое состояние, каждое ребро — чтение символа (а пустые переходы — чтение пустого символа), плюс также зафиксированы начальное состояние и конечные.

Картинка выглядит более громоздко, но это уже полноценная модель. При этом сопоставляется с исходной схемой почти 1-в-1. Матч получается, если мы можем из начала попасть в конец хотя бы одним путём. Например, рассмотрим простой негативный пример, abc:

А вот простой позитивный пример, xy:

Дошли до конца, при этом символы тоже кончились. Матч найден, успех.

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

Можно рассмотреть ту же регулярку (x+)+y и пример xxxx. Он очевидно не подходит, но программа об этом ещё не знает. Регулярки матчат группы жадно (пытаются забрать как можно больше), значит, можно построить первые итерации:

1. (xxxx) → нет y, остановка

2. (xxx)(x)

3. (xx)(xx)

4. (xx)(x)(x)

5. (x)(xxx) и другие

Количество вариантов растёт экспоненциально, а это значит, что даже небольшая, менее 40 символов, строка заблокирует этот поток полностью.

Теперь можно возвращаться к исходному сниппету FastAPI.

from fastapi import FastAPI
from pydantic import EmailStr


app = FastAPI()


@app.get("/")
async def validate_domains(email: EmailStr):
   return {"valid": True}

Внутри матрёшка:

1. FastAPI принял запрос;

2. валидирует pydantic;

3. для валидации используется email-validator.

Можно предположить, что проблема лежит где‑то в валидации email. Но всё гораздо тривиальнее. Перед валидацией email надо извлечь из строк с именем, например, Whatever <foobar@example.com>. Проблема именно на этом этапе. 

Покажу кусок PR (#10601):

-    email_group = r<\s*(.+)\s*>
+    email_group = r<(.+)>

(лишних пробелов не будет, потому что позже всё равно делается .strip())

В изначальной версии регулярного выражения пробел может быть «съеден» в любом из трёх разных мест: \s*, (.+), \s*. Они идут подряд, поэтому в худшем случае это может привести как раз к кубической сложности O(N³).

PR влит, в свежих версиях проблема исправлена. Почти случайно нашлась проблема в очень популярном проекте. Что делать дальше? Нужно посмотреть на другие! Для анализа, после доработки Regexploit напильником, (ссылка в конце текста) проверяем три разных списка Python‑проектов с GitHub: Awesome Python, Top 100 Stars in Python и персональный Awesome Python. Они пересекаются, но не слишком сильно. Предупреждение: оценка может быть завышена, так как результаты проверены на ложные срабатывания выборочно.

Вывод: проблемы есть, и их много. Удобнее всего разбить их на два класса:

1. Кубические (O(N³) и выше) — 12%, то есть каждый восьмой проект содержит потенциально проблемные регулярки! Задержка — примерно секунда на 2000 символах, как в pydantic.

2. Экспоненциальные (O(e^N)), как (x+)+y. По моим оценкам от 2 до 5%, немного по-разному для разных списков. Backtracking в них — почти бесконечность на твите, 140 символов.

В конце статьи оставил список проектов с моими PRами. На текущий момент все вмержены, так что можно аккуратно предположить, что проблема действительно была. Рассуждать о её серьёзности сложно — много экспоненциальных срабатываний на тестах, которые не так честно учитывать.

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

Как проще всего решить проблему регулярок?

Решение, внезапно, почти такое же старое, как сами недетерминированные автоматы: автоматы детерминированные. Для иллюстрации также возьмём регулярку [ab]*[ac]*a+[ac]+ и построим её схему. И сразу строим детерминированный автомат (ДКА):

Очень сильно отличается от схемы, но выглядит схоже с прошлым автоматом: такие же состояния и переходы. Потому что это такой же НКА, но альтернативных путей тут нет! Из каждого состояния только один путь.

С точки зрения математики любой НКА можно перевести в ДКА. Вместе с тем ДКА не используют всюду по трём с половиной причинам. Во‑первых, из‑за того, что связь с исходной схемой (=выражением) в целом теряется, у нас гораздо меньше контроля над процессом (об этом написано в .NET доках). Во‑вторых, перестаёт работать часть фич — например, бекреференсы (backreference) использовать не получится. В‑третьих, с оптимизациями сложнее, поэтому могут быть медленнее.

Кроме того, существует фундаментальная теоретическая проблема, хотя я не ловил её на реальных примерах: в худшем случае конвертация НКА → ДКА будет экспоненциальной, а значит, может потребовать очень много памяти. Дело в особенности процесса конвертации НКА в ДКА: это происходит через конвертацию каждого набора состояний НКА в одно состояние ДКА. Число наборов состояний — это экспонента 2^N, где N — число состояний НКА. Вместе с тем реальной жизни эти состояния почти всегда пустые, то есть в ДКА не попадают.

Далее берём несколько доступных для Python движков регулярных выражений. Их много, но production‑ready гораздо меньше.

• pcre2 — биндинг к PCRE2. Много оптимизаций, JIT. НКА (где‑то внутри есть ДКА, но в биндингах не видел).

• RE2 — создана Google в 2010, используется в Sheets и др. ДКА. Есть много биндингов для всего.

• Rust Regex с биндингом flpc. ДКА. flpc cейчас архивирован.

• Regex. In-place замена Python re. Добавляет фичей.

Теперь можно посмотреть НКА и ДКА на реальных примерах. Чтобы показать разницу, посмотрим на максимально простом примере,  IP-адреса. И возьмём самый простой вариант, (\d+\.)+\d+ — матчит просто числа через точку.

Чётко видно, что ReDoS мы получили даже на примере, где его как будто и нет вовсе. Получается, проблема может быть специфична именно для одного движка.

Сделаем регулярку, наоборот, максимально точной: будем матчить только валидные адреса максимально простым способом. Например, таким:

x = (0|1|2|3|...|255)
(x\.){3}x

(выражение конструируется, но читается/валидируется максимально легко)

Очевидно, никаких катастрофических возвратов быть не может — пример явно лишний. Но всё-таки проверим:

Движки с ДКА (обозначены пунктиром) лежат гораздо ниже остальных. Почему так? Дело в том, что возвраты всё равно возникают, просто их не больше 255 на каждую группу. Это даёт ещё одну причину выбирать ДКА‑движки. Они могут быть медленнее, но производительность остаётся стабильной всегда.

Но это были совсем простые примеры, хочется чего‑то сложнее. Строим бенчмарк для движков! Хотя тут есть ряд оговорок. Как было показано выше, реально оценить тяжело — всё зависит от входных данных и параметров. Время компиляции паттернов минимально даже при наличии JIT, я его не учитывал. Также для тестирования использованы плохие и неудобные примеры — как раз те, что я нашёл при ручном анализе репозиториев.

Ниже графики перцентилей времени работы: чем линия ниже, тем лучше. ДКА движки показаны пунктиром.

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

Согласно бенчмарку, в лучших запусках re2 значительно уступает всем, кроме pcre2. А вот встроенный движок re очень плохо справляется с возвратами: в случае сомнений лучше его вообще не рассматривать. ДКА движки на втором графики сливаются вместе, и это ожидаемо — они нечувствительны к возвратам. regex справляется значительно лучше pcre2, классические движки по-разному уязвимы к возвратам. Быстрее всех, на удивление, оказался  flpc (rust-regex).

Как ещё стоит работать с регулярными выражениями?

• Если регулярки не приходят от пользователей, то достаточно их проверять.

• Сверхжадные модификаторы (++, *+; python 3.11+) всех спасут, так как блокируют возвраты.

• Возможно, лучше перейти на движки с ДКА. Для Python проще всего взять RE2: он может быть медленнее, но полностью защищает от попадания на ReDoS.

• Rust Regex очень‑очень хорош, но актуальных биндингов я не нашёл (flpc и rure мертвы?). Если нужно много производительности на Python, то 100% заслуживает внимания.

Где узнать больше?

Ресурсы для проверки и валидации

• Онлайн для быстрой проверки нескольких примеров вручную: https://makenowjust‑labs.github.io/recheck/playground/

• Regexploit — для проверки в одну команду. У меня потребовало доработки для запуска, но потом запустилось бодро: https://github.com/doyensec/regexploit 

• ReDoSHunter. Не самый удобный вариант (плохо подходит для прода), но похоже на state of the art. Шикарная статья: https://www.usenix.org/system/files/sec21-li‑yeting.pdf плюс репозиторий: https://github.com/yetingli/ReDoSHunter

Актуальные бенчмарки

• Хороший набор — можно сравнивать производительность между движками и языками более глубоко, а также на разных задачах: https://github.com/BurntSushi/rebar

Под спойлером PRы с фиксами, которые я сделал при подготовке. Также указана сложность регулярок.