NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)

Summary

Tree.chomsky_normal_form() binarizes a parse tree and defaults to right factoring. For a node with N children the right-factor branch repeatedly removes the first element of a working list with list.pop(0), which shifts all remaining elements each time, so binarizing one wide node costs O(N^2). An application that converts an attacker-supplied treebank tree to Chomsky Normal Form can be forced into tens of seconds of single-threaded CPU by one wide flat tree. No authentication or user interaction is required.

Root Cause

In the default right-factor branch the transform executes curNode[0:] = [nodeCopy.pop(0), newNode] inside a loop over the N children of a node. list.pop(0) is O(len) because it shifts every remaining element down by one; performed N-2 times over a shrinking length-N list this sums to O(N^2). The left-factor branch instead uses nodeCopy.pop() (removing the last element), which is O(1) and linear overall, so the two branches differ only by this front-versus-back removal. No cap is placed on the child count of a node, and the public Tree.fromstring parser accepts an arbitrarily wide bracketed tree.

Affected function:
- nltk.tree.transforms.chomsky_normal_form (nltk/tree/transforms.py; right-factor sink at line 168, O(1) left control at line 179)
Public entry points: nltk.tree.Tree.chomsky_normal_form (nltk/tree/tree.py:455, default factor="right"); nltk.tree.Tree.fromstring (nltk/tree/tree.py:592).

Impact

An attacker who can influence the tree that an application normalizes to Chomsky Normal Form causes sustained single-threaded CPU consumption (availability loss). The path is network-reachable (AV:N) and needs no privileges or user interaction (PR:N, UI:N). Because the cost grows quadratically with the attacker-chosen child count, roughly 1.5 MB of treebank input costs about 14 seconds on one core and scales as N^2 above that. Confidentiality and integrity are not affected. The NLTK regular-expression wall-clock timeout wraps regex matching only and does not wrap this pure-Python list loop.

Proof of Concept

Environment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree.

import time
from nltk.tree import Tree

for N in (80000, 160000, 320000):
    s = "(S " + "(A a)" * N + ")"
    t = Tree.fromstring(s)
    start = time.perf_counter()
    t.chomsky_normal_form()          # default factor="right"
    print("right", N, round(time.perf_counter() - start, 3), "s")

right (default):  N=80000 1.972s | N=160000 5.004s (2.54x) | N=320000 14.518s (2.90x)   -> super-linear
left  (control):  N=80000 1.399s | N=160000 2.731s (1.95x) | N=320000  5.379s (1.97x)   -> linear

Attack Chain

1. Exposure: An application parses an attacker-influenced treebank string with the public Tree.fromstring and normalizes it with Tree.chomsky_normal_form().
2. Control: The attacker controls the number of children of a node (a wide flat tree such as (S (A a)(A a)...(A a))); no child-count cap exists in fromstring or the transform.
3. Path: Tree.chomsky_normal_form delegates to nltk.tree.transforms.chomsky_normal_form with the default factor="right".
4. Guard: None. There is no width bound on the loop, and the regex match timeout does not wrap this pure-Python list operation.
5. Primitive: curNode[0:] = [nodeCopy.pop(0), newNode] performs an O(N) front shift on each of N iterations.
6. Result: O(N^2) single-core CPU exhaustion; roughly 1.5 MB of input costs about 14 seconds and scales quadratically, blocking the processing thread.

Bypass Evidence

There is no guard to bypass on this path: neither Tree.fromstring nor chomsky_normal_form caps the child count, and the regular-expression wall-clock timeout wraps only regex matching, not this list loop. The finding was confirmed by fresh timing that isolates the cause: the right-factor default and the left-factor branch build the identical bounded head strings and copy the node once, so the only differing term is pop(0) versus pop(). The measured right-versus-left divergence grows with N (right rises toward a 4x per-doubling ratio while left holds near 2x), which proves a quadratic component beyond the shared linear costs. A relevant corroboration is that the inverse transform un_chomsky_normal_form was already rewritten to a single linear pass to remove exactly this quadratic class (see the comment at nltk/tree/transforms.py:195-201), while the forward default path retained the pop(0) idiom. The strongest disproof attempt (that the head-string join dominates and is linear) fails because that join is bounded and present in both branches and therefore cannot explain the branch-dependent quadratic growth.

Affected Versions

• Ecosystem: PyPI (pip)
• Package: nltk
• Confirmed affected range: <= 3.10.3
• Latest release checked: 3.10.3 (PyPI, https://pypi.org/pypi/nltk/json)
• Fix status: 3.10.4

The right-factor pop(0) idiom ships in every release carrying this transform and is present in the current latest published release, 3.10.3. The lower boundary was not bisected, so the introducing version is left open.

Suggested Fix

Rewrite the right-factor binarization to avoid removing from the front of a list: iterate the children with an index cursor or a collections.deque so each step is constant time, mirroring the linear rebuild already applied to un_chomsky_normal_form. As defense in depth, bound the child count accepted for normalization and raise a clear error past a configurable maximum. No configuration-only mitigation removes the exposure for a service that normalizes untrusted trees; until a fix ships, callers should cap accepted tree width and run the transform under a CPU or time budget in an isolated worker.

Reported by zx (GitHub: @manus-pi).

Fix status (2026-09-28)

PR: #3909 "Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)", merged 2026-09-23, merge commit 2f53e20ce on develop.

Fix commits: 457ebe349 (linear front consume in chomsky_normal_form) and 677857dca (refuse a binarisation that would nest a tree beyond MAX_TREE_DEPTH). Follow-up #3917 (merge 9ba132e43, commit f0686dea6) walks Tree equality and conversion with an explicit stack so the deep-tree tests pass on Python 3.10 and 3.11.

Probe: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; verdict on develop 2fa3f48fe: FIXED (chomsky_normal_form scales 5.1x over a 4x input).