GHSA-gjv8-xp57-g29c Soup Sieve: Polynomial-time ReDoS (O(n²)) in the `IDENTIFIER` / `VALUE` selector sub-patterns

• PyPI soupsieve: < 2.9.0 → fixed in 2.9.0

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:...)`, `*+`) 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.