Катастрофический откат

Катастрофический откат — это явление в регулярных выражениях, при котором движок тратит непомерно много времени на проверку определённых паттернов, что приводит к значительной деградации производительности — иногда счёт идёт на секунды, минуты или вычисление не завершается вовсе. Это происходит потому, что движок пытается сопоставить части строки множеством разных способов, прежде чем сдаться, а число комбинаций растёт экспоненциально с увеличением длины входных данных.

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

Почему это важно: Одно медленное регулярное выражение, применённое к пользовательскому вводу, — это реальный вектор атаки типа «отказ в обслуживании» (часто называемой «ReDoS»). Злоумышленнику достаточно отправить короткую строку, специально созданную для максимизации отката, чтобы заморозить цикл событий Node.js.

Что вызывает катастрофический откат?

Катастрофический откат обычно возникает при вложенных квантификаторах — когда квантификатор находится внутри группы, которая сама квантифицирована, например (a+)+. Опасность проявляется, когда две части паттерна могут сопоставлять одни и те же символы, и движок располагает множеством перекрывающихся способов разбить входные данные. Когда сопоставление в итоге завершается неудачей, движок вынужден перебрать все возможные разбиения, прежде чем сделать вывод об отсутствии совпадения. Вот классический пример:

Если на вашем компьютере это не занимает много времени, добавьте ещё один символ a в строку str. Так почему же это требует столько времени? Давайте разберём. Паттерн /^(a+)+$/ состоит из:

• ^ — проверяет позицию в начале строки.
• (a+) — сопоставляет один или более символов a.
• + — позволяет предыдущей группе (a+) повторяться один или более раз.
• $ — проверяет позицию в конце строки.

Процесс сопоставления выглядит так:

1. Начальное сопоставление: движок начинает с начала строки (^).
2. Сопоставление первой группы: движок сопоставляет первый a+, поглощая все символы a (aaa...).
3. Внешний квантификатор: внешний + позволяет движку повторять группу (a+).

Когда движок достигает восклицательного знака (!), он не может сопоставить его с паттерном, и сопоставление завершается неудачей. В этот момент начинается откат:

1. Попытка отката: движок выполняет откат, многократно перераспределяя сопоставленные символы a между внутренним квантификатором a+ и внешним +. Он повторно проверяет каждое разбиение, пытаясь найти такое, при котором паттерн совпадёт до конца строки.
2. Экспоненциальный рост: этот процесс отката может расти экспоненциально, поскольку движок перебирает все возможные способы разбить строку из символов a на группы, потенциально удовлетворяющие паттерну (a+)+.

Для строки из n символов a внутренний a+ и внешний + могут разбить эти символы на группы примерно 2^(n-1) способами. Когда завершающий ! приводит к неудаче сопоставления, движок вынужден перебрать все эти способы. Вот почему добавление одного лишнего символа a примерно удваивает время выполнения — это отличительный признак экспоненциального взрыва. Сопоставление ниже завершается быстро, поскольку нет неудачного хвоста, который вынуждал бы исчерпывающий перебор:

Вывод: катастрофический откат проявляется только тогда, когда паттерн может сопоставиться множеством способов и итоговое сопоставление в конечном счёте завершается неудачей. Специально созданный неудачный ввод — это именно то, что отправляет злоумышленник.

Выявление паттернов, склонных к катастрофическому откату

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

• Вложенные квантификаторы, например (a+)+, (\d*)*, (\w+)*.
• Квантифицированные группы с альтернацией, у которой есть перекрытие, например (a|a)+ или (\w|\d)+ (\w уже включает \d).
• Жадный .* или .+ между двумя частями, которые также могут сопоставлять одинаковые символы, например <.+>.*<.+>.
• Незаякоренные паттерны на длинных входных данных, которые повторно пробуют сопоставление с каждой стартовой позиции.

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

Стратегии предотвращения катастрофического отката

Цель каждого из приведённых ниже исправлений одна: устранить неоднозначность, которая позволяет движку разбивать входные данные более чем одним способом. Замена жадных квантификаторов на ленивые (+?, *?) не помогает — оба варианта перебирают все разбиения; ленивый лишь проходит их в другом порядке. Нужно изменить структуру паттерна, а не его жадность.

1. Устраните вложенный квантификатор

(a+)+ почти всегда эквивалентен одиночному квантификатору. Если вам нужно «один или более символов a», просто напишите a+. Для этого существует ровно один способ сопоставления, поэтому движок не может откатиться в комбинаторный взрыв.

2. Эмулируйте атомарную группу через опережающую проверку

В JavaScript отсутствуют встроенные атомарные группы (?>...) и притяжательные квантификаторы (a++), как в некоторых других реализациях регулярных выражений. Воспроизвести то же поведение «сопоставь один раз и не отдавай обратно» можно с помощью опережающей проверки и обратной ссылки: (?=(a+))\1. Опережающая проверка жадно сопоставляет a+, захватывает его, а \1 потребляет ровно этот текст — но поскольку захватывающая группа находилась внутри опережающей проверки, движок не будет перераспределять её при откате.

3. Используйте точные, непересекающиеся классы символов

Откат взрывается, когда соседние части паттерна могут сопоставлять одни и те же символы. Сделайте так, чтобы каждая часть сопоставляла отдельное множество символов, — тогда существует только один способ разбить входные данные. Например, предпочтите \d+\.\d+ вместо [\d.]+\.[\d.]+, где обе группы [\d.]+ конкурируют за одну и ту же точку.

4. Добавьте якоря и ограничьте паттерн

Якорение с помощью ^ и $ позволяет движку быстро завершить поиск неудачей вместо повторных попыток с каждой позиции строки. Явное верхнее ограничение квантификатора (a{1,20} вместо a+) ограничивает объём работы, который может породить одно повторение.

Практические примеры и решения

Пример 1: Сопоставление вложенных HTML-тегов

Частый сценарий применения регулярных выражений — сопоставление вложенных HTML-тегов, которое при неаккуратном подходе легко приводит к катастрофическому откату. Примечание: регулярные выражения в целом не подходят для разбора произвольных или глубоко вложенных HTML-структур; для сложных документов используйте полноценный HTML-парсер.

Проблемный паттерн

Улучшенный паттерн

Замените жадный .* (который может поглотить весь документ и затем медленно отступать) на класс, который не может пересечь закрывающую угловую скобку. [^<]* сопоставляет всё вплоть до следующего <, поэтому нет никакого перекрытия для отката.

Пример 2: Валидация списка идентификаторов

Проблемный паттерн

([a-zA-Z0-9_]+)+ — та же ловушка, что и (a+)+: внутренний + и внешний + оба повторяются по одним и тем же символам, поэтому длинные входные данные, для которых нет совпадения, вызывают экспоненциальный откат.

Безопасная альтернация

Не каждая квантифицированная группа опасна. (?:ab|cd)+e безопасна: ab и cd не пересекаются, поэтому движок никогда не сомневается в том, как разбил входные данные. Используйте незахватывающую группу (?:...), когда захваченный текст вам не нужен — она чуть быстрее и нагляднее, хотя и не меняет поведение отката в данном случае.

Заключение

Катастрофический откат способен заморозить JavaScript-приложение — и поскольку он провоцируется входными данными, это реальная угроза безопасности, а не просто проблема производительности. Решение почти всегда сводится к устранению неоднозначности: выравнивайте вложенные квантификаторы, делайте соседние части паттерна несовпадающими по наборам символов, используйте якоря ^/$, ограничивайте повторения или эмулируйте атомарную группу с помощью (?=(...))\1. Переход на ленивые квантификаторы не помогает.

Когда вы пишете регулярное выражение, которое применяется к недоверенным входным данным, проверяйте его на длинных неудачных строках (например, сотня символов a, за которой следует !) и следите за временем выполнения. Если добавление одного лишнего символа заметно увеличивает время, паттерн имеет экспоненциальную сложность и требует переработки.

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

Практика