CVE-2026-126190: Polynomial-Time Denial of Service in Soup Sieve CSS Descendant Combinator

Soup Sieve (soupsieve) is a CSS selector library designed to query HTML and XML documents parsed by Beautiful Soup 4 (bs4). Since Beautiful Soup 4.7.0, Soup Sieve serves as the default underlying engine for the .select() and .select_one() methods. Consequently, any Python application using Beautiful Soup to query or filter markup via CSS selectors relies directly on Soup Sieve's matching engine.

In versions prior to 4.0, Soup Sieve contains an Inefficient Algorithmic Complexity flaw (CWE-407) within soupsieve/css_match.py. When processing the CSS descendant combinator—represented by whitespace separating two compound selectors, such as a b—the matcher traverses upward through the document tree to verify whether candidate elements have matching ancestors. Because the implementation does not cache intermediate ancestor checks across multiple elements or chained combinators, identical ancestor subtrees are evaluated repeatedly.

This behavior exposes a significant attack surface for applications that ingest and query untrusted HTML or XML content. Web scrapers, automated crawlers, HTML sanitizers, content management systems, and document-processing microservices commonly execute multi-part CSS selectors (such as article .content div p) against external markup. An unauthenticated attacker can supply a compact, deeply nested document—often under 2 KB in size—that forces the selector engine into polynomial execution time, exhausting CPU resources and blocking application worker threads.

The root cause of CVE-2026-126190 lies in how CSSMatch.match_past_relations processes the REL_PARENT relationship token, which represents the CSS descendant combinator. In Soup Sieve's selector evaluation model, selectors are parsed right-to-left. When evaluating a selector a b, the engine first identifies an element matching b and then yields parent nodes sequentially via self.get_parent(parent) to verify if any ancestor matches a.

When a selector chains multiple descendant combinators—for example, a b c d, which contains $k = 3$ descendant combinators—the backtracking traversal compounds recursively. For every node matching d, the engine walks upward through all ancestors to locate a candidate matching c. From each matching c, it initiates a separate upward walk to locate b, and from each b, another upward walk to locate a. Prior to version 4.0, the engine did not record whether a given ancestor node had already been evaluated against a specific relation sub-selector.

The pathological worst-case complexity occurs under two conditions: the input document forms a deep, linear chain of nested elements of depth $n$ (such as <div><div><div>...), and the leftmost selector segment never matches any element in the tree (such as section div div evaluated against a tree composed exclusively of <div> tags). Because the leftmost token never matches, no early termination is possible, and every ancestor search traverses all the way to the document root.

For a tree of nesting depth $n$ evaluated against a selector with $k$ descendant combinators, the total number of element comparisons equals the binomial coefficient $\binom{n}{k+1}$, which scales asymptotically at $\mathcal{O}(n^{k+1})$. Specifically, a single combinator (section div) exhibits quadratic $\mathcal{O}(n^2)$ complexity, two combinators (section div div) exhibit cubic $\mathcal{O}(n^3)$ complexity, and three combinators (section div div div) exhibit quartic $\mathcal{O}(n^4)$ complexity. Doubling the nesting depth $n$ increases execution time by a factor of $2^{k+1}$, resulting in a $16\times$ slowdown for three combinators.

In Soup Sieve versions prior to 4.0, the match_past_relations method in soupsieve/css_match.py handled REL_PARENT directly inside an unmemoized while loop. Every time a descendant combinator was evaluated for a node el, the code walked the parent chain from scratch:

# Vulnerable implementation in soupsieve/css_match.py (prior to 4.0)
if relation[0].rel_type == REL_PARENT:
    parent: bs4.Tag | None = el
    while not found and parent and (parent := self.get_parent(parent)):
        # Yields every ancestor up to the root without checking if
        # (parent, relation) was already evaluated during a previous walk.
        found = parent is not None and (yield parent, relation)

Commit ff1a5ce7e5addc31626d7b6053511fecdb4f6320 resolves this flaw by introducing an ancestor evaluation cache (self.anc_cache) inside the CSSMatch class. This dictionary maps a tuple of object identifiers (id(parent), id(relation)) to a boolean indicating whether that specific ancestor satisfies the sub-selector relation.

# Patched implementation in soupsieve/css_match.py (version 4.0)
def match_ancestor(self, el: bs4.Tag, relation: ct.SelectorList) -> MatchGenerator:
    found = False
    visited: list[tuple[int, int]] = []
    parent: bs4.Tag | None = el
    while not found and parent and (parent := self.get_parent(parent)):
        key = (id(parent), id(relation))
        # Check if this ancestor was already evaluated for this specific relation
        if key in self.anc_cache:
            found = self.anc_cache[key]
            break
        visited.append(key)
        found = yield parent, relation
 
    # Propagate the boolean outcome to all ancestors visited during this walk
    for key in visited:
        self.anc_cache[key] = found
 
    return found

During an upward traversal in match_ancestor, every unvisited parent node's key (id(parent), id(relation)) is appended to a temporary visited list. If the loop encounters a parent that is already present in self.anc_cache, or if yield parent, relation returns True (indicating a match), the walk terminates immediately. Because every ancestor visited prior to termination shares the same outcome—either an ancestor above them matched the relation, or the walk reached the root without finding a match—all keys recorded in visited are updated with the boolean found value in self.anc_cache.

> [!NOTE] > In match_past_relations, match_ancestor is only invoked when self.enable_cache is True. If a caller compiles or executes a selector with the util.NOCACHE flag (sv.NOCACHE), Soup Sieve bypasses match_ancestor and falls back to the unmemoized while loop. Consequently, applications that explicitly pass NOCACHE remain susceptible to polynomial execution times even on version 4.0 and later.

Exploiting CVE-2026-126190 requires no authentication or specialized privileges if the target application parses attacker-supplied HTML or XML and queries it with CSS selectors containing descendant combinators. Because HTML parsers such as Python's built-in html.parser or lxml permit deep element nesting by default, an attacker can construct a tiny payload consisting of consecutive opening tags (<div>) without even requiring closing tags.

The following proof-of-concept demonstrates how a 1,000-byte payload (200 nested <div> elements) triggers over 40 seconds of CPU execution when evaluated against a selector with three descendant combinators (section div div div):

import time
import bs4
import soupsieve as sv
 
# Generate 200 levels of nested <div> tags (1,000 bytes total)
payload = "<div>" * 200 + "</div>" * 200
soup = bs4.BeautifulSoup(payload, "html.parser")
 
# Selector with k = 3 descendant combinators where 'section' never matches
selector = "section div div div"
 
start_time = time.process_time()
results = sv.select(selector, soup)
elapsed = time.process_time() - start_time
 
print(f"Matches found: {len(results)}")
print(f"Elapsed CPU Time: {elapsed:.2f} seconds")

Empirical benchmarks comparing Soup Sieve 3.0.4 against the patched 4.0 release highlight the amplification ratio between input size and CPU consumption:

In a web application or API environment running synchronous Python workers (such as Gunicorn sync workers or Celery task queues), submitting a small number of concurrent requests containing 2 KB to 4 KB of nested tags will saturate all available worker processes. Because the evaluation occurs entirely in CPU-bound Python bytecode loops, asynchronous event loops (such as asyncio or FastAPI endpoints running synchronous Beautiful Soup calls on the event loop thread) will block completely until the traversal finishes.

CVE-2026-126190 is rated High severity with a CVSS v3.1 base score of 7.5 (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H). The Attack Vector is Network (AV:N) and Attack Complexity is Low (AC:L), as descendant combinators are the most common combinator structure in CSS queries and require no special application configuration to trigger. No privileges (PR:N) or user interaction (UI:N) are required when the target system automatically parses external markup.

The security impact is strictly confined to Availability (A:H), with no direct impact on Confidentiality (C:N) or Integrity (I:N). However, the resource asymmetry is severe: a 4 KB HTTP request or webhook payload evaluated against a 3-stage selector (a b c) stalls a CPU core for nearly one minute, while a 1 KB payload against a 4-stage selector (a b c d) stalls execution for over 40 seconds.

Downstream impact extends across the Python ecosystem because soupsieve is installed automatically as a core dependency of beautifulsoup4. Any service that uses soup.select() or soup.select_one() to extract metadata, sanitize user-supplied HTML comments, generate link previews, or scrape remote web pages can be rendered unresponsive by an attacker controlling the input markup.

The primary remediation is to upgrade the soupsieve package to version 4.0 or later (4.0.1+), which implements ancestor memoization and reduces descendant combinator evaluation from $\mathcal{O}(n^{k+1})$ to linear $\mathcal{O}(n)$ time complexity.

pip install --upgrade "soupsieve>=4.0"

When upgrading to Soup Sieve 4.0, developers must ensure that application code does not pass the soupsieve.NOCACHE flag when compiling or executing selectors against untrusted markup. Passing NOCACHE disables self.anc_cache and forces Soup Sieve to execute the vulnerable unmemoized traversal path.

For environments where upgrading soupsieve is temporarily blocked, developers can apply structural workarounds to mitigate the complexity risk:

1. Replace Descendant Combinators with Child Combinators: Where the expected DOM structure is fixed, replace whitespace descendant combinators (a b c) with direct child combinators (a > b > c). The child combinator (REL_CLOSE_PARENT) inspects only the immediate parent element (self.get_parent(el)), preventing full upward tree walks.
2. Enforce Document Depth and Size Limits: Validate or reject HTML/XML documents that exceed a maximum nesting depth threshold prior to running Beautiful Soup selector queries.
3. Process Isolation with Timeouts: Execute untrusted HTML parsing and selector evaluation inside isolated worker processes (such as concurrent.futures.ProcessPoolExecutor) configured with strict execution timeouts to prevent main application threads from hanging indefinitely.