Отказ в обслуживании с использованием регулярных выражений ( ReDoS ) [1] — это алгоритмическая атака , вызывающая отказ в обслуживании путем предоставления регулярного выражения и/или входных данных, для оценки которых требуется много времени. Атака использует тот факт, что многие [2] реализации регулярных выражений имеют суперлинейную сложность в худшем случае ; в некоторых парах регулярное выражение-вход затраченное время может расти полиномиально или экспоненциально в зависимости от размера входных данных. Таким образом, злоумышленник может заставить программу потратить значительное время, предоставив специально созданное регулярное выражение и/или ввод. Программа будет работать медленнее или перестанет отвечать на запросы. [3] [4]
Сопоставление регулярных выражений («регулярных выражений») можно выполнить путем построения конечного автомата . Регулярное выражение можно легко преобразовать в недетерминированные автоматы (NFA), в которых для каждого состояния и входного символа может существовать несколько возможных следующих состояний. После построения автомата существует несколько возможностей:
Из приведенных выше алгоритмов первые два являются проблематичными. Первое проблематично, поскольку детерминированный автомат может иметь до состояний где – число состояний в недетерминированном автомате; таким образом, преобразование из NFA в DFA может занять экспоненциальное время . Второе проблематично, поскольку недетерминированный автомат может иметь экспоненциальное число путей длины , так что прохождение входной длины также займет экспоненциальное время. [7] Однако последние два алгоритма не демонстрируют патологического поведения.
Обратите внимание, что для непатологических регулярных выражений проблемные алгоритмы обычно работают быстро, и на практике можно ожидать, что они « скомпилируют » регулярное выражение за время O(m) и сопоставят его за время O(n); вместо этого моделирование NFA и ленивое вычисление DFA имеют сложность наихудшего случая O (m 2 n). [a] Отказ в обслуживании регулярных выражений возникает, когда эти ожидания применяются к регулярному выражению, предоставленному пользователем, а вредоносные регулярные выражения, предоставленные пользователем, вызывают наихудшую сложность сопоставителя регулярных выражений.
Хотя алгоритмы регулярных выражений могут быть написаны эффективным способом, большинство существующих механизмов регулярных выражений расширяют языки регулярных выражений дополнительными конструкциями, которые не всегда могут быть решены эффективно. Такие расширенные шаблоны по существу вынуждают реализацию регулярных выражений в большинстве языков программирования использовать возврат.
Самый серьезный тип проблем возникает при возврате совпадений регулярных выражений, когда время выполнения некоторых шаблонов экспоненциально зависит от длины входной строки. [8] Для строк символов время выполнения равно . Это происходит, когда регулярное выражение имеет три свойства:
+
, *
) к подвыражению;Второе условие лучше всего объяснить на двух примерах:
(a|a)+$
к подвыражению применяется повторение a|a
, которое может совпадать a
двумя способами с каждой стороны чередования.(a+)*$
к подвыражению применяется повторение a+
, которое может соответствовать a
или aa
и т. д.В обоих этих примерах мы использовали $
соответствие концу строки, удовлетворяющей третьему условию, но для этого можно использовать и другой символ. Например (a|aa)*c
, имеет ту же проблемную структуру.
Все три приведенных выше регулярных выражения будут демонстрировать экспоненциальное время выполнения при применении к строкам вида . Например, если вы попытаетесь сопоставить их с помощью механизма выражений с возвратом, это займет значительно больше времени, а время выполнения увеличится примерно вдвое для каждого дополнительного кода перед .aaaaaaaaaaaaaaaaaaaaaaaa!
a
!
Также возможно иметь возврат, который имеет полиномиальное время , а не экспоненциальное. Это также может вызвать проблемы при достаточно длинных входных данных, хотя этой проблеме уделялось меньше внимания, поскольку вредоносный ввод должен быть намного длиннее, чтобы иметь значительный эффект. Примером такого шаблона является " ", когда входные данные представляют собой последовательность произвольной длины " ".a*b?a*x
a
В онлайн-хранилищах регулярных выражений были обнаружены так называемые «злые» или уязвимые регулярные выражения. Обратите внимание, что достаточно найти уязвимое подвыражение , чтобы атаковать полное регулярное выражение:
^([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}))$
^(([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]
{{cite web}}
: Внешняя ссылка |author=
( помощь )CS1 maint: числовые имена: список авторов ( ссылка )При использовании System.Text.RegularExpressions для обработки ненадежных входных данных передайте тайм-аут.
Злоумышленник может предоставить входные данные в RegularExpressions, что приведет к атаке типа «отказ в обслуживании».
API-интерфейсы платформы ASP.NET Core, использующие регулярные выражения, проходят тайм-аут.