How to Validate Regular Expressions to Prevent ReDoS Attacks
Learn how to validate regular expressions and secure your web applications against ReDoS (Regular Expression Denial of Service) using best practices.
Regular expressions (regex) are indispensable tools in modern software engineering. They enable developers to search for patterns, execute text replacements, and validate user input formats with minimal code. However, their high flexibility carries a significant, often overlooked security risk: ReDoS attacks (Regular Expression Denial of Service).
Unlike distributed denial of service (DDoS) attacks, which require botnets sending massive traffic volumes, a ReDoS attack can be executed by a single user sending a single, short string of characters. If your application does not validate regular expressions properly, that malicious payload can fully saturate the server's CPU, blocking all incoming legitimate requests. In this article, we will examine how ReDoS attacks operate, what causes catastrophic backtracking, and how to write secure patterns to protect your systems.
What is a ReDoS Attack and How Does it Occur?
A ReDoS attack is an algorithmic complexity vulnerability. It occurs when a regular expression engine in a programming language (such as JavaScript, Python, PHP, or Java) is forced to process an input string designed to trigger an astronomical execution time.
At the core of this vulnerability is the type of engine used to parse regex. Many languages rely on NFA (Nondeterministic Finite Automaton) engines. These engines evaluate strings character by character. When a match path fails, they back up to evaluate alternative paths. If a pattern is poorly designed, this trial-and-error process increases exponentially with the length of the input, leading to catastrophic backtracking.
The Anatomy of Catastrophic Backtracking
To understand how this processing bottleneck occurs, consider a simple regex pattern: ^(a+)+$
This pattern validates strings containing only the letter "a". If you test it against "aaaa", the engine matches it instantly. But what happens if you input "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"? The engine matches all the "a" characters and then searches for "b". When it fails to find a match, it backtracks, trying every possible division of nested groups (a+)+ to check if another path matches.
The number of evaluated paths grows exponentially relative to the string's length ($2^n$, where $n$ is the number of "a" characters).
The diagram below shows the flow of catastrophic backtracking in an NFA engine:
[Input String: "aaaaab"]
|
[Regex Engine (NFA)]
|
+------------------+------------------+
| |
[Path 1: (aaaaa)b] [Path 2: (aaaa)(a)b]
(Fails on 'b') (Fails on 'b')
| |
[Backtrack Step] [Backtrack Step]
| |
[Path 3: (aaa)(aa)b] [Path 4: (aaa)(a)(a)b]
(Fails on 'b') (Fails on 'b')
| |
+------------------+------------------+
|
[Millions of additional paths]
|
=======> [100% CPU Usage]
For an input string of only 30 characters, the engine may process over one billion combinations, freezing the execution thread of your server for minutes.
Vulnerable vs. Secure Regex Patterns
The classic structure that introduces ReDoS risks involves overlapping nested quantifiers. Let's compare common vulnerable patterns with secure alternatives:
| Validation Target | Vulnerable Pattern (ReDoS Risk) | Secure Recommended Pattern |
|---|---|---|
| Simple Identifiers | ^(a+)+$ |
^a+$ (no nested quantifiers) |
| Text with Spaces | ^(\w+\s?)*$ |
^\w+(\s\w+)*$ (removes ambiguity) |
| Email (Simplified) | ^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,4}$ (can backtrack on dot sequences) |
^[a-zA-Z0-9]+([._+-][a-zA-Z0-9]+)*@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,4}$ |
| Phone Numbers | ^(\+?[0-9-\s]+)*$ |
^\+?[0-9]{1,4}([- ]?[0-9]{1,15})*$ |
How to Validate and Mitigate ReDoS Vulnerabilities in Code
Mitigating ReDoS requires proactive strategies during the software design phase. Implement these standard security practices:
1. Avoid Ambiguous and Nested Quantifiers
Never write structures like (a*)*, (a+)+, or (a|b+)*. When validating repeating strings containing optional tokens, verify that the engine does not have multiple, ambiguous ways to consume the same character.
2. Implement strict execution timeouts
Most modern programming languages allow you to set an execution timeout limit for regex matches. If the matching process exceeds this threshold (e.g., 100 milliseconds), the engine throws an exception and halts execution.
The example below demonstrates how to configure regex execution limits in C# (.NET Core) to block catastrophic backtracking:
using System;
using System.Text.RegularExpressions;
public class SecurityValidator
{
public static bool ValidateInput(string userInput)
{
// Define a strict timeout of 100 milliseconds
TimeSpan timeout = TimeSpan.FromMilliseconds(100);
string safePattern = @"^[a-zA-Z0-9]+([._-][a-zA-Z0-9]+)*$";
try
{
return Regex.IsMatch(userInput, safePattern, RegexOptions.None, timeout);
}
catch (RegexMatchTimeoutException)
{
// Regex execution exceeded limit, potentially a ReDoS payload
Console.WriteLine("Warning: Regex matching exceeded the maximum allowed duration.");
return false;
}
}
}
3. Use Deterministic Finite Automaton (DFA) Engines
Whenever possible, use DFA-based regex engines (such as Google's re2 library). DFA engines analyze inputs in linear time relative to the text length, making catastrophic backtracking mathematically impossible.
To evaluate your regular expressions and analyze their runtime behavior under load, use our regex tester tool. This developer tool helps you measure execution speed and refine patterns to prevent performance drops.
For a detailed analysis of algorithmic complexity and state machine vulnerability mitigation, refer to the OWASP ReDoS Reference Guide. You can also explore our supplementary article on validating regular expressions on TecnoCrypter for further safe development patterns.
Conclusion
Inefficient regular expressions can create a critical opening for denial of service. Validating your patterns before deploying them to production environments is not just a performance optimization; it is a fundamental cybersecurity step to prevent ReDoS attacks.
By keeping your patterns simple, avoiding ambiguous repitions, and enforcing execution timeouts, you ensure that malicious payloads cannot exhaust your server resources. Take the time to audit your input validation algorithms; the security of your backend architecture depends on it.
Sources and further reading:
- OWASP ReDoS Prevention Cheat Sheet — Standard guide for mitigating regex vulnerabilities.
- Google RE2 Library — Line-time regular expression engine without backtracking.
- Related post on TecnoCrypter: Validate Regular Expressions in Development
