Regular expression denial of service

Description

Regular expression denial of service (ReDoS) occurs when specially crafted input makes matching consume excessive computation. Processing the input can occupy server resources long enough to disrupt the service; it need not be an infinite loop.

Potential impact

Denial of service: Resource exhaustion can prevent normal requests from being processed.
Performance degradation: Slow matching can delay responses to users.
Resource exhaustion: High CPU or memory consumption can interfere with other work.

Remediation

Review expressions and keep their structure simple and efficient.
Set a matching timeout when the engine supports one. Python's standard re module has no matching-timeout parameter.
Limit input length before matching and simplify patterns with excessive backtracking, such as nested repetition.

Examples

The first example can take a very long time on the long input. The timeout in the second example limits execution time; it does not simplify the inefficient pattern itself.

Before

python

# Unsafe regular expression matching
import re

pattern = re.compile(r'(a+)+$')
test_string = 'a' * 10000 + '!'
if pattern.match(test_string):
    print("Match found")
else:
    print("No match")

After

python

# Regular expression matching with a timeout
import regex

# Apply the timeout to the matching call.
pattern = regex.compile(r'(a+)+$')
test_string = 'a' * 10000 + '!'
try:
    if pattern.match(test_string, timeout=1):
        print("Match found")
    else:
        print("No match")
except TimeoutError:
    print("Regex match timed out")

Explanation:

Before: Nested repetition causes excessive backtracking on input that almost matches, delaying request processing.
After: The regex matching call receives a timeout in seconds and handles the built-in TimeoutError if the operation takes too long.

References

OWASP: Regular expression Denial of Service - ReDoS
CWE: CWE-1333: Inefficient Regular Expression Complexity
regex timeouts