Как избежать катастрофического возврата (Catastrophic Backtracking) в регулярных выражениях (Regex)?

API7.ai

December 17, 2020

Technology

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

Предыстория

Я прочитал статью, в которой подробно описывается процесс обнаружения и решения проблемы, связанной с регулярным бэктрекингом, приводящим к 100% загрузке процессора. Оригинальная статья довольно длинная, и я сталкивался с подобными проблемами дважды ранее в разработке OpenResty.

Вот краткое резюме, чтобы вам не пришлось тратить время на предысторию.

  1. Движки регулярных выражений для большинства языков разработки реализованы с использованием NFA на основе бэктрекинга (а не на основе NFA Томпсона).
  2. Катастрофический бэктрекинг с 100% загрузкой процессора, если бэктрекингов слишком много.
  3. Необходимо анализировать дамп с помощью gdb или systemtap для локализации проблемы в рабочей среде.
  4. Такие проблемы сложно обнаружить до выхода кода в продакшн и требуют индивидуального анализа регулярных выражений.

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

lua_regex_match_limit 100000;

Таким образом, даже если произойдет катастрофический бэктрекинг, он будет ограничен и не приведет к полной загрузке процессора.

Ну что, выглядит ли это уже идеально? Давайте выйдем за рамки уровня разработки и рассмотрим это в другом измерении.

Атакующие

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

Эта атака также имеет свое название: ReDoS (RegEx Denial of Service).

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

Представьте сценарий, где хакер обнаруживает уязвимость ReDoS в WAF и отправляет запрос, чтобы вывести WAF из строя; вы не можете быстро локализовать проблему, даже не осознавая, что это атака; вы выбираете перезапустить или временно отключить WAF, чтобы поддерживать работу вашего бизнеса; пока WAF не работает, хакер использует SQL-инъекцию, чтобы утащить вашу базу данных. Вы же, возможно, все еще полностью в неведении.

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

Как обнаружить такие регулярные выражения?

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

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

Здесь на помощь приходят инструменты автоматизации.

У нас есть два автоматизированных метода для решения этой проблемы.

  • Статическое тестирование

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

Например, RXXR2, который реализован на основе алгоритма из статьи, преобразующего регулярные выражения в ε-NFA и затем выполняющего поиск, но он не поддерживает расширенный синтаксис регулярных выражений, поэтому могут быть пропущенные случаи.

  • Динамическое фаззинг-тестирование

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

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

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

SDLFuzzer — это специализированный инструмент для обнаружения ReDoS, разработанный Microsoft несколько лет назад, но больше не поддерживается.

В этой области не так много инструментов на выбор, и ей уделяется не так много внимания. Однако я был рад найти статью о ReDoS от нескольких преподавателей и докторов наук из Нанкинского университета во время поиска информации, и они открыли исходный код инструмента ReScue вместе со статьей: https://2bdenny.github.io/ReScue/. Этот инструмент обнаружил уязвимости ReDoS в нескольких открытых проектах.

Вот результаты сравнительных тестов из статьи.

1.jpg

2.jpg

Можно ли решить проблему раз и навсегда?

Даже если мы используем такие инструменты, неизбежно будут ложные срабатывания и пропущенные случаи, так есть ли способ решить ReDoS раз и навсегда?

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

Не будет ли все в порядке, если мы откажемся от этого подхода? Да, уже существует довольно много других реализаций движков регулярных выражений, которые могут решить проблему раз и навсегда. Все они отказываются от бэктрекинга и используют подход NFA/DFA автоматов для реализации, преимущество в том, что это подходит для потокового сопоставления и также безопаснее, недостаток в том, что они не поддерживают многие расширенные синтаксисы регулярных выражений, такие как обратные ссылки, но они обычно и не используются.

  • Google RE2

Google RE2 — один из наиболее завершенных открытых проектов. Он поддерживает большую часть синтаксиса PCRE, и есть реализации библиотек для Go, Python, Perl, Node.js и других языков разработки, начальные и затраты на замену очень низкие.

Давайте возьмем Perl в качестве примера и посмотрим, может ли RE2 избежать проблем с катастрофическим бэктрекингом.

Давайте взглянем на эту сравнительную таблицу результатов.

3.jpg

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

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

На выполнение этого регулярного выражения уходит 40,8 секунд, в течение которых процессор загружен на 99%.

С RE2 контраст очень очевиден.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total
  • Intel Hyperscan

Intel Hyperscan — это также движок регулярных выражений, похожий на RE2, и есть библиотеки для Perl, Python и других языков, поэтому начать с ним не слишком сложно.

Только в соответствии с практикой Intel, больше привязки к платформе, может работать только на x86.

Если есть уникальное преимущество, то, возможно, это возможность лучше работать с набором инструкций и аппаратным обеспечением Intel, с улучшением производительности, например, в сочетании с его собственным DPDK.

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

Дополнения

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

  1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

  2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

  3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

  4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html

Tags:
Regex
Codec