GCVE Workshop - 22 September 2026 (14:00-18:00), Luxembourg Before The Vulnopticon Conference - Registration

GHSA-FF5C-CP5C-9WJF

Vulnerability from github – Published: 2026-09-02 14:33 – Updated: 2026-09-02 14:33
VLAI
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
6.9 (Medium)
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
Show details on source website
To clipboard 

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 3.10.2"
      },
      "package": {
        "ecosystem": "PyPI",
        "name": "nltk"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "3.10.3"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-12876"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407",
      "CWE-674"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-09-02T14:33:38Z",
    "nvd_published_at": null,
    "severity": "MODERATE"
  },
  "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": "GHSA-ff5c-cp5c-9wjf",
  "modified": "2026-09-02T14:33:39Z",
  "published": "2026-09-02T14:33:38Z",
  "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.4.0",
  "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"
}



Log in or create an account to share your comment.




Tags
Taxonomy of the tags.





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.


Detection rules are retrieved from Rulezet.