ReDoS

A regular expression denial of service (ReDoS)^[1] is an algorithmic complexity attack that produces a denial-of-service by providing a regular expression and/or an input that takes a long time to evaluate. The attack exploits the fact that many^[2] regular expression implementations have super-linear worst-case complexity; on certain regex-input pairs, the time taken can grow polynomially or exponentially in relation to the input size. An attacker can thus cause a program to spend substantial time by providing a specially crafted regular expression and/or input. The program will then slow down or become unresponsive.^[3][4]

Description

Regular expression ("regex") matching can be done by building a finite-state automaton. Regex can be easily converted to nondeterministic automata (NFAs), in which for each state and input symbol, there may be several possible next states. After building the automaton, several possibilities exist:

• the engine may convert it to a deterministic finite-state automaton (DFA) and run the input through the result;
• the engine may try one by one all the possible paths until a match is found or all the paths are tried and fail ("backtracking").^[5][6]
• the engine may consider all possible paths through the nondeterministic automaton in parallel;
• the engine may convert the nondeterministic automaton to a DFA lazily (i.e., on the fly, during the match).

Of the above algorithms, the first two are problematic. The first is problematic because a deterministic automaton could have up to ${\displaystyle 2^{m}}$ states where ${\displaystyle m}$ is the number of states in the nondeterministic automaton; thus, the conversion from NFA to DFA may take exponential time. The second is problematic because a nondeterministic automaton could have an exponential number of paths of length ${\displaystyle n}$, so that walking through an input of length ${\displaystyle n}$ will also take exponential time.^[7] The last two algorithms, however, do not exhibit pathological behavior.

Note that for non-pathological regular expressions, the problematic algorithms are usually fast, and in practice, one can expect them to "compile" a regex in ${\displaystyle O(m)}$ time and match it in ${\displaystyle O(n)}$ time; instead, simulation of an NFA and lazy computation of the DFA have ${\displaystyle O(m\cdot 2^{n})}$ worst-case complexity.^[a] Regex denial of service occurs when these expectations are applied to a regex provided by the user, and malicious regular expressions provided by the user trigger the worst-case complexity of the regex matcher.

While regex algorithms can be written in an efficient way, most regex engines in existence extend the regex languages with additional constructs that cannot always be solved efficiently. Such extended patterns essentially force the implementation of regex in most programming languages to use backtracking.

Examples

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, if you try 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]

Mitigation

ReDoS can be mitigated without changes to the regular expression engine, simply by setting a time limit for the execution of regular expressions when untrusted input is involved.^[10]

ReDoS can be avoided entirely by using a non-vulnerable regular expression implementation. After CloudFlare's web application firewall (WAF) was brought down by a PCRE ReDoS in 2019, the company rewrote its WAF to use the non-backtracking Rust regex library, using an algorithm similar to RE2.^[11][12]

Vulnerable regular expressions can be detected programmatically by a linter.^[13] Methods range from pure static analysis^[14][15] to fuzzing.^[16] In most cases, the problematic regular expressions can be rewritten as "non-evil" patterns. For example, (.*a)+ can be rewritten to ([^a]*a)+. Possessive matching and atomic grouping, which disable backtracking for parts of the expression,^[17] can also be used to "pacify" vulnerable parts.^[18][19]

Linear-time (finite automata) regex

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 (RE2) by Google for C++:^[21]

#include <re2/re2.h>

import std;

using std::string;
using re2::RE2;

int main(int argc, char* argv[]) {
    string text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"
    string pattern = "(a+)+$";
    bool match = RE2::FullMatch(text, pattern);
    std::println("Match result: {}", match);
}

Using the regex crate for Rust:^[22]

use regex::Regex;

fn main() {
    // Regex::new() returns Result<Regex, Error> and must be unwrapped
    let re: Regex = Regex::new(r"^(a+)+$").unwrap();
    let matches: bool = re.is_match("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!");
    println!("Match result: {}", matches);
}

Regex match timeout

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

import java.util.concurrent.*;
import java.util.regex.*;

public class Example {
    public static boolean matchesWithTimeout(String regex, String input, long timeoutMillis) {
        ExecutorService executor = Executors.newSingleThreadExecutor();

        Future<Boolean> future = executor.submit(() -> {
            Pattern pattern = Pattern.compile(regex);
            Matcher matcher = pattern.matcher(input);
            return matcher.matches();
        });

        try {
            return future.get(timeoutMillis, TimeUnit.MILLISECONDS);
        } catch (TimeoutException e) {
            System.err.println("Regex evaluation timed out!");
            return false;
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
            return false;
        } finally {
            future.cancel(true); // Stop the thread
            executor.shutdownNow();
        }
    }

    public static void main(String[] args) {
        String regex = "(a+)+$";
        String input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
        boolean result = matchesWithTimeout(regex, input, 100); // 100 ms timeout
        System.out.printf("Match result: %s%n", result);
    }
}

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#:

using System;
using System.Text.RegularExpressions;

public class Example
{
    static void Main(string[] args)
    {
        string pattern = @"(a+)+$";
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaX";
    
        try
        {
        	Regex regex = new(pattern, RegexOptions.None, TimeSpan.FromMilliseconds(100));
            bool match = regex.IsMatch(input);
	        Console.WriteLine($"Match result: {match}");
        }
        catch (RegexMatchTimeoutException ex)
        {
	        Console.WriteLine($"Regex operation timed out! {ex.Message}");
        }
    }
}

See also

• Denial-of-service attack
• Billion laughs attack, a similar attack on XML parsers
• Black fax
• Busy beaver, a program that produces the maximum possible output before terminating
• Email bomb
• Fork bomb
• Logic bomb
• Online algorithm, limit discovered rather than declared
• Zip bomb
• Time bomb (software)
• Denial-of-service attack
• Cyberwarfare
• Low Orbit Ion Cannon
• High Orbit Ion Cannon