Как я могу программно идентифицировать злые регулярные выражения?

Есть ли алгоритм, позволяющий определить, уязвимо ли данное регулярное выражение JavaScript для ReDoS? Алгоритм не обязательно должен быть идеальным - допустимы некоторые ложные срабатывания и ложные отрицания. (Меня особенно интересуют регулярные выражения ECMA-262.)


javascript security regex denial-of-service automaton
person fblundun    schedule 02.12.2015    source источник
comment
Более прагматичным решением может быть остановка вычисления выражения по истечении определенного времени ожидания, например 1 секунды. Возможно, попробуйте несколько раз, чтобы убедиться, что это не просто загруженная хост-машина. Однако это сильно зависит от вашей среды выполнения.   -  person deceze♦    schedule 02.12.2015
comment
Я хочу программно проинформировать разработчиков о том, что их регулярное выражение может быть злом, до того, как регулярное выражение будет использовано в производстве, поэтому тайм-аут не является вариантом.   -  person fblundun    schedule 02.12.2015
comment
Преобразуйте регулярное выражение в NFA, а затем попробуйте преобразовать его в DFA, выходя из строя на некотором субъективном пределе сложности (размере автомата).   -  person Bergi    schedule 02.12.2015
comment
@Bergi, это интересная идея ... Но разве ^a*$, ^a*a*$, ^(a*a*)*$ и ^(a|a)*$ не будут все переведены в один и тот же DFA, даже если только первые два безопасны?   -  person fblundun    schedule 03.12.2015
comment
@fblundun: Да ладно, этого недостаточно, так как DFA нормализуется. Я предполагаю, что этот шаг является интересным: когда вы канонизируете NFA и свободные состояния в этом процессе, то с регулярным выражением что-то не так. Хотя, если DFA растет экспоненциально, тоже есть проблема.   -  person Bergi    schedule 03.12.2015
comment
@deceze, как ограничить / остановить выполнение регулярных выражений в JavaScript?   -  person omer    schedule 30.06.2019

Ответы (2)


arrow_upward
2
arrow_downward

Трудно проверить, является ли регулярное выражение злом или нет, не запустив его на самом деле. Вы можете попробовать определить некоторые из шаблонов, подробно описанных в Wiki, и обобщить их:

например За

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+
  • (. * a) {x} для x> 10

Вы можете проверить последовательности )+, )* или ){ и проверить их соответствие. Однако я гарантирую, что злоумышленник найдет способ их обойти.

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

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

person SilverlightFox    schedule 02.12.2015
comment
Я не думаю, что проблема остановки относится к регулярным выражениям. Каждое формальное регулярное выражение останавливается при каждом вводе. Насколько мне известно, это также верно и для расширенных регулярных выражений JavaScript (см. этот вопрос ). - person fblundun; 02.12.2015

arrow_upward
0
arrow_downward

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 - это комбинация двух факторов: комбинаторного взрыва и недосмотра в реализации движка. Таким образом, худший случай также зависит от движка регулярных выражений и иногда от флагов. Поиск с возвратом не всегда легко идентифицировать.

Однако можно выделить простые случаи.

person Dima Tisnek    schedule 05.08.2016