# Super-linear text processing DoS

Weak hashing, repeated reference tokens, or case-sensitive terminator search making parser cost grow quadratically on crafted input

_Area: Web business logic and race conditions. Seen in 2 disclosed reports; one confirmed bounty: $7,640; latest 2022-11-04. Updated 2026-10-24._

## How it works
A parser or renderer assumes its per-token work stays roughly constant, so total cost grows linearly with input size. That assumption breaks when a lookup structure, a reference extractor, or a terminator search degrades on crafted input: many keys land in one bucket, many reference-like tokens each trigger a full re-scan, or a failed terminator search returns a sentinel that drives a huge substring. Cost then grows quadratically (or worse) per request, and a single maximal input burns CPU for tens of seconds.

## Where it shows up
- Hash tables keyed by a weak hash (e.g. SDBM) that allow duplicate keys and compare by hash value only, so lookups chain into one long list [E1](https://bugbountylibrary.com/r/h1%3A1341957.md)
- Reference/link extractors that accumulate token lists and re-render a collection per token, scaling super-linearly with repeated `![l`-style tokens [E2](https://bugbountylibrary.com/r/h1%3A1543718.md)
- Terminator searches using case-sensitive `indexOf` where the spec requires case-insensitive matching, leaving a `-1` result [E3](https://bugbountylibrary.com/r/ghsa%3AGHSA-6mj3-qw4j-hgrw.md)
- Unguarded `substring`/slice calls with a negative or sentinel end index [E3](https://bugbountylibrary.com/r/ghsa%3AGHSA-6mj3-qw4j-hgrw.md)
- Preview or render endpoints accepting maximal-length user text without cost bounds [E2](https://bugbountylibrary.com/r/h1%3A1543718.md)

## How to review
Identify every user-controlled string that reaches a parser, hasher, or renderer. For each, confirm the invariant: total work must stay linear (or bounded) in input length regardless of content. Check that hash tables use a strong hash and compare full keys, not just hash values [E1](https://bugbountylibrary.com/r/h1%3A1341957.md); that reference extraction does not re-render per token [E2](https://bugbountylibrary.com/r/h1%3A1543718.md); and that every terminator search handles a not-found result before slicing, with case handling matching the spec [E3](https://bugbountylibrary.com/r/ghsa%3AGHSA-6mj3-qw4j-hgrw.md). Trace sentinel returns (`-1`, empty) through callers to ensure no negative index reaches a substring.

## Variants seen
- Weak-hash bucket collision building an O(N) chain in a markdown reference table [E1](https://bugbountylibrary.com/r/h1%3A1341957.md)
- Quadratic CPU in a preview renderer from repeated reference-like tokens [E2](https://bugbountylibrary.com/r/h1%3A1543718.md)
- Case-mismatched raw-text close tag causing output amplification via negative substring [E3](https://bugbountylibrary.com/r/ghsa%3AGHSA-6mj3-qw4j-hgrw.md)

## Impact and severity
All three led to denial of service: CPU exhaustion on shared instances, ~60s CPU per request in one case [E2](https://bugbountylibrary.com/r/h1%3A1543718.md), and output amplification in another [E3](https://bugbountylibrary.com/r/ghsa%3AGHSA-6mj3-qw4j-hgrw.md). Severity rises when the endpoint is unauthenticated or preview-triggered, letting a single request tie up workers; maximal-size inputs made it worse.

## Evidence
- E1: https://bugbountylibrary.com/r/h1%3A1341957.md
- E2: https://bugbountylibrary.com/r/h1%3A1543718.md
- E3: https://bugbountylibrary.com/r/ghsa%3AGHSA-6mj3-qw4j-hgrw.md