GHSA-98qm-p6jx-5wj2: 
Python Analyse et atténuation de la vulnérabilité

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:

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:

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