Що таке ReDoS і як регулярний вираз може покласти сервер?

ReDoS (Regular expression Denial of Service) - регулярний вираз, який на спеціально підібраному рядку працює експоненційно довго. Один запит займає процесор на секунди чи хвилини; кілька - і сервер не відповідає.

Причина - катастрофічний бектрекінг. Більшість рушіїв регулярних виразів (PCRE у PHP, рушій JavaScript) при невдачі повертаються й пробують інші варіанти розбиття рядка. Вкладені квантифікатори дають експоненційну кількість варіантів:

^(a+)+$         на рядку "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"
^(\w+\s?)*$     на довгому рядку слів із символом у кінці, що не підходить
^(a|aa)+$

Небезпечні ознаки: вкладений квантифікатор ((x+)+, (x*)*), перекриваючі альтернативи під квантифікатором ((a|a)*, (\w|\d)+), і рядок, який майже підходить, але ламається в кінці.

Де шукати в застосунку:

• власні правила валідації (regex: у Laravel), перевірки email, URL, телефонів;
• регулярні вирази з даних користувача (пошук за шаблоном) - найгірший варіант: зловмисник сам пише вираз;
• розбір логів, парсери вмісту, підсвітка синтаксису.

Як поводиться PHP: PCRE має ліміти pcre.backtrack_limit і JIT-стек. При перевищенні preg_match повертає false (не 0!), а preg_last_error() - PREG_BACKTRACK_LIMIT_ERROR. Це рятує від нескінченного зависання, але:

• до ліміту процесор усе одно працює;
• код, що перевіряє if (! preg_match(...)), сприйме false як «не підходить» - і в деяких випадках це обхід валідації.

Захист:

• переписувати вирази без неоднозначності: ^\w+(\s\w+)*$ замість ^(\w+\s?)*$, атомарні групи (?>...) і присвійні квантифікатори (a++), які забороняють повернення;
• обмежувати довжину вводу перед регулярним виразом - найпростіший і дуже ефективний захист;
• не приймати регулярні вирази від користувачів; якщо потрібно - рушій з лінійним часом (RE2) чи обмеження часу виконання;
• перевіряти preg_last_error() і трактувати false як помилку;
• готові валідатори (filter_var для email/URL, бібліотека libphonenumber) замість саморобних виразів;
• статичні аналізатори (наприклад, правила Semgrep, safe-regex для JS) знаходять небезпечні шаблони.

Node.js особливо вразливий: однопотоковий цикл подій - один повільний регулярний вираз блокує обробку всіх запитів.

Докладніше в документації: OWASP: ReDoS