Атака ReDoS на сервисы, неправильно использующие регулярные выражения, позволяет их замедлить или полностью вывести из строя. Она основана на проблеме регулярных выражений под названием catastrophic backtracking. Если ваш сервис проверяет данные с помощью регулярных выражений с catastrophic backtracking и без дополнительных проверок, то выполнение регулярного выражения может занять очень большое время.
import re
# Запустим выражение на строке из 20 символов a:
re.findall(r"(a+)+b", "a" * 20)
# Выполнилось за 0.07218690006993711
# Запустим выражение на строке из 30 символов a:
re.findall(r"(a+)+b", "a" * 30)
# Выполнилось за 75.4667053000303
# Прирост более чем в тысячу раз!!!
Если совпадений нет, то движок возвращается к предыдущим позициям, где снова начинает поиск. Движок регулярных выражений пытается сделать это много раз, пока не исследует все возможные пути.
Если к группе применён квантификатор и внутри этой группы используется ещё один квантификатор или |, то регулярное выражение может быть неконтролируемым.
(?:a+)+
([a-zA-Z_]+)*
(?:a|aa)+
(a|a?)+
- Переписать регулярное выражение - сократить количество квантификаторов и условий ИЛИ
- Перед использованием выражения проверять входные данные (например, не принимать слишком большой текст)
- Использовать специальные средства из модуля re
- Контролировать использование регулярного выражения (например, останавливать поиск, если он идёт слишком долго)
Если после жадного квантификатора поставить '+', то он станет притяжательным.
Притяжательные квантификаторы, как и жадные, пытаются найти максимально возможное количество вхождений. Но, в отличие от жадных квантификаторов, они не разрешают back-tracking, когда регулярное выражение не может найти совпадение.
Это значит, что движок не будет проходить огромное количество путей и закончит свою работу раньше, если совпадение не будет найдено.
Второе решение проблемы с catastrophic backtracking - атомарная группировка:
(?>regex)
Пытается найти вхождения regex, как если бы оно было отдельным регулярным выражением. Если совпадения найдены - движок регулярных выражений пытается найти совпадения для оставшейся части регулярного выражения, следующего после атомарной группировки. Если совпадений нет - движок регулярных выражения может откатиться назад только на место до атомарной группировки.
С помощью атомарной группировки можно сказать движку, что откатываться в этом месте и искать всевозможные пути не имеет смысла: внутри (?>regex) откат запрещён.