# V5626. OWASP. Possible ReDoS vulnerability. Potentially tainted data is processed by regular expression that contains an unsafe pattern.

- Суть ReDoS-атаки
- Способы устранения ReDoS-уязвимости

Анализатор обнаружил применение потенциально опасного регулярного выражения для обработки данных из внешнего источника. Это может сделать приложение уязвимым к ReDoS-атаке.

## Суть ReDoS-атаки

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

Регулярное выражение является уязвимым, если соответствует следующим условиям:

- Существует два подвыражения, при этом одно из них включено в другое и к каждому из них применяется один из следующих кванторов: '*', '+', '*?', '+?', '{...}' (к примеру, подвыражение 'x+' включено в '(x+)*');
- Существует такая строка, которую можно было бы сопоставить с обоими этими подвыражениями (строку 'xxxx' можно сопоставить как с шаблоном 'x+', так и с '(x+)*').

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

- ...(a+)+...
- ...(b?a*c?)+...
- ...(.+a+c?)*?...
- ...(a+){x}...
- ...(...|a...|...|a?...|...)+...
- и т. д.

Здесь 'a', 'b', 'c' могут быть:

- отдельными символами;
- набором символов в квадратных скобках '[...]';
- подвыражением в круглых скобках '(...)';
- любым классом символов, которые поддерживаются регулярным выражением ('\d', '\w', '.' и т. д.).

Также важно, чтобы после этих подвыражений было хотя бы одно подвыражение, не помеченное кванторами '?' или '*'. Например: '(x+)+y', '(x+)+$', '(x+)+(...)', ' (x+)+[...]' и т. д.

Разберем проблему этих выражений на примере '(x+)+y'. В этом выражении шаблону 'x+' может соответствовать любое количество символов 'x'. Строка, которая соответствует шаблону '(x+)+y', состоит из любого количества подстрок, сопоставленных с 'x+'. Как следствие, появляется большое множество вариантов сопоставлений одной и той же строки с регулярным выражением.

Несколько вариантов сопоставлений строки 'xxxx' с шаблоном '(x+)+y' продемонстрированы в таблице ниже:

Каждый раз, когда регулярному выражению не удаётся найти символ 'y' в конце строки, оно начинает проверку следующего варианта. Лишь проверив их все, регулярное выражение даст ответ – совпадений не найдено. Однако время выполнения этого процесса может оказаться катастрофически большим в зависимости от длины подстроки, соответствующей уязвимому паттерну.

График ниже отражает зависимость времени вычисления регулярного выражения (x+)+y от количества символов во входных строках вида 'xx....xx':

Рассмотрим пример кода:

    Regex _datePattern = new Regex(@"^(-?\d+)*$");

    public bool IsDateCorrect(string date)
    {
      if (_datePattern.IsMatch(date))
        ....
    }

В этом примере дата проверяется с помощью регулярного выражения. Если дата корректна, регулярное выражение отработает так, как и ожидалось. Ситуация изменится, если в качестве даты приложение получит следующую строку:

    3333333333333333333333333333333333333333333333333333333333333 Hello ReDoS!

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

Возможное решение – ограничить время обработки регулярным выражением входной строки:

    Regex _datePattern = new Regex(@"^(-?\d+)*$",
                                   RegexOptions.None,
                                   TimeSpan.FromMilliseconds(10));

Рассмотрим ещё один пример. В регулярном выражении намеренно добавлено подвыражение '(\d|[0-9]?)', чтобы показать суть проблемы.

    Regex _listPattern = new Regex(@"^((\d|[0-9]?)(,\s|\.))+$(?<=\.)");
    public void ProcessItems(string path)
    {
      using (var reader = new StreamReader(path))
      {
        while (!reader.EndOfStream)
        {
          string line = reader.ReadLine();
          if (line != null && _listPattern.IsMatch(line))
          ....
        }
      }
    }

Здесь данные считываются из файла и проверяются регулярным выражением на соответствие следующему паттерну: строка должна представлять собой список, каждый элемент которого является цифрой или пустой строкой. Корректный ввод может выглядеть так:

    3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4.

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

В регулярном выражении используются подвыражения '\d' и '[0-9]?', которые могут сопоставляться с одними и теми же значениями. Обратите внимание, что ко второму подвыражению применяется квантор '? ', а к родительскому подвыражению '((\d|[0-9]?)(,\s|\.))' – квантор '+'. Это приводит к появлению большого количества возможных сопоставлений в строке. Если бы не было хотя бы одного из этих двух кванторов, ReDoS-уязвимости не возникло бы.

В данном примере для устранения ReDoS-уязвимости достаточно убрать лишнее сопоставление:

    Regex _listPattern = new Regex(@"^([0-9]?(,\s|\.))+$(?<=\.)");

Еще больше узнать о ReDoS-уязвимостях можно, к примеру, на сайте OWASP.

## Способы устранения ReDoS-уязвимости

Устранить ReDoS-уязвимость можно несколькими способами. Рассмотрим их на примере регулярного выражения '^(-?\d+)*$'.

Способ 1. Добавить ограничение на время обработки строки регулярным выражением. Это можно сделать, задав параметр 'matchTimeout' при создании объекта 'Regex' или при вызове статического метода:

    RegexOptions options = RegexOptions.None;
    TimeSpan timeout = TimeSpan.FromMilliseconds(10);

    Regex datePattern = new Regex(@"^(-?\d+)*$", options, timeout);
    Regex.IsMatch(date, @"^(-?\d+)*$", options, timeout);

Способ 2. Использовать атомарные группы '(?>...)'. Атомарные группы отключают поиск всех возможных комбинаций символов, соответствующих подвыражению, ограничиваясь лишь одной:

    Regex datePattern = new Regex(@"^(?>-?\d+)*$");

Способ 3. Переписать регулярное выражение, убрав опасный паттерн. Предположим, что выражение '^(-?\d+)*$' предназначено для поиска даты вида '27-09-2022', в этом случае его можно заменить на более надёжный аналог:

    Regex datePattern = new Regex (@"^(\d{2}-\d{2}-\d{4})$");

В этом варианте любая подстрока сопоставляется не более чем с одним подвыражением из-за обязательной проверки символа '-' между шаблонами '\d{...}'.

Выявляемые диагностикой ошибки классифицируются согласно ГОСТ Р 71207–2024 как критические и относятся к типу: Ошибки непроверенного использования чувствительных данных (ввода пользователя, файлов, сети и пр.).

Данная диагностика классифицируется как:

CWE-1333

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