РеДоС

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

Описание

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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}))$
Репозиторий регулярных выражений проверки 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]

См. также

Ссылки

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

^ OWASP (10 февраля 2010 г.). «Отказ в обслуживании регулярных выражений» . Проверено 16 апреля 2010 г.
^ Дэвис, Джеймс; Луи, Майкл; Коглан, Кристи; Слуга, Франциско; Ли, Донюн (2019). «Почему регулярные выражения не являются лингва-франка? Эмпирическое исследование повторного использования и переносимости регулярных выражений» (PDF) . Объединенная европейская конференция ACM по разработке программного обеспечения и симпозиум по основам программной инженерии : 443–454.
^ Программное обеспечение RiverStar (18 января 2010 г.). «Бюллетень по безопасности: осторожность при использовании регулярных выражений» . Архивировано из оригинала 15 июля 2011 г. Проверено 16 апреля 2010 г.
^ Ристич, Иван (15 марта 2010 г.). Руководство по ModSecurity . Лондон, Великобритания: Feisty Duck Ltd., с. 173. ИСБН 978-1-907117-02-2 . Архивировано из оригинала 8 августа 2016 г. Проверено 16 апреля 2010 г.
^ Кросби и Уоллах, Usenix Security (2003). «Отказ в обслуживании с помощью регулярных выражений» . Архивировано из оригинала 1 марта 2005 г. Проверено 13 января 2010 г.
^ Брайан Салливан , журнал MSDN (3 мая 2010 г.). «Атаки и защита от отказа в обслуживании с помощью регулярных выражений» . Проверено 6 мая 2010 г. {{cite web}}: Внешняя ссылка в |author= ( помощь ) CS1 maint: числовые имена: список авторов ( ссылка )
^ Кирраж, Дж.; Ратнаяке, А.; Тилеке, Х. (2013). «Статический анализ атак типа «отказ в обслуживании» с использованием регулярных выражений». Сетевая и системная безопасность . Мадрид, Испания: Спрингер. стр. 135–148. arXiv : 1301.0849 . дои : 10.1007/978-3-642-38631-2_11 .
^ Джим Манико и Адар Вайдман (7 декабря 2009 г.). «Подкаст OWASP 56 (ReDoS)» . Проверено 2 апреля 2010 г.
^ Барлас, Эфе; Ду, Синь; Дэвис, Джеймс (2022). «Использование очистки ввода для отказа в обслуживании регулярных выражений» (PDF) . Международная конференция ACM/IEEE по разработке программного обеспечения : 1–14. arXiv : 2303.01996 .
^ «Откат в регулярных выражениях .NET — .NET» . Learn.microsoft.com . 11 августа 2023 г. При использовании System.Text.RegularExpressions для обработки ненадежных входных данных передайте тайм-аут. Злоумышленник может предоставить входные данные в RegularExpressions, что приведет к атаке типа «отказ в обслуживании». API-интерфейсы платформы ASP.NET Core, использующие регулярные выражения, проходят тайм-аут.
^ «Ускорение WAF на 40 %» . Блог Cloudflare . 1 июля 2020 г.
^ Кокс, Расс (2007). «Сопоставление регулярных выражений может быть простым и быстрым» . Проверено 20 апреля 2011 г. – описывает алгоритм RE2
^ См., например Шмидт, Майкл (30 марта 2023 г.). «ЗапуститьРазработку/scslre» . , ЦУЮСАТО, Кицунэ. «перепроверить введение» . , и Дэвис, Джеймс. "vuln-regex-detector/src/detect/README.md" . Гитхаб .
^ Х. Тилеке, А. Ратнаяке (2013). « Статический анализ отказа в обслуживании (ReDoS) с помощью регулярных выражений. Архивировано 3 августа 2014 г. на Wayback Machine ». Проверено 30 мая 2013 г.
^ Б. ван дер Мерве, Н. Вайдеман (2017). « Статический анализ регулярных выражений ». Проверено 12 августа 2017 г.
^ «Фаззинг с помощью статического анализа | перепроверка» . makenowjust-labs.github.io .
^ «Основные классы: регулярные выражения: квантификаторы: различия между жадными, неохотными и притяжательными квантификаторами» . Учебники по Java . Оракул . Архивировано из оригинала 7 октября 2020 года . Проверено 23 декабря 2016 г.
^ "compose-regexp.js, "Атомарное сопоставление" " . Гитхаб . 2 января 2024 г.
"tc39/proposal-regexp-atomic-operators" . Экма TC39. 31 декабря 2023 г.
^ «Предотвращение отказа в обслуживании с помощью регулярных выражений (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 г.

[8] Ленивые вычисления DFA обычно могут достигать скорости детерминированных автоматов, сохраняя при этом поведение в худшем случае, аналогичное моделированию NFA. Однако его значительно сложнее реализовать и он может использовать больше памяти.

[ReDoS_in_OWASP-1] OWASP (10 февраля 2010 г.). «Отказ в обслуживании регулярных выражений» . Проверено 16 апреля 2010 г.

[2] Дэвис, Джеймс; Луи, Майкл; Коглан, Кристи; Слуга, Франциско; Ли, Донюн (2019). «Почему регулярные выражения не являются лингва-франка? Эмпирическое исследование повторного использования и переносимости регулярных выражений» (PDF) . Объединенная европейская конференция ACM по разработке программного обеспечения и симпозиум по основам программной инженерии : 443–454.

[RiverStar-3] Программное обеспечение RiverStar (18 января 2010 г.). «Бюллетень по безопасности: осторожность при использовании регулярных выражений» . Архивировано из оригинала 15 июля 2011 г. Проверено 16 апреля 2010 г.

[ModSecurity-4] Ристич, Иван (15 марта 2010 г.). Руководство по ModSecurity . Лондон, Великобритания: Feisty Duck Ltd., с. 173. ИСБН 978-1-907117-02-2 . Архивировано из оригинала 8 августа 2016 г. Проверено 16 апреля 2010 г.

[Crossby&Wallach-5] Кросби и Уоллах, Usenix Security (2003). «Отказ в обслуживании с помощью регулярных выражений» . Архивировано из оригинала 1 марта 2005 г. Проверено 13 января 2010 г.

[Sullivan-6] Брайан Салливан , журнал MSDN (3 мая 2010 г.). «Атаки и защита от отказа в обслуживании с помощью регулярных выражений» . Проверено 6 мая 2010 г. {{cite web}}: Внешняя ссылка в |author= ( помощь ) CS1 maint: числовые имена: список авторов ( ссылка )

[KirrageRathnayakeThielecke-7] Кирраж, Дж.; Ратнаяке, А.; Тилеке, Х. (2013). «Статический анализ атак типа «отказ в обслуживании» с использованием регулярных выражений». Сетевая и системная безопасность . Мадрид, Испания: Спрингер. стр. 135–148. arXiv : 1301.0849 . дои : 10.1007/978-3-642-38631-2_11 .

[Podcast-9] Джим Манико и Адар Вайдман (7 декабря 2009 г.). «Подкаст OWASP 56 (ReDoS)» . Проверено 2 апреля 2010 г.

[10] Барлас, Эфе; Ду, Синь; Дэвис, Джеймс (2022). «Использование очистки ввода для отказа в обслуживании регулярных выражений» (PDF) . Международная конференция ACM/IEEE по разработке программного обеспечения : 1–14. arXiv : 2303.01996 .

[11] «Откат в регулярных выражениях .NET — .NET» . Learn.microsoft.com . 11 августа 2023 г. При использовании System.Text.RegularExpressions для обработки ненадежных входных данных передайте тайм-аут. Злоумышленник может предоставить входные данные в RegularExpressions, что приведет к атаке типа «отказ в обслуживании». API-интерфейсы платформы ASP.NET Core, использующие регулярные выражения, проходят тайм-аут.

[12] «Ускорение WAF на 40 %» . Блог Cloudflare . 1 июля 2020 г.

[13] Кокс, Расс (2007). «Сопоставление регулярных выражений может быть простым и быстрым» . Проверено 20 апреля 2011 г. – описывает алгоритм RE2

[14] См., например Шмидт, Майкл (30 марта 2023 г.). «ЗапуститьРазработку/scslre» . , ЦУЮСАТО, Кицунэ. «перепроверить введение» . , и Дэвис, Джеймс. "vuln-regex-detector/src/detect/README.md" . Гитхаб .

[15] Х. Тилеке, А. Ратнаяке (2013). « Статический анализ отказа в обслуживании (ReDoS) с помощью регулярных выражений. Архивировано 3 августа 2014 г. на Wayback Machine ». Проверено 30 мая 2013 г.

[16] Б. ван дер Мерве, Н. Вайдеман (2017). « Статический анализ регулярных выражений ». Проверено 12 августа 2017 г.

[17] «Фаззинг с помощью статического анализа | перепроверка» . makenowjust-labs.github.io .

[es-re-18] «Основные классы: регулярные выражения: квантификаторы: различия между жадными, неохотными и притяжательными квантификаторами» . Учебники по Java . Оракул . Архивировано из оригинала 7 октября 2020 года . Проверено 23 декабря 2016 г.

[19] "compose-regexp.js, "Атомарное сопоставление" " . Гитхаб . 2 января 2024 г.
"tc39/proposal-regexp-atomic-operators" . Экма TC39. 31 декабря 2023 г.

[20] «Предотвращение отказа в обслуживании с помощью регулярных выражений (ReDoS)» . www.regular-expressions.info .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[а]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]