Это краткое изложение исследовательской работы Влияние отказа в обслуживании при регулярном выражении (REDOS) на практике: эмпирическое исследование в масштабе экосистемы »e,, опубликованной на ESEC / FSE 2018. Я был первый автор; Замыкают команду Кристи Коглан, Слуга Франциско и Донъюн Ли.

Если вы хотите получить представление о ReDoS, см. Мою Шпаргалку по ReDoS.

Резюме

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

К сожалению, как показали предыдущие исследования, некоторые совпадения регулярных выражений имеют полиномиальную или даже экспоненциальную сложность длины входных данных. Такое плохое поведение требует, чтобы программа выполняла «ReDoS regex» на ненадежных входных данных. Хотя ненадежный ввод довольно распространен в веб-домене, насколько распространены регулярные выражения ReDoS?

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

  • Извлечено около 400 000 уникальных регулярных выражений из примерно 500 000 модулей npm и pypi;
  • Определено, сколько из этих регулярных выражений были регулярными выражениями ReDoS (~ 1%) * (см. Продолжение внизу);
  • Замерил их сложность (большинство из них квадратичные и начинают медленно работать при отметке около 10К символов на типичном настольном компьютере);
  • Помеченные общие семейства регулярных выражений (у нас есть сотни различных примеров регулярных выражений, которые идентифицируют электронные письма!);
  • Изучена эффективность эвристики для определения регулярных выражений ReDoS (множество ложных срабатываний); а также
  • Изучал, как разработчики исправляют регулярные выражения ReDoS (обрезать, исправлять или заменять).

Вступление

Регулярные выражения (регулярные выражения) - удобный инструмент для обработки текста. Люди используют их для таких вещей, как проверка ввода. Например, вопрос «Строка, введенная пользователем, похожа на электронное письмо?» можно ответить с помощью регулярного выражения.

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

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

Регулярное выражение отказа в обслуживании (ReDoS)

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

Этот тип дорогостоящего поведения обсуждался в академическом сообществе с 1970-х годов, и, насколько мне известно, его актуальность для проблем веб-безопасности была впервые отмечена в 2003 году. Однако крупномасштабных исследований ReDoS в реальных условиях не проводилось. Я всегда думал об этом больше как о академической уловке, чем как о серьезной проблеме на практике. Однако во время моего проекта Чувство времени я был удивлен, обнаружив, что около 10% уязвимостей безопасности, обнаруженных в npm, были уязвимостями ReDoS. Это заставило меня задуматься, может ли ReDoS быть серьезной проблемой на практике.

ReDoS regex, пример 1: экспоненциальные имена пользователей от Microsoft

Во время некоторой исследовательской работы мы обнаружили это регулярное выражение в проекте Microsoft. Он используется для сопоставления имен пользователей Windows.

/^[a-zA-Z0–9]+([._]?[a-zA-Z0–9]+)*$/

Во многих языках это регулярное выражение экспоненциально на входе «aaa… aaa!». Вот пример, который вы можете попробовать в Node.js:

/^[a-zA-Z0–9]+([._]?[a-zA-Z0–9]+)*$/.exec('a'.repeat(100) + '!')

ReDoS regex, пример 2: квадратичные электронные письма в Django

Мы нашли это регулярное выражение в Django. Он использовался для сопоставления электронных писем.

/^\S+@\S+\.\S+$/

Во многих языках это регулярное выражение квадратично для ввода ‘@@@… @@@’. Вот пример, который вы можете попробовать в Node.js:

/^\S+@\S+\.\S+$/.exec('@'.repeat(100000))

Почему эти совпадения регулярных выражений занимают так много времени?

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

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

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

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

Давайте подумаем о его поведении на строке «ааа!».

  • Каждый раз, когда механизм регулярных выражений видит «а», он может взять либо внутренний цикл, либо внешний цикл из вершины «а».
  • Это означает, что каждая «а», которую он видит, будет удваивать количество путей, которые он будет пробовать при несоответствии: «все пути, которые он уже собирался попробовать, за которыми следует либо внутренний цикл, либо внешний петля на этой конкретной букве «а» ».
  • Финал "!" гарантирует, что механизм регулярных выражений не найдет совпадения ни на одном из этих путей.
  • Итак, с тремя «а» у нас есть 2 * 2 * 2 пути, которые можно попробовать. Если мы добавим еще одну букву «а», у нас будет (2 * 2 * 2) * 2 пути, которые нужно будет попробовать. Для входов этой формы поведение будет экспоненциальным от числа «а».

Сбор регулярных выражений

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

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

  • Получите список всех модулей в реестрах npm (JavaScript) и pypi (Python).
  • Оставьте те, у которых есть репозитории, которые мы можем клонировать.
  • Статически извлекать регулярные выражения из файлов JavaScript (npm) и Python (pypi). Мы обнаружили, что регулярные выражения используются довольно широко: 45% изученных нами модулей npm и 35% изученных нами модулей pypi включают как минимум одно регулярное выражение.
  • Сократите до (гигантских) списков уникальных регулярных выражений.

Определение регулярных выражений ReDoS

На этом рисунке показано, как мы идентифицировали регулярные выражения ReDoS из наших гигантских списков регулярных выражений («корпусов»).

  • Примените детекторы ReDoS regex (драйверы см. Здесь).
  • Динамически проверяйте регулярные выражения, которые они считают опасными для интересующего вас языка (npm → Node.js; pypi → Python).
  • Определите, сколько модулей содержат эти регулярные выражения в своем GitHub / etc. проект.

Мы нашли похожие результаты в npm и pypi.

Известные места, где мы нашли регулярные выражения ReDoS

Мы нашли регулярные выражения ReDoS (ура!) В:

  • MongoDB
  • Хапи
  • Джанго

Мы также нашли их (двойной eek!) В:

  • Базовые библиотеки Node.js
  • Базовые библиотеки Python

К счастью, все это теперь исправлено.

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

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

Опять же, мы нашли аналогичные результаты в npm и pypi.

Как люди исправляют регулярные выражения ReDoS?

Мы хотели понять, как люди исправляют регулярные выражения ReDoS после того, как идентифицируют их в своем коде. Мы рассмотрели исправления 37 уязвимостей ReDoS, обнаруженных в базах данных CVE и Snyk.io.

Разработчики использовали одну из трех стратегий:

  • Обрезать Не трогайте регулярное выражение. Просто обрежьте ввод, чтобы он не был слишком длинным, что ограничивает худшее поведение. Это нормально работает при условии, что (1) допустимый ввод не должен быть «слишком длинным» (например, 500 символов?); и (2) поведение наихудшего случая не является экспоненциальным.
  • Изменить. Настройте регулярное выражение, чтобы оно больше не было уязвимо для ReDoS, но по-прежнему соответствовало тому же языку. Или похожие. Будьте осторожны - мы видели несколько случаев, когда исправленное регулярное выражение становилось безопасным для одного ввода, но уязвимо для нового стиля ввода.
  • Заменить. Заменить регулярное выражение строковыми операциями.

Затем мы разослали сообщения об уязвимостях в 284 проекта с описанием возможных регулярных выражений ReDoS в них. 48 проектов ответили исправлением. Самым популярным вариантом оставался вариант «Ревизия». Интересно, что многие из этих исправленных регулярных выражений не соответствовали тому же набору строк, что и исходное регулярное выражение.

Выводы

Мы считаем, что наше исследование показывает, что

  • ReDoS - это настоящая проблема на практике, и
  • Сообществу практиков нужны более совершенные инструменты для обнаружения и исправления регулярных выражений ReDoS.

Больше информации

  1. Полный текст статьи доступен здесь. В нем есть больше деталей и дополнительный контент.
  2. Слайды PowerPoint находятся здесь.
  3. Артефакт исследования находится на Зенодо здесь. Он включает ~ 400K уникальных регулярных выражений, которые мы определили в модулях npm и pypi, на случай, если вам понадобится гигантский корпус регулярных выражений.
  4. Наши драйверы для ансамбля детекторов регулярных выражений ReDoS поддерживаются на GitHub здесь.

Обновление - 07.11.2019

Во время проекта Lingua Franca (запись в блоге здесь) мы улучшили суперлинейные детекторы регулярных выражений, чтобы исключить ложноотрицательные результаты. Используя улучшенные детекторы, мы обнаружили, что до 10% регулярных выражений демонстрируют сверхлинейное поведение в худшем случае. Это на порядок больше, чем мы сообщали в этой статье!

Подпишитесь на Infosec Write-ups, чтобы увидеть больше таких замечательных статей.



Записи InfoSec
Коллекция рецензий лучших хакеров мира по самым разным темам, от вознаграждений за ошибки и CTF до vulnhub… medium.com