Вступление

Этот пост задуман как техническая двухстраничная страница, чтобы обобщить уязвимость системы безопасности под названием отказ в обслуживании на основе регулярных выражений (AKA Regex DoS, ReDoS ). О ReDoS пишут самые разные, но я не знаю ни одного хорошего универсального магазина с высокоуровневым подходом ко всем аспектам предмета. Я включил в конце ссылки на более подробное лечение.

Я использовал заголовки, чтобы помочь вам сориентироваться в проблеме.

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

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

Регулярное выражение - это язык шаблонов для строк. Вы можете использовать регулярные выражения, чтобы задавать такие вопросы, как «Эта строка похожа на электронное письмо?».

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

Что такое Regex DoS?

ReDoS - это проблема производительности. Это может привести к сбоям в обслуживании либо из-за внешней атаки типа отказ в обслуживании, либо из-за комбинации случайных, но не вредоносных факторов (см. Совокупность ошибок в Stack Overflow).

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

Это долгое время сопоставления может отвлечь вычислительные ресурсы (время ЦП, рабочие потоки) от легитимных клиентов на несколько длительных сопоставлений регулярных выражений. Это может привести к проблемам двумя способами:

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

Стоит ли беспокоиться о ReDoS?

Регулярные выражения используются во всем системном стеке (см. Рисунок), поэтому программное обеспечение во всем системном стеке может быть источником ReDoS.

Вот условия, которые вы должны проверить:

  1. Вы используете регулярное выражение ReDoS для ненадежного ввода. Я расскажу об этом в следующем разделе.
  2. Ваш механизм регулярных выражений использует алгоритм медленного сопоставления регулярных выражений. Так обстоит дело с механизмами регулярных выражений, встроенными в большинство сред выполнения языков программирования, включая Java, JavaScript (в различных вариантах) и Node.js, C # /. NET, Ruby, Python, Perl и PHP. На всякий случай и Go, и Rust используют быстрые движки регулярных выражений, и библиотека Google RE2 тоже быстрая.
  3. Ваш механизм регулярных выражений не имеет ограничения на использование ресурсов. Некоторые механизмы регулярных выражений предлагают ограничения, включая Perl, PHP и C # /. NET. Среди них полезны только временные ограничения, подобные тем, которые предлагаются механизмом регулярных выражений .NET. Если вы используете регулярные выражения в .NET, используйте API с тайм-аутами!

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

Как узнать, есть ли у меня регулярное выражение ReDoS?

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

Если вы хотите найти регулярное выражение ReDoS вручную, основное практическое правило - избегать двусмысленности - случаев, когда механизм регулярных выражений может сделать два разных выбора и оказаться в одной и той же точке (я расскажу об этом в приложение ниже, см. заголовок «Почему регулярные выражения ReDoS такие медленные?»).

Неоднозначность обычно возникает из-за ИЛИ и квантификаторов (*, +, {5,10} и т. Д.). Одна двусмысленность хуже других - (a | a) двусмысленна, но совсем немного. (a | a) * экспоненциально неоднозначно, потому что количество путей удваивается для каждого дополнительного a. См. Рисунок для иллюстрации.

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

  1. Вложенные квантификаторы могут быть экспоненциально опасными - например, (a *) *. Проверьте, можете ли вы «вернуться» к внутреннему квантификатору, взяв вместо него внешний квантор.
  2. Количественная оценка дизъюнкции может быть экспоненциально опасной - например, (а | а) *. Проверьте, можно ли сопоставить какие-либо строки двумя разными путями через дизъюнкцию.
  3. Составные кванторы могут быть полиномиально опасными - например, abc. * def. *. Может ли некоторая строка соответствовать первому квантификатору, промежуточному шаблону и следующему квантификатору? Это наиболее распространенный вид регулярных выражений ReDos, поскольку многие регулярные выражения содержат . * или [\ s \ S] * (т. е. универсальный квантификатор). Каждый дополнительный достижимый квантор умножает стоимость.
  4. В качестве особого случая предыдущего, если вы выполняете частичное совпадение, например «Найдите в этом тексте произвольной формы адрес электронной почты», тогда механизм регулярных выражений добавляет неявный . *? в начало вашего регулярного выражения.

Как мне исправить ReDoS в моем программном обеспечении?

Вы можете бороться с ReDoS, аннулировав любое из условий ReDoS, описанных выше.

  1. Вы можете преобразовать регулярное выражение ReDoS в безопасное регулярное выражение или в альтернативную строковую логику.
  2. Вы можете дезинфицировать ввод.
  3. Вы можете использовать более быстрый движок регулярных выражений.
  4. Вы можете использовать ограничение ресурсов вашего механизма регулярных выражений (применимо только в C # /. NET).

Вариант 1. Используйте безопасное регулярное выражение (или альтернативную строковую логику)

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

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

  1. Я обычно выявляю такую ​​двусмысленность с помощью инструмента визуализации, такого как regexper.
  2. Далее я устраняю двусмысленность. Это можно сделать несколькими способами. Например, вы можете изменить то, что вы количественно оцениваете - например, из регулярного выражения электронной почты . + @. + в такое, как [^ @] + @. +. Тогда промежуточный «@» становится защитником между двумя квантификаторами. Или вы можете изменить опциональность, например преобразование числового регулярного выражения \ d + \.? \ d + в эквивалентное \ d + (\. \ d +)?. Если вы используете группы захвата в своем коде, вам может потребоваться ввести несколько уровней регулярных выражений, например крупнозернистый, затем мелкозернистый.
  3. Затем я подтверждаю, что ранее проблемный ввод теперь безопасен (например, с использованием Regex 101), и проверяю, не добавил ли я новой двусмысленности в этот процесс.
  4. Наконец, я сравниваю регулярное выражение с моим тестовым набором входных данных, чтобы убедиться, что я не изменил его строковый язык (или, по крайней мере, не проблемным образом).

Вариант 2. Очистите ввод

Самая простая дезинфекция, которую вы можете применить, - это проверить длину ввода перед передачей его в регулярное выражение. Если допустимый ввод короткий, установите этот предел длины ДО, а не ПОСЛЕ проверки регулярного выражения. Это помогает избежать ReDoS за счет полиномиального поведения (например, общий шаблон abc. * Def. *).

Есть и более сложные способы очистки, но я бы не доверял себе делать их должным образом. Если законный ввод длинен, не следуйте этому подходу. Если ваше регулярное выражение является экспоненциальным, то 30 символов будет «слишком длинным». Большинство медленных регулярных выражений являются квадратичными (они слишком свободно используют. *), Для которых вы увидите время совпадения от миллисекунды к секунде для входных значений 1000–5000 символов.

Вариант 3. Используйте более быстрый движок регулярных выражений

На данный момент наиболее широко доступным механизмом быстрых регулярных выражений является Расс Кокс / механизм регулярных выражений Google RE2. Он имеет привязки для большинства языков программирования. Вы можете ввести его как зависимость и оценить там свои запросы регулярных выражений. Вы также можете попробовать движок HyperScan Джеффа Лонгдейла / Intel.

Плюсы: гарантированно работает быстро.

Минусы:

  1. Более быстрые движки могут не поддерживать расширенные функции, в первую очередь обратные ссылки и утверждения поиска.
  2. Некоторые регулярные выражения могут демонстрировать несколько иное поведение сопоставления. Это может быть трудно обнаружить, поэтому сейчас хорошее время для улучшения вашего набора тестов. Вы также можете попробовать генератор ввода, такой как Microsoft Rex project (ансамбль входных генераторов находится здесь).

Вариант 4. Используйте ограничение на ресурсы

Если вы работаете в C # /. NET, лучше всего всегда использовать API на основе тайм-аута для совпадений регулярных выражений.

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

Почему нет веб-сайтов с инструментами для этого?

Если у вас есть опыт создания веб-сайтов и вы хотите помочь, напишите мне. У меня куча идей.

Где я могу узнать больше?

Вот коллекция ресурсов о ReDoS с разных точек зрения: тематические исследования, академические исследования и другие публикации, ориентированные на практиков.

Примеры ReDoS в продакшене

  • У Cloudflare произошел сбой в 2019 году. Основная причина заключалась в неконтролируемой оценке регулярного выражения. Их вскрытие здесь.
  • В 2016 г. в Stack Overflow произошел сбой, также вызванный неконтролируемым регулярным выражением. Их вскрытие здесь.
  • В текстовом редакторе Atom в 2016 году появилось неконтролируемое регулярное выражение. Это не было ReDoS (отказ в обслуживании других клиентов), но интересный взгляд разработчика на проблему можно найти здесь.

ReDoS в академической литературе

В обратном хронологическом порядке представлены наиболее актуальные исследовательские работы по ReDoS. Я включил ссылки на сообщения в блогах, исходный код и т. Д., Если они доступны.

  • О влиянии и устранении отказа в обслуживании с помощью регулярных выражений. (Дэвис 2020) - Это моя докторская диссертация. Он задуман как исчерпывающий справочник по ReDoS. В справочном разделе описывается вся известная мне литература (включая некоторые более ранние работы, не упомянутые ниже). Диссертация, видео.
  • Регулярные выражения сложны. (Майкл и др., ASE’19) - методы разработки программного обеспечения, связанные с регулярными выражениями. В Разделе 8 они сообщают, что большинство разработчиков программного обеспечения не знают о ReDoS. Резюме, полная статья.
  • Почему регулярные выражения не являются Lingua Franca? (Дэвис и др., ESEC / FSE’19). Раздел 7 включает разбивку производительности регулярных выражений по языкам программирования. Резюме, полная статья.
  • Влияние регулярного отказа в обслуживании (REDOS) на практике. ( Дэвис и др., ESEC / FSE’18) - измеряет степень использования суперлинейных регулярных выражений, а также эвристику идентификации и стратегии исправления. Резюме, полная статья, детекторный ансамбль.
  • ReScue: создание DoS-атак с регулярным выражением. (Шен и др., ASE’18) - Динамический подход к идентификации суперлинейных регулярных выражений. Полная статья, Детектор.
  • Чувство времени для JavaScript и Node.js. (Дэвис и др., SECURITY’18) - обсуждает ReDoS среди связанных угроз, которые особенно проблематичны для веб-сервисов Node.js. Резюме, бумага + видео + слайды.
  • Статическое обнаружение DoS-уязвимостей в программах, использующих регулярные выражения. (Wustholz et al., TACAS’17). Подобно Weideman et al., Они описывают необходимые и достаточные условия для ReDoS на основе анализа автоматов. Они включают сквозное обнаружение эксплойтов для программ Java. Полная бумага, jar-файл детектора.
  • Анализ поведения сопоставления во времени для сопоставителей регулярных выражений с возвратом с использованием неоднозначности NFA. (Weideman et al., CIAA’16) - Необходимые и достаточные условия для ReDoS на основе автоматного анализа. Полная статья, Диссертация Вайдемана, Исходный код детектора.
  • Сопоставление регулярных выражений может быть простым и быстрым (но медленным в Java, Perl, PHP, Python, Ruby и т. д.). (Cox 2007) - умеренная полемика против движков регулярных выражений с возвратом в пользу Томпсона алгоритм сопоставления. В этой серии есть еще несколько сообщений в блоге. Технический отчет, Линейный механизм регулярных выражений RE2.

Другие взгляды на ReDoS

Приложение: что делает регулярные выражения ReDoS такими медленными?

Этот раздел немного более технический.

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

Так работает поисковая система с регулярными выражениями. Механизм регулярных выражений смотрит на свою текущую позицию в регулярном выражении и текущий символ строки, и:

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

Перекрывающиеся ИЛИ

В качестве примера применим этот подход к этому изображению в строке ab.

  • Механизм регулярных выражений запускается с левой стороны и находит на пути развилку. Он видит, что может соответствовать a, поднимаясь или опускаясь - он попробует одну ветвь сейчас и сохранит другую на потом.
  • Теперь он видит, что может соответствовать b, поднимаясь или опускаясь - он попробует одну ветвь и сохранит другую.
  • Теперь он ищет c, но не хватает символов. Так что он вернется.
  • Он пробует другую ветвь для b и (избыточно) снова ищет c. Это не удастся, поэтому он вернется к своему последнему непроверенному пути, «неработающей» версии для a.
  • Опять же, мы достигаем пары b (мы были здесь раньше!), И снова мы попробуем подняться и опускаться (мы уже пробовали это раньше!), Достигнем c, и не получится.
  • Механизм регулярных выражений выполняет поиск c четыре раза по четырем разным путям, которые ведут к одной и той же точке.

Перекрывающиеся звезды

Приведем еще один пример. Это немного сложнее для понимания, чем предыдущее, но оно также более характерно для типов проблем с регулярными выражениями, которые возникают в реальном программном обеспечении (см. Отключение переполнения стека). Итак, давайте попробуем использовать этот подход на этой картинке, со строкой aaa… aab, которая состоит из N + 1 букв.

  • Механизм регулярных выражений запускается с левой стороны и имеет выбор: он может использовать первый a в цикле (а затем снова столкнуться с тем же выбором) или пропустить цикл и перейти к следующему .
  • Когда он перейдет ко второму циклу, он поглотит оставшиеся там a.
  • Когда все элементы a израсходованы, он встречает b и отклоняет этот путь поиска.

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

  • Механизм регулярных выражений должен использовать последовательность a. Он может разделить эту последовательность на «левую половину» и «правую половину» и передать левую половину первому a -циклу, а правую половину - второму a -петля.
  • Каждый цикл может занимать от нуля до всех элементов a, поэтому мы можем разделить строку на N точек - это решение N. указывает в первом a -цикле, где мы решаем, оставаться или двигаться дальше.
  • Итак, у нас есть N путей с ошибками, и каждый из путей требует, чтобы мы использовали все N символов в строке. Это означает, что алгоритм выполняет N² шагов, прежде чем объявить сбой. Это небольшое упрощение, так как пути разделяют некоторую работу - N путей подразумевают, соответственно, 1 отдельный шаг, 2 отдельных шага и так далее, при затратах 1 + 2 +… + N-1 + N = N².

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

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