{"id":"CVE-2026-12876","aliases":["DEBIAN-CVE-2026-12876","GHSA-ff5c-cp5c-9wjf","PYSEC-2026-3869","UBUNTU-CVE-2026-12876"],"status":"published","title":"NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars","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.\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 -\u003e unbounded recursion\ng = CFG.fromstring(\"S -\u003e S S | 'a'\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n\n# (b) ambiguous grammar -\u003e exponential number of parses\ng = CFG.fromstring(\"S -\u003e '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.","severity":{"version":"4.0","score":6.9,"vector":"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","level":"medium","from":"ghsa"},"facts":{"in_kev":false,"known_exploited":false,"public_exploit":false,"fix_available":true},"cwes":["CWE-407","CWE-674"],"published":"2026-08-14T00:00:00Z","modified":"2026-10-17T12:58:05Z","fixes":[{"ecosystem":"PyPI","package":"nltk","fixed_in":["3.10.3"],"sources":["ghsa","osv"]}],"affected":[{"source":"ghsa","ecosystem":"PyPI","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"last_affected":"3.10.2"},{"fixed":"3.10.3"}]}]},{"source":"osv","ecosystem":"Debian:12","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.10.0-1","3.10.1-1","3.10.3-1","3.8-1","3.8.1-1","3.9.1-1","3.9.1-2","3.9.2-1","3.9.3-1"]},{"source":"osv","ecosystem":"Debian:13","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.10.0-1","3.10.1-1","3.10.3-1","3.9.1-2","3.9.2-1","3.9.3-1"]},{"source":"osv","ecosystem":"Debian:14","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.10.0-1","3.10.1-1","3.10.3-1","3.9.1-2","3.9.2-1","3.9.3-1"]},{"source":"osv","ecosystem":"PyPI","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.3"}]}],"versions":["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","2.0.1","2.0.1rc1","2.0.1rc2-git","2.0.1rc3","2.0.1rc4","2.0.2","2.0.3","2.0.4","2.0.5","2.0b4","2.0b5","2.0b6","2.0b7","2.0b8","2.0b9","3.0.0","3.0.0b1","3.0.0b2","3.0.1","3.0.2","3.0.3","3.0.4","3.0.5","3.1","3.10.0","3.10.1","3.10.2","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.5","3.5b1","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.9","3.9.1","3.9.2","3.9.3","3.9.4","3.9b1"]},{"source":"osv","ecosystem":"PyPI","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.3"}]}],"versions":["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","2.0.1","2.0.1rc1","2.0.1rc2-git","2.0.1rc3","2.0.1rc4","2.0.2","2.0.3","2.0.4","2.0.5","2.0b4","2.0b5","2.0b6","2.0b7","2.0b8","2.0b9","3.0.0","3.0.0b1","3.0.0b2","3.0.1","3.0.2","3.0.3","3.0.4","3.0.5","3.1","3.10.0","3.10.1","3.10.2","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.5","3.5b1","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.9","3.9.1","3.9.2","3.9.3","3.9.4","3.9b1"]},{"source":"osv","ecosystem":"Ubuntu:Pro:14.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["2.0~b9-0ubuntu4","2.0~b9-0ubuntu4.1~esm2","2.0~b9-0ubuntu4.1~esm4","2.0~b9-0ubuntu4.1~esm5","2.0~b9-0ubuntu4.1~esm6"]},{"source":"osv","ecosystem":"Ubuntu:Pro:16.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.0.4-1","3.0.5-1","3.1-1","3.1-1ubuntu0.1","3.1-1ubuntu0.1+esm1","3.1-1ubuntu0.1+esm2","3.1-1ubuntu0.1+esm3","3.1-1ubuntu0.1+esm4"]},{"source":"osv","ecosystem":"Ubuntu:Pro:18.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.2.4-1","3.2.5-1","3.2.5-1ubuntu0.1","3.2.5-1ubuntu0.1+esm1","3.2.5-1ubuntu0.1+esm2","3.2.5-1ubuntu0.1+esm3","3.2.5-1ubuntu0.1+esm4"]},{"source":"osv","ecosystem":"Ubuntu:Pro:20.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.4.5-1","3.4.5-2","3.4.5-2ubuntu0.1~esm1","3.4.5-2ubuntu0.1~esm2","3.4.5-2ubuntu0.1~esm3","3.4.5-2ubuntu0.1~esm4"]},{"source":"osv","ecosystem":"Ubuntu:Pro:22.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.5-1","3.6.5-1","3.6.7-1","3.7-1","3.7-1ubuntu0.1~esm1","3.7-1ubuntu0.1~esm2"]},{"source":"osv","ecosystem":"Ubuntu:Pro:24.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.8.1-1","3.8.1-1ubuntu0.1~esm1","3.8.1-1ubuntu0.1~esm2"]},{"source":"osv","ecosystem":"Ubuntu:26.10","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.9.2-1","3.9.3-1","3.10.0-1","3.10.1-1","3.10.3-1"]},{"source":"osv","ecosystem":"Ubuntu:Pro:26.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.9.1-2","3.9.1-2build1","3.9.2-1","3.9.2-1ubuntu0.1~esm1","3.9.2-1ubuntu0.1~esm2"]}],"references":[{"url":"https://github.com/nltk/nltk/security/advisories/GHSA-ff5c-cp5c-9wjf","tags":["web","report"]},{"url":"https://github.com/nltk/nltk/pull/3649","tags":["web"]},{"url":"https://github.com/nltk/nltk/commit/43aaca1b9024138421c97f970bf13ee19ac8129d","tags":["web"]},{"url":"https://github.com/nltk/nltk/releases/tag/v3.10.3","tags":["web"]},{"url":"https://github.com/advisories/GHSA-ff5c-cp5c-9wjf","tags":["advisory"]},{"url":"https://security-tracker.debian.org/tracker/CVE-2026-12876","tags":["advisory"]},{"url":"https://github.com/nltk/nltk","tags":["package"]},{"url":"https://pypi.org/project/nltk","tags":["package"]},{"url":"https://nvd.nist.gov/vuln/detail/CVE-2026-12876","tags":["advisory"]},{"url":"https://ubuntu.com/security/CVE-2026-12876","tags":["report"]},{"url":"https://www.cve.org/CVERecord?id=CVE-2026-12876","tags":["report"]}],"sources":{"ghsa":[{"id":"GHSA-ff5c-cp5c-9wjf","title":"NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars","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.\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 -\u003e unbounded recursion\ng = CFG.fromstring(\"S -\u003e S S | 'a'\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n\n# (b) ambiguous grammar -\u003e exponential number of parses\ng = CFG.fromstring(\"S -\u003e '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.","status":"published","published":"2026-09-02T14:33:38Z","modified":"2026-09-02T14:33:39Z","cvss":[{"version":"4.0","score":6.9,"vector":"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","level":"medium"}],"cwes":["CWE-407","CWE-674"],"updated_at":"2026-11-02T14:41:10.121131Z"}],"osv":[{"id":"GHSA-ff5c-cp5c-9wjf","title":"NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars","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.\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 -\u003e unbounded recursion\ng = CFG.fromstring(\"S -\u003e S S | 'a'\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n\n# (b) ambiguous grammar -\u003e exponential number of parses\ng = CFG.fromstring(\"S -\u003e '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.","status":"published","published":"2026-09-02T14:33:38Z","modified":"2026-09-10T12:25:59.67226195Z","cvss":[{"version":"4.0","score":6.9,"vector":"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","level":"medium"}],"cwes":["CWE-407","CWE-674"],"updated_at":"2026-11-02T15:46:46.39441Z"},{"id":"PYSEC-2026-3869","title":"NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars","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.\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 -\u003e unbounded recursion\ng = CFG.fromstring(\"S -\u003e S S | 'a'\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24))   # hangs\n\n# (b) ambiguous grammar -\u003e exponential number of parses\ng = CFG.fromstring(\"S -\u003e '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.","status":"published","published":"2026-09-10T09:44:59.291918Z","modified":"2026-09-10T12:15:10.248081657Z","cvss":[{"version":"4.0","score":6.9,"vector":"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","level":"medium"}],"updated_at":"2026-11-02T15:52:57.255153Z"},{"id":"DEBIAN-CVE-2026-12876","status":"published","published":"2026-08-14T14:47:39.722036028Z","modified":"2026-09-01T15:05:52.986961574Z","updated_at":"2026-11-02T15:45:51.374409Z"},{"id":"UBUNTU-CVE-2026-12876","description":"[Unknown description]","status":"published","published":"2026-08-14T00:00:00Z","modified":"2026-10-17T12:58:05.123379474Z","updated_at":"2026-11-02T16:56:00.592716Z"}]}}