Еще раз о регекспах, бэктрекинге и том, как можно положить на лопатки JVM двумя строками «безобидного» кода

Раннее утро, десятая чашка кофе, безуспешные попытки понять почему ваше клиентское (или еще хуже – серверное) java-приложение намертво зависло при вычислении простого регекспа на небольшой строке… Если подобная ситуация уже возникала в вашей жизни, вы уже наверняка знаете про бэктрекинг и темную сторону регулярных выражений. Остальным – добро пожаловать под кат!

Бэктрекинг, или вечное ожидание результата

Проблема бэктрекинга при матчинге регулярных выражений уже неоднократно поднималась в различных статьях на хабре (раз, два, три), поэтому опишем ее суть без погружения в детали. Рассмотрим простой синтетический пример – типичный экземпляр из так называемых "evil regexes" (аналог изначально представлен тут):

@Test
public void testRegexJDK8Only() {
  final Pattern pattern = Pattern.compile("(0*)*1");
  Assert.assertFalse(pattern.matcher("0000000000000000000000000000000000000000").matches());
}

Напомню: символ * в регулярных выражениях ("ноль или несколько символов") называется квантификатором. Им же являются такие символы, как ?, +, {n} (n – количество повторений группы или символа).

Если запустить код на JDK8 (почему на более актуальных версиях воспроизводиться не будет – опишем далее), то JVM будет очень долго вычислять результат работы метода matches(). Едва ли вам удастся его дождаться, не состарившись на несколько месяцев или даже лет.

Что же пошло не так? Стандартная реализация Pattern/Matcher из пакета java.util.regex будет искать решение из теста следующим образом:

1. * - жадный квантификатор, поскольку всегда будет пытаться захватить в себе как можно большее количество символов. Так, в нашем случае группа (0) захватит полностью всю строку, звезда снаружи группы увидит, что может повториться ровно один раз, а единицы в строке не окажется. Первая проверка на соответствие провалилась.

2. Произведем откат (backtrack) к начальному состоянию. Мы попытались захватить максимальную группу из нулей и нас ждал провал; давайте теперь возьмём на один нолик меньше. Тогда группа (0) захватит все нули без одного, снаружи группы укажет на наличие единственной группы, а оставшийся ноль не равен единице. Снова провал.

3.  Снова откатываемся к начальному состоянию и забираем группой (0) все нули без двух последних. Но ведь оставшиеся два нуля тоже могут заматчиться группой (0)! И теперь эта группа тоже попытается сначала захватить два нуля, после чего попытается взять один ноль, и после этого произойдет откат и попытка матчинга строки уже без трех нулей.

Легко догадаться, что по мере уменьшения "начальной" жадной группы будет появляться множество вариаций соседних групп (0), которые также придется откатывать и проверять все большее количество комбинаций. Сложность будет расти экспоненциально; при наличии достаточного количества нулей в строке – прямо как в нашем примере – возникнет так называемый катастрофический бэктрекинг, который и приведет к печальным последствиям.

"Но ведь пример абсолютно синтетический! А в жизни так бывает?" - резонно спросите вы. Ответ вполне ожидаем: бывает, и очень часто. Например, для решения бизнес-задачи программисту необходимо составить регулярку, проверяющую, что в строке есть не более 10 слов, разделенных пробелами и знаками препинания. Не заморачиваясь с аккуратным созданием регекспа, на свет может появиться следующий код:

@Test
public void testRegexAnyJDK() {
	final Pattern pattern = Pattern.compile("([A-Za-z,.!?]+( |\\-|\\')?){1,10}");
  Assert.assertFalse(pattern.matcher("scUojcUOWpBImlSBLxoCTfWxGPvaNhczGpvxsiqagxdHPNTTeqkoOeL3FlxKROMrMzJDf7rvgvSc72kQ").matches());
}

Представленная тестовая строка имеет длину 80 символов и сгенерирована случайным образом. Она не заставит JVM на JDK8+ работать вечно – всего лишь около 30 минут – но этого уже достаточно, чтобы нанести вашему приложению существенный вред. В случае разработки серверных приложений риск многократно увеличивается из-за возможности проведения ReDoS-атак. Причиной же подобного поведения, как и в первом примере, является бэктрекинг, а именно – сочетание квантификаторов "+" внутри группы и "{1,10}" – снаружи.

Война с бэктрекингом или с разработчиками Java SDK?

Чем запутаннее паттерн, тем сложнее для неопытного человека увидеть проблемы в регулярном выражении. Причем речь сейчас идет вовсе не о внешних пользователях, использующих ваше ПО, а о разработчиках. Так, с конца нулевых было создано значительное количество тикетов с жалобой на бесконечно работающий матчинг. Несколько примеров: JDK-5026912, JDK-7006761, JDK-8139263. Реже можно встретить жалобы на StackOverflowError, который тоже типичен при проведении матчинга (JDK-5050507). Все подобные баги закрывались с одними и теми же формулировками: "неэффективный регексп", "катастрофический бектрекинг", "не является багом". 

Альтернативным предложением сообщества в ответ на невозможность "починить" алгоритм было внедрение таймаута при применении регулярного выражения или другого способа остановить матчинг, если тот выполняется слишком долго. Подобный подход можно относительно легко реализовать самостоятельно (например, часто его можно встретить на сервисах для проверки регулярных выражений - таких как этот), но предложение реализации таймаута в API java.util.regex также неоднократно выдвигалось и к разработчикам JDK (тикеты JDK-8234713, JDK-8054028, JDK-7178072). Первый тикет все еще не имеет исполнителя; два остальных были закрыты, поскольку "правильным решением будет улучшить реализацию, которая лучше справляется с кейсами, в которых наблюдается деградация" (пруф). 

Доработки алгоритма действительно происходили. Так, в JDK9 реализовано следующее улучшение: каждый раз, когда применяется жадный квантификатор, не соответствующий данным для проверки, выставляется курсор, указывающий на позицию в проверяемом выражении. При повторной проверке после отката достаточно убедиться, что если для текущей позиции проверка уже была провалена, продолжение текущего подхода лишено смысла и проводиться не будет (JDK-6328855, пояснение). Это позволило исключить бесконечный матчинг в тесте testRegexJDK8Only() начиная с версии jdk9-b119, однако второй тест вызывает задержки вне зависимости от версии JDK. Более того, при наличии обратных ссылок в регулярных выражениях оптимизация не используется.

Опасный враг: внешнее управление

Публикации, упомянутые в самом начале статьи, отлично раскрывают варианты оптимизации регулярных выражений, в результате чего катастрофический бектрекинг перестает быть опасным врагом; для сложных случаев потребуется дополнительная экспертиза, но в целом регулярное выражение можно почти всегда записать "безопасным" образом. Да и проверить себя тоже можно, например, на npmjs.com. Проблема остается при составлении очень сложных регулярок, а также в тех сценариях, когда регулярное выражение задается не программистом, а аналитиком, заказчиком после передачи решения, или же пользователем. В последнем случае управление сложностью регулярного выражения оказывается снаружи – и вам придется позаботиться о том, чтобы при любых условиях приложение продолжало корректную работу.

Использование стандартной библиотеки в таком случае, очевидно, не лучший выбор. К счастью, существуют сторонние фреймворки, позволяющие производить матчинг за линейное время. Одним из таких фреймворков является RE2, под капотом которого используется DFA - подход. Не будем вдаваться в детали реализации и подробно описывать разницу подходов; отметим лишь его растущую популярность – RE2 используется как дефолтный движок в Rust, а также активно применяется во множестве продуктов экосистемы Google. Для JDK7+ существует RE2/J, которая является прямым портом из C++ - версии библиотеки.

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

RE2/J - серебряная пуля?

Может показаться, что переход на RE2/J – отличный выбор практически для каждого проекта. Какова цена линейного времени выполнения?

• У RE2/J отсутствует ряд методов API у Matcher;

• Синтаксис регулярных выражений совпадает не полностью (у RE2/J отствутет часть конструкций, в том числе – обратные ссылки, backreferences). Вполне вероятно, после замены импорта ваша регулярка перестанет корректно распознаваться;

• Несмотря на то, что формально код принадлежит Google, библиотека не является официальной, а основным ее мейнтейнером является единственный разработчик – Джеймс Ринг.

• Разработчик фреймворка подчеркивает: "Основная задача RE2/J заключается в обеспечении линейного времени выполнения матчинга при наличии регулярных выражений от внешних источников. Если все регулярные выражения находятся под контролем разработчика, вероятно, использование java.util.regex является лучшим выбором".

Надеюсь, этих пунктов достаточно, чтобы убедиться: RE2/J – не серебряная пуля; фреймворк не является бескомпромиссным решением для проверки на соответствие регулярным выражениям. Реализация при создании кода повлечет ограниченный функционал, а прямая замена импорта в уже существующем коде может негативно сказаться на стабильности работы приложения.

Итоги

1. Даже простые регулярные выражения при невнимательном написании могут сделать ваш продукт уязвимым для ReDoS.

2. Движков регулярных выражений, которые были бы одновременно максимально функциональны, быстры и стабильны, не существует.

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

Если возможность самостоятельно задавать регулярное выражение есть не только у разработчика, то стоит реализовать защиту от вечной проверки с помощью создания таймаута или использования сторонних решений, позволяющих решать задачу матчинга за линейное время – например, таких, как RE2/J.