Регулярные выражения Атаки на отказ в обслуживании (ReDOS): от эксплуатации к предотвращению

Вступление

Когда речь заходит о безопасности веб-приложений, одна из рекомендаций по написанию программного обеспечения, устойчивого к атакам, заключается в правильной проверке входных данных. Однако по мере роста количества мобильных приложений и API-интерфейсов (Application Programming Interface) количество ненадежных источников, откуда поступают данные, увеличивается, и потенциальный злоумышленник может воспользоваться отсутствием проверок для компрометации наших приложений. 

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

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

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

Аппаратные функции для этой статьи

Чтобы предоставить информацию о времени выполнения, производительности, использовании процессора и других фактах, мы полагаемся на виртуальную машину, которая использует 32-разрядную операционную систему Windows 7, 5,22 ГБ ОЗУ. Процессор Intel® Core®TM iT-3820QM с частотой 2,7 ГГц. Мы также используем 4 ядра.

Понимание проблемы.

OWASP Foundation (2012) определяет регулярное выражение атаки типа «отказ в обслуживании» следующим образом:

«Регулярное выражение« Отказ в обслуживании »(ReDoS) представляет собой атаку« Отказ в обслуживании », в которой используется тот факт, что большинство реализаций Регулярного выражения могут достигать экстремальных ситуаций, которые заставляют их работать очень медленно (экспоненциально в зависимости от размера ввода). Затем злоумышленник может вызвать программа, использующая регулярные выражения для входа в эти экстремальные ситуации, а затем зависания в течение очень долгого времени ».

Хотя широкое объяснение механизмов регулярных выражений выходит за рамки данной статьи, важно понимать, что, согласно Stubblebine, T (Pocket Reference для регулярных выражений), сопоставление с образцом состоит из нахождения описываемого фрагмента текста ( соответствует) регулярным выражением. Два основных правила используются для сопоставления результатов:

1. Самые ранние (самые левые) выигрыши: регулярное выражение применяется к вводу, начинающемуся с первого символа и перемещающемуся к последнему. Как только механизм регулярных выражений находит совпадение, он возвращается.
2. Стандартные квантификаторы являются жадными: согласно Stubblebine, «Квантификаторы определяют, сколько раз что-то может повторяться. Стандартные квантификаторы пытаются совпадать столько раз, сколько возможно. Процесс отказа от символов и попытки менее жадных совпадений называется обратным отслеживанием».

В этой статье мы нацелены на механизм регулярных выражений, называемый недетерминированным конечным автоматом (NFA). Эти механизмы обычно сравнивают каждый элемент регулярного выражения с входной строкой, отслеживая позиции, в которых он выбирал между двумя опциями в регулярном выражении. Если опция не срабатывает, двигатель возвращается к последней сохраненной позиции (Stubblebine, T 2007). Важно отметить, что этот движок также реализован в .NET, Java, Python, PHP и Ruby on rails.

Эта статья посвящена C #, и поэтому мы полагаемся на классы Microsoft .NET Framework System.Text.RegularExpression, которые в своей основе используют механизмы NFA.

По словам Брайана Салливана

«Одним из важных побочных эффектов обратного отслеживания является то, что хотя механизм регулярных выражений может довольно быстро подтвердить положительное совпадение (то есть входная строка соответствует заданному регулярному выражению), подтверждение отрицательного совпадения (входная строка не соответствует регулярному выражению) может занять немного дольше. Фактически, движок должен подтвердить, что ни один из возможных «путей» через входную строку не соответствует регулярному выражению, что означает, что все пути должны быть проверены. С помощью простого не группирующего регулярного выражения время, потраченное Подтвердить отрицательные совпадения не является большой проблемой «.

Чтобы проиллюстрировать проблему, давайте использовать это регулярное выражение (\ w + \ d +) + C, которое в основном выполняет следующие проверки:

1. От одного до неограниченного количества раз, столько раз, сколько возможно, отдача по мере необходимости.
2. \ w + соответствует любому слову слова  a-zA-Z0-9_ .
3. \ d + соответствует цифре  0-9
4. Соответствует символу C буквально (с учетом регистра)

Таким образом, совпадающими значениями являются  12C, 1232323232C и !!!! cD4C,  а несовпадающими значениями являются, например,  !!!!! C, aaaaaaC и abababababC .

Следующий модульный тест был создан для проверки обоих случаев.

const string RegExPattern = @"(\w+\d+)+C";

public void TestRegularExpression() 
{
    var validInput   = "1234567C";
    var invalidInput = "aaaaaaaC";
    Regex.IsMatch(validInput, RegExPattern).assert_Is_True();
    Regex.IsMatch(invalidInput, RegExPattern).assert_Is_False();
}

Execution time : 6 milliseconds

const string RegExPattern = @"(\w+\d+)+C";
[TestMethod]
public void IsValidInput()
{
    var sw = new Stopwatch();
    Int16 maxIterations = 25;
    for (var index = 15; index < maxIterations; index++)
    {
        sw.Start();
        //Generating x random numbers using FluentSharp API
        var input = index.randomNumbers() + "!";
        Regex.IsMatch(input, RegExPattern).assert_False();
        sw.stop();
        sw.Reset();
    }
  }

const string EmailRegex = @"^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@([0-9a-zA-Z][-\w]*[0-9a-zA-Z]\.)+[a-zA-Z]{2,9})$";
[TestMethod]
public void ValidateEmailAddress() 
{
    var validEmailAddress   = "[email protected]";
    var invalidEmailAddress = new String[] { "a", "abc.com", "1212", "aa.bb.cc", "aabcr@s" };
    Regex.IsMatch(validEmailAddress, EmailRegex).assert_Is_True();
    //Looping throught invalid email address
    foreach (var email in invalidEmailAddress) 
    {
        Regex.IsMatch(email, EmailRegex).assert_Is_False();
    }
}
Elapsed time: 6ms.

const string EmailRegex = @"^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@([0-9a-zA-Z][-\w]*[0-9a-zA-Z]\.)+[a-zA-Z]{2,9})$";
[TestMethod]
public void ValidateEmailAddress() 
{
    var validEmailAddress   = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
    var watch = new Stopwatch();
    watch.Start();
    validEmailAddress.regEx(EmailRegex).assert_Is_False();
    watch.Stop();
    Console.WriteLine("Elapsed time {0}ms", watch.ElapsedMilliseconds);
    watch.Reset();
}
**Elapsed Time : ~23 minutes (1423127 milliseconds).**

const string EmailRegex = @"^[\w-\.]{1,}\@([\w]{1,}\.){1,}[a-z]{2,4}$";
//Number of random strings to generte.
const int maxIterations = 10000;
[TestMethod]
public void Fuzz_EmailAddress() 
{
    //Valid email should return true
    "[email protected]".regEx(EmailRegex).assert_Is_True();
    //Invalid email should return false
    "abce"                     .regEx(EmailRegex).assert_Is_False();
    //Testing maxIterations times
    for (int index = 0; index < maxIterations; index++) 
    {
        //Generating a random string
        var fuzzInput = (index * 5).randomString();
        var sw = new Stopwatch();
        sw.Start();
        fuzzInput.regEx(EmailRegex).assert_Is_False();
        //Elapsed time should be less than 3 seconds per input.
        sw.Elapsed.seconds().assert_Size_Is_Smaller_Than(3);
    }
}

const string EmailRegexPattern = @"^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@([0-9a-zA-Z][-\w]*[0-9a-zA-Z]\.)+[a-zA-Z]{2,9})$";
[TestMethod]
public void ValidateEmailAddress() 
{
    var emailAddress   = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
    var watch = new Stopwatch();
    watch.Start();
    //Timeout of 5 seconds
    try
    {
        Regex.IsMatch(emailAddress, EmailRegexPattern,
                       RegexOptions.IgnoreCase,
                       TimeSpan.FromSeconds(5));
    }
    catch (Exception ex)
    {
        ex.Message.assert_Not_Null();
        ex.GetType().assert_Is(typeof(RegexMatchTimeoutException));
    }
    finally
    {
        watch.Stop();
        watch.Elapsed.seconds().assert_Size_Is_Smaller_Than(5);
        watch.Reset();
    }
}