llamaCVEVulnerability Intelligence
/
Advisory · GitHub · PyPI · soupsieve

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

Sin parche publicado
Descargar PNG JSON
CVSS 3.1
5.3
Media
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L Fuente: GitHub
ExplotaciónSin evidenciaNo figura en CISA KEV
Exploits públicos0Ninguno conocido
ParcheSin parcheEl fabricante no ha publicado corrección
Exposición1 dDesde la divulgación, 20 nov 2026, 7:59 a. m.
Detección5 minDesde la divulgación hasta su ingreso al índice
Decisión estimadaSeguir
Remediar en la ventana regular de mantenimiento
Estimación de Llama con el árbol SSVC de CISA a partir de vector CVSS 3.1 y la evidencia de explotación (sin evaluación oficial): sin explotación conocida, automatizable e impacto técnico parcial. No hay versión corregida: aplique mitigaciones.
Parche en la próxima ventana y listo, campeón.Si haces parches mensuales, ya estás cubierto.
Timeline

Ciclo de vida de la vulnerabilidad

Hoy
Divulgación
Publicada
Explotación
Remediación
Monitoreo
Detectada +1
07:59 a. m.
08:04 a. m.
10:42 a. m.
07:59 a. m.
02:40 p. m.
09:20 p. m.
04:01 a. m.
10:42 a. m.
FechaFaseEventoDetalle
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
Resumen
Descripción del advisory
Texto original · GitHub · en inglés

## 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 quadratically

Measured 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.

Vector CVSS 3.1

Desglose de métricas

Opción resaltada = valor del vector · izquierda = peor caso · GitHub
Vector de ataqueAV:N
RedAdyacenteLocalFísica
ComplejidadAC:L
BajaAlta
PrivilegiosPR:N
NingunoBajosAltos
InteracciónUI:N
NingunaRequerida
AlcanceS:U
CambiadoSin cambio
ConfidencialidadC:N
AltoBajoNinguno
IntegridadI:N
AltoBajoNinguno
DisponibilidadA:L
AltoBajoNinguno
Score de explotaciónQué tan fácil y probable es que la exploten
10.0/ 10Muy alto
Vector 10.0 (muy fácil) · sin evidencia de explotación.
Versiones

Rangos afectados

Afectada Corregida Última
soupsieve≤ 4.1.2
4.1.2
Remediación

Estado del parche por paquete

Paquete / productoEstadoCorregida enDesde divulgaciónÚltima versión
pypisoupsieve
Sin parche — — 4.1.2 afectada
Explotación

Arsenal público

Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.

Referencias
Advisoryhttps://github.com/facelessuser/soupsieve/security/advisories/GHSA-624v-2mmw-6jvq

Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.