ReDoS
Атака типа «отказ в обслуживании» с использованием регулярных выражений

Отказ в обслуживании с помощью регулярного выражения ( ReDoS ) [ 1] — это атака на алгоритмическую сложность , которая вызывает отказ в обслуживании , предоставляя регулярное выражение и/или входные данные, оценка которых занимает много времени. Атака использует тот факт, что многие [2] реализации регулярных выражений имеют сверхлинейную сложность в худшем случае ; на определенных парах регулярное выражение-входные данные затраченное время может расти полиномиально или экспоненциально по отношению к размеру входных данных. Таким образом, злоумышленник может заставить программу тратить значительное время, предоставляя специально созданное регулярное выражение и/или входные данные. После этого программа замедлится или перестанет отвечать. [3] [4]

Описание

Сопоставление регулярных выражений («regex») может быть выполнено путем построения конечного автомата . Regex можно легко преобразовать в недетерминированные автоматы (NFA), в которых для каждого состояния и входного символа может быть несколько возможных следующих состояний. После построения автомата существует несколько возможностей:

  • движок может преобразовать его в детерминированный конечный автомат (DFA) и пропустить входные данные через результат;
  • движок может попробовать один за другим все возможные пути, пока не будет найдено совпадение или все пути будут испробованы и потерпят неудачу («возврат»). [5] [6]
  • двигатель может параллельно рассматривать все возможные пути через недетерминированный автомат;
  • движок может преобразовать недетерминированный автомат в DFA лениво ( т.е. на лету, во время матча).

Из вышеперечисленных алгоритмов первые два являются проблематичными. Первый является проблематичным, поскольку детерминированный автомат может иметь до состояний, где — число состояний в недетерминированном автомате; таким образом, преобразование из NFA в DFA может занять экспоненциальное время . Второй является проблематичным, поскольку недетерминированный автомат может иметь экспоненциальное число путей длины , так что прохождение по входу длины также займет экспоненциальное время. [7] Последние два алгоритма, однако, не демонстрируют патологического поведения. 2 м {\displaystyle 2^{м}} м {\displaystyle м} н {\displaystyle n} н {\displaystyle n}

Обратите внимание, что для непатологических регулярных выражений проблемные алгоритмы обычно быстры, и на практике можно ожидать, что они « скомпилируют » регулярное выражение за время O(m) и сопоставят его за время O(n); вместо этого моделирование NFA и ленивое вычисление DFA имеют сложность O (m 2 n) в худшем случае. [a] Отказ в обслуживании регулярных выражений происходит, когда эти ожидания применяются к регулярному выражению, предоставленному пользователем, и вредоносные регулярные выражения, предоставленные пользователем, запускают наихудшую сложность сопоставителя регулярных выражений.

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

Примеры

Экспоненциальный возврат

Наиболее серьезный тип проблемы возникает при обратном поиске соответствий регулярных выражений, где некоторые шаблоны имеют время выполнения, которое экспоненциально зависит от длины входной строки. [8] Для строк символов время выполнения составляет . Это происходит, когда регулярное выражение имеет три свойства: н {\displaystyle n} О ( 2 н ) {\displaystyle O(2^{n})}

  • регулярное выражение применяет повторение ( +, *) к подвыражению;
  • подвыражение может соответствовать одному и тому же вводу несколькими способами, или подвыражение может соответствовать входной строке, которая является префиксом более длинного возможного соответствия;
  • и после повторяющегося подвыражения следует выражение, которое соответствует чему-то, чему подвыражение не соответствует.

Второе условие лучше всего объяснить на двух примерах:

  • в (a|a)+$повторение применяется к подвыражению a|a, которое может сопоставляться aдвумя способами с каждой стороны чередования.
  • в (a+)*$повторение применяется к подвыражению a+, которое может соответствовать aили aaи т. д.

В обоих этих примерах мы использовали $для сопоставления конец строки, удовлетворяя третьему условию, но для этого также можно использовать другой символ. Например, (a|aa)*cимеет ту же проблемную структуру.

Все три из приведенных выше регулярных выражений будут демонстрировать экспоненциальное время выполнения при применении к строкам формы . Например, если вы попытаетесь сопоставить их с движком выражений с возвратом, это займет значительно больше времени, а время выполнения будет примерно удваиваться для каждого дополнительного выражения перед . а . . . а ! {\displaystyle а...а!} aaaaaaaaaaaaaaaaaaaaaaaa!a!

Также возможно обратное отслеживание, которое является полиномиальным временем , а не экспоненциальным. Это также может вызвать проблемы для достаточно длинных входных данных, хотя этой проблеме уделялось меньше внимания, поскольку вредоносный входной сигнал должен быть намного длиннее, чтобы иметь значительный эффект. Примером такого шаблона является " ", когда входные данные представляют собой произвольно длинную последовательность " ". О ( н х ) {\displaystyle O(n^{x})} a*b?a*xa

Уязвимые регулярные выражения в онлайн-репозиториях

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

  1. RegExLib, id=1757 (проверка адреса электронной почты) - см. красную часть
    ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
  2. Репозиторий регулярных выражений проверки OWASP, имя класса Java — см. красную часть
    ^(([a-z])+.)+[A-Z]([a-z])+$

Эти два примера также восприимчивы к входным данным aaaaaaaaaaaaaaaaaaaaaaaa!.

Атаки

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

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

В случае веб-приложения программист может использовать одно и то же регулярное выражение для проверки ввода как на стороне клиента, так и на стороне сервера системы. Злоумышленник может проверить клиентский код, ища вредоносные регулярные выражения, и отправить созданный ввод непосредственно на веб-сервер, чтобы повесить его. [9]

Смягчение

ReDoS можно смягчить без внесения изменений в механизм регулярных выражений, просто установив ограничение по времени для выполнения регулярных выражений при использовании ненадежных входных данных. [10]

ReDoS можно полностью избежать, используя неуязвимую реализацию регулярных выражений. После того, как брандмауэр веб-приложений CloudFlare (WAF) был выведен из строя PCRE ReDoS в 2019 году, компания переписала свой WAF для использования библиотеки регулярных выражений Rust без возврата, используя алгоритм, аналогичный RE2 . [11] [12]

Уязвимые регулярные выражения могут быть обнаружены программно с помощью линтера . [13] Методы варьируются от чисто статического анализа [14] [15] до фаззинга . [16] В большинстве случаев проблемные регулярные выражения могут быть переписаны как «незлые» шаблоны. Например, (.*a)+можно переписать в ([^a]*a)+. Притяжательное соответствие и атомарная группировка , которые отключают возврат для частей выражения, [17] также могут использоваться для «успокоения» уязвимых частей. [18] [19]

Смотрите также

Ссылки

  1. ^ Ленивое вычисление DFA обычно может достигать скорости детерминированных автоматов, сохраняя при этом поведение в худшем случае, аналогичное моделированию NFA. Однако его значительно сложнее реализовать, и он может использовать больше памяти.
  1. ^ OWASP (2010-02-10). "Regex Denial of Service" . Получено 2010-04-16 .
  2. ^ Дэвис, Джеймс; Луис, Майкл; Коглан, Кристи; Сервант, Франциско; Ли, Донюн (2019). «Почему регулярные выражения не являются языком общения? Эмпирическое исследование повторного использования и переносимости регулярных выражений» (PDF) . Объединенная европейская конференция и симпозиум ACM по основам программной инженерии : 443–454 .
  3. ^ RiverStar Software (2010-01-18). "Бюллетень безопасности: осторожность при использовании регулярных выражений". Архивировано из оригинала 2011-07-15 . Получено 2010-04-16 .
  4. ^ Ристич, Иван (2010-03-15). ModSecurity Handbook. Лондон, Великобритания: Feisty Duck Ltd. стр. 173. ISBN 978-1-907117-02-2. Архивировано из оригинала 2016-08-08 . Получено 2010-04-16 .
  5. ^ Crosby и Wallach, Usenix Security (2003). "Regular Expression Denial Of Service". Архивировано из оригинала 2005-03-01 . Получено 2010-01-13 .
  6. ^ Брайан Салливан, журнал MSDN (03.05.2010). "Атаки на отказ в обслуживании с использованием регулярных выражений и методы защиты" . Получено 06.05.2010 . {{cite web}}: Внешняя ссылка в |author=( помощь )CS1 maint: числовые имена: список авторов ( ссылка )
  7. ^ Kirrage, J.; Rathnayake, A.; Thielecke, H. (2013). «Статический анализ атак типа «отказ в обслуживании» с использованием регулярных выражений». Сетевая и системная безопасность . Мадрид, Испания: Springer. С.  135–148 . arXiv : 1301.0849 . doi : 10.1007/978-3-642-38631-2_11.
  8. ^ Джим Манико и Адар Вайдман (2009-12-07). "OWASP Podcast 56 (ReDoS)" . Получено 2010-04-02 .
  9. ^ Барлас, Эфе; Ду, Синь; Дэвис, Джеймс (2022). «Использование очистки входных данных для отказа в обслуживании регулярных выражений» (PDF) . Международная конференция ACM/IEEE по программной инженерии : 1–14 . arXiv : 2303.01996 .
  10. ^ "Backtracking in .NET regular expressions - .NET". learn.microsoft.com . 11 августа 2023 г. При использовании System.Text.RegularExpressions для обработки ненадежных входных данных передайте тайм-аут. Злонамеренный пользователь может предоставить входные данные RegularExpressions, что приведет к атаке типа "отказ в обслуживании". API-интерфейсы фреймворка ASP.NET Core, использующие RegularExpressions, передают тайм-аут.
  11. ^ "Сделаем WAF на 40% быстрее". Блог Cloudflare . 1 июля 2020 г.
  12. ^ Кокс, Расс (2007). "Соответствие регулярным выражениям может быть простым и быстрым" . Получено 20 апреля 2011 г.– описывает алгоритм RE2
  13. ^ См., например, Шмидт, Михаэль (30 марта 2023 г.). "RunDevelopment/scslre". GitHub ., ЦУЮСАТО, Кицунэ. "перепроверьте Введение"., и Дэвис, Джеймс. "vuln-regex-detector/src/detect/README.md". GitHub .
  14. ^ H. Thielecke, A. Rathnayake (2013). "Regular expression Denial of Service (ReDoS) статический анализ Архивировано 2014-08-03 на Wayback Machine ". Получено 2013-05-30.
  15. ^ Б. ван дер Мерве, Н. Вайдеман (2017). «Статический анализ регулярных выражений». Проверено 12 августа 2017 г.
  16. ^ "Fuzzing with Static Analysis | перепроверить". makenowjust-labs.github.io .
  17. ^ "Essential classes: Regular Expressions: Quantifiers: Differences Among Greedy, Reluctant, and Possessive Quantifiers". Учебники Java . Oracle . Архивировано из оригинала 7 октября 2020 г. Получено 23 декабря 2016 г.
  18. ^ "compose-regexp.js, "Атомарное сопоставление"". GitHub . 2 января 2024 г.
    "tc39/proposal-regexp-atomic-operators". Ecma TC39. 31 декабря 2023 г.
  19. ^ «Предотвращение отказа в обслуживании с помощью регулярных выражений (ReDoS)». www.regular-expressions.info .
  • Примеры ReDoS в приложениях с открытым исходным кодом:
    • ReDoS в DataVault (CVE-2009-3277)
    • ReDoS в EntLib (CVE-2009-3275)
    • ReDoS в NASD CORE.NET Terelik (CVE-2009-3276)
  • Некоторые тесты для ReDoS
    • Ахим Хоффман (2010). "ReDoS - бенчмарк для DoS-атак с использованием регулярных выражений в JavaScript". Получено 19 апреля 2010 г.
    • Ричард М. Смит (2010). "Результаты теста атаки типа "отказ в обслуживании" с использованием регулярных выражений (ReDoS)". Получено 19 апреля 2010 г.
Взято с "https://en.wikipedia.org/w/index.php?title=ReDoS&oldid=1253382915"