GHSA-VFXQ-CHJ9-V7XC
filter() with a list is O(n²) in time and memory for documents with many top level elements
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-VFXQ-CHJ9-V7XC divulgada · CVSS 5.3 (GitHub) | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
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.
Desglose de métricas
Versiones afectadas
4.1.2Estado 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-vfxq-chj9-v7xcLas referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
