NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
Published 2 Sept 2026 · Updated 10 Sept 2026
Is your project on an affected nltk?
Look after several Python apps? Indie watches up to 15 repos, private ones too, for $5 a month. See Indie
Affected package
- Affected
- <3.10.3
- Fixed in
- 3.10.3
pip install 'nltk>=3.10.3'Details
nltk.parse.RecursiveDescentParser (and SteppingRecursiveDescentParser) enumerate parses top-down with no bound on the number of recursive steps. A small, crafted context-free grammar makes a short input consume unbounded CPU (and/or exhaust the Python recursion stack), pinning a process indefinitely — a denial of service.
Proof of concept
Both of the following hang on a 24-token input (killed after 8s; growth is super-linear in input length), on NLTK develop:
from nltk import CFG
from nltk.parse import RecursiveDescentParser
# (a) left recursion -> unbounded recursion
g = CFG.fromstring("S -> S S | 'a'")
list(RecursiveDescentParser(g).parse(["a"] * 24)) # hangs
# (b) ambiguous grammar -> exponential number of parses
g = CFG.fromstring("S -> 'a' S | 'a' S S | 'a'")
list(RecursiveDescentParser(g).parse(["a"] * 24)) # hangsImpact
An application that runs RecursiveDescentParser on a grammar (or an input) drawn from an untrusted source can be driven into an unbounded CPU / stack-exhaustion loop by a tiny payload. No confidentiality or integrity impact; single-process availability only.
Sibling
The RegexpTokenizer ReDoS reported alongside this (CVE-2026-12875) is a different class (caller-supplied regex) and is addressed under GHSA-w3v8-gmh9-3wv7.
Is GHSA-ff5c-cp5c-9wjf in any of your client repos?
Checking one package by hand is fine. Checking it across forty client projects is not. NPMscan reads the lockfiles in every GitHub repo you pick, finds each project with an affected nltk, and gives you the command that fixes it.
More advisories for nltk
- HighCVE-2026-128134NLTK dot2img runs Graphviz 'dot' without the trusted-exec chokepoint, enabling local code execution via a writable PATH element · 16 Nov 2026
- MediumCVE-2026-126302NLTK: Symlink escape in chat80.sql_query bypasses the pathsec data-root sandbox to read out-of-root SQLite databases · 16 Nov 2026
- MediumCVE-2026-126296NLTK: Path Traversal in save_maxent_params / load_maxent_params Allow Arbitrary File READ/WRITE · 16 Nov 2026
- HighCVE-2026-126299NLTK: Quadratic-time CPU denial of service in CCG lexicon parser (fromstring) on wide bracket bodies and operator chains · 14 Nov 2026
- HighCVE-2026-126298NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0) · 14 Nov 2026
- HighCVE-2026-126297NLTK: Quadratic-time CPU denial of service in ConllCorpusReader SRL instance builder via nested span rescan · 14 Nov 2026
References
Advisory data from OSV.dev (opens OSV.dev in a new tab), refreshed daily.