Как бороться с ReDoS

Проверка кода (Code Scanning) автоматически обнаруживает ReDoS-уязвимости, но исправить их бывает не всегда просто. В этой статье описана 4-х этапная стратегия исправления багов ReDoS.

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

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

Хорошая новость заключается в том, что уязвимости ReDoS легко обнаружить благодаря запросам CodeQL, которые были включены в Code Scanning с 2017 года и значительно улучшены моим коллегой, Эриком Кристенсеном, в 2021 году. Плохая же новость заключается в том, что исправление этих уязвимостей по-прежнему производится вручную. В этой статье я постараюсь дать вам несколько советов, которые помогут вам фиксить баги ReDoS. По моему опыту, многие из этих багов можно исправить, изменив всего один или два символа в регулярном выражении; но бывает непросто понять, какие именно символы нужно изменить. Все примеры в этой статье приведены на Python, но те же принципы применимы и к другим языкам, например, Javascript.

Прежде чем выпустить запросы CodeQL ReDoS в 2021 году, мы проверили их на максимально возможном количестве проектов с открытым исходным кодом и отправили отчёты об уязвимостях большому количеству ответственных лиц. Это была командная работа: авторы запросов CodeQL (в частности, Erik Kristensen, Rasmus Petersen, Nick Rolfe, Tony Torralba, и Joseph Farebrother) провели большую часть анализа, а GitHub Security Lab (команда, в которую вхожу я) написала отчёты и отправила их ответственным лицам затронутых проектов. Я сам работал примерно над 20 отчётами. К сожалению, несколько ответственных, которым я сообщал об уязвимостях ReDoS, так и не ответили на мои сообщения, что означало, что я не мог закрыть тикеты. Поскольку уязвимости были низкой степени серьёзности, и я не мог связаться с ответственными, я решил, что лучшим решением будет отправка [публичных] пулл-реквестов на исправление. Эта стратегия оказалась гораздо более успешной. Выясняя, как исправить эти баги, я научился техникам, о которых расскажу в этой статье.

Я очень удивлюсь, если какая-либо другая нотация программирования будет столь же плотной, как regex (регулярное выражение). Количество логики, которую можно упаковать всего примерно в 10 символов, просто поражает. В результате регулярные выражения превратились в маленькие самородки мудрости, которыми можно делиться друг с другом. К сожалению, это также может привести к тому, что ошибочные регулярные выражения станут распространяться, подобно вирусу. Интересным примером этого является огромное регулярное выражение для URL, вариации которого мы видели во многих репозиториях с открытым исходным кодом. Некоторые его версии имеют уязвимости к ReDoS-атаке, и из-за его размера его довольно сложно исправить. На самом деле, когда я в последний раз пытался это сделать, я уж было подумал, что это невозможно; но недавно обнаружил, что у этой проблемы есть простое решение — о нём расскажу ниже.

Что такое ReDoS?

ReDoS — это уязвимость типа «отказ в обслуживании» (denial-of-service, DOS), при которой регулярное выражение работает на некоторых входных данных исключительно медленно. Вот простой пример, частично основанный на одной из уязвимостей, которую нашёл наш CodeQL запрос:

(bb|b.)*a

Это регулярное выражение не может обрабатывать длинные строки вида "bbbbbb...", в чём вы можете убедиться сами, запустив этот Python-скрипт:

import re
import time
for n in range(100):
    start_time = time.time()
    re.match("(bb|b.)*a", "b" * n)
    print(n, time.time() - start_time)

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

Я был озадачен, когда впервые услышал о концепции ReDoS, поскольку знал, что регулярные выражения могут быть реализованы как детерминированные конечные автоматы (Deterministic Finite Automaton — DFA). Это означает, что время их выполнения должно быть линейным относительно размера входных данных при постоянном использовании памяти. Как перейти от этого к экспоненциальному времени выполнения? Проблема в том, что во многих языках программирования используется движок регулярных выражений, который не преобразует регулярное выражение в DFA. Например, в Python используется реализация недетерминированного конечного автомата (NFA) с обратным возвратом, что и служит причиной отвратительной производительности. Алгоритм, который Python использует для оценки приведённого выше примера, примерно эквивалентен этому коду:

def matchit(str, i):
    if i+2 <= len(str) and str[i] == 'b' and str[i+1] == 'b' and matchit(str, i+2):
        return True
    elif i+2 <= len(str) and str[i] == 'b' and matchit(str, i+2):
        return True
    elif i+1 <= len(str) and str[i] == 'a':
        return True
    else:
        return False

Обратите внимание, что есть два рекурсивных вызова matchit — они будут вызваны, если строка не совпадёт. Для строк вида "bbbbbb..." рекурсия идёт настолько глубоко, насколько длинна строка, что означает экспоненциальный размер дерева поиска.

Важно понять, что «выбор» (например, a|b|c) реализуется в виде каскада if-then-else, а повторение (например, + или ) — с помощью рекурсии. В сочетании эти два элемента могут привести к экспоненциально большим деревьям поиска.

Только некоторые языки программирования имеют уязвимые для ReDoS regex-движки. Большинство уязвимостей ReDoS, с которыми я сталкивался, были связаны с Python или Javascript, но они могут встречаться и в других языках, таких как C#, Java, Ruby, Perl и PHP. С другой стороны, Go, Rust и библиотека RE2 для C++ не уязвимы для ReDoS. Java (начиная с версии 9) и Ruby (начиная с версии 3.2.0) внесли улучшения в свои regex-движки, что делает появление ReDoS-уязвимостей менее вероятным. У нас есть CodeQL-запросы на ReDoS в Javascript, Python, Java, C# и Ruby.

Как исправить ReDoS

Итак, CodeQL говорит, что ваше регулярное выражение содержит ReDoS. Что вы должны сделать?

В качестве примера я использую ReDoS из проекта Airbnb's streamalert:

Шаг 1: Создание PoC

Первый шаг — воспроизвести проблему. В оповещении о проверке кода приведена инструкция по тому, как воспроизвести баг:

«Эта часть регулярного выражения может вызвать экспоненциальный backtracking (возврат к исходным данным) в строках, начинающихся с '-.' и содержащих много повторений '-.'".

Я обнаружил, что отладка становится намного проще, если создать отдельную программу на Python для воспроизведения бага:

import re
_URL_REGEX = re.compile(
    r'^(?:http(s)?://)?[\w.-]+(?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]+$'
)
_URL_REGEX.fullmatch("-." + "-." * 100)

Однако эта программа завершается мгновенно. Почему же она не запускает ReDoS? Ответ в том, что регулярное выражение не должно найти совпадения, чтобы он был вынужден исследовать всё экспоненциальное дерево поиска. Обычно этого можно добиться, добавив в конец строки необычный символ. В данном случае хорошо работает символ %:

_URL_REGEX.fullmatch("-." + "-." * 100 + "%")

При таком изменении тестовая программа запускает ReDoS.

Шаг 2: Уменьшение проблемы

Регулярные выражения очень плотные. Приведённое ниже состоит всего из 77 символов, но от него всё равно болит голова:

^(?:http(s)?://)?[\w.-]+(?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]+$

Мне гораздо проще решить ReDoS, если сначала отсечь всё, что не имеет отношения к проблеме. Поэтому я редактирую свою тестовую программу, стараясь сделать регулярное выражение как можно короче, сохраняя при этом ReDoS. Например, первая часть этого регулярного выражения — (?:http(s)?://)?. Символ ? в конце означает, что этот сегмент необязателен — поэтому я могу удалить его, оставив более простое регулярное выражение, который всё ещё имеет ReDoS:

^[\w.-]+(?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]+$

После каждого шага я повторно запускаю тест, чтобы убедиться, что ReDoS всё ещё проявляется. Вот некоторые общие шаги по упрощению:

• Удалите необязательные разделы, такие как X? или X.

• Замените X+ на X.

• Заменить X|Y на просто X или просто Y.

• Упростите диапазоны символов. Например, замените [a-z0-9] на [ab].

Применим некоторые из этих шагов, чтобы ещё больше упростить это регулярное выражение:

^[\w.-]+(?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]+$	убрать +
^[\w.-](?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]+$	убрать +
^[\w.-](?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]$	упростить диапазоны символов
^[-](?:\.[\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]$	упростить диапазон символов
^[-](?:\.[\.-]+)+[\w]$	использовать обычные скобки
^[-](\.[\.-]+)+[\w]$

Наконец, я заменяю такие символы, как - и ., на буквы, например x и y, чтобы было легче читать. Входная строка в PoC нуждается в соответствующем изменении:

import re
_URL_REGEX = re.compile(
    r'^x(y[yx]+)+z$'
)
_URL_REGEX.fullmatch("xy" + "xy" * 100 + "%")

Шаг 3: Определение проблемы и переписывание регулярного выражения

Теперь ясно, что за ReDoS отвечает этот сегмент:

(y[yx]+)+

Это потому, что существует несколько способов его соответствия строке типа "yxyxyxyxyxyx", как показано ниже, с добавлением круглых скобок, чтобы показать, где может совпасть внутренний +:

• (yx)(yx)(yx)(yx)(yx)(yx)

• (yxyx)(yxyx)(yxyx)

• (y)(xyxyxyxyxyx)

• ...

Если подумать, то внутренний сегмент регулярного выражения (y[yx]+) может спарсить любую строку типа "yxyyxxxyx..." — то есть любую строку, которая начинается с y и за которой следует произвольная последовательность символов x или y. Другими словами, внутренний сегмент уже достаточно гибкий, чтобы спарсить любую валидную строку, а внешний + ничего не добавляет (кроме ReDoS). Поэтому я могу избавиться от ReDoS, удалив внешний +:

y[yx]+

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

старая	^(?:http(s)?://)?[\w.-]+(?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]+$
новая	^(?:http(s)?://)?[\w.-]+(?:\.[\w\.-]+)[\w\-\._~:/?#[\]@!\$＆\'\(\)\*\+,;=.]+$

Исправление регулярного выражения — это всегда самый сложный шаг. Вы должны понять шаблон, который он пытается спарсить, и понять, можно ли добиться того же с помощью меньшего количества операторов (например, + или |). Но гораздо легче найти решение, если сначала максимально сократить проблему.

Не забывайте, что вы можете использовать Code Scanning для подтверждения того, что ваше обновлённое регулярное выражение действительно свободно от ReDoS.

Шаг 4: Используйте fuzzer для проверки исправления

Правильно подобрать регулярное выражение очень сложно, поэтому без тщательного тестирования не обойтись. Важно проверить, не изменили ли вы случайно поведение регулярного выражения. Если вы используете Python, то я рекомендую использовать для этого фаззер atheris. Ниже приведен пример скрипта, который использует atheris для сравнения двух регулярных выражений:

#! /usr/bin/env python3
import atheris
import sys
import re

regex_old = re.compile(r"a(?P[b-z]+)c", flags=re.UNICODE)
regex_new = re.compile(r"a(?P[b-y]+)c", flags=re.UNICODE)

# Extract data from a Match object so that it can be tested for equality.
def getMatchData(result):
    if result is None:
        return None
    return (result.group(), result.groups(), result.groupdict())

def TestOneInput(input_bytes):
    try:
        s = input_bytes.decode('utf-8')
    except:
        return
    if getMatchData(regex_old.fullmatch(s)) != getMatchData(regex_new.fullmatch(s)):
        raise RuntimeError("results don't match!")

atheris.instrument_all()
atheris.Setup(sys.argv, TestOneInput)
atheris.Fuzz()

Запустите скрипт:

python3 fuzz_regexes.py -max_len=10

Если же вы хотите задействовать все свои ядра и у вас есть каталог corpus, содержащий тест-кейсы, то можно провести более эффективный фаззинг (синтаксис командной строки такой же, как у libFuzzer):

python3 `realpath fuzz_regexes.py` corpus/ -jobs=$(nproc) -workers=$(nproc) -max_len=10

Скрипт проверяет, что regex_old.fullmatch(s) и regex_new.fullmatch(s) вычисляют один и тот же результат. В приведённом выше примере два регулярных выражения намеренно отличаются, и atheris обычно способен найти контрпример (например, "azc") за пару минут. Очевидно, что для сложных регулярных выражений это может занять больше времени, поэтому я бы рекомендовал оставить фаззер работать как минимум на несколько часов. Обратите внимание, что можно использовать параметр -max_len, чтобы контролировать максимальный размер входной строки. Обычно ошибки регулярных выражений можно воспроизвести с очень короткой входной строкой, но если у вас очень сложное регулярное выражение, то вам может понадобиться увеличить максимальную длину, чтобы охватить все возможности.

История о вирусном ReDoS

Люди любят делиться регулярными выражениями. Мы столкнулись с интересным примером, когда искали ReDoS-уязвимости в проектах с открытым исходным кодом, потому что постоянно находили один и тот же ReDoS во многих несвязанных проектах. ReDoS находится в огромном регулярном выражении для парсинга URL. Вот несколько примеров: validators, textacy и dparse. (Перейдите по одной из этих ссылок, чтобы посмотреть, о чём я говорю). Нет никакой тайны в том, откуда взялся ReDoS, потому что многие регулярные выражения содержат комментарий вроде этого:

# source: https://gist.github.com/dperini/729294

Интересно, что регулярное выражение в этом gist не имеет ReDoS сейчас, но если обратиться к истории ревизий, то можно увидеть, что он имел ReDoS до 2018-09-12. Многие проекты до сих пор используют старую, уязвимую версию регулярного выражения, что не удивительно, поскольку этот ответ на Stack Overflow был написан в 2012 году, так что люди используют это регулярное выражение как минимум столько же времени.

Я совершил две большие ошибки, когда сообщил об этой ReDoS-уязвимости нескольким проектам ещё в 2021 году. Первая ошибка заключалась в том, что я так и не удосужился выполнить наш ReDoS-запрос на самой актуальной версии регулярного выражения из gist. Если бы я это сделал, то понял бы, что ReDoS в gist уже исправлен, и мог бы посоветовать проектам обновиться до последней версии. На самом деле, я понял это только во время написания этой статьи: я был настолько сосредоточен на текущих багах, что не изучил историю регулярного выражения.

Вторая моя ошибка заключалась в том, что я испугался размера регулярного выражения. Я сделал лишь полусерьёзную попытку исправить ReDoS, прежде чем пришёл к (неверному) выводу, что такое большое регулярное выражение наверняка неисправимо. Опять же, только при написании этой статьи я обнаружил, что его можно исправить, удалив всего два символа +. С тех пор я отправил пулл-реквесты (здесь и здесь), чтобы закрыть две из оставшихся проблем, которые висели с 2021 года.

Исправление ReDoS валидатора URL

Шаги по исправлению этого ReDoS точно такие же, как я описал ранее. И хотя регулярное выражение выглядит устрашающе, в нём есть огромные сегменты, которые можно быстро устранить. В качестве примера я использую textacy. ReDoS может быть вызван длинной строкой, например, такой:

http://0.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00…

После создания автономного PoC я понял, что большие сегменты регулярного выражения можно быстро удалить на этапе сокращения. Например, строки 56-69 не участвуют в ReDoS и могут быть удалены. После ещё нескольких шагов сокращения PoC стал гораздо более управляемым:

import re
url_regex = re.compile(
    r"http://"
    r"("
    # host name
    r"(([0-9]-?)*[0-9]+)"
    # domain name
    r"(\.([0-9]-?)*[0-9]+)*"
    # TLD identifier
    r"[a-z]"
    r")",
    flags=re.IGNORECASE
)
url_regex.fullmatch("http://0" + ".00" * 100)

После ещё нескольких шагов по сокращению стало ясно, что я могу исправить ReDoS, удалив два символа + из этого фрагмента:

# host name
r"(?:(?:[a-z\u00a1-\uffff0-9]-?)*[a-z\u00a1-\uffff0-9]+)"
# domain name
r"(?:\.(?:[a-z\u00a1-\uffff0-9]-?)*[a-z\u00a1-\uffff0-9]+)*"

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

Заключение

Мне грустно от того, что ReDoS вообще существует как класс уязвимостей. Теория DFA была понятна еще в 1940-х годах, поэтому, на мой взгляд, нет никакого оправдания для regex-движков с экспоненциальным поведением во время выполнения. Будем надеяться, что больше языков последуют примеру Ruby 3.2.0 и улучшат свои regex-движки, чтобы уменьшить количество ReDoS уязвимостей. Хорошей новостью является то, что проверка кода может обнаружить ReDoS-уязвимости, так что это должно помочь устранить их. Если вы обнаружили, что в вашем проекте есть ReDoS, то я надеюсь, что шаги, описанные в этой статье, помогут вам быстро устранить её.

В завершение приглашаем всех тестировщиков, которые хотят начать заниматься автоматизацией на Java, на открытый урок, посвященный паттерну Page Object. Записаться можно по ссылке.