Введение

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

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

Почему так происходит

Спросите себя,

  • Вход контролируется пользователем.
  • Размер ввода не ограничивается небольшим количеством символов.
  • Нет тайм-аута, чтобы ограничить время оценки регулярного выражения.

Если вы ответили утвердительно на любой из этих вопросов, существует риск.

Рекомендуемые методы безопасного кодирования

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

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

  • Если у вас есть повторение r* или r*?, так что регулярное выражение r может создавать разные возможные совпадения (возможно, разной длины) на одном и том же входе, время совпадения в наихудшем случае может быть экспоненциальным. Это может быть в том случае, если r содержит необязательные части, чередования или дополнительные повторения (но не в том случае, если повторение написано таким образом, что существует только один способ его сопоставления).
  • Если у вас есть несколько повторений, которые могут соответствовать одному и тому же содержимому и являются последовательными или разделены только необязательным разделителем или разделителем, который может сопоставляться обоими повторениями, время совпадения в худшем случае может быть полиномиальным (O (n ^ c) где с — количество проблемных повторений). Например, a*b* не является проблемой, потому что a* и b* соответствуют разным вещам, а a*_a* не является проблемой, потому что повторения разделены '_' и не могут соответствовать этому '_'. Однако a*a* и .*_.* имеют квадратичное время выполнения.
  • Если регулярное выражение не привязано к началу строки, особенно трудно избежать квадратичного времени выполнения, потому что всякий раз, когда совпадение не удается, механизм регулярных выражений будет пытаться снова начать со следующего индекса. Это означает, что любое неограниченное повторение, если за ним следует шаблон, который может дать сбой, может вызвать квадратичное время выполнения на некоторых входных данных. Например, str.split(/\s*,/) будет выполняться за квадратичное время для строк, полностью состоящих из пробелов (или, по крайней мере, содержащих большие последовательности пробелов без запятой).

Чтобы переписать регулярное выражение без этих шаблонов, рассмотрите следующие стратегии:

  • Если применимо, определите максимальное количество ожидаемых повторений, используя ограниченные квантификаторы, например, {1,5} вместо +.
  • Рефакторинг вложенных квантификаторов, чтобы ограничить количество способов сопоставления внутренней группы с внешним квантификатором, например, эта ситуация с вложенным квантификатором (ba+)+ не вызывает проблем с производительностью, действительно, внутренняя группа может быть сопоставлена, только если существует ровно один b char за повторение группы.
  • Оптимизируйте регулярные выражения, эмулируя притяжательные квантификаторы и атомарную группировку.
  • Используйте отрицательные классы символов вместо ., чтобы исключить разделители, где это применимо. Например, квадратичное регулярное выражение .*_.* можно сделать линейным, изменив его на [^_]*_.*.

Иногда невозможно переписать регулярное выражение, чтобы оно было линейным, но при этом соответствовало тому, что вы хотите. Особенно, когда регулярное выражение не привязано к началу строки, для чего довольно сложно избежать квадратичного времени выполнения. В таких случаях рассмотрите следующие подходы:

  • Решить задачу без регулярных выражений
  • Используйте альтернативные реализации регулярных выражений без возврата, такие как Google RE2 или node-re2.
  • Используйте несколько проходов. Это может означать предварительную и/или постобработку строки вручную до/после применения к ней регулярного выражения или использование нескольких регулярных выражений. Одним из примеров этого может быть замена str.split(/\s*,\s*/) на str.split(","), а затем удаление пробелов из строк в качестве второго шага.
  • Часто можно сделать регулярное выражение безошибочным, сделав все части, которые могут дать сбой, необязательными, что предотвратит откат. Конечно, это означает, что вы примете больше строк, чем предполагалось, но с этим можно справиться, используя группы захвата, чтобы проверить, совпали ли необязательные части, а затем проигнорировать совпадение, если они не совпали. Например, регулярное выражение x*y можно заменить на x*(y)?, а затем вызов str.match(regex) можно заменить на matched = str.match(regex) и matched[1] !== undefined.

Пример конфиденциального кода

Оценка регулярного выражения никогда не закончится:

/(a+)+$/.test(
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaa!"
); // Sensitive

Совместимое решение

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

/((?=(a+))\2)+$/.test(
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaa!"
); // Compliant

Ссылки: