Regular Expressions Denial of the Service (ReDOS) Attacks: From the Exploitation to the Prevention

autors :michael hidalgo, dinis cruz

introduction

when it comes to web application security, one of the recommendations to write software that is resilient to attacks is to perform a correct input data validation. however, as mobile applications and apis (application programming interface) proliferates, the number of untrusted sources where data comes from goes up, and a potential attacker can take advantage of the lack of validations to compromise our applications.

regular expressions provides a versatile mechanism to perform input data validation. developers use them to validate email addresses, zip codes, phone numbers and many other task that are easily implemented thought them.

unfortunately most of the time software engineers don't fully understand how regular expressions works in the background and by choosing a wrong regular expression pattern they can introduce a risk in the application.

in this article we are going to discuss about the so called regular expression denial of the service (redos) vulnerability and how we can identify this problems early in the software development life cycle (sdlc) stages by enforcing a culture focused on unit testing.

hardware features for this article

in order to provide information about execution time, performance, cpu utilisation and other facts, we are relying on virtual machine that uses windows 7 32-bit operating system, 5.22 gb ram. intel(r) core (tm) it-3820qm cpu @2.7 ghz. we are also using 4 cores.

understanding the problem.

the owasp foundation (2012) defines a regular regular expression denial of service attack as follows:

"the regular expression denial of service (redos) is a denial of service attack, that exploits the fact that most regular expression implementations may reach extreme situations that cause them to work very slowly (exponentially related to input size). an attacker can then cause a program using a regular expression to enter these extreme situations and then hang for a very long time."

although a broad explanation about regular expression engines is out of the scope of this article,it is important to understand that, according to stubblebine,t (regular expressions pocket reference), a pattern matching consist of finding a section of text that is described (matched) by a regular expression. two main rules are used to match results:

1. the earliest (leftmost) wins : the regular expression is applied to the input starting at the first character and moving toward the last. as soon as the regular expression engine finds a match,it returns.
2. standard quantifiers are greedy : according to stubblebine, "quantifiers specify how many times something can be repeated. the standard quantifiers attempt to match as many times as possible. the process of giving up characters and trying less-greedy matches is called backtracking."

for this article we are focused a regular expression engine called nondeterministic finite automaton (nfa).this engines usually compare each element of the regex to the input string, keeping track of positions where it chose between two options in the regex. if an option fails, the engine backtracks to the most recently saved position.(stubblebine,t 2007). it is important to note that this engine is also implemented in .net, java, python, php and ruby on rails.

this article is focused on c# and therefore we are relying on the microsoft .net framework system.text.regularexpression classes which at the heart uses nfa engines.

according to bryan sullivan

"one important side effect of backtracking is that while the regex engine can fairly quickly confirm a positive match (that is, an input string does match a given regex), confirming a negative match (the input string does not match the regex) can take quite a bit longer. in fact, the engine must confirm that none of the possible “paths” through the input string match the regex, which means that all paths have to be tested. with a simple non-grouping regular expression, the time spent to confirm negative matches is not a huge problem."

in order to illustrate the problem, let's use this regular expression (\w+\d+)+c which basically performs the following checks:

1. between one and unlimited times, as many times as possible, giving back as needed.
2. \w+ match any word character a-za-z0-9_ .
3. \d+ match a digit 0-9
4. matches the character c literally (case sensitive)

so matching values are 12c,1232323232c and !!!!cd4c and non matching values are for instance !!!!!c,aaaaaac and abababababc .

the following unit test was created to verify both cases.

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();
    }
  }

now let's take a look at the test results:

a real-life use-case and an appeal for a unit testing approach

now that we have seen the problems we can face by selecting a wrong (evil) regular expression, let's discuss about a realistic scenario where we need to validate input data thought regular expressions.

we strongly believe that unit testing techniques can not only help to write quality code but also we can use them to find vulnerabilities in the code we are writing. by writing unit test that performs security checks (like input data validation)

a common task in web applications consist on request an email address to the user signing in our application. from a ux (user experience perspective) complaining browsers support friendly error messages when an input, that was supposed to be an email address, does not match with the requirements in terms of format. here is a ui validation when a input textbox (with the email type is set) and the value is not a valid email address.

however relying on a ui validation is not longer enough. an eavesdropper can easily perform an http request without using a browser (namely by using a proxy to capture data in transit) and then send a payload that can compromise our application.

in the following use case, we are using a backend validation for the email address by using a regular expression. we will show you the real power of regular expressions here, we are not only testing that the regular expression validates the input but also how it behaves when it receives any arbitrary input.

we are using this evil regular expression to validate the email: ^( 0-9a-za-z @([0-9a-za-z][-\w][0-9a-za-z].)+[a-za-z]{2,9})$ .

with the following test we are verifying that a valid email and invalid emails formats are correctly processed by the regular expression, which is the functional aspect from a development point of view.

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   = "michael.hidalgo@owasp.org";
    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.

the exploit

so far the previous regular expression selected to valid an email address seems to work well, we have added some unit test that verifies valid an invalid inputs.

but how does it behaves when we send an arbitrary input?, from a variable length, do we face a denial of the service attack?.

this kind of questions can be solved wit unit testing technique like this one:

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).**

results are disturbing. we can clearly see the performance problem introduced by evaluating the given input.it takes roughly 23 minutes to validate the input given the hardware characteristics described before.

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
    "michael.hidalgo@owasp.org".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();
    }
}