High

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

  • Disclosed: 14.11.2026
  • Updated: 15.11.2026 10:00

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.
python
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).

What to do

Upgrade NLTK to version 3.10.4 or higher. The issue is addressed by commits 457ebe349 and 677857dca in PR #3909 (merge commit 2f53e20ce on develop) and follow-up PR #3917.

As a workaround, cap the accepted tree width and run the normalization under a CPU or execution time limit in an isolated worker process.

Affected software

Click a technology to see all vulnerabilities affecting it.

PlatformPackageVulnerable versionsFixed in
Python (PyPI) nltk < 3.10.4 3.10.4

References

CVSS score 7.5/10
CVSS vector
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Weakness (CWE)
CWE-400, CWE-407
Platform
Python (PyPI)
Package
nltk
Disclosed
14.11.2026
Updated
15.11.2026 10:00

Sources and licenses · Edited or translated by DockRay; source rights and applicable licenses are retained.

OSV / GitHub Advisory Database - GHSA-r53h-rw34-8h97 - CC BY 4.0

Vulnerability history: nltk

All published vulnerabilities of this package (Python (PyPI)), newest first. Shows whether this is a one-off slip or a package that needs watching.

All (79) in the archive
Total entries
79
First → latest
08.2019 11.2026
Without a fix
5
Exploited in attacks
0

Severity breakdown

  • Critical 5
  • High 41
  • Medium 31
  • Low 2

Disclosures per year

  1. 2019: 1
  2. 2020: 0
  3. 2021: 2
  4. 2022: 1
  5. 2023: 0
  6. 2024: 1
  7. 2025: 0
  8. 2026: 74
Severity:
  1. NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0) this entry
    High · 7.5 CVE-2026-126298 < 3.10.4 3.10.4
  2. High CVE-2026-79674 < 3.10.3 3.10.3
  3. High · 8.8 CVE-2026-71513 >= 3.10.0, < 3.10.3 3.10.3
  4. High · 5.9 CVE-2026-62385 < 3.10.0 3.10.0
  5. High · 7.5 CVE-2026-33231 < 3.9.4 3.9.4
  6. High · 8.6 CVE-2026-0847 < 3.9.3 3.9.3
  7. Critical · 10.0 CVE-2025-14009 < 3.9.3 3.9.3
  8. High · 7.5 CVE-2024-39705 < 3.9 3.9
  9. High · 7.5 CVE-2021-3842 < 3.6.6 3.6.6
  10. High · 7.5 CVE-2021-3828 < 3.6.4 3.6.4
  11. High · 7.5 CVE-2019-14751 < 3.4.5 3.4.5

Know which vulnerabilities affect your application

With the DockRay integration and software inventory enabled, DockRay checks reported component versions against known vulnerabilities and notifies you about confirmed matches. Coverage depends on the supported technology and available advisory data.

Connect your application
DockRay newsletter

Application security in your inbox

Important vulnerabilities, actionable guidance and practical advice for your applications. Choose your technologies and follow what matters to your project.

  • A daily digest of new vulnerabilities, critical ones included.
  • Notifications about important updates.
  • Practical advice on application security and monitoring.

Leave empty to receive updates for every technology.

Free to subscribe. Unsubscribe with one click in any email.