CVE-2026-81722: NLTK Denial of Service Vulnerability

{
  "schema_version" : "1.4.0",
  "id" : "GHSA-ww6m-cw3f-q94g",
  "modified" : "2026-09-02T14:36:15Z",
  "published" : "2026-09-02T14:36:15Z",
  "aliases" : [ "CVE-2026-81722" ],
  "summary" : "NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y'",
  "details" : "`nltk.stem.PorterStemmer.stem()` -- a ubiquitous public API applied to arbitrary, often untrusted, tokens -- runs in O(n^2) time on a token containing a long run of the letter 'y', letting a single ~20-50 KB token pin a CPU core (CWE-407).\n\n## Root cause\n\n`_is_consonant(word, i)` was made *iterative* (commit for #3633, GHSA/CWE-674) to fix an earlier unbounded-recursion `RecursionError` on `'y'*10000`. The iterative form walks *backward* over the whole run of 'y's on every call:\n\n```python\nwhile i > 0 and word[i] == 'y':\n    negate = not negate\n    i -= 1\n```\n\n`_measure()` then calls `_is_consonant(stem, i)` once for **every** position `i` of the stem. For a run of n 'y's that is sum_{i} O(i) = O(n^2). The recursion fix therefore traded a CWE-674 RecursionError for a CWE-407 quadratic-time DoS.\n\n## Proof of concept\n\nMeasured (Python 3.13): `stem('y'*5000 + 'ness')` = 2.6s, `stem('y'*10000 + 'ness')` = 11.3s (2x input -> ~4.3x time = quadratic), `stem('y'*20000 + 'ness')` > 20s. A pure run of 'y' with no matching suffix is fast because the stemmer rules that call `_measure` do not fire; a real suffix such as 'ness' triggers `_measure` on the long stem.\n\n```python\nfrom nltk.stem import PorterStemmer\nPorterStemmer().stem('y' * 20000 + 'ness')   # >20s of CPU\n```\n\n## Impact\n\nStemming is routinely applied to untrusted text (search, indexing, NLP pipelines). A single unbroken ~20-50 KB token of 'y' characters (no whitespace, so it survives tokenization) causes multi-second-to-minutes CPU consumption per request. No confidentiality/integrity impact; single-process availability only.\n\n## Fix direction\n\nClassify each character's consonant/vowel status in a single left-to-right O(n) pass (memoise the 'y' run parity) instead of re-walking the run on every `_is_consonant` call, so `_measure` and stemming are linear. This is a sibling of the corpus-reader quadratic advisories GHSA-vp2x-qp44-57v7 and GHSA-8mpw-7fpc-4gqj (CWE-407).",
  "severity" : [ {
    "type" : "CVSS_V4",
    "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"
  } ],
  "affected" : [ {
    "package" : {
      "ecosystem" : "PyPI",
      "name" : "nltk"
    },
    "ranges" : [ {
      "type" : "ECOSYSTEM",
      "events" : [ {
        "introduced" : "0"
      }, {
        "fixed" : "3.10.3"
      } ]
    } ],
    "database_specific" : {
      "last_known_affected_version_range" : "<= 3.10.2"
    }
  } ],
  "references" : [ {
    "type" : "WEB",
    "url" : "https://github.com/nltk/nltk/security/advisories/GHSA-ww6m-cw3f-q94g"
  }, {
    "type" : "ADVISORY",
    "url" : "https://nvd.nist.gov/vuln/detail/CVE-2026-81722"
  }, {
    "type" : "WEB",
    "url" : "https://github.com/nltk/nltk/commit/7808692d451b962711005d954859bb83aabcf8fa"
  }, {
    "type" : "PACKAGE",
    "url" : "https://github.com/nltk/nltk"
  }, {
    "type" : "WEB",
    "url" : "https://github.com/nltk/nltk/releases/tag/v3.10.3"
  }, {
    "type" : "WEB",
    "url" : "https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3738.yaml"
  }, {
    "type" : "WEB",
    "url" : "https://www.vulncheck.com/advisories/nltk-porterstemmer-before-3.10.3-quadratic-time-dos"
  } ],
  "database_specific" : {
    "cwe_ids" : [ "CWE-407" ],
    "severity" : "MODERATE",
    "github_reviewed" : true,
    "github_reviewed_at" : "2026-09-02T14:36:15Z",
    "nvd_published_at" : null
  }
}