JEP draft: Predictable regex performance

Проблема

Всё больше внимания уделяется производительности сопоставления с регулярными выражениями, и особенно её предсказуемости.

• атаки типа «отказ в обслуживании» через регулярные выражения настолько известны в отрасли, что для них появился термин ReDoS.
• веб-сайты часто предоставляют поиск по большим корпусам текстов с помощью регулярных выражений, которые задают пользователи, и наличие надёжно эффективного (т. е. O(N)) движка вычисления регулярных выражений может считаться строгим требованием. Именно это послужило толчком к созданию библиотеки re2, которую написал Russ Cox,.
• некоторые распространённые задачи разработки ПО на удивление трудно эффективно решить с помощью одного лишь регулярного выражения. Главный пример — обнаружение и удаление пробельных символов в конце строки: эта задача рассматривается в микробенчмарке, и именно она стала причиной знаменитого сбоя stackoverflow, вызванного \s+$.. Неверно, что тщательное составление регулярных выражений опытным инженером, например с использованием сверхжадных квантификаторов, может решить конкретную проблему производительности регулярного выражения.
• Использовать Matcher#find (вместо Matcher#matches) очень удобно, но это добавляет неявный цикл O(N) по входным данным или, что то же самое, не сверхжадный префикс «^.*?» в регулярном выражении. Чтобы вся операция поиска не была O(N^2), большинство операций сопоставления с регулярным выражением при сканировании входных данных должны выполняться за O(1), а для этого могут потребоваться менее очевидные конструкции, например ретроспективная проверка (lookbehind). Использования сверхжадных квантификаторов в самом регулярном выражении, к сожалению, недостаточно.

Текущая реализация (jdk16) — это движок с возвратами на основе NFA. Она смягчает, но не устраняет производительность O(2^N). Есть риск StackOverflowError.

Цели

Сделать возможным создание защищённого от ReDoS «движка поиска по регулярным выражениям», который может безопасно принимать регулярные выражения от пользователей и обеспечивает время выполнения O(N), использование стека O(1) и как можно более близкое к O(M) потребление памяти для скомпилированного регулярного выражения. Допустимо отказаться от некоторых возможностей регулярных выражений, например от обратных ссылок. Пользователи могут выбрать безопасность или выразительность: как обеспечить и то и другое, не знает никто. Разумеется, мы сохраняем совместимость — существующий API должен остаться небезопасным.

Возможные подходы

Библиотека re2 настойчиво продвигает построение движка регулярных выражений на основе DFA, и это гарантирует производительность сопоставления O(N) во время выполнения. Но DFA-движок не может поддерживать некоторые популярные возможности современных движков регулярных выражений, в частности обратные ссылки. Библиотека re2 просто не поддерживает такие возможности, и это разумное ограничение, когда регулярные выражения задают пользователи. Один из возможных путей развития API — добавить в Pattern.compile(String, int) флаг, который явно запрашивал бы производительность O(N) (или приводил бы к ошибке). Другой возможный путь развития API — разрешить альтернативные реализации Pattern и сделать так, чтобы большинство API Java SE, принимающих регулярное выражение в виде String, принимали на вход и Pattern.

Библиотека re2 была перенесена с C++ на другие языки:

• стандартная библиотека регулярных выражений golang.
• re2j — порт на Java, но он неполный, возможно, потому что j.u.regex прочно занимает это место.

Некоторые реализации библиотек — это тонкая обёртка над нативной re2:

• perl re::engine::RE2
• python re2
• re2-java (не поддерживается)

Обёртки над нативной re2 лучше работают в языках, отличных от java. Там такие обёртки привычнее, а распространённая в этих языках сборка мусора на основе подсчёта ссылок лучше справляется с быстрым освобождением ресурсов. Никто не хочет вызывать close() для своих объектов Pattern, когда они больше не нужны, чтобы освободить связанную с ними нативную память!

GNU grep, в производительность которого вложено много сил, реализует и DFA-, и NFA-движок и переходит на NFA, если регулярное выражение нельзя скомпилировать в DFA.

OpenJDK занялся проблемой экспоненциальной производительности O(2^N) в JDK-6328855, добавив мемоизацию предыдущих неудачных попыток сопоставления, и это смягчает большинство проблем экспоненциальной производительности, вызванных небрежно написанными регулярными выражениями, но:

• это неполное решение, и у пользователей нет гарантий производительности.
• оптимизация отключается при наличии обратных ссылок
• проблемы производительности O(N^2) остаются, как в случае Matcher#find

В Perl проблему решили, добавив управляющие глаголы возврата (Backtracking Control Verbs), с помощью которых очень опытный программист регулярных выражений может написать эффективную программу, но ценой привязки к модели выполнения с возвратами и без решения общей проблемы.

В современной Java есть invokedynamic и возможность создавать на JVM высокопроизводительные языки. Эти же приёмы можно применить и к языку регулярных выражений.

Оптимизированному DFA- или NFA-движку могут пойти на пользу value types из проекта Valhalla.

Хотя самая первая реализация регулярных выражений, созданная Ken Thompson, использовала эффективный DFA, большинство современных реализаций используют NFA с возвратами. Возможно, лучше всего было бы переработать все такие реализации и вернуться к DFA (где это возможно), но это огромный объём инженерной работы.

Помимо процессорного времени при выполнении, нужно учитывать и другие ресурсы:

• Пространство стека ограничено сильнее, чем пространство кучи, поэтому движки регулярных выражений не должны использовать O(N) памяти стека при сопоставлении группы с квантификатором, однако JDK-8260866 демонстрирует переполнение стека.
• Теоретический результат, обеспечивающий время сопоставления O(N), может требовать O(2^M) времени на компиляцию регулярного выражения, где M — длина регулярного выражения. Реальные DFA-движки могут проверять потребление ресурсов при компиляции или завершаться с ошибкой из-за исчерпания памяти. Мы не хотим, чтобы неиспользуемый Pattern занимал гигабайты кучи. Идеальной реализации, возможно, придётся искать баланс между ресурсами во время компиляции и во время выполнения.

Очень амбициозный проект sregex (тоже основанный на re2) заявляет:

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

но, по-видимому, он не завершён и не развивается.

Создать отличный движок сложно!