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

Vulnerability ID: CVE-2026-126190
CVSS Score: 7.5
Published: 2026-11-13

CVE-2026-126190 (GHSA-mmhr-3c5m-f64f) is an inefficient algorithmic complexity vulnerability (CWE-407) in Soup Sieve, the default CSS selector library integrated into Beautiful Soup 4. In versions prior to 4.0, evaluating CSS selectors that contain descendant combinators (whitespace between compound selectors) executes an unmemoized upward traversal of the document tree. When evaluated against deeply nested HTML or XML documents, the time complexity scales polynomially at O(n^(k+1)), where n is the tree depth and k is the number of descendant combinators. Remote attackers can supply compact, deeply nested markup (1 KB to 4 KB) to trigger prolonged CPU starvation and denial of service in Python applications.

TL;DR

Soup Sieve versions prior to 4.0 fail to memoize ancestor evaluations when matching CSS descendant combinators, leading to O(n^(k+1)) polynomial time complexity and remote denial of service via small, deeply nested HTML or XML payloads.

⚠️ Exploit Status: POC

Technical Details

• Vulnerability ID: CVE-2026-126190 / GHSA-mmhr-3c5m-f64f
• Weakness Class: CWE-407: Inefficient Algorithmic Complexity
• CVSS v3.1 Score: 7.5 HIGH (AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H)
• Affected Component: soupsieve (< 4.0.0) / CSSMatch.match_past_relations
• Time Complexity: O(n^(k+1)) unpatched vs. O(n) patched
• Primary Impact: Denial of Service via CPU Exhaustion
• Exploit Status: Public PoC Available
• Patched Version: soupsieve 4.0

Affected Systems

• Soup Sieve (soupsieve PyPI package)
• Beautiful Soup 4 (bs4) applications utilizing .select() or .select_one()
• soupsieve: < 4.0.0 (Fixed in: 4.0)

Code Analysis

Commit: ff1a5ce

Cache whether an element is or has a matching ancestor when matching the descendant combinator (a b) to avoid polynomial time complexity.

diff --git a/soupsieve/css_match.py b/soupsieve/css_match.py
index ced22901..f2bcdabc 100644
--- a/soupsieve/css_match.py
+++ b/soupsieve/css_match.py
@@ -614,6 +614,7 @@ def __init__(
         self.enable_cache = not bool(self.flags & util.NOCACHE)
         self.nth_cache: dict[Hashable, list[int]] = {}
         self.sib_cache: dict[Hashable, int] = {}
+        self.anc_cache: dict[tuple[int, int], bool] = {}
         self.dir_cache: dict[int, int] = {}
         self.index_cache: dict[int, dict[int, int]] = {}

@@ -648,6 +649,7 @@ def reset(self) -> None:  # pragma: no cover

         self.nth_cache.clear()
         self.sib_cache.clear()
+        self.anc_cache.clear()
         self.dir_cache.clear()
         self.index_cache.clear()

@@ -989,6 +991,31 @@ def match_general_sibling(self, el: bs4.Tag, relation: ct.SelectorList) -> Match

         return found

+    def match_ancestor(self, el: bs4.Tag, relation: ct.SelectorList) -> MatchGenerator:
+        """
+        Match descendant combinator.
+
+        A selector with several descendant combinators tries every ancestor for each one, which is
+        a polynomial of the depth with a degree of the number of combinators. Every element visited
+        on the walk shares the result, so cache whether each one is or has a matching ancestor.
+        """
+
+        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))
+            if key in self.anc_cache:
+                found = self.anc_cache[key]
+                break
+            visited.append(key)
+            found = yield parent, relation
+
+        for key in visited:
+            self.anc_cache[key] = found
+
+        return found
+
     def match_past_relations(self, el: bs4.Tag, relation: ct.SelectorList) -> MatchGenerator:
         """Match past relationship."""

@@ -998,9 +1025,12 @@ def match_past_relations(self, el: bs4.Tag, relation: ct.SelectorList) -> MatchG
             return found

         if relation[0].rel_type == REL_PARENT:
-            parent: bs4.Tag | None = el
-            while not found and parent and (parent := self.get_parent(parent)):
-                found = parent is not None and (yield parent, relation)
+            if self.enable_cache:
+                found = yield from self.match_ancestor(el, relation)
+            else:
+                parent: bs4.Tag | None = el
+                while not found and parent and (parent := self.get_parent(parent)):
+                    found = parent is not None and (yield parent, relation)
         elif relation[0].rel_type == REL_CLOSE_PARENT:
             parent = self.get_parent(el)
             found = parent is not None and (yield parent, relation)

Exploit Details

• GitHub Security Advisory: Official advisory containing benchmark data and proof-of-concept demonstrating O(n^(k+1)) polynomial slowdown using nested div tags.

Mitigation Strategies

• Upgrade the soupsieve Python package to version 4.0 or later to enable ancestor evaluation caching.
• Audit codebase to ensure the soupsieve.NOCACHE flag is never enabled when evaluating selectors on untrusted HTML or XML input.
• Refactor CSS selectors to use direct child combinators (>) instead of whitespace descendant combinators where document structure permits.
• Enforce maximum DOM nesting depth limits and execution timeouts around HTML parsing routines.

Remediation Steps:

1. Run pip install --upgrade 'soupsieve>=4.0' in all affected Python environments and container images.
2. Verify the installed version using python -c 'import soupsieve; print(soupsieve.__version__)' to confirm it is 4.0 or newer.
3. Search application source code for references to sv.NOCACHE or util.NOCACHE and remove them from untrusted parsing workflows.
4. If immediate patching is not possible, rewrite multi-stage descendant selectors (e.g., section div div) to use child combinators (section > div > div) or single-stage queries.

References

• GitHub Security Advisory GHSA-mmhr-3c5m-f64f
• NVD Detail for CVE-2026-126190
• CVE.org Record for CVE-2026-126190
• Soup Sieve Pull Request #351
• Soup Sieve Fix Commit ff1a5ce7e5addc31626d7b6053511fecdb4f6320
• Soup Sieve 4.0 Release Notes
• Soup Sieve GitHub Repository

Read the full report for CVE-2026-126190 on our website for more details including interactive diagrams and full exploit analysis.