Мне известно об отказе в обслуживании регулярных выражений (ReDoS). Есть ли какой-нибудь разумный способ позволить пользователям создавать собственные регулярные выражения, гарантируя при этом, что они не отправляют экспоненциально медленный шаблон?
regular-expressions
icirellik
источник
источник
Ответы:
Проблема с регулярными выражениями заключается не в самом регулярном выражении, а в том, что движок регулярных выражений имеет все виды «удобных» функций, таких как возврат. Следовательно, использование движка регулярных выражений без этих функций исключает.
Регулярные выражения концепции компьютерных наук всегда могут быть сопоставлены в линейном времени после их компиляции в конечный автомат. Таким образом, механизм регулярных выражений на основе конечного автомата не может быть использован для ReDoS. Однако необходимые патологические машины могут стать довольно большими в патологических примерах. Но ограничение доступной памяти обычно проще, чем ограничение доступного времени вычислений.
Двигатель RE2 был разработан специально для борьбы с ненадежными регулярными выражениями и предназначен для выполнения линейного времени.
Другой альтернативой является сборка регулярных выражений самостоятельно из упрощенной записи. Например, вы можете разрешить пользователям использовать шаблоны глобуса (например
*.txt). Затем вы можете проанализировать это таким образом, чтобы предотвратить возврат, например, запретив вложение и используя только жадные квантификаторы. Для многих случаев использования вполне достаточно упрощенной системы обозначений.источник
Анализировать регулярное выражение, чтобы увидеть, будет ли оно медленным или нет, сам анализ не станет медленным , равносильно решению проблемы остановки. Другими словами, невозможно найти правильное и полное решение.
Можно, конечно, найти решение , которое является правильным и в комплекте. Например, вы можете работать с ограниченным белым списком функций, которые безопасно использовать (например, классы символов да, повторение нет ...). Это позволит вам пропустить множество некритических регулярных выражений, отвергнуть все критические и (ошибочно) отклонить те, которые в порядке, но слишком сложные, чтобы автоматически оказаться безопасными.
источник
Как автор re reser для проекта lazarus, я бы сказал, что нет никаких способов понять для какого-либо данного регулярного выражения, какие ресурсы он будет использовать для данного текста.
Не тратя те же самые ресурсы, которые я имею в виду (по крайней мере, в значении big-O).
Поэтому лучший подход - запускать re parser в отдельном потоке и уничтожать его по истечении времени ожидания.
источник
В дополнение к другим ответам, решение может также состоять в том, чтобы развернуть собственную библиотеку регулярных выражений, которая позволяет измерять производительность во время выполнения и, таким образом, предоставляет средства для прекращения выполнения на полпути, если выполнены некоторые критерии.
Точно так же вы можете запустить регулярные выражения в другом потоке и убить потоки, если они занимают слишком много времени.
источник