CVE-2026-126298: Quadratic Algorithmic Complexity Denial of Service in NLTK Tree.chomsky_normal_form

The Natural Language Toolkit (NLTK) is a widely deployed Python library used for symbolic and statistical natural language processing (NLP). Within its syntactic parsing subsystem, the nltk.tree module provides data structures and transformation routines for manipulating hierarchical phrase-structure trees. A primary operation in computational linguistics and context-free grammar processing is the conversion of arbitrary syntax trees into Chomsky Normal Form (CNF), where every production rule is strictly binary ($A \to BC$) or unary terminal ($A \to a$).

In NLTK versions prior to 3.10.4, the nltk.tree.transforms.chomsky_normal_form() function—commonly invoked via the Tree.chomsky_normal_form() instance method—contains an inefficient algorithmic complexity flaw (CWE-407) that leads to uncontrolled resource consumption (CWE-400). When a tree node contains more than two children ($N > 2$), the function binarizes the node by introducing a chain of intermediate branching nodes. By default, this transformation uses a right-factoring strategy (factor="right").

During right-factoring, the implementation copied the target node's children into a standard Python list and iteratively removed elements from the front using nodeCopy.pop(0). Because CPython implements lists as contiguous arrays of pointers, popping the first element requires shifting all remaining elements left in memory, executing in $O(N)$ linear time per pop. Executing this operation $N - 2$ times across a single wide node results in $O(N^2)$ quadratic time complexity.

If an application exposes Tree.fromstring() and Tree.chomsky_normal_form() to untrusted network input, an unauthenticated attacker can supply a compact, flat tree representation containing tens or hundreds of thousands of sibling leaf nodes. Processing a 1.5 MB payload stalls a CPU core at 100% utilization for over 14 seconds, scaling quadratically as payload size increases. In addition, the transformation converts horizontal node width directly into vertical nesting depth, creating deep tree spines that exceed Python's recursion limit and trigger RecursionError (CWE-674) during subsequent tree operations.

The primary root cause of CVE-2026-126298 is a data structure mismatch between the algorithmic requirements of right-factored tree binarization and the memory model of CPython's built-in list type. In CPython (Objects/listobject.c), a PyListObject stores a pointer (ob_item) to a dynamically allocated, contiguous C array of PyObject* pointers. While appending or removing elements at the tail end of the array (list.pop()) adjusts the size metadata in $O(1)$ amortized constant time, removing the element at index 0 (list.pop(0)) requires an explicit memmove() call to shift all remaining $k - 1$ pointers one position to the left.

In nltk/tree/transforms.py, the chomsky_normal_form function accepts a factor parameter that defaults to "right". When iterating over a node with $N > 2$ children, the algorithm duplicates the node's child references via nodeCopy = node.copy(), clears the parent node's child list, and enters a for loop running from 1 to len(nodeCopy) - 1. On each iteration under the factor == "right" branch, the function constructs a new intermediate Tree object and assigns [nodeCopy.pop(0), newNode] to the current node.

Because nodeCopy.pop(0) is executed $N - 2$ times as the list length $k$ decays from $N$ down to 2, the total number of pointer shifts across a single node follows the arithmetic series:

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

By contrast, when factor="left" is specified, the function extracts children from the end of the list using curNode[0:] = [newNode, nodeCopy.pop()]. Because tail removal requires no memory shifting, the left-factoring code path executes in $O(1)$ per step and $O(N)$ overall. Notably, NLTK's inverse transformation function (un_chomsky_normal_form) had previously been refactored to avoid quadratic list manipulation, leaving the forward right-factoring path as an unaddressed bottleneck.

A secondary architectural weakness compounds this issue: width-to-depth amplification. While Tree.fromstring() enforces a maximum bracket nesting depth (MAX_TREE_DEPTH, defaulting to 500) to prevent stack overflow during parsing, it places no cap on the horizontal width (number of sibling children) of a single node. Binarizing a flat node of width $N$ converts those siblings into a nested chain of depth $N - 1$. Once chomsky_normal_form() mutates a wide node (e.g., $N = 3000$) into a deep vertical spine, any subsequent call to standard recursive Tree methods—such as __str__(), leaves(), height(), productions(), or copy.deepcopy()—exhausts the CPython call stack and raises an unhandled RecursionError.

The vulnerability was remediated across two commits in GitHub Pull Request #3909 (457ebe349f8dd8080224f76a64aff806dd437057 and 677857dcafd84e4591865d976b562a27dfde566e). The first commit addresses the $O(N^2)$ CPU complexity, while the second commit prevents width-to-depth recursion exhaustion.

Primary Fix: Eliminating Quadratic List Pops

In commit 457ebe349f8dd8080224f76a64aff806dd437057, the maintainers replaced the standard Python list copy with a collections.deque object. In CPython, a deque is implemented as a doubly-linked list of fixed-size pointer blocks, supporting $O(1)$ constant-time insertion and removal at both ends.

# File: nltk/tree/transforms.py
from collections import deque
from nltk.tree.tree import Tree
 
def chomsky_normal_form(
    tree, factor="right", horzMarkov=None, vertMarkov=0, childChar="|", parentChar="^"
):
    # ... [omitted setup and vertical Markov tracking] ...
    for node in tree.treepositions():
        node = tree[node]
        if isinstance(node, Tree) and len(node) > 2:
            childNodes = [
                str(child.label()) if isinstance(child, Tree) else str(child)
                for child in node
            ]
            
            # VULNERABLE CODE (<= 3.10.3):
            # nodeCopy = node.copy()  # Creates a standard Python list
            
            # PATCHED CODE (>= 3.10.4):
            # Consume children from the front in O(1) via a deque so the
            # right-factoring loop stays linear (CWE-407 / CWE-400, GHSA-r53h-rw34-8h97).
            nodeCopy = deque(node)
            node[0:] = []  # Clear existing children from the current node
 
            curNode = node
            numChildren = len(nodeCopy)
            for i in range(1, numChildren - 1):
                if factor == "right":
                    newHead = "{}{}<{}>{}".format(
                        originalNode,
                        childChar,
                        "-".join(
                            childNodes[i : min([i + horzMarkov, numChildren])]
                        ),
                        parentString,
                    )
                    newNode = Tree(newHead, [])
                    
                    # VULNERABLE CODE (<= 3.10.3):
                    # curNode[0:] = [nodeCopy.pop(0), newNode]  # O(N) memmove shift per iteration
                    
                    # PATCHED CODE (>= 3.10.4):
                    curNode[0:] = [nodeCopy.popleft(), newNode] # O(1) pointer advancement
                    curNode = newNode

By substituting nodeCopy.popleft() for nodeCopy.pop(0) (including the final two-element assignment outside the loop in the full source), right-factoring scales strictly in $O(N)$ linear time.

Secondary Fix: Pre-Transformation Depth Validation

Once the $O(N^2)$ CPU bottleneck was removed, wide trees could be binarized rapidly, exposing the secondary RecursionError hazard (CWE-674). Commit 677857dcafd84e4591865d976b562a27dfde566e introduced an iterative helper function, _binarised_depth(), to calculate the exact post-transformation nesting depth prior to mutating the tree.

# File: nltk/tree/transforms.py
def _binarised_depth(tree, factor):
    """Nesting depth *tree* will have after binarisation, computed iteratively."""
    depth = {}
    stack = [(tree, False)]
    while stack:
        node, visited = stack.pop()
        if not isinstance(node, Tree):
            continue
        if not visited:
            stack.append((node, True))
            stack.extend((child, False) for child in node)
            continue
        width = len(node)
        deepest = 1
        for position, child in enumerate(node):
            if width > 2 and factor == "right":
                levels = min(position + 1, width - 1)
            elif width > 2:
                levels = min(width - position, width - 1)
            else:
                levels = 1
            deepest = max(deepest, levels + depth.get(id(child), 0))
        depth[id(node)] = deepest
    return depth.get(id(tree), 0)

At the entry point of chomsky_normal_form(), the function now evaluates _binarised_depth(tree, factor) against _tree.MAX_TREE_DEPTH:

    binarised_depth = _binarised_depth(tree, factor)
    if binarised_depth > _tree.MAX_TREE_DEPTH:
        raise ValueError(
            f"Binarising this tree would nest it {binarised_depth} levels deep, "
            f"beyond MAX_TREE_DEPTH ({_tree.MAX_TREE_DEPTH}): a wide node becomes "
            "a chain as deep as it is wide, which the recursive Tree methods "
            "cannot walk. Raise nltk.tree.tree.MAX_TREE_DEPTH to allow it."
        )

Assessment of Fix Completeness

The combination of both commits completely resolves the vulnerability within chomsky_normal_form(). First, _binarised_depth() uses an explicit heap-allocated stack list rather than call-stack recursion, ensuring the pre-check itself cannot trigger a RecursionError on edge-case inputs. Second, the ValueError check occurs before any in-place mutation of tree, maintaining state consistency and matching the exception contract of Tree.fromstring(). Finally, note that while childNodes string slicing (childNodes[i : min([i + horzMarkov, numChildren])]) remains inside the loop when horzMarkov is unbounded (defaulting to 999), the slice width is capped at the constant 999, bounding that operation to $O(1)$ amortized cost per step and keeping overall complexity strictly $O(N)$.

Exploiting CVE-2026-126298 requires an application to parse untrusted input into an NLTK Tree object (typically via Tree.fromstring()) and subsequently pass that object to chomsky_normal_form() without explicitly overriding factor="right". No authentication or special privileges are required at the library level.

Attack Methodology

To maximize the ratio of CPU consumption to payload byte length, an attacker constructs a flat, bracketed tree string where a single root node (S ...) encapsulates $N$ minimal subtree children (A a). Each child token (A a) occupies 5 bytes. Because the nesting depth of (S (A a)(A a)...) is only 2, it passes Tree.fromstring()'s MAX_TREE_DEPTH (500) validation check without issue.

Proof of Concept

The following proof-of-concept script benchmarks the execution duration of the default right-factoring path against the linear left-factoring control path across doubling input widths ($N \in {80000, 160000, 320000}$):

import time
from nltk.tree import Tree
 
for N in (80000, 160000, 320000):
    # Construct a flat tree string of depth 2 and width N
    # At N=320,000, payload size is approximately 1.6 MB
    payload = "(S " + "(A a)" * N + ")"
    
    t_right = Tree.fromstring(payload)
    start = time.perf_counter()
    t_right.chomsky_normal_form(factor="right")
    elapsed_right = time.perf_counter() - start
    
    t_left = Tree.fromstring(payload)
    start = time.perf_counter()
    t_left.chomsky_normal_form(factor="left")
    elapsed_left = time.perf_counter() - start
    
    print(
        f"N={N:6d} | factor='right' (vuln): {elapsed_right:6.3f}s | "
        f"factor='left' (control): {elapsed_left:6.3f}s"
    )

Empirical Observations

On NLTK versions $\le 3.10.3$, empirical timing confirms super-linear quadratic scaling on the default branch compared to linear scaling on the control branch:

• $N = 80,000$ (~400 KB): factor='right' takes 1.972s; factor='left' takes 1.399s.
• $N = 160,000$ (~800 KB): factor='right' takes 5.004s ($2.54\times$ increase); factor='left' takes 2.731s ($1.95\times$ linear increase).
• $N = 320,000$ (~1.6 MB): factor='right' takes 14.518s ($2.90\times$ increase); factor='left' takes 5.379s ($1.97\times$ linear increase).

Furthermore, on vulnerable versions, even a much smaller payload of $N = 1,500$ (~7.5 KB) completes the chomsky_normal_form() transformation in milliseconds but yields a tree of depth 1,500. When the application attempts to serialize the result via str(tree) or extract rules via tree.productions(), CPython immediately raises RecursionError: maximum recursion depth exceeded, terminating the request handler if uncaught.

The primary security impact of CVE-2026-126298 is a high-severity loss of service availability. There is no direct impact on system confidentiality or data integrity, as the vulnerability does not permit memory corruption, arbitrary code execution, or unauthorized data disclosure.

In Python web services and API backends (such as those built on Gunicorn, uWSGI, Flask, Django, or FastAPI), request handling is constrained by the Global Interpreter Lock (GIL) within each worker process. Because list.pop(0) executes tight memmove() loops inside the CPython runtime while holding the GIL, a single malicious request processing a 1.5 MB to 5 MB tree payload monopolizes an entire Python worker process for tens of seconds to several minutes. Concurrent requests sent by an attacker can saturate all available worker processes or threads, causing health check failures, gateway timeouts, and complete denial of service for legitimate users.

CVSS v3.1 and v4.0 Breakdown

NVD and the GitHub Security Advisory score this vulnerability at CVSS v3.1 7.5 (High) (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H). The assigning CNA (VulnCheck) evaluated the flaw under CVSS v4.0 at 8.7 (High) (CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N). Both vectors reflect that the attack can be delivered over the network (AV:N) with low complexity (AC:L), zero attack requirements (AT:N), no privileges (PR:N), and no user interaction (UI:N), resulting in a high impact to the vulnerable system's availability (A:H / VA:H).

Threat Intelligence Context

According to FIRST.org Exploit Prediction Scoring System (EPSS) data, CVE-2026-126298 holds an EPSS score of 0.00582 (0.582%), placing it in the 48.34th percentile. The vulnerability is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog, and there is no evidence of active exploitation in ransomware campaigns. Real-world exploitability depends strictly on whether a downstream application exposes NLTK tree parsing and CNF normalization to untrusted external inputs.

The definitive remediation for CVE-2026-126298 is to upgrade the nltk package to version 3.10.4 or later. Version 3.10.4 replaces the quadratic list manipulation with $O(1)$ deque.popleft() operations and enforces pre-transformation depth boundaries.

pip install --upgrade "nltk>=3.10.4"

> [!NOTE] > Upgrading to NLTK 3.10.4 introduces a behavioral change for applications that previously binarized wide trees resulting in depths exceeding nltk.tree.tree.MAX_TREE_DEPTH (default 500). In 3.10.4, chomsky_normal_form() will raise a ValueError upfront if the post-binarization depth exceeds MAX_TREE_DEPTH. Applications that legitimately process trusted wide trees and manage Python's recursion limit (sys.setrecursionlimit()) must explicitly raise nltk.tree.tree.MAX_TREE_DEPTH to match.

Workarounds for Unpatched Environments

If an immediate upgrade to nltk>=3.10.4 cannot be deployed, engineering teams can apply the following application-level mitigations:

1. Enforce Node Width Limits Prior to Binarization: Inspect parsed Tree objects and reject any structure where the number of children on a single node—or the cumulative binarized depth—exceeds a safe threshold before calling chomsky_normal_form():

from nltk.tree import Tree
 
MAX_NODE_WIDTH = 100
 
def safe_cnf_transform(tree_str: str) -> Tree:
    # Enforce input payload byte length limit first
    if len(tree_str) > 100_000:
        raise ValueError("Input tree string exceeds maximum allowed length.")
        
    tree = Tree.fromstring(tree_str)
    for subtree in tree.subtrees():
        if len(subtree) > MAX_NODE_WIDTH:
            raise ValueError(
                f"Node width {len(subtree)} exceeds safety limit of {MAX_NODE_WIDTH}."
            )
    tree.chomsky_normal_form()
    return tree

2. Use Left Factoring (Partial Mitigation): If downstream grammar algorithms do not strictly require right-branching CNF trees, calling tree.chomsky_normal_form(factor="left") avoids the $O(N^2)$ list.pop(0) loop by using $O(1)$ list.pop(). However, note that left factoring still turns node width into tree depth and remains susceptible to RecursionError on unpatched versions unless combined with the node width validation check shown above.

3. Enforce Worker Timeouts and Input Size Quotas: Configure reverse proxies (such as Nginx or Envoy) to restrict request body sizes on NLP endpoints, and run tree transformation tasks inside isolated worker processes with strict wall-clock execution timeouts.