Регулярний вираз може виглядати нешкідливим, проходити всі звичайні тести й витрачати секунди або хвилини CPU на одному спеціально підібраному input. Це називають catastrophic backtracking. У backtracking engine проблема виникає, коли pattern створює багато можливих способів розділити той самий текст, а потім зазнає невдачі наприкінці й перевіряє варіанти один за одним.
Звичайний backtracking допомагає matching
Greedy quantifier спочатку споживає максимум. Якщо наступний token не збігається, engine відступає й пробує коротший варіант. Завдяки цьому гнучкий pattern може знайти правильну межу.
Небезпека з’являється, коли кілька вкладених або сусідніх частин здатні споживати ті самі символи. Кожна невдача породжує branches: можливо, outer repetition мав узяти менше, inner repetition — інакше, або alternative — розділити текст іншим способом. Кількість комбінацій може зростати експоненційно.
Класична неоднозначна форма
Pattern на кшталт (a+)+ ризикований, бо inner і outer plus можуть багатьма способами розділити послідовність a. Якщо далі очікується символ, якого немає, engine перевірить майже всі поділи перед остаточною відмовою.
У реальному коді проблема менш очевидна. Повторені group з optional whitespace, broad wildcard або overlapping alternatives створюють ту саму неоднозначність. Review повинен шукати структуру, а не лише відомий навчальний приклад.
Вибори повинні бути взаємовиключними
Швидкий pattern залишає engine мало рішень. Character class, що зупиняється на delimiter, зрозуміліший за repeated dot перед тим самим delimiter. Alternatives бажано починати різними символами, а quantifier — обмежувати реальним максимумом домену.
Atomic group і possessive quantifier можуть заборонити backtracking у engines, які їх підтримують. Але вони повинні виражати правильне рішення: після match ця частина ніколи не віддає символи назад. Це інструмент видалення неоднозначності, а не випадкова оптимізація.
Обмежуйте input до matching
Навіть хороший validator не повинен приймати необмежений текст. Якщо username має максимум 64 символи, довші значення відхиляють до складного regex. Size limit захищає parser, logs, storage та downstream systems.
Для документів і логів розгляньте line-by-line або streaming processing замість одного виразу над великим рядком. Менші одиниці знижують performance risk і випадковий match між записами.
Тестуйте невдалі near-match
Проблеми performance часто ховаються у ввідних даних, які майже збігаються. Створюйте довгі рядки з очікуваним prefix і неправильним останнім символом, повтореними separator та відсутнім terminator. Вимірюйте час зі зростанням довжини; nonlinear growth є сигналом небезпеки.
Automated tests можуть встановити практичну межу часу, хоча потребують tolerance для різних середовищ. Спеціалізований analyzer і fuzzing також знаходять неоднозначні конструкції.
Знайте свій regex engine
Не кожен engine використовує необмежений backtracking. Деякі гарантують linear-time behavior, відмовляючись від features, які потребують складнішого пошуку. Інші підтримують backreference і lookaround, але можуть мати pathological performance.
Pattern, безпечний в одному runtime, може бути ризиковим в іншому. Framework upgrade іноді змінює engine або defaults, тому важливі правила повинні мати behavior і performance tests.
ReDoS є ризиком застосунку
Якщо недовірений input потрапляє до вразливого pattern, нападник може зайняти worker thread або event loop невеликим запитом. Authentication, search, routing і validation endpoints особливо привабливі, бо доступні широко.
Mitigation поєднує безпечний дизайн pattern, input limits, timeout там, де він доступний, і isolation для дорогої обробки. Rate limit допомагає, але один надто дорогий request усе одно може зашкодити.
Production monitoring повинен бачити повільні match
Performance tests не охоплять усі реальні форми тексту. Інструментуйте незвично довгі виконання й пов’язуйте їх із назвою правила, не записуючи чутливий input. Зміна upstream data може відкрити неоднозначність, якої раніше не було.
Для high-traffic endpoint навіть невелике уповільнення одного match множиться на тисячі запитів. Regex latency варто розглядати як application metric, а не тільки локальну деталь.
Безпечна відмова важливіша за поблажливість
Коли pattern перевищує timeout або отримує надто довгий input, система повинна повернути контрольовану validation error, а не продовжувати часткову обробку. Неповний результат може бути помилково прийнятий як правильний.
Операційні метрики мають відрізняти звичайний non-match від захисної відмови через ресурсний ліміт. Це допомагає побачити атаку або невдалу зміну формату.
Аналізуйте складність до публікації
Під час review шукайте nested quantifiers, broad wildcard усередині repetition та alternatives зі спільним prefix. Ці форми не завжди небезпечні, але потребують доказу, що matching path обмежений. Спеціалізовані static analyzers можуть доповнити ручну перевірку.
Якщо безпеку pattern важко обґрунтувати, виберіть простішу конструкцію або engine з гарантованим linear time. Передбачувана продуктивність важливіша за підтримку рідкісної regex feature.
Обмеження повинні діяти на правильному рівні
Ліміт HTTP body не захищає від одного надто довгого поля всередині дозволеного запиту. Schema validation має обмежити конкретне значення до запуску regex. Для batch request потрібно обмежити також кількість елементів.
Кілька невеликих дорогих match можуть бути не менш небезпечними за один великий. Resource budget повинен враховувати весь endpoint, а не лише один виклик.
Timeout обмежує шкоду, але не виправляє pattern
Деякі платформи дозволяють встановити execution timeout. Це корисний defense in depth: один match не займає worker безкінечно. Timeout має завершуватися контрольованою помилкою й telemetry, а не автоматичним повтором того самого pattern.
Часті timeout означають, що потрібно змінити pattern, input limits або engine. Вони не роблять неоднозначну конструкцію ефективною.
Matching path має бути очевидним
Надійний pattern виражає чіткі межі й майже не залишає engine причин переглядати поділ тексту. Якщо потрібне довге пояснення, чому вкладені repetitions не overlap, regex краще спростити або замінити parser-ом.
Catastrophic backtracking можна уникнути, якщо тестувати hostile failures і розуміти неоднозначність. Regex залишається потужним інструментом, але як будь-яка виконувана мова потребує performance-aware дизайну на недовіреній межі.