{"id":"CVE-2026-12876","aliases":["GHSA-ff5c-cp5c-9wjf","PYSEC-2026-3869"],"title":"NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars","summary":"NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars","severity":"medium","vendor":"nltk","product":"nltk","ecosystem":"pip","affected":["nltk < 3.10.3"],"patched":["nltk 3.10.3"],"published":"2026-09-02","updated":"2026-09-10","sourceUpdated":"2026-09-10T12:25:59.672261950Z","source":"OSV","sourceUrl":"https://osv.dev/vulnerability/GHSA-ff5c-cp5c-9wjf","references":[{"url":"https://github.com/nltk/nltk/security/advisories/GHSA-ff5c-cp5c-9wjf"},{"url":"https://github.com/nltk/nltk/pull/3649"},{"url":"https://github.com/nltk/nltk/commit/43aaca1b9024138421c97f970bf13ee19ac8129d"},{"url":"https://github.com/nltk/nltk"},{"url":"https://github.com/nltk/nltk/releases/tag/v3.10.3"},{"url":"https://pypi.org/project/nltk"},{"url":"https://github.com/advisories/GHSA-ff5c-cp5c-9wjf"},{"url":"https://nvd.nist.gov/vuln/detail/CVE-2026-12876"}],"tags":["osv","pip","ghsa"],"cwe":["CWE-407","CWE-674"],"ingestedAt":"2026-09-02T14:45:30.389Z","slug":"CVE-2026-12876","body":"## Overview\n\n`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.\n\n## Proof of concept\n\nBoth of the following hang on a 24-token input (killed after 8s; growth is super-linear in input length), on NLTK develop:\n\n```python\nfrom nltk import CFG\nfrom nltk.parse import RecursiveDescentParser\n\n# (a) left recursion -> unbounded recursion\ng = CFG.fromstring(\"S -> S S | 'a'\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n\n# (b) ambiguous grammar -> exponential number of parses\ng = CFG.fromstring(\"S -> 'a' S | 'a' S S | 'a'\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n```\n\n## Impact\n\nAn 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.\n\n## Sibling\n\nThe RegexpTokenizer ReDoS reported alongside this (CVE-2026-12875) is a different class (caller-supplied regex) and is addressed under GHSA-w3v8-gmh9-3wv7.\n\n## Affected packages\n\n- `nltk < 3.10.3`\n\n## Remediation\n\nUpgrade to a patched release:\n\n- `nltk 3.10.3`","depth":"sunlit","depthScore":28,"depthScoreParts":{"impact":27.5,"likelihood":0,"exploitation":0,"ransomware":0},"changes":[]}