# ReDoS catastrophic backtracking

Regex with nested or overlapping quantifiers run on attacker-controlled input; benchmark worst-case, not typical, strings

_Area: Web injection and code execution. Seen in 4 disclosed reports; 4 confirmed bounties, median $1,381, range $505-$2,162; latest 2025-02-05. Updated 2026-10-23._

## How it works
A regex engine that backtracks tries alternatives when a match fails. If a pattern has nested quantifiers or adjacent groups that can consume the same characters (e.g. `\s*` next to `.+?`, or several `.*` separated by optional tokens), the number of ways to split the input grows exponentially or cubically. When the terminating token is absent, the engine explores all those splits before failing. Runtime then scales with input length to a high power, so a short crafted string pins CPU. The broken assumption is that regex cost is linear in input size; it is not for ambiguous patterns.

## Where it shows up
- Regexes with nested quantifiers (`(a+)+`, `(\s*)(.+?)(\s*)`) or multiple greedy groups over the same character class.
- Patterns anchored at both ends (`\A...\Z`) where a missing terminator forces full backtracking.
- Syntax highlighters and lexers with many per-language regexes [E1](https://bugbountylibrary.com/r/h1%3A1283484.md).
- URL-detection or sanitizer helpers that scan and re-scan punctuation [E2](https://bugbountylibrary.com/r/h1%3A2881639.md)[E3](https://bugbountylibrary.com/r/h1%3A2795558.md).
- Template filters and text helpers that run regexes on user content [E3](https://bugbountylibrary.com/r/h1%3A2795558.md)[E4](https://bugbountylibrary.com/r/h1%3A2792776.md).
- Any regex applied to unbounded user input without a length cap.

## How to review
The invariant: for every regex applied to attacker input, worst-case match time must be bounded by a small constant times input length. Check each pattern for two quantifiers that can match overlapping characters, and for optional separators between greedy groups. Then benchmark the actual function on adversarial strings: long runs of one character, repeated delimiter pairs (`;:`, `.;`, `&;`) [E2](https://bugbountylibrary.com/r/h1%3A2881639.md)[E3](https://bugbountylibrary.com/r/h1%3A2795558.md), and tab- or space-padded text with the closing token removed [E4](https://bugbountylibrary.com/r/h1%3A2792776.md). Test on the oldest supported runtime; newer engines may memoize and hide the bug [E4](https://bugbountylibrary.com/r/h1%3A2792776.md). Confirm a length limit or timeout exists before the regex runs.

## Variants seen
- Cubic backtracking in third-party lexer regexes reached through fenced code blocks [E1](https://bugbountylibrary.com/r/h1%3A1283484.md).
- Quadratic scanning in `urlize()` on `&` plus repeated `;:` [E2](https://bugbountylibrary.com/r/h1%3A2881639.md).
- Superlinear behavior in `urlize()` on repeated `.;` [E3](https://bugbountylibrary.com/r/h1%3A2795558.md).
- Exponential backtracking in a blockquote text regex with overlapping `\s*` and `.+?` [E4](https://bugbountylibrary.com/r/h1%3A2792776.md).

## Why fixes fail
Fixing one pathological sequence leaves sibling patterns: after the `;:` case was addressed, `.;` still blew up in the same function [E2](https://bugbountylibrary.com/r/h1%3A2881639.md)[E3](https://bugbountylibrary.com/r/h1%3A2795558.md). Fixes validated only on a newer Ruby engine showed no issue while the bug persisted on 3.1 [E4](https://bugbountylibrary.com/r/h1%3A2792776.md).

## Impact and severity
CPU exhaustion leading to 500/502 responses and request timeouts, i.e. denial of service [E1](https://bugbountylibrary.com/r/h1%3A1283484.md)[E2](https://bugbountylibrary.com/r/h1%3A2881639.md)[E3](https://bugbountylibrary.com/r/h1%3A2795558.md)[E4](https://bugbountylibrary.com/r/h1%3A2792776.md). Severity rises when the input is unauthenticated, unbounded, or reaches a shared server process; a single crafted string can stall many requests.

## Evidence
- E1: https://bugbountylibrary.com/r/h1%3A1283484.md
- E2: https://bugbountylibrary.com/r/h1%3A2881639.md
- E3: https://bugbountylibrary.com/r/h1%3A2795558.md
- E4: https://bugbountylibrary.com/r/h1%3A2792776.md