Как вызвать Regex отказ в обслуживании в PHP?
Как я могу вызвать Regex-DOS, используя preg_match() функция с использованием злого регулярного выражения (например, (А +) + )?
Например, у меня следующая ситуация:
preg_match('/(a+)+/',$input);
Если у меня есть контроль над $inputКак я мог вызвать DOS атаки или достичь предел возврата из preg_* функции в php?
Как я мог сделать это со следующими выражениями?
([a-zA-Z]+)*
(a|aa)+
(a|a?)+
(.*a){x} | for x > 10
Решение
Нет возможности вызвать ReDOS на (a+)+, ([a-zA-Z]+)*, (a|aa)+, (a|a?)+ , поскольку нет ничего, что могло бы вызвать сбой совпадения и вызвать возврат после проблемной части регулярного выражения.
Если вы немного измените регулярное выражение, например, добавление b$ после каждого из регулярных выражений выше, тогда вы можете вызвать катастрофический возврат с помощью входа, как aaa…aabaa…aa,
В зависимости от реализации и оптимизации движка в некоторых случаях мы ожидаем катастрофического возврата, но движок не демонстрирует никаких признаков такого поведения.
Например, учитывая (a+)+b и вход aaa…aac, PCRE проваливает матч, так как он имеет оптимизацию, которая проверяет наличие необходимого символа во входной строке перед началом правильного соответствия.
Зная, что делает двигатель, мы можем сбрось свое раннее обнаружение с входом aaa…aacb и получить двигатель, чтобы показать катастрофическое возвращение назад.
Что касается (.*a){x}можно запустить ReDOS, так как он имеет неисправное состояние меньше, чем x итерации. Учитывая входную строку aaa…a (с x или больше персонажа a), регулярное выражение продолжает пытаться все перестановки aнаходится в конце строки, так как она отходит от конца строки. Следовательно, сложность регулярного выражения равна O (2Икс). Зная это, мы можем сказать, что эффект более заметен, когда x большее число, скажем 20. Кстати, это один редкий случай, когда подходящая строка имеет сложность наихудшего случая.
Другие решения
Других решений пока нет …