ReDoS

Exponential backtracking

The most severe type of problem happens with backtracking regular expression matches, where some patterns have a runtime that is exponential in the length of the input string.^[8] For strings of ${\displaystyle n}$ characters, the runtime is ${\displaystyle O(2^{n})}$. This happens when a regular expression has three properties:

• the regular expression applies repetition (+, *) to a subexpression;
• the subexpression can match the same input in multiple ways, or the subexpression can match an input string which is a prefix of a longer possible match;
• and after the repeated subexpression, there is an expression that matches something which the subexpression does not match.

The second condition is best explained with two examples:

• in (a|a)+$, repetition is applied to the subexpression a|a, which can match a in two ways on each side of the alternation.
• in (a+)*$, repetition is applied to the subexpression a+, which can match a or aa, etc.

In both of these examples we used $ to match the end of the string, satisfying the third condition, but it is also possible to use another character for this. For example (a|aa)*c has the same problematic structure.

All three of the above regular expressions will exhibit exponential runtime when applied to strings of the form ${\displaystyle a...ax}$. For example, trying to match them against aaaaaaaaaaaaaaaaaaaaaaaax on a backtracking expression engine, it will take a significantly long time to complete, and the runtime will approximately double for each extra a before the x.

It is also possible to have backtracking which is polynomial time ${\displaystyle O(n^{x})}$, instead of exponential. This can also cause problems for long enough inputs, though less attention has been paid to this problem as malicious input must be much longer to have a significant effect. An example of such a pattern is "a*b?a*c", when the input is an arbitrarily long sequence of "a"s.

Vulnerable regexes in online repositories

So-called "evil" or vulnerable regexes have been found in online regular expression repositories. Note that it is enough to find a vulnerable subexpression in order to attack the full regex:

1. RegExLib, id=1757 (email validation) – see red part
   ^([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}))$
2. OWASP Validation Regex Repository, Java Classname – see red part
   ^(([a-z])+.)+[A-Z]([a-z])+$

These two examples are also susceptible to the input aaaaaaaaaaaaaaaaaaaaaaaa!.

Attacks

If the regex itself is affected by user input, such as a web service permitting clients to provide a search pattern, then an attacker can inject a malicious regex to consume the server's resources. Therefore, in most cases, regular expression denial of service can be avoided by removing the possibility for the user to execute arbitrary patterns on the server. In this case, web applications and databases are the main vulnerable applications. Alternatively, a malicious page could hang the user's web browser or cause it to use arbitrary amounts of memory.

However, if a vulnerable regex exists on the server-side already, then an attacker may instead be able to provide an input that triggers its worst-case behavior. In this case, e-mail scanners and intrusion detection systems could also be vulnerable.

In the case of a web application, the programmer may use the same regular expression to validate input on both the client and the server side of the system. An attacker could inspect the client code, looking for evil regular expressions, and send crafted input directly to the web server in order to hang it.^[9]

Linear-time (finite automata) implementation

While some regex libraries do not have built-in defence against ReDoS attacks, such as C++ Standard Library <regex>, C POSIX library <regex.h>^[20] or Boost boost.regex (which use backtracking, leading to exponential time), other regex libraries are engineered for preventing regex denial of service attacks. This is done using deterministic finite automata, which run in linear time relative to the input size.

Using the RE2 library by Google for C++:^[21]

import <re2/re2.h>;
import std;

using std::string_view;
using re2::RE2;

constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
constexpr string_view PATTERN = "^(a+)+$";

int main(int argc, char* argv[]) {
    bool isMatch = RE2::FullMatch(TEXT, PATTERN);
    std::println("Match result: {}", isMatch);
}

Using the regex crate for Rust:^[22]

use regex::Regex;

const TEXT: &str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
const PATTERN: &str = r"^(a+)+$";

fn main() {
    // Regex::new() returns Result<Regex, Error> and must be unwrapped
    match Regex::new(PATTERN) {
        Ok(re) => {
            let is_match: bool = re.is_match(TEXT);
            println!("Match result: {}", is_match);
        }
        Err(err) => {
            eprintln!("Failed to unwrap regex: {}", err);
        }
    }
}

Regex match timeout

Timeouts can be used to cancel regex tasks if they take too long.

Timeouts are built in to the .NET standard library, as the class System.Text.RegularExpressions.Regex supports a property MatchTimeout.^[23] The following is an example in C#:

namespace Wikipedia.Examples;

using System;
using System.Text.RegularExpressions;

public class Example
{
    private const string Text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
    private const string Pattern = @"^(a+)+$";

    static void Main(string[] args)
    {
        try
        {
        	Regex re = new(Pattern, RegexOptions.None, TimeSpan.FromMilliseconds(100));
            bool isMatch = re.IsMatch(Text);
	        Console.WriteLine($"Match result: {isMatch}");
        }
        catch (RegexMatchTimeoutException ex)
        {
	        Console.WriteLine($"Regex operation timed out! {ex.Message}");
        }
    }
}

Compile-time regular expressions

Compile-time regular expressions are regular expressions which move parsing and validation into compile time, eliminating runtime overhead. However, compile-time regular expressions are useful only when the pattern can be provided at compile-time.

The C++ compile-time regular expressions (ctre) library by Hana Dusíková, provides a ctre::match<> functor, which performs regular expression parsing at compile-time.^[24] If a pattern at compile time causes compilation to exceed the constexpr evaluation step limit, it will fail to compile. It has been proposed for the C++ Standard Library, but as of yet has not been included.^[25]

import <ctre.hpp>;
import std;

using std::string_view;

constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";

int main(int argc, char* argv[]) {
    // ctre::match<> is a ctre::regex_results<> type
    // matching logic is done at compile-time when marked constexpr
    constexpr bool isMatch = ctre::match<"^(a+)+$">(TEXT);
    std::println("Match result: {}", isMatch);
}

The D programming language offers std.regex.ctRegex, which is a compile-time regular expression.^[26]

In Rust, compile-time regular expressions can be accomplished by some third-party crates, like lazy_regex, ctreg and regex-automata, which offer various macros for compile-time regex validation.^[27]

In C#, there is a System.Text.RegularExpressions.GeneratedRegexAttribute attribute, which generates an implementation of a regular expression through source generation on a partial method.^[28]

namespace Wikipedia.Examples;

using System;
using System.Text.RegularExpressions;

public partial class Example
{
    [GeneratedRegex(@"^(a+)+$")]
    private static partial Regex Pattern();

    private const string Text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";

    static void Main(string[] args)
    {
        // IsMatch() logic happens at runtime
        bool isMatch = Pattern().IsMatch(Text);
        Console.WriteLine($"Match result: {isMatch}");
    }
}