Ответ 1
Проблемы, связанные с отказом в обслуживании
Наиболее распространенная проблема с регулярными выражениями - атака типа "отказ в обслуживании" через патологические шаблоны, которые экспоненциальны или даже суперэкспоненциальны! - и поэтому, похоже, навсегда нужно решить. Они могут отображаться только на определенных входных данных, но обычно можно создать один, в котором это не имеет значения.
Какие из них будут зависеть от того, насколько разумным является ваш компилятор регулярных выражений, потому что некоторые из них могут быть обнаружены во время компиляции. Компиляторы Regex, которые реализуют рекурсию, обычно имеют встроенный счетчик глубины рекурсии для проверки непрогрессии.
Russ Coxs превосходная статья 2007 года на Регуляция регулярных выражений может быть простой и быстрой (но медленный в Java, Perl, PHP, Python, Ruby,...) рассказывает о том, как большинство современных NFA, которые, как представляется, происходят из кода Генри Спенсера, страдают серьезной деградацией производительности, но там, где Томпсон -style NFA не имеет таких проблем.
Если вы допускаете только шаблоны, которые могут быть решены DFA, вы можете скомпилировать их как таковые, и они будут работать быстрее, возможно, намного быстрее. Однако для этого требуется время. В документе Кокса упоминается этот подход и его сопутствующие проблемы. Все сводится к классическому компромиссу в пространстве времени.
С DFA вы тратите больше времени на его создание (и выделяете больше состояний), тогда как с NFA вы тратите больше времени на его выполнение, так как это может быть несколько состояний одновременно, и откат может съесть ваш обед - и ваш процессор.
Решения для отказа в обслуживании
Вероятно, наиболее разумным способом решения этих шаблонов, которые находятся на проигрыше в конце гонки с жарой смерти Вселенной, является обернуть их таймером, который эффективно помещает максимальное количество времени, которое может быть выполнено для их выполнения. Обычно это будет намного меньше, чем время ожидания по умолчанию, которое предоставляет большинство HTTP-серверов.
Существуют различные способы их реализации, начиная с простого alarm(N) на уровне C, до какого-либо try {} блокирует исключения исключений типа тревоги, вплоть до создания нового потока, специально созданного с ограничением по времени, встроенным в него.
Выноски кода
В языках регулярных выражений, которые допускают выноски кода, должен быть предоставлен некоторый механизм для разрешения или запрета их из строки, которую вы собираетесь компилировать. Даже если кодовые обозначения кода кодируются только на используемом вами языке, вы должны их ограничить; они не должны иметь возможность вызывать внешний код, хотя, если они могут, у вас возникают гораздо большие проблемы.
Например, в Perl нельзя иметь выноски кода в регулярных выражениях, созданных из строковой интерполяции (как это было бы, как они были скомпилированы во время выполнения), если только специальная лексически-ограниченная прагма use re "eval"; не активна в текущей области.
Таким образом, никто не может прокрасться в выноску кода для запуска системных программ, например, rm -rf *. Поскольку выноски кода настолько чувствительны к безопасности, Perl отключает их по умолчанию во всех интерполированных строках, и вам нужно уйти с пути, чтобы повторно активировать их.
Пользовательский \P {roperties}
Остается еще одна проблема с безопасностью, связанная со свойствами стиля Unicode - например, \pM, \p{Pd}, \p{Pattern_Syntax} или \p{Script=Greek} - которые могут существовать в некоторых компиляторах, которые поддерживают эту нотацию.
Проблема в том, что в некоторых из них набор возможных свойств расширяется пользователем. Это означает, что вы можете иметь настраиваемые свойства, которые являются фактическими выносками кода для названных функций в определенном пространстве имен, например \p{GoodChars} или \p{Class::Good_Characters}. Как ваш язык справляется с тем, на что стоит обратить внимание.
Песочница
В Perl отсек с песочницей через модуль Safe обеспечит контроль над видимостью пространства имен. Другие языки предлагают аналогичные технологии песочницы. Если такие устройства доступны, вы можете посмотреть их, потому что они специально предназначены для ограниченного выполнения ненадежного кода.