Как вызвать Regex Denial-of-Service в PHP?

Question

Как я могу вызвать Regex-DOS с помощью функции preg_match() с использованием злого регулярного выражения (например, (a +) +)?

Например, я следующая ситуация:

preg_match('/(a+)+/',$input); 

Если у меня есть контроль над $input, как я мог бы вызвать DOS атаки или достичь предела возвращаться обратно из preg_* функций в PHP?

Как я могу сделать это со следующими выражениями?

([a-zA-Z]+)* 
(a|aa)+ 
(a|a?)+ 
(.*a){x} | for x > 10 

Answer 1

Там нет никакого способа, чтобы вызвать Redos на (a+)+, ([a-zA-Z]+)*, (a|aa)+, (a|a?)+, так как нет ничего, что может привести к отказу матча и запуск откаты после проблемных частей регулярного выражения.

Если изменить регулярное выражение немного, например, adding b$ after each of the regex above, то вы можете вызвать катастрофические откаты с входом как aaa ... aabaa ... aa.

В зависимости от реализации и оптимизации двигателя бывают случаи, когда мы ожидаем катастрофического возврата, но двигатель не проявляет никаких признаков такого поведения.

Например, при (a+)+b и входе aaa ... aac, PCRE fails the match outright, так как есть оптимизация, которая проверяет наличие необходимого символа во входной строке перед началом матча собственно.

Зная, что делает двигатель, мы можем throw off its early detection с входом aaa ... aacb и заведите двигатель, чтобы показать катастрофические откаты.

Что касается (.*a){x}, то можно вызвать Redos, так как он имеет неудовлетворительное состояние менее x итераций. Учитывая входную строку aaa ... a (с x или более символов a), регулярное выражение продолжает попытки всех перестановок a в конце строки, поскольку она отступает от конца строки. Поэтому сложность регулярного выражения равна O (2 ^x). Зная это, мы можем сказать, что эффект более заметен, когда x больше, let's say 20. Кстати, это один редкий случай, когда совпадающая строка имеет худшую сложность.