brew-safety-cve-2026-12876
Vulnerability from osv_homebrew
Published
2026-09-03 10:05
Modified
2026-09-10 20:47
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.
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
{
"affected": [
{
"ecosystem_specific": {
"fix": "bump",
"range_state": "fixed",
"resource": "nltk",
"resource_purl": "pkg:pypi/nltk@3.10.3",
"upstream_fixed_in": "3.10.3"
},
"package": {
"ecosystem": "Homebrew",
"name": "safety",
"purl": "pkg:brew/safety"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "3.8.1_2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"database_specific": {
"confidence": "high",
"source": "matched",
"strategy": "registry",
"upstream_evidence": [
{
"ecosystem": "PyPI",
"key": "pkg:pypi/nltk@3.10.3",
"name": "nltk",
"resource": "nltk",
"strategy": "registry",
"subject_version": "3.10.3"
}
]
},
"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": "BREW-safety-CVE-2026-12876",
"modified": "2026-09-10T20:47:06Z",
"published": "2026-09-03T10:05:22Z",
"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"
}
],
"schema_version": "1.7.3",
"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",
"upstream": [
"GHSA-ff5c-cp5c-9wjf",
"CVE-2026-12876",
"PYSEC-2026-3869"
]
}
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…