это регулярное выражение уязвимо для атак REDOS

Question

Регулярное выражение:

^\d+(\.\d+)*$

Я пытался разорвать его с помощью:

1234567890.1.1.1.1.1.1.1. 1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1. 1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1. 1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1. 1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1x]

, то есть 200x ".1"

Я читал об атаках ReDos:

• Предотвращение отказа в обслуживании регулярных выражений (ReDoS)
• Нерегулярные регулярные выражения: катастрофическое возвращение назад

Однако я не слишком уверен в своих навыках для подготовки атаки ReDos на выражение. Я пытался вызвать катастрофический откат из-за «Вложенных квантификаторов».

Это выражение может быть разбито? Какой вклад следует использовать для этого и, если да, как вы это сделали?

Answer 1

«Вложенные квантификаторы» по своей сути не являются проблемой. Это просто простой способ обратиться к проблеме, которая на самом деле немного сложнее. Проблема заключается в «количественном определении подвыражения, которое может во многих отношениях совпадать в одной и той же позиции». Просто получается, что вам почти всегда нужен квантификатор во внутреннем подвыражении, чтобы обеспечить достаточно богатый запас совпадений, и поэтому квантификаторы внутри квантификаторов служат красным флагом, указывающим на вероятность проблемы.

(.*)* проблематично, потому что .* имеет максимальную симметрию - он может совпасть с любым значением от нуля до всех оставшихся символов в любой точке ввода. Повторение этого приводит к комбинаторному взрыву.

([0-9a-f]+\d+)* проблематично, потому что в любой точке последовательности цифр будет много возможных способов выделить эти цифры между начальной подстрокой [0-9a-f]+ и конечнойподстрока \d+, поэтому она имеет ту же проблему, что и (.*)*.

(\.\d+)* - это , а не проблематично, потому что \. и \d соответствуют совершенно разным вещам. Цифра не точка, а точка не цифра. В любой заданной точке ввода есть только один возможный способ сопоставления \. и только один возможный способ сопоставления \d+, который оставляет открытой возможность повторения (потребляют все цифры, потому что, если мы остановимся передцифра, следующий символ, конечно, не точка). Следовательно, (\.\d+)* не хуже в обратном направлении, чем \d* в том же контексте, даже если он содержит вложенные квантификаторы.

Answer 2

Ваше регулярное выражение безопасно, но только из-за "\".

Тестирование на regex101.com показывает, что нет никаких комбинаций входных данных, которые создают неконтролируемые проверки - но ваше регулярное выражение ОЧЕНЬ близко к уязвимости,так что будьте осторожны при его изменении.

Как вы уже читали, катастрофический откат происходит, когда два квантификатора находятся рядом друг с другом. В вашем случае, регулярное выражение расширяется до \d+\.\d+\.\d+\.\d+\. ... и так далее. Поскольку вы делаете точку, необходимую для каждого совпадения между \d+, ваше регулярное выражение увеличивается всего на три шага для каждого добавляемого числа периода. (Это означает 4 шага на номер периода, если вы ставите недопустимый символ в конце.) Это линейный темп роста, поэтому с вашим регулярным выражением все в порядке. Демо

Однако, , если вы сделаете необязательный параметр \., случайно забудете escape-символ, чтобы сделать его простым ., или удалите его вообще, тогда у вас проблемы. Такое регулярное выражение позволило бы катастрофическое возвращение назад;неверный символ в конце примерно удваивает время выполнения с каждым дополнительным числом, которое вы добавляете перед ним. Это экспоненциальный темп роста, и этого достаточно, чтобы crash превысил настройки по умолчанию для движка regex101 с 18 цифрами и 1 недопустимым символом. Демо

Как написано, с вашим регулярным выражением все в порядке, и оно останется таким, пока вы убедитесь, что между первым \d+ и вторым \d+ есть что-то "твердое", кака также нечто «твердое» между вторым \d+ и * вне его группы захвата.