# Catastrophic regex backtracking DoS

Ambiguous or interpolated regexes on user input whose match time grows super-linearly

_Area: Web business logic and race conditions. Seen in 8 disclosed reports; 4 confirmed bounties, median $1,650, range $250-$7,640; latest 2023-04-26. Updated 2026-10-23._

## How it works
A regex engine tries many ways to split input across overlapping repetition. When a pattern has nested or adjacent quantifiers that can consume the same characters (e.g. `\d+[^);]+[^);]*`, or `\s*(.+?)\s*` where the wildcard also matches whitespace), a failing match forces the engine to explore a combinatorial number of partitions. Cost grows quadratically or cubically with input length, so one request with a long crafted string pins a CPU for tens of seconds. The broken assumption is that regex matching is cheap and linear; it is not when the pattern is ambiguous and the input is attacker-shaped. A second shape: user input is concatenated into a pattern without escaping, so the attacker supplies the explosive quantifiers directly. A related but separate non-regex shape: a renderer or extractor whose per-token work grows super-linearly with repeated tokens [E5](https://bugbountylibrary.com/r/h1%3A1543718.md).

## Where it shows up
- Regexes with nested quantifiers, lazy `.*?` next to optional groups, or adjacent classes that overlap
- Patterns parsing structured text: Markdown, CSS, SVG, dates, color codes, slugs, IDs
- User input interpolated into a regex (search resolvers, filters) without escaping metacharacters
- Validators and rewriters that `scan`/`match` user-controlled fields on every request
- Preview, render, move, or import endpoints that re-scan large user text
- HTTP client header parsers using unanchored trailing-whitespace regexes like `/\s+\z/` [E1](https://bugbountylibrary.com/r/h1%3A1531958.md)

## How to review
The invariant: for any user-controlled string, match time must stay bounded and roughly linear in input length. Check each regex that touches user input: does any repetition contain another repetition, or can two adjacent parts consume the same characters? If so, it is a candidate. Confirm by feeding a long crafted prefix that fails to match and measuring CPU; a jump from milliseconds to seconds is the signal. For interpolated patterns, require escaping of all metacharacters before compilation. For renderers, benchmark repeated-token inputs, not just correctness. As reviewer instrumentation, GraphQL tracing extensions expose resolver timing and help baseline slow patterns [E3](https://bugbountylibrary.com/r/h1%3A1000567.md). Prefer anchored, unambiguous patterns or non-regex parsing.

## Variants seen
- Unanchored trailing-whitespace regex in net/http header parsing, quadratic on long space runs [E1](https://bugbountylibrary.com/r/h1%3A1531958.md)
- Ambiguous patterns in parsers (ua-parser, cookiejar) causing cubic backtracking [E2](https://bugbountylibrary.com/r/blog%3Ablog-doyensec-com-2021-03-11-regexploit-html.md)
- Search parameter concatenated unescaped into a server-side regex [E3](https://bugbountylibrary.com/r/h1%3A1000567.md)
- URI validator regex backtracking exponentially on double-`#` input [E4](https://bugbountylibrary.com/r/h1%3A1944515.md)
- Markdown reference/image token extraction scaling super-linearly on repeated tokens [E5](https://bugbountylibrary.com/r/h1%3A1543718.md)
- Uploads rewriter regex with lazy quantifiers and optional groups during issue move [E6](https://bugbountylibrary.com/r/h1%3A1543584.md)
- Color validator regex with catastrophic backtracking on long crafted input [E7](https://bugbountylibrary.com/r/h1%3A511381.md)

## Why fixes fail
Escaping metacharacters fixes only the interpolation variant [E3](https://bugbountylibrary.com/r/h1%3A1000567.md); it does nothing for patterns that are themselves ambiguous [E1](https://bugbountylibrary.com/r/h1%3A1531958.md)[E4](https://bugbountylibrary.com/r/h1%3A1944515.md)[E6](https://bugbountylibrary.com/r/h1%3A1543584.md)[E7](https://bugbountylibrary.com/r/h1%3A511381.md). Fixing one renderer path leaves other rewriters (move, import) still vulnerable [E6](https://bugbountylibrary.com/r/h1%3A1543584.md). Length caps help but do not remove super-linear growth if the cap is still large enough to burn CPU; caps must be paired with a pattern rewrite.

## Impact and severity
Service-wide denial of service: a single authenticated request burned ~60s of CPU, and repeated requests exhausted instance CPUs [E5](https://bugbountylibrary.com/r/h1%3A1543718.md)[E6](https://bugbountylibrary.com/r/h1%3A1543584.md)[E7](https://bugbountylibrary.com/r/h1%3A511381.md); one webhook job sat at 100% CPU for over a year [E1](https://bugbountylibrary.com/r/h1%3A1531958.md). Severity is high where the endpoint is unauthenticated or cheap to call; authenticated-only fields lower reachability but not the CPU cost. Worse when the same text is re-scanned by multiple code paths (preview, move, import) and when no input length cap exists.

## Evidence
- E1: https://bugbountylibrary.com/r/h1%3A1531958.md
- E2: https://bugbountylibrary.com/r/blog%3Ablog-doyensec-com-2021-03-11-regexploit-html.md
- E3: https://bugbountylibrary.com/r/h1%3A1000567.md
- E4: https://bugbountylibrary.com/r/h1%3A1944515.md
- E5: https://bugbountylibrary.com/r/h1%3A1543718.md
- E6: https://bugbountylibrary.com/r/h1%3A1543584.md
- E7: https://bugbountylibrary.com/r/h1%3A511381.md