Долг по регулярному выражению

20 июля 2016 года Stack Overflow перестал отвечать. Внутри инцидента не было ни DDoS, ни упавшей базы, ни кривого деплоя. Виноват оказался один-единственный пост на сайте, в самом конце которого кто-то оставил двадцать тысяч пробелов и одну непробельную букву. Этого хватило, чтобы серверы ушли в полку.

Звучит как байка из жанра «сегодня я узнал». Но за этой комической миниатюрой стоит история длиной в полвека и стоимостью в сотни уязвимостей. Оптимальный алгоритм для регулярных выражений был известен ещё с 1968 года. Индустрия от него отказалась. Сегодня мы расплачиваемся.

С чего всё начиналось: математик, изучавший нервы

Регулярные выражения родились не в редакторе. Они родились в работе, которая называлась «Representation of Events in Nerve Nets and Finite Automata» и вышла в 1951 году. Автор — Стивен Клини, ученик Алонзо Чёрча и один из отцов теории рекурсивных функций. Клини придумал понятие регулярных множеств, чтобы описать, какие последовательности «событий» способны различить идеализированные нейроны.

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

Но в любом случае никаких практических задач у регулярных выражений тогда не предполагалось. Это была чистая математика с автоматами, и существовала она в довольно узком круге людей, которые читают журналы вроде «Annals of Mathematics Studies» добровольно.

Кен Томпсон: «у меня тут редактор лежит»

Через семнадцать лет, в 1968-м, Кен Томпсон публикует в Communications of the ACM скромную трёхстраничную статью «Regular Expression Search Algorithm». В ней он объясняет, как взять выражение Клини, скомпилировать его в недетерминированный конечный автомат и симулировать так, чтобы получалось линейное время. O(m × n), где m это размер паттерна, а n длина строки. Никаких сюрпризов, никаких патологических случаев, ничего лишнего.

Параллельно Томпсон встроил алгоритм в текстовый редактор ed. Тот самый, из которого позже выделится и заживёт своей жизнью команда g/re/p. У Томпсона вообще была привычка делать вещи, которые потом будут жить десятилетиями: операционная система, язык, кодировка, та самая теорема о компиляторах с трояном. Регулярные выражения в этой коллекции скромно стоят в углу. Но именно они в итоге проникнут в каждый язык программирования и в каждый текстовый редактор на свете.

Тихий период: Пайк, Лаурикари и подсчёт скобок

В начале 1980-х Роб Пайк, тогда ещё работавший в Bell Labs, писал редактор sam и столкнулся с нюансом. Алгоритм Томпсона прекрасно отвечает на вопрос «совпадает или нет», но плохо помогает с вопросом «где именно совпала вот эта группа в скобках?». Пайк аккуратно расширил автоматную симуляцию так, чтобы она параллельно с матчингом отслеживала границы захваченных подвыражений.

В 1999 году финский инженер Виль Лаурикари независимо переоткрыл то же самое и наконец оформил всё в виде формальной теории. Получился алгоритм, который сегодня называют TNFA. Он по-прежнему работает за линейное время и при этом умеет возвращать группы.

Запомните этот момент: решение существовало, было опубликовано, было реализовано. Дальше начинается грустная часть.

Ларри Уолл и большой обмен

В 1987 году Ларри Уолл, лингвист по образованию, выпустил Perl. Его подход к языку был чисто прагматическим: он не пытался быть красивым, он пытался решать задачи системного администратора так, чтобы скрипт умещался на одной странице. К регулярным выражениям Уолл относился как к синтаксической песочнице. Чем больше можно навертеть, тем лучше.

К Perl 4 (1991 год), и особенно к Perl 5, в выражениях появились вещи, которых в академическом мире не существовало как класса. Обратные ссылки \1. Опережающие проверки (?=...). Ретроспективные проверки (?<=...). Жадные и ленивые квантификаторы. Условные подвыражения. Рекурсивные паттерны. Целая экосистема внутри одной строки.

Проблема в том, что половину этого нельзя реализовать на конечном автомате. Не потому, что лень, а потому, что задача сопоставления с обратными ссылками формально NP-полная. Это математика, спорить не о чем.

Поэтому Уолл и его наследники сделали единственное, что могли. Они выкинули алгоритм Томпсона и переписали движок на бэктрекинге.

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

В regex-движке это выглядит так. Паттерн a+b на строке aaab пробует «съесть» как можно больше a, потом смотрит, есть ли дальше b. Если нет, отдаёт одну a обратно и проверяет снова. И так пока не сойдётся или пока варианты не кончатся. На обычных строках это работает быстро. На злых строках количество вариантов на каждом уровне растёт по экспоненте, перебор уходит в космос и не возвращается.

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

Получился размен в духе «отдадим скорость и безопасность, возьмём способов поиска побольше». Индустрии понравилось.

Генри Спенсер и «но я же не специально»

Чтобы понять, как именно perl-овая модель расползлась по миру, надо упомянуть Генри Спенсера. В середине 1980-х Спенсер, добрый и честный программист из Университета Торонто, написал свободную реализацию regex.h для восьмой редакции Unix. Без злого умысла, просто чтобы существовало. На бэктрекинге, потому что иначе ему было трудно поддерживать совместимость с уже разросшимися расширениями Уолла.

Эта библиотека разошлась широко. В той или иной форме её код лёг в основу движков Perl, Python, Ruby, Java, JavaScript и в библиотеку PCRE, которую потом подхватили буквально все. Ирония в том, что Спенсер потом сам признавал: реализация получилась простой, но не той, которую стоило класть в основу языков. Но было поздно.

К началу нулевых стандартом de facto стал бэктрекинговый движок с perl-совместимым синтаксисом. Алгоритм Томпсона остался жить в учебниках по теории формальных языков, и почти нигде больше.

ReDoS: тихая бомба под половиной интернета

Теперь вернёмся к Stack Overflow и двадцати тысячам пробелов. Феномен, в который упёрся сайт, называется catastrophic backtracking. Ему даже отдельное название придумали, потому что встречается часто.

Возьмём паттерн ^(a+)+$ и строку из двадцати пяти букв a плюс восклицательный знак на конце. Автоматный движок честно пройдёт строку слева направо, не найдёт совпадения, ответит «нет» примерно за двадцать пять шагов. Бэктрекинговый движок начнёт перебирать все возможные способы разбить эти двадцать пять a на группы. Способов 2^24, около шестнадцати миллионов. На тридцати символах будет миллиард. На тридцати пяти — тридцать миллиардов.

Атака, использующая это поведение, называется ReDoS, Regular Expression Denial of Service. И самое неприятное в ней даже не математика, а то, насколько она универсальна. Регулярные выражения сегодня применяются везде:

• валидация email-адресов в форме регистрации;
• маршрутизация HTTP-запросов в веб-фреймворке;
• парсинг логов;
• правила WAF;
• подсветка синтаксиса в редакторе.

Любая из этих точек способна оказаться вектором атаки, если разработчик не подумал о патологических входах. А он, как правило, не подумал.

Ещё в 2003 году Скотт Кросби и Дэн Уоллах опубликовали статью «Denial of Service via Algorithmic Complexity Attacks», в которой формально предсказали целый класс атак на сложность алгоритмов. Регулярные выражения там фигурировали как один из ярких примеров. Но даже двадцать с лишним лет спустя индустрия всё ещё реагирует на отдельные инциденты так, будто это сюрприз.

Парад уязвимостей

CVE по этой теме идут плотным потоком. Если выписать только ярких представителей последних лет, получается небольшая хроника:

• Stack Overflow, июль 2016. Подсветка кода в комментариях нашла свой пробельный Чернобыль. Тот самый инцидент, с которого начался пост.
• Cloudflare, июль 2019. WAF-правило с параметрической бомбой положило мировую CDN на 27 минут.
• CVE-2024-21538, cross-spawn. Маленький утилитарный модуль, который тащит за собой почти любой Node.js-проект. Крафтовая строка, и процесс встаёт колом. Чинят в 6.0.6 и 7.0.5.
• CVE-2025-69873, ajv. Валидатор JSON Schema подставлял паттерны из схем прямо в RegExp(). 31 байт пейлоада блокировали CPU на 44 секунды, каждый дополнительный символ удваивал время.
• CVE-2026-26996, minimatch. Звёздочка в шаблоне имени файла, помноженная на саму себя, кладёт обработку glob-паттернов.

Репозиторий awesome-redos-security собирает ReDoS-паттерны. Их там сотни, без преувеличения.

Два мира

Чтобы поговорить о решении, надо признать, что регулярные выражения сегодня живут в двух непересекающихся вселенных.

Автоматные движки безопасны, но за это берут цену. Они не умеют в обратные ссылки, потому что задача NP-полная, и упрощений тут не предвидится. Lookaround в них либо отсутствует, либо разрешён в ограниченном виде. Зато их время не зависит от изобретательности атакующего.

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

Языки и их выбор

Самое интересное произошло в последние пятнадцать лет, когда новые языки начали открыто пересматривать решение, принятое индустрией по умолчанию.

Go в стандартной библиотеке тащит пакет regexp с синтаксисом RE2. Это сознательное решение Расса Кокса, который в 2010 году открыл RE2 ещё в Google, а потом перенёс ту же философию в стандарт Go. Никаких обратных ссылок, никаких lookaround. Линейное время гарантировано спецификацией. Если вам мало, есть сторонние пакеты, но в них надо лезть осознанно, и решение это документируется как «я понимаю, что делаю».

Rust идёт тем же путём. Крейт regex от Эндрю Галланта (того самого, что написал ripgrep) автоматный по умолчанию. Есть fancy-regex, который комбинирует автоматный движок с бэктрекингом для редких случаев, но это явный отдельный выбор разработчика, а не дефолт.

Zig поступил радикально. В стандартной библиотеке регулярных выражений просто нет. Эндрю Келли, автор языка, считает, что для большинства задач хватает парсер-комбинаторов и comptime-парсинга, а regex слишком специальный инструмент, чтобы класть его в стандарт. Если очень надо, есть биндинги к PCRE2 или к чему-то RE2-подобному.

Nim даёт пример обратного выбора. В стандартной библиотеке у него есть модуль re, и это обёртка над PCRE со всеми её прелестями: бэктрекинг, обратные ссылки, lookaround и риск ReDoS из коробки. Зато в экосистеме лежит пакет regex от Эстебана Кастро Борсани (@nitely), который написан полностью на Nim, использует NFA/DFA и гарантирует линейное время. Получается зеркальная картина по сравнению с Go: безопасный движок существует и работает отлично, но за ним надо осознанно сходить на nimble. Дефолт по-прежнему ReDoS-уязвимый.

.NET 7 в 2022 году сделал самое любопытное движение. Microsoft добавила режим RegexOptions.NonBacktracking. По одному и тому же API. Хотите безопасности, передаёте флаг, и движок переключается на автоматную реализацию. Хотите backreferences, не передавайте, остаётся старая семантика. Это первый случай в большом мейнстримном языке, когда выбор отдан пользователю осознанно, на уровне опции, а не отдельной библиотеки.

JavaScript живёт по принципу «и хочется, и колется». ECMAScript-движки бэктрекинговые, и это не изменится из-за обратной совместимости. V8 относительно недавно добавил экспериментальный режим, в котором регулярка прекомпилируется в граф, похожий на томпсоновский, но включается он только для совместимого подмножества. Это лучше, чем ничего, и хуже, чем дефолт.

Python до сих пор живёт со стандартным re, который бэктрекинговый. Есть сторонний пакет regex, есть биндинги к RE2, есть гордые попытки портировать. На уровне языка не меняется ничего уже двадцать лет.

Если хочется потрогать руками, рядом с этим постом лежат маленькие демо: regex_demo.go с честным regexp из stdlib, regex_demo.rs и regex_demo.zig с ручным NFA для a*b, и regex_demo.nim, где ReDoS на стандартном re показан вживую: достаточно увеличить N с 20 до 30, чтобы разница стала наглядной.

Что с этим делать в реальной жизни

Если вы пишете код и принимаете на вход что-то от пользователя, есть несколько вариантов поведения.

Первый и самый простой. Используйте язык, в котором стандартный движок автоматный. Если вы пишете на Go или Rust, считайте, что эту проблему вы уже решили самим выбором языка.

Второй. Если вы на Java, Python, JavaScript или Ruby, прежде чем писать RegExp(userInput), остановитесь и подумайте, действительно ли пользователь должен задавать паттерн. В 90 % случаев должен задаваться кусок данных, а не сам паттерн. Эти случаи нужно разделять архитектурно, а не надеяться на интуицию.

Третий. Прогоняйте свои паттерны через статический анализатор. Инструменты вроде recheck, safe-regex и vuln-regex-detector находят вложенные квантификаторы и альтернации с перекрытием автоматически. Это пять минут в CI и спокойный сон.

Четвёртый. Уберите вложенные квантификаторы там, где они появились случайно. Паттерн (a+)+ почти всегда переписывается в a+. Паттерн (.*a)+ обычно превращается в [^a]*a([^a]*a)*. Получается некрасиво, зато безопасно.

Пятый, неожиданный. Подумайте, нужны ли вам тут вообще регулярные выражения. strings.Contains(s, "ERROR") в Go и if "ERROR" in s в Python работают за линейное время, читаются мгновенно и не имеют патологических случаев. Регулярка нужна, когда у вас и правда нерегулярная задача. Большинство существующих регулярок в кодовой базе среднего проекта эту проверку не проходят.

Послесловие, чуть-чуть с горечью

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

Хорошая новость в том, что знание никуда не делось. RE2, Go regexp, Rust regex, RE/flex, .NET NonBacktracking. Алгоритм Томпсона жив, работает и доступен. Чтобы он стал дефолтом, надо принять, что некоторые удобные конструкции придётся отдать обратно. Звучит как небольшая цена за то, чтобы случайный пост из двадцати тысяч пробелов больше не клал ваш сервис.

Источники

• Stephen Kleene, «Representation of Events in Nerve Nets and Finite Automata» (1951), оригинальная работа о регулярных множествах.
• Ken Thompson, «Regular Expression Search Algorithm» (1968), та самая статья.
• Russ Cox, «Regular Expression Matching Can Be Simple And Fast» (2007), классический разбор разницы между автоматным движком и бэктрекингом.
• Russ Cox, «Regular Expression Matching: the Virtual Machine Approach», описание Pike VM.
• Ville Laurikari, «NFAs with Tagged Transitions» (2000), формальное обоснование TNFA.
• Crosby, Wallach, «Denial of Service via Algorithmic Complexity Attacks» (2003), предсказание атак на сложность.
• Stack Overflow Outage Postmortem (July 20, 2016), первоисточник истории про двадцать тысяч пробелов.
• Details of the Cloudflare outage on July 2, 2019, 27 минут офлайна из-за одной регулярки.
• OWASP: Regular Expression Denial of Service, общий обзор ReDoS.
• awesome-redos-security, коллекция CVE.
• RE2 (Google), автоматный движок.
• .NET NonBacktracking Regex, автоматный режим в .NET 7.
• Rust regex crate.
• Go regexp package.
• Nim stdlib re module, обёртка над PCRE и тот самый небезопасный дефолт.
• nitely/nim-regex, пакет с автоматным движком и линейным временем для Nim.