CVE-2026-86000: Polynomial-Time Regular Expression Denial of Service in Soup Sieve Selector Parser

The Soup Sieve library is a highly utilized component in the Python ecosystem, serving as the default CSS selector implementation for the ubiquitous Beautiful Soup 4 library. It allows developers to search and filter parsed HTML/XML documents using complex CSS selector patterns, mirroring modern browser capability. Because of this, Soup Sieve is commonly integrated into automated data ingestion systems, web scrapers, data aggregators, and document processing backends. These applications frequently accept and process external, user-supplied data, making selector parsing a critical boundary for system stability and security.

Prior to version 2.9, Soup Sieve's selector compiler contained a vulnerability within its regular expression patterns. An unauthenticated attacker capable of providing a custom, crafted CSS selector string could trigger a massive resource consumption state. This is tracked as CVE-2026-86000 and is classified under CWE-1333 (Inefficient Regular Expression Complexity) and CWE-400 (Uncontrolled Resource Consumption).

The vulnerability is activated when Soup Sieve processes custom selectors using functions such as soupsieve.compile(), soupsieve.select(), or BeautifulSoup.select(). When a long or unclosed CSS selector pattern is compiled, the backtracking regular expression engine attempts to resolve overlapping paths. This results in quadratic time complexity ($O(n^2)$) relative to the length of the string, keeping the system process bound to the CPU, locking the Global Interpreter Lock, and completely stalling service for any other tasks.

To understand the technical root cause of CVE-2026-86000, we must examine how the Soup Sieve parser processes CSS identifiers. In src/soupsieve/css_parser.py, the tokenization engine depends on a hand-written regular expression sub-pattern named IDENTIFIER. This pattern is responsible for matching selectors such as tags, IDs, class names, and attributes.

The vulnerable definition of IDENTIFIER was structured with two adjacent quantified sub-groups. The first group, representing the identifier prefix, was defined as (?:-?(?:[^\x00-\x2f\x30-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})+|--). The second group, matching the identifier continuation, was defined as (?:[^\x00-\x2c\x2e\x2f\x3A-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})*. The critical vulnerability resides in the fact that these two adjacent groups match heavily overlapping character classes.

The character classes in both groups permit standard alphanumeric characters, such as lowercase and uppercase letters (a-z, A-Z) and underscores (_). When a long string consisting entirely of overlapping characters is evaluated, the Python standard re module (which implements a backtracking NFA-based engine) experiences high ambiguity. It cannot deterministically determine where the first group (quantified with +) ends and where the second group (quantified with *) begins.

If the input eventually fails downstream—such as when a long alphanumeric identifier is terminated with an invalid character like !—the NFA engine is forced to backtrack. It evaluates every possible split of characters between the first and second groups to find a valid match. The number of splits grows quadratically ($O(n^2)$) relative to the length of the string. This leads to massive CPU exhaustion, pinning a CPU core at 100% until the evaluation is complete.

Comparing the code of src/soupsieve/css_parser.py before and after the version 2.9 release demonstrates a clean remediation of this regular expression complexity. The vulnerability was resolved in commit ce44e4996e6632871c18cdd7a7fb641be8ef34ef by making the prefix matching deterministic.

Before the patch, the IDENTIFIER regular expression was defined as follows:

# Vulnerable code in soupsieve/css_parser.py
IDENTIFIER = fr'''
(?:(?:-?(?:[^\x00-\x2f\x30-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})+|--)
(?:[^\x00-\x2c\x2e\x2f\x3A-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})*)
'''

The presence of the + quantifier in the first group allows it to consume an arbitrary length of valid identifier characters. Because the second group also consumes standard identifier characters via the * quantifier, the engine is forced to explore a massive state space when backtracking occurs.

The patch successfully resolved the flaw by refactoring the expression to remove the variable quantifier from the prefix group:

# Patched code in soupsieve/css_parser.py (v2.9)
IDENTIFIER = fr'''
(?:(?:--|-?(?:[^\x00-\x2f\x30-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES}))
(?:[^\x00-\x2c\x2e\x2f\x3A-\x40\x5B-\x5E\x60\x7B-\x9f]|{CSS_ESCAPES})*)
'''

By replacing + with a deterministic requirement matching exactly one character or double hyphens (--), the engine is forced to consume precisely one character in the prefix group. Any remaining characters are consumed strictly by the continuation group. This completely eliminates the ambiguity, changing the matching operation's time complexity from $O(n^2)$ back to linear $O(n)$ time. This fix is complete and robust because it removes the foundational mechanism required for catastrophic backtracking.

Exploiting CVE-2026-86000 is straightforward and requires no special system privileges. An attacker simply needs to submit a crafted CSS selector to any system that processes inputs with the vulnerable Soup Sieve library. Since the vulnerability is located inside the tokenizing engine, simply compiling a malformed selector is sufficient to trigger the CPU hang.

There are two main payload variants that trigger the backtracking behaviour. The first is a plain identifier payload where a very long string of alphanumeric characters is terminated with a syntax-breaking character (like an exclamation mark). This forces the engine to parse the long string as an identifier, reach the end, realize the match has failed, and backtrack through the entire string:

/* Plain identifier payload */
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... [10,000+ chars] ...aaa!

The second vector involves unquoted attribute-value selectors. The Soup Sieve parser embeds the vulnerable IDENTIFIER definition inside the pattern used to evaluate attribute values. If an attacker submits an unclosed attribute selector containing a long run of unquoted characters, the engine experiences identical backtracking during EOF resolution:

/* Unquoted attribute-value payload */
[a=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... [12,000+ chars]

When a Python process executes either payload, the regular expression engine holds the Python Global Interpreter Lock (GIL). This prevents any other threads in the same process from executing, stalling the entire application worker. An attacker can easily weaponize this by sending multiple concurrent requests to fully saturate all worker processes on the application server, resulting in complete denial of service.

The primary impact of CVE-2026-86000 is a complete Denial of Service (DoS) of the affected Python application. Because the execution of the regular expression engine occurs within native C code in the Python standard library, it runs at maximum processor speed, pinning a CPU core at 100%. If the host application is single-process or has limited worker threads, a single malicious request can completely lock up the service.

When the regular expression engine is forced to backtrack over a malicious payload, it consumes 100% of the allocated CPU core. Because Python's Global Interpreter Lock (GIL) is held during the C-level execution of the re module, even multi-threaded application servers (such as those running under certain configurations of gunicorn or uWSGI) can experience complete lockups. The entire process becomes unresponsive to health checks and incoming user traffic.

In environments where multiple worker processes are deployed, an attacker can trivially send a small number of concurrent malicious requests (matching the number of worker processes) to completely exhaust the application pool. This results in an immediate, sustained denial of service across the entire platform. Since the exploit complexity is low and requires no special privileges, systems that parse arbitrary, user-supplied HTML documents or support custom selectors are highly exposed.