CVE-2026-126192: Quadratic Algorithmic Complexity Denial of Service in Soup Sieve CSS Selector Engine

Soup Sieve (soupsieve) is the underlying CSS selector library integrated into Python's Beautiful Soup 4 (bs4) HTML and XML parsing package. It compiles CSS selector strings into internal abstract syntax structures and executes tree-traversal routines (select, select_one, iselect, match, filter, and closest) across parsed document object models. Web scrapers, sanitization pipelines, document converters, and content ingestion services rely on Beautiful Soup and Soup Sieve to extract and filter HTML elements.

In versions prior to 2.10, Soup Sieve contains an inefficient algorithmic complexity flaw classified under CWE-407 (Inefficient Algorithmic Complexity) and CWE-400 (Uncontrolled Resource Consumption). The vulnerability manifests when evaluating a CSS selector that uses a general sibling combinator (~) inside a :has() relational pseudo-class, such as div:has(a ~ b).

When the engine processes this selector pattern against an HTML parent node containing $n$ matching left-hand child elements (<a>) but no matching right-hand sibling element (<b>), it fails to memoize prior sibling traversal results. Consequently, the engine performs repeated linear scans across the remaining sibling list for every candidate element.

This behavior degrades selector evaluation from linear $\mathcal{O}(n)$ time to quadratic $\mathcal{O}(n^2)$ time relative to the number of sibling tags. If an application applies affected selectors to untrusted HTML provided by external users or remote servers, an attacker can trigger prolonged CPU saturation and Denial of Service (DoS) using minimal network bandwidth.

In the CSS Selectors Level 4 specification, the :has() relational pseudo-class matches an anchor element if any relative selector argument matches at least one element relative to that anchor. When evaluating a selector such as div:has(a ~ b), Soup Sieve first identifies a candidate <div> element and invokes CSSMatch.match_future_child() in soupsieve/css_match.py to traverse its descendants looking for the left-hand sub-selector (a).

Each time match_future_child() locates a matching <a> element, Soup Sieve evaluates the relative relationship to determine whether a subsequent sibling <b> exists under the same parent. Internally, the general sibling combinator inside :has() is represented by the constant REL_HAS_SIBLING, which routes execution to CSSMatch.match_future_relations().

Prior to version 2.10, the REL_HAS_SIBLING handler inside match_future_relations() executed an uncached while loop that stepped forward through every subsequent sibling tag via self.get_next_tag(sibling) until a tag matched b or the sibling chain ended. Simultaneously, the standard past general sibling combinator (REL_SIBLING in match_past_relations()) executed a similar uncached backward walk via self.get_previous_tag(sibling).

When the target element b is absent from the DOM subtree, the inner loop cannot short-circuit early. For a parent element containing $n$ sibling <a> elements and zero <b> elements, the first <a> scans $(n - 1)$ siblings, the second scans $(n - 2)$ siblings, and the $(n - 1)$-th scans $1$ sibling. The total number of tag comparisons equals:

$$\sum_{k=1}^{n-1} (n - k) = \frac{n(n - 1)}{2} = \mathcal{O}(n^2)$$

In contrast, the adjacent sibling combinator (+, represented by REL_HAS_CLOSE_SIBLING in div:has(a + b)) inspects only the single immediate next tag via one call to self.get_next_tag(el). Because it does not iterate across the remainder of the sibling list, the + combinator executes in strictly linear $\mathcal{O}(n)$ time.

The vulnerability resides in soupsieve/css_match.py within the CSSMatch class. In versions <= 2.9.2, both match_past_relations() and match_future_relations() traversed sibling chains statelessly on every invocation:

# Vulnerable implementation in soupsieve/css_match.py (< 2.10)
def match_future_relations(self, el: bs4.Tag, relation: ct.SelectorList) -> bool:
    found = False
    if relation[0] is ct.Null:
        return found
 
    if relation[0].rel_type == REL_HAS_PARENT:
        found = self.match_future_child(el, relation, True)
    elif relation[0].rel_type == REL_HAS_CLOSE_PARENT:
        found = self.match_future_child(el, relation)
    elif relation[0].rel_type == REL_HAS_SIBLING:
        # VULNERABLE: Walks every subsequent sibling tag from 'el' to the end of the parent.
        # No state is saved across calls for siblings sharing the same parent.
        sibling = self.get_next_tag(el)
        while not found and sibling:
            found = self.match_selectors(sibling, relation)
            sibling = self.get_next_tag(sibling)
    elif relation[0].rel_type == REL_HAS_CLOSE_SIBLING:
        sibling = self.get_next_tag(el)
        if sibling and self.is_tag(sibling):
            found = self.match_selectors(sibling, relation)
    return found

Commit ffb88cca745c591224f74a8e86414a85e8f35fc0 resolves the issue by introducing a per-parent sibling cache (self.sib_cache) and delegating both REL_SIBLING and REL_HAS_SIBLING evaluations to a new helper method, match_general_sibling():

# Patched implementation in soupsieve/css_match.py (2.10)
def match_general_sibling(self, el: bs4.Tag, relation: ct.SelectorList) -> bool:
    """Match general sibling combinator."""
    found = False
    if relation[0] is ct.Null:
        return found
 
    pkey: tuple[str | None, int] | None = None
    key: tuple[ct.SelectorList, int] | None = None
 
    parent = self.get_parent(el)
    if parent is None:
        return found
 
    if parent:
        # Key the cache by parent tag name and object identity
        pkey = (parent.name, id(parent))
        if pkey not in self.sib_cache:
            self.sib_cache[pkey] = {}
 
    # For REL_HAS_SIBLING (reverse=True), scan backward from the last child.
    # For REL_SIBLING (reverse=False), scan forward from the first child.
    reverse = relation[0].rel_type == REL_HAS_SIBLING
    start = len(parent) - 1 if reverse else 0
    if pkey:
        key = (relation, id(relation))
        if key in self.sib_cache[pkey]:
            index = self.sib_cache[pkey][key]
            if index >= 0:
                # A matching sibling exists at 'index'; check if 'el' precedes/follows it
                a, b = (index, start) if reverse else (start, index)
                return not within(el, parent, a, b)
            else:
                # Cached -1 indicates no matching sibling exists under this parent
                return False
        self.sib_cache[pkey][key] = start
 
    passed = False
    incr = -1 if reverse else 1
    for child in self.get_children(parent, start=start, reverse=reverse):
        start += incr
        if not isinstance(child, bs4.Tag):
            continue
        if child is el:
            passed = True
        if self.match_selectors(child, relation):
            found = True
            break
 
    # Cache the index of the furthest matching sibling, or -1 if none exists
    if pkey and key:
        self.sib_cache[pkey][key] = start if found else -1
 
    if passed:
        found = False
 
    return found

The patched algorithm changes both the traversal direction and the state management. For REL_HAS_SIBLING, match_general_sibling() starts at the end of the parent's child list (len(parent) - 1) and walks backward toward the first child to locate the furthest matching sibling (b). If a match is found at child index $k$, that index is stored in self.sib_cache[pkey][key], allowing all subsequent sibling checks under the same parent to simply compare their position against index $k$ via within(). If no match exists under the parent, -1 is stored in self.sib_cache[pkey][key], and all remaining n - 1 sibling candidates return False in $\mathcal{O}(1)$ constant time.

> [!NOTE] > In addition to the caching fix, version 2.10 includes commit b416f7d69dc12d8e7ac04c0da99b488827e24220, which adds an ignore parameter to Soup Sieve's public API functions (compile, select, match, etc.). This allows applications that accept user-supplied CSS selectors to explicitly block complex relational pseudo-classes such as :has.

Exploiting CVE-2026-126192 requires two conditions: the target application must evaluate a CSS selector containing a general sibling combinator nested within :has() (or evaluate user-supplied selectors directly), and the application must parse untrusted HTML input through Beautiful Soup and Soup Sieve. No authentication or special privileges are required if the HTML ingestion endpoint is publicly reachable.

An attacker constructs an HTML document containing a parent container matched by the outer selector (such as <div>) populated with a dense sequence of sibling tags matching the left-hand selector (<a></a>), while omitting the right-hand selector (<b>). Because HTML opening and closing tags for single-letter elements require only 7 bytes (<a></a>), an attacker can pack thousands of sibling nodes into a compact HTTP request body or webhook payload.

import time
import soupsieve
from bs4 import BeautifulSoup
 
# Selector containing a general sibling combinator inside :has()
selector = "div:has(a ~ b)"
 
for n in (1000, 2000, 4000, 8000):
    # Generate markup with 'n' matching left-hand siblings and no matching 'b' sibling
    html = "<div>" + ("<a></a>" * n) + "</div>"
    soup = BeautifulSoup(html, "html.parser")
    
    start = time.perf_counter()
    soupsieve.select(selector, soup)
    elapsed_ms = round((time.perf_counter() - start) * 1000)
    print(f"n={n:<5} -> {elapsed_ms:>6} ms")

Executing this proof-of-concept on soupsieve==2.9.2 demonstrates exact quadratic scaling where doubling the sibling count $n$ quadruples the execution time ($2^2 = 4$):

n=1000   ->    837 ms
n=2000   ->   3667 ms
n=4000   ->  14797 ms
n=8000   ->  59746 ms

At $n = 8000$, the entire HTML payload is approximately 56 KB in size, which easily bypasses standard web server request body limits (typically 1 MB to 10 MB). When processed by a synchronous Python web worker (such as Gunicorn sync workers, uWSGI processes, or Celery task runners), the thread blocks on the GIL-bound CPU loop for nearly 60 seconds per request.

The primary impact of CVE-2026-126192 is application-level Denial of Service (MITRE ATT&CK technique T1499: Endpoint Denial of Service). The vulnerability does not permit memory corruption, arbitrary code execution, or unauthorized data disclosure (VC:N/VI:N), as all operations occur within memory-safe Python data structures.

In synchronous Python web frameworks (such as Django or Flask running under Gunicorn with standard worker counts of $2 \times \text{CPU cores} + 1$), an attacker sending a handful of concurrent 56 KB requests can occupy all available worker processes for a full minute. Legitimate incoming HTTP requests will queue at the reverse proxy layer and eventually fail with 502 Bad Gateway or 504 Gateway Timeout errors.

In asynchronous Python frameworks (such as FastAPI or aiohttp), calling soupsieve.select() directly inside an async def coroutine blocks the main asyncio event loop thread. A single 56 KB payload freezes the entire event loop for 60 seconds, preventing the server from handling any concurrent connections, health checks, or WebSocket heartbeats on that worker process.

The vulnerability is scored at 6.3 (Medium) under CVSS v4.0 (CVSS:4.0/AV:N/AC:L/AT:P/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N). The Attack Requirements metric is set to Present (AT:P) because exploitation depends on the target application using the specific :has(... ~ ...) selector pattern or allowing arbitrary user-controlled CSS selectors.

The definitive remediation is to upgrade the soupsieve package to version 2.10 (2.10.0) or later. In version 2.10, the match_general_sibling() cache reduces the evaluation complexity of div:has(a ~ b) back to linear $\mathcal{O}(n)$ time, completing the $n = 8000$ proof-of-concept in milliseconds.

pip install --upgrade "soupsieve>=2.10.0"

If an immediate dependency upgrade is not feasible, developers can refactor affected CSS selectors to avoid nesting the general sibling combinator (~) inside :has(). Where the document structure permits, replacing the general sibling combinator with the adjacent sibling combinator (div:has(a + b)) avoids the quadratic loop even on unpatched versions of Soup Sieve. Additionally, narrowing broad anchor selectors (replacing *:has(a ~ b) with specific tag or class qualifiers) reduces the number of subtrees evaluated.

For applications that accept dynamic or user-authored CSS selectors and upgrade to soupsieve >= 2.10.0, developers should restrict expensive relational pseudo-classes using the newly introduced ignore parameter:

import soupsieve as sv
from bs4 import BeautifulSoup
 
soup = BeautifulSoup(untrusted_html, "html.parser")
 
# Reject selectors containing :has() or :-soup-contains()
compiled_selector = sv.compile(
    user_supplied_selector,
    ignore=[":has", ":-soup-contains"]
)
results = compiled_selector.select(soup)

Finally, services that parse untrusted HTML documents should enforce strict input size quotas on incoming markup and execute DOM parsing and selector matching within isolated worker processes configured with hard CPU execution timeouts (such as Celery time_limit settings or OS-level RLIMIT_CPU constraints).