Есть ли алгоритм для определения того, уязвимо ли данное JavaScript-регек к ReDoS? Алгоритм не должен быть совершенным - допустимы ложные срабатывания и ложные негативы. (Меня интересует ECMA-262 regexes.)Как я могу программно идентифицировать злые регулярные выражения?
Трудно проверить, является ли регулярное выражение злом или нет, без фактического его запуска. Вы можете попытаться определить некоторые шаблоны, подробно описанные в Wiki, и обобщить их:
например. Для
Вы можете проверить )+ или )* или ){ последовательности и проверки против них. Тем не менее, я гарантирую, что злоумышленник найдет способ обойти их.
По существу это minefield to allow user set regexps. Однако, если вы можете тайм-аут поиска в регулярном выражении, прекратите поток, а затем отметьте, что regexp как «плохой», вы можете немного смягчить угрозу. В случае, когда регулярное выражение используется позже, возможно, вы можете проверить его, выполнив его против ожидаемого ввода в точке входа?
Позже вам все равно нужно будет его прекратить, если текст, оцененный на более позднем этапе, имеет другое влияние на ваше регулярное выражение и пометит его как плохое, поэтому он не будет использоваться снова без вмешательства пользователя.
Я не думаю, что проблема с остановкой применяется к регулярным выражениям. Каждое официальное регулярное выражение останавливается на каждом входе. Насколько я знаю, это также относится к расширенным регулярным выражениям JavaScript (см. [Этот вопрос] (http://stackoverflow.com/questions/1241215/do-all-regular-expressions-halt)). – fblundun
Вы правы - удалены. – SilverlightFox
TL; DR рода, но не в полной мере
In [9]: re.compile("(a+)+", re.DEBUG)
max_repeat 1 4294967295
subpattern 1
max_repeat 1 4294967295
literal 97
Примечание те вложенные повтор 1..N, для больших N, что это плохо.
Это касается всех примеров из Википедии, кроме (a|aa)+ и a*b?a*x.
Сложно также учитывать обратные ссылки, если ваш двигатель поддерживает их.
IMO evil regexp - это комбинация двух факторов: комбинаторного взрыва и надзора в реализации двигателя. Таким образом, худший случай также зависит от двигателя regexp и иногда от флагов. Откат не всегда легко идентифицировать.
Простые случаи, однако, могут быть идентифицированы.
Более прагматичным решением может быть остановка оценки выражения после определенного таймаута, например, 1 секунда. Возможно, попробуйте несколько раз, чтобы убедиться, что это не просто занятая хост-машина. Тем не менее это сильно зависит от среды выполнения. – deceze
Я хочу программным образом сообщить разработчикам, что их регулярное выражение может быть злым до того, как регулярное выражение будет использовано в производстве, поэтому тайм-аут не является вариантом. – fblundun
Переведите регулярное выражение в NFA, а затем попробуйте преобразовать его в DFA, выполняя некоторые ограничения субъективной сложности (размер автомата). – Bergi