Для каждого «злого» регулярного выражения существует ли не злая альтернатива или дьявол в грамматике?

16

По-видимому, атаки ReDos используют характеристики некоторых (в противном случае полезных) регулярных выражений ... по сути, вызывая взрыв возможных путей через граф, определенный NFA.

Можно ли избежать таких проблем, написав эквивалентное «не злое» регулярное выражение? Если нет (таким образом, грамматика не может быть обработана в практическом пространстве / времени NFA), какие подходы анализа были бы лучше? Почему?

Дэвид Баллок
источник
Если мне удалось использовать точный технический язык, это случайность. Пожалуйста, набросайте свои ответы для неакадемических :-)
Дэвид Баллок
1
На самом деле я просто пытаюсь найти практичный способ избежать ReDos'd , и этот вопрос возник.
Дэвид Баллок
Перефразируя ваш вопрос (?): Есть ли у каждого регулярного языка регулярное выражение, длина которого ограничена полиномом по числу состояний его минимального NFA?
А.Шульц
1
@ A.Schulz. Я не думаю, что это вопрос. Это не то, как работают атаки ReDos. При атаке ReDos регулярное выражение жестко кодируется в исходный код программы и предоставляется разработчиком, которому, как предполагается, доверяют. Затем злоумышленник получает строку ввода, которую программа сопоставляет с регулярным выражением. Если злоумышленник может найти входную строку, которая заставляет совпадение работать в течение очень долгого времени, злоумышленник побеждает. Таким образом, мы беспокоимся о состязательных входах, а не о состязательных регулярных выражениях. (продолжение)
DW
Следовательно, я думаю, что вопрос заключается в следующем: есть ли в каждом регулярном языке регулярное выражение, такое, что сопоставление строки символа с этим регулярным выражением занимает время O ( f ( n ) ) , где f ( n ) - не слишком быстро растущая функция n (скажем, полином или что-то в этом роде)? [Между прочим, эта переформулировка проясняет, что ответ будет зависеть от алгоритма, используемого для сопоставления ... как я упоминаю в своем ответе.] Размер регулярного выражения как функция размера минимального NFA не действительно важно здесь. NО(е(N))е(N)N
DW

Ответы:

14

Это зависит от того, есть ли у вас регулярное выражение или регулярное выражение: регулярные выражения являются злом, но регулярные выражения - вещь прекрасная и никогда не повредит вам.

Под регулярным выражением я подразумеваю современное регулярное выражение: то есть регулярное выражение с дополнительными современными функциями, такими как обратные ссылки - например, Perl-совместимое регулярное выражение. Это более мощно, чем классическое регулярное выражение из учебника теории формальных языков / автоматов, поскольку классические регулярные выражения не допускают обратных ссылок, просмотра в будущее, просмотра назад и т. Д.

Для классического регулярного выражения, если у вас есть хорошая реализация для сопоставителя, то никакое регулярное выражение не является слишком злым. В частности, стандартный алгоритм сопоставления заключается в преобразовании регулярного выражения в NFA и последующем выполнении NFA для входной строки. Для этого алгоритма наихудшее время выполнения для проверки строки символа - это O ( n ) , когда регулярное выражение фиксировано. Это означает, что время работы не может взорваться слишком быстро. Там нет строки, которая приведет к экспоненциальному увеличению времени выполнения. Таким образом, если вы используете средство сравнения, использующее этот алгоритм, никакое классическое регулярное выражение не будет злым.NО(N)

Это зависит от реализации средства сравнения регулярных выражений. Если у вас наивная или плохая реализация сопоставления, сопоставление может занять экспоненциальное время; конечно, есть алгоритмы с этим свойством. Но лучший ответ на это, вероятно, не в том, чтобы изменить регулярное выражение; вероятно, лучше выбрать более подходящее средство, если вы обеспокоены атаками типа «отказ в обслуживании».

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

(Такой эквивалент может существовать и даже может быть найден в теории, но при вероятных предположениях нахождение эквивалентного регулярного выражения займет экспоненциальное время, что на практике неосуществимо. Если у вас была систематическая процедура для нахождения эквивалентного регулярного выражения за полиномиальное время , тогда вы могли бы решить NP-трудную задачу за полиномиальное время, доказав, что P = NP. Нет ничего хорошего в существовании эквивалентного регулярного выражения, если нет способа найти его в течение жизни.)


Предпосылки и источники:

DW
источник
Не проще ли найти не злую альтернативу, разделив регулярное выражение на несколько меньших регулярных выражений и используя их в комбинации?
inf3rno
1

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

В Википедии есть 15 категорий атак типа « отказ в обслуживании», и эта атака попадает в список «наводнения уровня приложения» в этом списке. Другой похожий пример - атака, заполняющая журналы приложений.

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

Другой подход к улучшению отказоустойчивости / устойчивости, который применим здесь, - это тайм-ауты указанные на разных уровнях программного стека / иерархии. Идея заключалась бы в том, чтобы указать время / процессор или лимит инструкций для «средней» оценки регулярного выражения и завершить досрочно, если оно превышено. Они могут быть реализованы с помощью пользовательских решений, но не так много программного обеспечения или языков программирования имеют встроенные тайм-ауты или структуры для этой цели.

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

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

Вот хороший научный обзор этой конкретной темы с решениями статического анализа :

  • Статический анализ для экспоненциальной среды выполнения регулярных выражений с помощью субструктурной логики / Rathnayake, Thielecke

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

ВЗН
источник
Этот ответ кажется запутанным в отношении некоторых аспектов ReDos. 1. ReDoS не имеет ничего общего с инъекционной атакой. Инъекционные атаки (например, XSS, SQL-инъекция, внедрение команд и т. Д.) Совершенно разные. 2. ReDos не о злонамеренных регулярных выражениях, представленных противником. Обычно регулярное выражение жестко закодировано в программе (предоставлено разработчиком), а входная строка предоставлена ​​пользователем. Проблема не может быть разумно решена путем проверки входных данных, потому что обычно нет четкой политики проверки входных данных, которая была бы достаточна для устранения проблемы.
DW
Подумайте, что ваши очки сводятся к техническим особенностям / укладке волос на основе ссылки ReDos и пропускает лес за деревьями. это похоже на «искусственные инъекционные атаки». Ответ указывает на то, что существуют альтернативы использованию регулярных выражений в коде. Статический анализ может найти «злые регулярные выражения». все пункты ответа верны. предложение типа «обычно регулярное выражение жестко запрограммировано в программе (предоставлено разработчиком), а входная строка предоставлена ​​пользователем» точно не соответствует записи ReDos, которая в некоторых местах более расплывчата, и относится к злоумышленнику и т. д. .
ВЗН