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

Vulnerability ID: CVE-2026-126298
CVSS Score: 7.5
Published: 2026-11-14

CVE-2026-126298 (also tracked as GHSA-r53h-rw34-8h97) is an algorithmic complexity Denial of Service (DoS) vulnerability in the Natural Language Toolkit (NLTK) Python library affecting all versions prior to 3.10.4. The vulnerability resides in the nltk.tree.transforms.chomsky_normal_form function and its corresponding public method Tree.chomsky_normal_form(). When transforming a parse tree into Chomsky Normal Form using the default right-factoring strategy, the function repeatedly invokes list.pop(0) inside a loop iterating over all children of a node. In CPython, removing the initial element of a standard list requires an O(N) memory shift operation, causing the overall binarization algorithm to degrade to O(N^2) quadratic time complexity relative to the width of a node. Furthermore, converting horizontal node width into vertical tree depth bypasses initial parsing depth bounds, triggering subsequent stack exhaustion (RecursionError) when recursive methods traverse the mutated structure. Unauthenticated remote attackers who can submit bracketed tree strings to applications invoking this transformation can exhaust single-threaded CPU resources or induce unhandled application exceptions.

TL;DR

An O(N^2) algorithmic complexity flaw in NLTK's Tree.chomsky_normal_form() function allows remote attackers to trigger CPU exhaustion and RecursionError crashes by supplying wide, flat syntax trees. Fixed in NLTK 3.10.4 via deque-based O(1) element extraction and pre-transformation depth validation.

⚠️ Exploit Status: POC

Technical Details

• Vulnerability Class: CWE-407 (Inefficient Algorithmic Complexity) / CWE-400 (Uncontrolled Resource Consumption)
• CVSS v3.1 / v4.0: 7.5 High (v3.1) / 8.7 High (v4.0)
• Attack Vector: Network (Unauthenticated untrusted syntax tree strings)
• Affected Component: nltk.tree.transforms.chomsky_normal_form / Tree.chomsky_normal_form()
• Security Impact: Denial of Service via O(N^2) CPU exhaustion and CWE-674 RecursionError
• EPSS Score: 0.582% (48.34th Percentile)
• Exploit Status: Public Proof-of-Concept Available
• Patched Version: nltk >= 3.10.4

Affected Systems

• Natural Language Toolkit (NLTK) Python package (PyPI: nltk)
• nltk: <= 3.10.3 (Fixed in: 3.10.4)

Code Analysis

Commit: 457ebe3

Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)

@@ -107,6 +107,8 @@

 """

+from collections import deque
+
 from nltk.tree.tree import Tree


@@ -149,7 +151,10 @@ def chomsky_normal_form(
                     str(child.label()) if isinstance(child, Tree) else str(child)
                     for child in node
                 ]
-                nodeCopy = node.copy()
+                # 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:] = []  # delete the children

                 curNode = node
@@ -165,7 +170,7 @@ def chomsky_normal_form(
                             parentString,
                         )  # create new head
                         newNode = Tree(newHead, [])
-                        curNode[0:] = [nodeCopy.pop(0), newNode]
+                        curNode[0:] = [nodeCopy.popleft(), newNode]
                     else:
                         newHead = "{}{}<{}>{}".format(
                             originalNode,

Commit: 677857d

Refuse binarisation that would nest a tree beyond MAX_TREE_DEPTH

+def _binarised_depth(tree, factor):
+    """Nesting depth *tree* will have after binarisation, computed iteratively.
+
+    Binarising a node with n > 2 children hangs them off a chain of n - 2 new
+    nodes, so the transform turns WIDTH into DEPTH: a flat 3000-child node
+    becomes a 3000-deep spine, and the widths of nested nodes compound. The
+    depth is counted exactly as ``Tree.fromstring`` counts bracket nesting
+    (Tree levels on the deepest root-to-leaf path), with the child positions
+    the right- or left-factoring loop will produce.
+    """
+    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)
+
+
 def chomsky_normal_form(
     tree, factor="right", horzMarkov=None, vertMarkov=0, childChar="|", parentChar="^"
 ):
@@ -123,6 +158,19 @@ def chomsky_normal_form(
     if horzMarkov is None:
         horzMarkov = 999

+    # The recursive Tree methods (__str__, leaves, productions, deepcopy ...)
+    # rely on Tree.fromstring's MAX_TREE_DEPTH bound, which binarisation would
+    # silently break by turning width into depth (CWE-674); refuse up front,
+    # before the tree is mutated, on the exact post-transform 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."
+        )

Exploit Details

• GitHub Security Advisory: Official advisory containing benchmark PoC script demonstrating quadratic CPU exhaustion via wide flat trees passed to Tree.chomsky_normal_form().

Mitigation Strategies

• Upgrade the NLTK library to version 3.10.4 or later to eliminate O(N^2) list shifting and enforce post-binarization depth limits.
• Validate and restrict the maximum number of children per node (horizontal tree width) on all untrusted Tree objects prior to invoking transformation methods.
• Switch to left-factored CNF conversion (factor='left') as a partial workaround to avoid O(N^2) CPU complexity if downstream consumers support left-branching trees.
• Enforce strict payload size limits at the API gateway or web server layer and execute CPU-bound NLP parsing tasks within time-bounded worker processes.

Remediation Steps:

1. Audit project dependencies (requirements.txt, Pipfile.lock, poetry.lock) to identify any installations of nltk <= 3.10.3.
2. Run pip install --upgrade 'nltk>=3.10.4' in all affected environments and rebuild deployment containers.
3. Verify that application exception handlers gracefully catch ValueError exceptions raised by both Tree.fromstring() and Tree.chomsky_normal_form() when depth or width limits are exceeded.
4. If upgrading is temporarily blocked, implement a pre-processing validator iterating over tree.subtrees() to reject any subtree with len(subtree) > 100 before calling chomsky_normal_form().

References

• GitHub Security Advisory GHSA-r53h-rw34-8h97
• VulnCheck Advisory: NLTK before 3.10.4 Quadratic CPU Denial of Service via Tree.chomsky_normal_form
• NVD - CVE-2026-126298
• CVE.org Record: CVE-2026-126298
• NLTK Pull Request #3909
• Fix Commit 457ebe349f8dd8080224f76a64aff806dd437057: Replace list.pop(0) with deque.popleft()
• Guard Commit 677857dcafd84e4591865d976b562a27dfde566e: Refuse binarisation beyond MAX_TREE_DEPTH
• NLTK Release v3.10.4
• NLTK Official GitHub Repository

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