llamaCVEVulnerability Intelligence
/
Advisory · GitHub · PyPI · soupsieve

GHSA-VFXQ-CHJ9-V7XC

filter() with a list is O(n²) in time and memory for documents with many top level elements

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.
Rumio tranquila, pero no me olvido de esta.Mi diagnóstico: un ticket y una sonrisa.
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.
11:02 a. m.
07:59 a. m.
02:44 p. m.
09:30 p. m.
04:16 a. m.
11:02 a. m.
FechaFaseEventoDetalle
Divulgación Publicada GHSA-VFXQ-CHJ9-V7XC 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
Summary

`soupsieve.filter()` given a list of tags takes time and memory quadratic in the number of top level elements of the
document. A document has many top level elements whenever an HTML fragment is parsed with `html.parser` (for example a
user comment, an e-mail body or a scraped snippet), and the selector can be fixed and harmless, such as `:nth-child(2n)`.
A 76 KB fragment takes about 15 s and 1.75 GB of memory on 4.1.2.

Affects: 4.1.2 (released 18 Nov 2026), and `main` up to 97bfd17. The O(n²) memory comes from 8bc0b6f ("Share caches in
filter when tag is under the same top level element"). 4.1.1 has the same O(n²) time but not the memory growth (there,
`filter()` on a list calls `match()` once per tag).

Details

The changelog entry and docs added in 8bc0b6f say that `filter()` given a list now shares caches, so that "filtering
many tags of a document takes time that grows with the size of the document, not faster". The security notice in
`index.md` also says the contract holds for documents "with many top level elements".

`SoupSieve.filter()` groups the tags by the top level element above each one and creates one `CSSMatch` for each group.
Top level elements are their own top, so a document with `n` top level elements gets `n` separate `CSSMatch` objects,
and none of their caches are shared. Any sibling-counting selector (`:nth-child`, `:nth-last-child`, `:nth-of-type`,
`:first-of-type`, ...) then walks all `n` top level siblings once for every tag. Each `CSSMatch` also keeps its own
`NthState` with positions for all `n` siblings, so memory is O(n²) as well.

PoC
import resource, time
import soupsieve as sv
from bs4 import BeautifulSoup

print('soupsieve', sv.__version__)
for n in (1000, 2000, 4000):
    soup = BeautifulSoup('<div><p>x</p></div>' * n, 'html.parser')  # n top level <div>
    tags = soup.find_all(True)

    t = time.perf_counter()
    sv.select(':nth-child(2n)', soup)
    t_select = time.perf_counter() - t

    rss0 = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
    t = time.perf_counter()
    sv.filter(':nth-child(2n)', tags)  # the documented "one filter with a list of them"
    t_filter = time.perf_counter() - t
    rss = (resource.getrusage(resource.RUSAGE_SELF).ru_maxrss - rss0) / 1024  # MB on Linux

    print(f'n={n:5}  doc={len(str(soup)):6} B  select {t_select:6.3f}s  filter(list) {t_filter:7.3f}s  peak RSS +{rss:5.0f} MB')

Results with CPython 3.13, bs4 4.15.0, default flags:

| n top level `<div>` | document | `select()` | `filter(list)` on 4.1.2 | peak RSS on 4.1.2 | `filter(list)` on 4.1.1 |
|---|---|---|---|---|---|
| 1000 | 19 KB | 0.069 s | 0.92 s | +135 MB | 1.03 s |
| 2000 | 38 KB | 0.018 s | 4.01 s | +434 MB | 4.15 s |
| 4000 | 76 KB | 0.044 s | 14.9 s | +1751 MB | 15.6 s |

Doubling the document size makes `filter()` about 4x slower and use about 4x more memory. In a separate run, n = 8000
(about 150 KB) was killed by the out-of-memory killer on an 8 GB machine. `:nth-child(n of p)`, `:nth-last-child(n)`,
`:first-of-type` and `:nth-of-type(n)` behave the same. The trigger is the top level tags in the list: a list that
holds only the inner `<p>` tags stays linear, and so do siblings under one ordinary parent element.

Impact

An application that runs `filter()` with a list of tags over HTML it doesn't control (the pattern the docs recommend for
testing many tags) can be made to spend CPU time and memory quadratic in the input size. One request with a fragment of
about 100 KB ties up a worker for tens of seconds and can exhaust its memory. The attacker only needs to control the
HTML; the selector can be fixed. `select()` is not affected.

Suggested fix

Top level elements of the same document are siblings, so key the group on their document instead:

-            matcher = matchers.get(id(top))
+            # Top level elements of the same document are siblings, so they share one `CSSMatch`.
+            group = top.parent if top.parent is not None and CSSMatch.is_doc(top.parent) else top
+            matcher = matchers.get(id(group))
             if matcher is None:
-                matcher = matchers[id(top)] = CSSMatch(self.selectors, node, self.namespaces, self.flags)
+                matcher = matchers[id(group)] = CSSMatch(self.selectors, node, self.namespaces, self.flags)

With this change, n = 4000 takes 0.049 s and +1 MB, n = 16000 takes 0.16 s, and the test suite passes
(723 passed, 1 skipped). For 12 selectors I also compared `filter(list)` against
`[t for t in tags if sv.match(sel, t)]` on a mixed fragment, and the results were identical. I have not reviewed
whether a top level `template` fragment needs separate handling.

This was found with automated analysis (selector/document scaling sweeps) and manually verified.

Details

The changelog entry and docs added in 8bc0b6f say that `filter()` given a list now shares caches, so that "filtering
many tags of a document takes time that grows with the size of the document, not faster". The security notice in
`index.md` also says the contract holds for documents "with many top level elements".

`SoupSieve.filter()` groups the tags by the top level element above each one and creates one `CSSMatch` for each group.
Top level elements are their own top, so a document with `n` top level elements gets `n` separate `CSSMatch` objects,
and none of their caches are shared. Any sibling-counting selector (`:nth-child`, `:nth-last-child`, `:nth-of-type`,
`:first-of-type`, ...) then walks all `n` top level siblings once for every tag. Each `CSSMatch` also keeps its own
`NthState` with positions for all `n` siblings, so memory is O(n²) as well.

Proof of concept

import resource, time
import soupsieve as sv
from bs4 import BeautifulSoup

print('soupsieve', sv.__version__)
for n in (1000, 2000, 4000):
soup = BeautifulSoup('<div><p>x</p></div>' * n, 'html.parser') # n top level <div>
tags = soup.find_all(True)

t = time.perf_counter()
sv.select(':nth-child(2n)', soup)
t_select = time.perf_counter() - t

rss0 = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
t = time.perf_counter()
sv.filter(':nth-child(2n)', tags) # the documented "one filter with a list of them"
t_filter = time.perf_counter() - t
rss = (resource.getrusage(resource.RUSAGE_SELF).ru_maxrss - rss0) / 1024 # MB on Linux

print(f'n={n:5} doc={len(str(soup)):6} B select {t_select:6.3f}s filter(list) {t_filter:7.3f}s peak RSS +{rss:5.0f} MB')

Results with CPython 3.13, bs4 4.15.0, default flags:

| n top level `<div>` | document | `select()` | `filter(list)` on 4.1.2 | peak RSS on 4.1.2 | `filter(list)` on 4.1.1 |
|---|---|---|---|---|---|
| 1000 | 19 KB | 0.069 s | 0.92 s | +135 MB | 1.03 s |
| 2000 | 38 KB | 0.018 s | 4.01 s | +434 MB | 4.15 s |
| 4000 | 76 KB | 0.044 s | 14.9 s | +1751 MB | 15.6 s |

Doubling the document size makes `filter()` about 4x slower and use about 4x more memory. In a separate run, n = 8000
(about 150 KB) was killed by the out-of-memory killer on an 8 GB machine. `:nth-child(n of p)`, `:nth-last-child(n)`,
`:first-of-type` and `:nth-of-type(n)` behave the same. The trigger is the top level tags in the list: a list that
holds only the inner `<p>` tags stays linear, and so do siblings under one ordinary parent element.

Impact

An application that runs `filter()` with a list of tags over HTML it doesn't control (the pattern the docs recommend for
testing many tags) can be made to spend CPU time and memory quadratic in the input size. One request with a fragment of
about 100 KB ties up a worker for tens of seconds and can exhaust its memory. The attacker only needs to control the
HTML; the selector can be fixed. `select()` is not affected.

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

Versiones afectadas

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-vfxq-chj9-v7xc

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