GHSA-624V-2MMW-6JVQ
Quadratic-time (O(n^2)) CPU denial of service in the of-type nth selector family (:first-of-type/:last-of-type/:only-of-type/:nt
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Fuente: GitHub
Ciclo de vida de la vulnerabilidad
| Fecha | Fase | Evento | Detalle |
|---|---|---|---|
| Divulgación | Publicada | GHSA-624V-2MMW-6JVQ divulgada · CVSS 5.3 (GitHub) | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
## Summary
`soupsieve` (CSS selector engine used by BeautifulSoup) matches the of-type `nth`
selector family in quadratic time — `O(n^2)` — against documents whose siblings have
distinct tag names. An application that runs a FIXED, developer-written of-type selector
(`:first-of-type`, `:last-of-type`, `:only-of-type`, `:nth-of-type(1)`) over
attacker-influenced HTML can be driven into sustained single-core CPU exhaustion with a
single small request and no authentication.
## Root Cause
In `get_nth_index` (`soupsieve/css_match.py`, line 1329 on the 4.1.1 release tag; ~1404 on
HEAD), the `NthState` memoization cache key for of-type selectors includes the element's
tag name:
key = (id(parent), id(n), self.get_tag(el), self.get_tag_ns(el)) # of_type branch
# vs plain :nth-child:
key = (id(parent), id(n), None, None)When a parent has W children each with a DISTINCT tag name, every element maps to a
distinct cache key and therefore builds its own fresh `NthState(pos=0)`. The rescan loop
`while state.pos < end` (css_match.py:1423-1428) then runs from position 0 for each
element, so element i performs i+1 comparisons. Total work is
`Σ_{i=0}^{W-1}(i+1) = Θ(W^2)`.
The `index_cache` (css_match.py:1419-1421) is built once per parent in O(W) and only
O(1)-locates `end`; it does not stop the per-element rescan.
## Impact
Unauthenticated CPU denial of service. A ~64 KB document (W≈4000 distinct-named siblings)
costs 6-19 s of single-core CPU; a ~0.6 MB document costs minutes. Repeatable → sustained
single-core exhaustion / worker starvation for any service that runs an of-type selector
over untrusted HTML (scrapers, sanitizers, feed/HTML ingestion, `soup.select(...)`).
Proof of Concept
import soupsieve, bs4
doc = "<body>" + "".join(f"<t{i}></t{i}>" for i in range(8000)) + "</body>"
soup = bs4.BeautifulSoup(doc, "html.parser")
soupsieve.select(":only-of-type", soup) # ~75 s; grows quadraticallyMeasured growth (html.parser, default flags), ratio per doubling converges to 4.0 = clean O(n^2):
:first-of-type (DISTINCT) W=500->4000: 91->378->1553->6314 ms ratio 4.14,4.11,4.06
:only-of-type (DISTINCT) W=500->4000: 235->1172->4732->18822 ms ratio 4.99,4.04,3.98
CONTROL :first-of-type (SAME tag name): 1.9->3.8->7.6->15.4 ms ratio ~2.0 (LINEAR)The same-name control is linear, isolating the tag-name cache key as the sole cause
(not of-type semantics or a parsing artifact).
## Attack Chain
1. Entry: attacker submits HTML to any service that runs an of-type selector over it.
Action: upload/POST a document whose parent has W uniquely-named children:
`<body><t0></t0><t1></t1>...<t{W-1}></t{W-1}></body>` (~16 B/tag).
Guard: none — html.parser/lxml/html5lib accept arbitrary custom element names;
BeautifulSoup does not restrict tag names.
Bypass proof: N/A — ordinary untrusted HTML, no special characters.
2. Processing: app runs a FIXED short of-type selector (not attacker-controlled).
Action: `soupsieve.select(":first-of-type", soup)` (or :only-of-type / :nth-of-type(1)).
Guard: SELECTOR_LIMIT / parser ReDoS guards; the NthState memoization added by the
prior nth rewrite.
Bypass proof: the of_type cache key includes `get_tag(el)` (css_match.py:1404), so each
of the W distinct-named siblings maps to a DISTINCT key → its own fresh
`NthState(pos=0)`. The memoization "once per parent" guarantee is satisfied
per-key, but there are W keys.
3. Sink: `select()` visits all W siblings; element at index i rescans contents[0..i].
Action: `while state.pos < end` runs pos=0→i for each element (css_match.py:1423-1428),
i+1 comparisons, exactly 1 match.
Guard: index_cache (css_match.py:1419) + documented linear-time contract.
Bypass proof: index_cache only O(1)-locates `end`; it does NOT stop the rescan.
Total = Σ(i+1) = Θ(W^2).
4. Impact: Θ(W^2) CPU on one core per request; 6-19 s at W=4000, minutes at W≈16k-38k.
Repeatable → sustained single-core exhaustion. No auth, one request, no UI.
## Bypass Evidence
Measured ratio→4.0 per doubling with constant t/n^2; the same-name linear control isolates
the tag-name key. Code trace confirms distinct-named siblings each receive a fresh
`NthState(0,0,{})` with `pos=0` and no shared memoization. The prior nth rewrite removed
the of_type tag-name key at one site and re-added it verbatim — it changed the cache value
(lazy-scan NthState) but preserved the per-tag-name key, so this path remains uncovered.
## Affected Versions
`<= 4.1.1` (latest release; vulnerable code present on the 4.1.1 tag at css_match.py:1329
and on HEAD). No fix released.
## Suggested Fix
Drop the tag name from the of_type cache key and track per-`(tag, ns)` running counts
inside a single shared `NthState` scan — mirroring how plain `:nth-child` already works —
so all siblings share one O(W) counting pass per parent.
---
Reported by zx (Jace) — GitHub: @manus-use
Incluye detalles técnicos publicados por el investigador. Úselos solo para validar y corregir sus propios sistemas.
Desglose de métricas
Rangos afectados
Estado del parche por paquete
| Paquete / producto | Estado | Corregida en | Desde divulgación | Última versión |
|---|---|---|---|---|
pypisoupsieve |
Sin parche | — | — | 4.1.2 afectada |
Arsenal público
Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.
https://github.com/facelessuser/soupsieve/security/advisories/GHSA-624v-2mmw-6jvqLas referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
