Написання ReDoS-безпечних шаблонів

ReDoS (регулярний вираз відмова в обслуговуванні) – це клас атак, де ретельно створений вхідний сигнал робить час збігу регулярного виразу розбитим. Механізм JS використовує зворотне відстеження: якщо шаблон «неоднозначний», на an невдалий вхід він може виконати експоненціальну кількість спроб.

Класична катастрофічна модель

Pattern: ^(a+)+$
Input:   "aaaaaaaaaaaaaaaaaaaaab"

Щоб зіставити, механізм намагається кожне можливе розділення "a" між ними два квантори +. На 20 "а" це 2^20 = ~1 мільйон спроб. На 30 «а» мільярд.

Інші небезпечні приклади:

• (a*)*b -- "вкладені зірочки".
• (a|a)* -- альтернативи, що збігаються.
• (\w+)+@ -- жадібні групи із зовнішнім квантором.

Як помітити небезпеку

Шукайте такі структури:

1. Квантор всередині квантифікатора: (...+)+, (...*)*, (...{n,})+.
2. Альтернативи, що збігаються під квантором: (a|ab)*, (\w|\d)+.
3. Огляд вперед/позаду зі складними альтернативами повторюється.

Захисне переписування

Dangerous:  ^(\w+\s+)+$
Safe:       ^(?:\w+\s+)*\w+$

Безпечна версія відокремлює базовий випадок від повторюваного, видаляючи неоднозначність. Інші техніки:

• Присвійні квантифікатори (a++) -- не підтримуються в JS, але доступні в інших механізмах.
• Атомарні шаблони ((?>...)) -- не в JS.
• Обмежте довжину вхідних даних перед відповідністю.
• Тайм-аут під час відповідності (редактор цього курсу використовує воркер із тайм-аутом 500 мс).

Рекомендації щодо ReDoS-безпечних шаблонів

1. Переконайтеся, що варіанти чергування є взаємовиключними (наприклад, не використовуйте (a|a+)).
2. Уникайте застосування вкладених кванторів до виразів, що накладаються (наприклад, (\\s*)*).
3. Завжди віддавайте перевагу конкретним запереченим класам символів ([^\\n]*) над загальною крапкою підстановки (.*).

Спробуйте

Повторна вправа

Додатковий виклик