Мы используем куки, чтобы пользоваться сайтом
было удобно.
ReDoS — это атака типа DoS (Denial of Service). Её задача — существенно замедлить или остановить выполнение программы. Осуществляется она посредством эксплуатации уязвимого регулярного выражения.
Уязвимым регулярным выражением считается выражение, которое выполняется за очень большое время из-за особенностей его построения и структуры входной строки. В худшем случае время выполнения регулярного выражения может доходить до экспоненциального относительно входных данных. Такие ситуации именуются катастрофическим возвратом. Именно катастрофические возвраты приводят к замедлению или остановке выполняемой программы.
Катастрофический возврат является следствием работы функции обратного отслеживания в движке регулярных выражений, которая выполняет перебор возможных сопоставлений строки до тех пор, пока не найдёт верное. Если правильного сопоставления нет, регулярное выражение не остановится, пока не переберёт все возможные варианты. Полный перебор огромного количества вариантов приведёт к непозволительно долгому вычислению регулярного выражения. А это может создать существенное зависание или вовсе заставить программу прекратить своё выполнение. Именно в этом и заключается суть ReDoS-атаки.
Возможны следующие сценарии осуществления ReDoS:
Регулярное выражение является уязвимым к катастрофическому возврату, если оно содержит хотя бы одно подвыражение, из-за которого может возникнуть большое количество вариантов сопоставлений.
Для наглядности рассмотрим простой синтетический пример.
Есть следующее регулярное выражение:
(x+)+y
Разберём его по частям:
x+ — один или более символов x;(x+)+ — повторение группы x+ один или более раз;y — символ y в конце строки.Таким образом, выражение ищет строку, состоящую из одного или нескольких "блоков", состоящих из одного или нескольких символов x, за которыми следует символ y. Например, строка xxy подходит под этот шаблон.
Проблемы возникнут, если подать строку, которая соответствует шаблону лишь частично. Например, строку xxxx.
Причина проблемы в том, что регулярное выражение не находит совпадение с первой попытки. Из-за этого регулярным выражением будут проверяться все возможные комбинации "блоков", которые содержат один или более символ x. И так до тех пор, пока не будут перебраны все возможные варианты. Ниже в таблице это представлено наглядно:
С увеличением количества символов x в исходной строке будет экспоненциально увеличиваться число проверяемых комбинаций. И, как следствие, время выполнения регулярного выражения будет увеличиваться, из-за чего появятся ощутимые подвисания, а отсюда и возможные падения программы.
0
0
0