ReDoS - ReDoS

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

Описание

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

Атаки

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

Однако некоторые из примеров в приведенных выше параграфах значительно менее «искусственны», чем другие; таким образом, они демонстрируют, как уязвимые регулярные выражения могут использоваться в результате ошибок программирования. В этом случае сканеры электронной почты и системы обнаружения вторжений также может быть уязвимым. К счастью, в большинстве случаев проблемные регулярные выражения можно переписать как «не злые» шаблоны. Например, (. * а) + можно переписать на ([^ a] * a) +.

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

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

внешняя ссылка

Примеры ReDoS в приложениях с открытым кодом:
Некоторые тесты для ReDoS
- Ахим Хоффман (2010). "ReDoS - тест для DoS с регулярными выражениями в JavaScript ". Проверено 19 апреля 2010.
- Ричард М. Смит (2010). "Результаты тестирования атаки отказа в обслуживании (ReDoS) с использованием регулярного выражения ". Проверено 19 апреля 2010.
Документ о реализации регулярных выражений, неуязвимых для определенных классов ReDoS
- Расс Кокс (2007). "Сопоставление регулярных выражений может быть простым и быстрым ". Проверено 20 апреля 2011.
Инструменты для обнаружения уязвимостей ReDoS
- Х. Тилеке, А. Ратнаяке (2013). "Статический анализ отказа в обслуживании (ReDoS) с использованием регулярных выражений ". Проверено 30 мая 2013.
- Б. ван дер Мерве (2016). "Страница проекта статического анализа регулярных выражений (ReDos) ". Проверено 12 августа 2016.

[ReDoS_in_OWASP-1] OWASP (2010-02-10). "Regex отказ в обслуживании". Получено 2010-04-16.

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

[ModSecurity-3] Ристич, Иван (15.03.2010). Руководство по ModSecurity. Лондон, Великобритания: Feisty Duck Ltd., стр. 173. ISBN 978-1-907117-02-2.

[Crossby&Wallach-4] Кросби и Уоллах, Usenix Security (2003). «Обычное выражение отказа в обслуживании». Получено 2010-01-13.

[Sullivan-5] Брайан Салливан, Журнал MSDN (2010-05-03). «Регулярное выражение отказа в обслуживании, атаки и защиты». Получено 2010-05-06.

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

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

[Podcast-8] Джим Манико и Адар Вайдман (07.12.2009). "Подкаст OWASP 56 (ReDoS)". Получено 2010-04-02.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]