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-22549716
  • published14 Nov 2026
  • disclosed14 Nov 2026
  • creditzx

Introduced: 14 Nov 2026

NewCVE-2026-126297  (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 ConllCorpusReader._get_srl_instances in nltk/corpus/reader/conll.py. For a sentence block with P predicates and P span columns, the function rescans every span column and every span within it once per predicate while searching for each predicate's head span, giving O(P^2 * R) work. An attacker who supplies a CoNLL SRL corpus with the sole V head span placed in the last column defeats the inner break short-circuit, forcing a full traversal of all earlier columns for every predicate. An application that reads attacker-supplied CoNLL SRL data and iterates srl_instances() can be driven into tens of seconds of single-threaded CPU consumption per roughly 1 MB corpus, scaling super-linearly with attacker-chosen predicate and column counts.

Note: This is only exploitable when the application calls srl_instances() on a ConllCorpusReader configured with words, pos, tree, and srl columns and processes attacker-supplied CoNLL data.

PoC

Environment: nltk 3.10.3, CPython. Stage a crafted CoNLL corpus under an authorized data root and iterate srl_instances().
Corpus construction: one blank-line-delimited block with P predicate rows and P SRL span columns, the sole "V" head span in the last column.
import time, os, tempfile
from nltk.corpus.reader.conll import ConllCorpusReader

def build_block(n):
    # n predicates, n SRL columns; the single V head placed in the last column
    # (columns: words pos tree srl...): emit n predicate rows and n SRL span
    # columns, with the single "V" head span placed in the final column.
    ...

for n in (40, 80, 160, 320):
    root = tempfile.mkdtemp()
    open(os.path.join(root, "c.conll"), "w").write(build_block(n))
    r = ConllCorpusReader(root, ["c.conll"], ("words", "pos", "tree", "srl"))
    t = time.perf_counter()
    list(r.srl_instances())
    print(n, round(time.perf_counter() - t, 3), "s")
Negative control (single predicate): n=40 -> 1.88 ms ; n=320 -> 4.45 ms      (flat)
Attack (P=R=n):  n=40 -> 0.022s (10 KB) | n=80 -> 0.148s (39 KB) | n=160 -> 1.164s (156 KB) | n=320 -> 10.002s (619 KB)

The attack timing rises about 8x per doubling of n while the file grows only about 4x, confirming super-linear cost driven by attacker-chosen predicate and column count; the single-predicate control stays in the millisecond range.

Note: The PoC states it runs on nltk 3.10.3 and CPython, staging a crafted CoNLL corpus under an authorized data root and iterating srl_instances().

CVSS Base Scores

version 4.0
version 3.1