Skip to content

CVE-2026-12876 NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars

MediumCVSS 6.9
Published
Updated
Exploit status
No public exploit known

Description

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.

Affected products

ProductAffected versionsFixed in
pypi nltk(PyPI) < 3.10.3 3.10.3
pypi nltk(PyPI) = 0.8 No fix listed
pypi nltk(PyPI) = 0.9 No fix listed
pypi nltk(PyPI) = 0.9.3 No fix listed
pypi nltk(PyPI) = 0.9.4 No fix listed
pypi nltk(PyPI) = 0.9.5 No fix listed
pypi nltk(PyPI) = 0.9.6 No fix listed
pypi nltk(PyPI) = 0.9.7 No fix listed
pypi nltk(PyPI) = 0.9.8 No fix listed
pypi nltk(PyPI) = 0.9.9 No fix listed
pypi nltk(PyPI) = 2.0.1 No fix listed
pypi nltk(PyPI) = 2.0.1rc1 No fix listed
pypi nltk(PyPI) = 2.0.1rc2-git No fix listed
pypi nltk(PyPI) = 2.0.1rc3 No fix listed
pypi nltk(PyPI) = 2.0.1rc4 No fix listed
pypi nltk(PyPI) = 2.0.2 No fix listed
pypi nltk(PyPI) = 2.0.3 No fix listed
pypi nltk(PyPI) = 2.0.4 No fix listed
pypi nltk(PyPI) = 2.0.5 No fix listed
pypi nltk(PyPI) = 2.0b4 No fix listed
pypi nltk(PyPI) = 2.0b5 No fix listed
pypi nltk(PyPI) = 2.0b6 No fix listed
pypi nltk(PyPI) = 2.0b7 No fix listed
pypi nltk(PyPI) = 2.0b8 No fix listed
pypi nltk(PyPI) = 2.0b9 No fix listed
Show 73 more
ProductAffected versionsFixed in
pypi nltk(PyPI) = 3.0.0 No fix listed
pypi nltk(PyPI) = 3.0.0b1 No fix listed
pypi nltk(PyPI) = 3.0.0b2 No fix listed
pypi nltk(PyPI) = 3.0.1 No fix listed
pypi nltk(PyPI) = 3.0.2 No fix listed
pypi nltk(PyPI) = 3.0.3 No fix listed
pypi nltk(PyPI) = 3.0.4 No fix listed
pypi nltk(PyPI) = 3.0.5 No fix listed
pypi nltk(PyPI) = 3.1 No fix listed
pypi nltk(PyPI) = 3.10.0 No fix listed
pypi nltk(PyPI) = 3.10.1 No fix listed
pypi nltk(PyPI) = 3.10.2 No fix listed
pypi nltk(PyPI) = 3.2 No fix listed
pypi nltk(PyPI) = 3.2.1 No fix listed
pypi nltk(PyPI) = 3.2.2 No fix listed
pypi nltk(PyPI) = 3.2.3 No fix listed
pypi nltk(PyPI) = 3.2.4 No fix listed
pypi nltk(PyPI) = 3.2.5 No fix listed
pypi nltk(PyPI) = 3.3 No fix listed
pypi nltk(PyPI) = 3.4 No fix listed
pypi nltk(PyPI) = 3.4.1 No fix listed
pypi nltk(PyPI) = 3.4.2 No fix listed
pypi nltk(PyPI) = 3.4.3 No fix listed
pypi nltk(PyPI) = 3.4.4 No fix listed
pypi nltk(PyPI) = 3.4.5 No fix listed
pypi nltk(PyPI) = 3.5 No fix listed
pypi nltk(PyPI) = 3.5b1 No fix listed
pypi nltk(PyPI) = 3.6 No fix listed
pypi nltk(PyPI) = 3.6.1 No fix listed
pypi nltk(PyPI) = 3.6.2 No fix listed
pypi nltk(PyPI) = 3.6.3 No fix listed
pypi nltk(PyPI) = 3.6.4 No fix listed
pypi nltk(PyPI) = 3.6.5 No fix listed
pypi nltk(PyPI) = 3.6.6 No fix listed
pypi nltk(PyPI) = 3.6.7 No fix listed
pypi nltk(PyPI) = 3.7 No fix listed
pypi nltk(PyPI) = 3.8 No fix listed
pypi nltk(PyPI) = 3.8.1 No fix listed
pypi nltk(PyPI) = 3.9 No fix listed
pypi nltk(PyPI) = 3.9.1 No fix listed
pypi nltk(PyPI) = 3.9.2 No fix listed
pypi nltk(PyPI) = 3.9.3 No fix listed
pypi nltk(PyPI) = 3.9.4 No fix listed
pypi nltk(PyPI) = 3.9b1 No fix listed
pypi nltk(PyPI) <= 3.10.2 No fix listed
debian/nltk(Debian:12) All versions No fix listed
debian/nltk(Debian:12) = 3.10.0-1 No fix listed
debian/nltk(Debian:12) = 3.10.1-1 No fix listed
debian/nltk(Debian:12) = 3.10.3-1 No fix listed
debian/nltk(Debian:12) = 3.8-1 No fix listed
debian/nltk(Debian:12) = 3.8.1-1 No fix listed
debian/nltk(Debian:12) = 3.9.1-1 No fix listed
debian/nltk(Debian:12) = 3.9.1-2 No fix listed
debian/nltk(Debian:12) = 3.9.2-1 No fix listed
debian/nltk(Debian:12) = 3.9.3-1 No fix listed
debian/nltk(Debian:13) All versions No fix listed
debian/nltk(Debian:13) = 3.10.0-1 No fix listed
debian/nltk(Debian:13) = 3.10.1-1 No fix listed
debian/nltk(Debian:13) = 3.10.3-1 No fix listed
debian/nltk(Debian:13) = 3.9.1-2 No fix listed
debian/nltk(Debian:13) = 3.9.2-1 No fix listed
debian/nltk(Debian:13) = 3.9.3-1 No fix listed
debian/nltk(Debian:14) All versions No fix listed
debian/nltk(Debian:14) = 3.10.0-1 No fix listed
debian/nltk(Debian:14) = 3.10.1-1 No fix listed
debian/nltk(Debian:14) = 3.10.3-1 No fix listed
debian/nltk(Debian:14) = 3.9.1-2 No fix listed
debian/nltk(Debian:14) = 3.9.2-1 No fix listed
debian/nltk(Debian:14) = 3.9.3-1 No fix listed
ubuntu/nltk(Ubuntu:22.04) All versions No fix listed
ubuntu/nltk(Ubuntu:24.04) All versions No fix listed
ubuntu/nltk(Ubuntu:26.04) All versions No fix listed
ubuntu/nltk(Ubuntu:26.10) All versions No fix listed

References