GHSA-98QM-P6JX-5WJ2
CPU denial of service: nested :nth-last-child(An+B of S) defeats the nth cache, O(n^k) matching (112-byte selector + 1.3 KB document = ~4 min CPU)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Fuente: GitHub
Ciclo de vida de la vulnerabilidad
| Fecha | Fase | Evento | Detalle |
|---|---|---|---|
| Divulgación | Publicada | GHSA-98QM-P6JX-5WJ2 divulgada · CVSS 7.5 (GitHub) | |
| Remediación | Parche 4.1.1 | soupsieve · 0 d desde divulgación | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
Summary
Placing any `nth` selector (`:nth-child`, `:nth-last-child`, `:nth-of-type` or `:nth-last-of-type`) inside the `S` of a `:nth-last-child(An+B of S)` defeats the `nth` cache, so each nesting level multiplies the matching cost by the number of siblings. A selector with `k` nested levels takes roughly `O(n^k)` time on a parent with `n` children. This also applies when the `:nth-last-child(... of S)` is itself nested inside a `:nth-child(... of S)`.
A 112-byte selector run against a 1,309-byte document (a `<ul>` with 100 `<li>`) keeps a CPU busy for about 4 minutes with the default flags (cache enabled, strict mode). The equivalent selector written only with `:nth-child` finishes in 3 ms, because the cache handles it correctly.
An application that compiles CSS selectors supplied by untrusted users, such as scraping or extraction services, user-defined filters, or query builders, can be stalled by a single short selector against any ordinary document. This is the same exposure as GHSA-6655-6qjp-jx7x, but the cause is in the matcher rather than the parser regex, and the `SELECTOR_LIMIT` guard doesn't apply because the selector is tiny.
Affected versions
- soupsieve 4.1 (latest release, PyPI sdist)
This was tested with Beautiful Soup 4.15.0 and with both `html.parser` and `lxml`. Older versions are also affected, some more broadly: in soupsieve 2.9.2, nesting only `:nth-child(n of ...)` is already polynomial (four levels over 100 `<li>` took about 93 s), so the forward-only protection described below doesn't exist there.
Details
`CSSMatch.match_nth()` (`soupsieve/css_match.py`, around lines 1271-1376) caches a `(start, rindex)` position per `(id(parent), id(nth))`. The cached position only moves forward, for both the "first" and "last" variants: a cache hit is only usable when the element being tested lies at or after the cached `start` (`self.within(el, parent, start)`). Otherwise the cache is reset and the siblings are walked again from scratch.
To evaluate an outer `:nth-last-child(... of S)`, the matcher walks the siblings in reverse (`get_children(..., reverse=True)`) and evaluates `S` on each sibling it passes (`yield child, n.selectors`). Any `nth` selector inside `S` is therefore looked up in reverse document order. Each lookup lands before the cached `start`, so the `within()` check fails and the cache is reset. The inner selector then walks the sibling list again, which costs O(n) instead of amortized O(1). This happens whatever kind the inner selector is: `:nth-child(n)`, `:nth-of-type(n)` or another `:nth-last-child`. Every additional level nested under a reverse walk repeats this, so the degree of the polynomial grows with the nesting depth.
`:nth-child(... of S)` walks forward, so the selectors directly inside its `S` are looked up in forward order and their cache stays valid. That doesn't protect anything nested further down: if a `:nth-last-child(... of S)` appears at any level, everything below it is looked up in reverse again.
Counting sibling visits (`get_children` yields) for `select()` on a `<ul>` with `n` `<li>` shows this directly:
| selector depth k | `:nth-child` visits/element (n=50 / n=100) | `:nth-last-child` visits/element (n=50 / n=100) |
|---|---|---|
| 1 | 1.0 / 1.0 | 2.0 / 2.0 |
| 2 | 2.1 / 2.0 | 28.5 / 53.5 |
| 3 | 3.1 / 3.0 | 494.1 / 1819.0 |
A reverse walk isn't the only way to break the forward-only cache. A `:has()` with a subsequent-sibling combinator restarts its search at each element's next sibling, so an `nth` selector inside it is looked up out of order as well. For example, `:nth-child(n of :has(~ :nth-child(n of li.x)))` is quadratic in the number of siblings (0.02 s, 0.08 s and 0.31 s for 200, 400 and 800 `<li>`). This path is quadratic rather than growing with each nesting level like the `:nth-last-child` case, but it doesn't need `:nth-last-child` at all.
Steps to reproduce
import time
import soupsieve as sv
from bs4 import BeautifulSoup
soup = BeautifulSoup('<ul>' + '<li>item</li>' * 100 + '</ul>', 'html.parser') # 1,309 bytes
def nested(fn, k):
s = 'li'
for _ in range(k):
s = ':%s(n of %s)' % (fn, s)
return s
for fn in ('nth-child', 'nth-last-child'):
for k in range(1, 6):
sel = nested(fn, k)
t = time.perf_counter(); sv.select(sel, soup); print(fn, k, len(sel), round(time.perf_counter() - t, 3))Measured on soupsieve 4.1 and on `main` af2f49b (CPython 3.12, default flags, html.parser), in two separate runs:
| k | selector bytes | `:nth-child` | `:nth-last-child` |
|---|---|---|---|
| 1 | 19 / 24 | 0.001 s | 0.001 s |
| 2 | 36 / 46 | 0.001 s | 0.013 s |
| 3 | 53 / 68 | 0.002 s | 0.43 s |
| 4 | 70 / 90 | 0.002 s | 11.4 s (4.1: 13.9 s) |
| 5 | 87 / 112 | 0.003 s | 242.5 s (4.1: 255.5 s) |
With the nesting fixed at k=3 and the document growing, the time grows as n^3: 100 `<li>` → 0.43 s, 200 → 3.3 s, 400 → 26.1 s. The same k=3 selector with `:nth-child` takes 13 ms at 800 `<li>`.
Mixing the two also triggers the issue whenever a "last" variant has another `nth` selector inside its `S`. `:nth-last-child(n of :nth-child(n of li))` is quadratic: 2,000 `<li>` takes 4.7 s. Even a plain `:nth-last-child(n of :nth-last-child(n))` is quadratic. An outer `:nth-child` doesn't help: `:nth-child(n of :nth-last-child(n of li))` stays linear (0.03 s) only because the innermost `li` has no `nth` selector, while `:nth-child(n of :nth-last-child(n of :nth-child(n of li)))` is quadratic again. The lxml parser gives the same numbers.
The full PoC scripts and outputs are available on request (`poc_nth_last.py`, `supp.py`, `rootcause.py`).
Impact
This is a denial of service (CPU exhaustion) against any application that compiles or selects with a CSS selector influenced by an untrusted party. No special document is needed: any page with about 100 siblings under one parent is enough. The selector is far below `SELECTOR_LIMIT` and is valid under the default strict rules. It runs with the cache enabled, so none of the documented mitigations (keeping the cache on, not using `NOSTRICT`) help. Ordinary single-level selectors such as `:nth-last-child(2n of li)` are linear, so applications that only run fixed, developer-written selectors over untrusted HTML aren't affected.
CVSS 3.1: `AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H` (7.5). This uses the same scoring as GHSA-6655-6qjp-jx7x, which has the same precondition (an untrusted selector string). Availability is the only impact.
This issue was found with automated analysis (fuzzing / selector performance sweeps) and manually verified.
Mitigations
Upgrading to soupsieve 4.1.1 or later fixes the issue. Each sibling is then evaluated against an `nth` selector at most once per parent, whatever order elements are looked up in, so nested `nth` selectors stay linear in both directions.
If you can't upgrade yet and accept selectors from untrusted sources, you can reject `:nth-last-child` and `:has` with the `ignore` option https://facelessuser.github.io/soupsieve/api/#ignore-pseudo-class. Compiling a selector that uses either of them anywhere, including inside `:is()`, `:not()` or an `nth` selector, then raises `SelectorSyntaxError`. Beautiful Soup passes the option through to Soup Sieve:
import soupsieve as sv
# Raises soupsieve.SelectorSyntaxError
sv.compile(':nth-last-child(n of :nth-last-child(n of li))', ignore=[':nth-last-child', ':has'])
# The same option works through Beautiful Soup
soup.select(untrusted_selector, ignore=[':nth-last-child', ':has'])Blocking `:nth-last-child` covers the polynomial case: it is the only `nth` selector that walks siblings in reverse while evaluating a nested selector. `:nth-last-of-type` walks in reverse but only compares tag names, and `:nth-child(... of S)` walks forward. Blocking `:has` covers the quadratic subsequent-sibling case described above. The documentation already lists `:has` as a pseudo-class to consider blocking for untrusted input.
Keep the cache enabled when matching untrusted selectors. With `NOCACHE`, every `nth` lookup walks the siblings again, so nested `of S` selectors are polynomial in both directions, as the documentation already warns.
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 |
Corregida | 4.1.1 | 0 d | 4.1.2 no afectada |
4.1.1Arsenal 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-98qm-p6jx-5wj2Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
