MediumGHSA-ff5c-cp5c-9wjfCVE-2026-12876PYSEC-2026-3869

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?

Private repo? Upload its lockfile instead, or connect GitHub to check every repo.

Look after several Python apps? Indie watches up to 15 repos, private ones too, for $5 a month. See Indie

Affected package

nltkPyPI
Affected
<3.10.3
Fixed in
3.10.3
Update to the fixed version for your release line, for example: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))   # hangs

Impact

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
All 64 advisories for nltk

References

Advisory data from OSV.dev (opens OSV.dev in a new tab), refreshed daily.