NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
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.
What the EG score is made of (scorer v4.0: the three questions the 0–10 score mixes, published apart · methodology)
- EG Severity
- Not assessed: no CVSS publishedA missing CVSS is not a severity of zero.
- EG Likelihood
- Unknown (no EPSS on record)Unknown, not low: FIRST has published no EPSS probability for this CVE.
- Confirmed exploitation
- None on record (CISA KEV, EG-KEV Tier 1)Reported apart from the likelihood: an observed fact, not a probability.
- EG Priority
- No SSVC decision: EchelonGraph has not assessed this CVECISA BOD 26-04: 14 days if the affected system is publicly exposed; Fix on system upgrade if it is not.Each input and its source, and whom BOD 26-04 binds: the BOD 26-04 block below.
BOD 26-04 (CISA's remediation timeline, Table 1)14 days if the affected system is publicly exposed; Fix on system upgrade if it is not.
The score's inputs: In CISA KEV no (CISA's KEV catalog) · Automatable no (CISA's BOD 26-04 default) · Technical impact total (CISA's BOD 26-04 default). Where an input reads “CISA's BOD 26-04 default”, no one has published it for this CVE, and CISA's implementation guidance says: “If “Automatable” and “Technical Impact” information items about a CVE ID are not available and the CVE ID is not in the KEV Catalog, CISA will treat its values as “no” and “total,” respectively, until CISA or a third party provides metadata about the CVE ID. CISA will always provide the Vulnrichment data for a CVE ID listed in the KEV Catalog.” Whether your system is publicly exposed is yours to answer. BOD 26-04 binds US Federal Civilian Executive Branch agencies; for anyone else it is CISA's published timeline, a reference rather than an obligation. The directive · how EchelonGraph applies it