Написание шаблонов, безопасных для ReDoS.

ReDoS (отказ в обслуживании по регулярному выражению) — это класс атак, при которых тщательно обработанные входные данные приводят к взрыву времени сопоставления регулярного выражения. Движок JS использует обратное отслеживание: если шаблон «неоднозначен», на неудачный ввод, он может выполнить экспоненциальное количество попыток.

Классический катастрофический образец

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

Для сопоставления движок пытается все возможные разделы «а» между два квантора +. Для 20 "a" это 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]*), а не общей подстановочной точке (.*).

Попробуйте это

Обзор упражнения

Дополнительная задача