GHSA-CJ8F-5FP3-6M88

Vulnerability from github – Published: 2026-11-19 23:48 – Updated: 2026-11-19 23:48
VLAI
Summary
NLTK: Quadratic CPU exhaustion in NLTK XMLCorpusView.read_block via deeply nested XML corpus tags
Details

Summary

NLTK's XMLCorpusView.read_block rebuilds the full root-to-node context path with "/".join(context) on every start tag while it is still searching for a matching element. Because the context stack grows with XML nesting depth and the join is repeated once per start tag, a single corpus file containing deeply nested tags forces O(n^2) pure-Python work, where n is the number of nested elements. Any application that parses attacker-influenced XML corpus data through an XMLCorpusView subclass (for example the nps_chat, framenet, bnc, mte, nkjp, or semcor readers) can be driven to exhaust a CPU core for an extended period, producing a denial of service without any authentication or special privilege.

Root Cause

read_block maintains a context list that is appended on each start tag and popped on each end tag, so it grows monotonically to the maximum nesting depth while an element is being sought. For every start tag, while no target element has been located yet (elt_start is None), the code recomputes the entire path string from scratch and matches it against the reader's tagspec. The tagspec is anchored (tagspec + "\\Z"), so a nested path such as a/a/a/... never completes a full match against a concrete tagspec like Session/Posts/Post; elt_start therefore stays None for the entire file and the per-start-tag join runs for all n tags over depths 1..n. Summing those join costs yields O(n^2). There is no nesting-depth limit, context-length bound, or cumulative-work budget in read_block, and the per-call regex timeout used elsewhere in the file does not observe this cumulative pure-Python string cost.

nltk/corpus/reader/xmldocs.py : XMLCorpusView.read_block
  context.append(name)                              # start-tag: stack grows with depth
  if elt_start is None:
      if tagspec.match("/".join(context)):          # full path rebuilt per start tag -> O(depth)
          ...
  # empty-element variant rebuilds "/".join(context) + "/" + name the same way

Impact

An unauthenticated attacker who can supply or influence an XML corpus file processed by an XMLCorpusView subclass can cause quadratic CPU consumption. A crafted file of roughly 200 KB consumes several seconds of a single core; a few-megabyte file pins a core for minutes, and an arbitrarily large or unclosed nested file can hang the affected process indefinitely on that core. The result is a denial-of-service condition (CWE-407 / CWE-400). No confidentiality or integrity impact is demonstrated; the impact is availability of the processing thread or process. The prerequisite is that the application feed untrusted or attacker-influenced corpus XML into one of the affected readers, which is the same trust boundary already accepted for the seed issue in the same file.

Proof of Concept

Requires only the nltk package and its standard XML corpus reading path; no network or special configuration.

Reproduction drives a real SeekableUnicodeStreamReader and the real read_block with an nps_chat-style tagspec, comparing nested input (growing context depth) against a flat negative control with an identical tag count.

import time, io
from nltk.corpus.reader.xmldocs import XMLCorpusView

def measure(build, label):
    print(label)
    prev = None
    for n in (4000, 8000, 16000, 32000):
        body = build(n).encode("utf-8")
        # write to a temp file and open through an XMLCorpusView subclass tagspec
        import tempfile, os
        fd, path = tempfile.mkstemp(suffix=".xml")
        os.write(fd, b"<Session>" + body + b"</Session>"); os.close(fd)
        view = XMLCorpusView(path, "Session/Posts/Post")
        t = time.time()
        try:
            list(view)
        except Exception:
            pass
        dt = time.time() - t
        ratio = "" if prev is None else f"({dt/prev:.1f}x)"
        print(f"  n={n:>6} time={dt:7.3f}s {ratio}")
        prev = dt
        os.remove(path)

measure(lambda n: "<a>"*n + "</a>"*n, "NESTED  (context depth = n):")
measure(lambda n: "<a></a>"*n,        "FLAT    (context depth = 1, negative control):")
NESTED  (context depth = n):
  n=  4000 time=  0.162s
  n=  8000 time=  0.484s (2.99x)
  n= 16000 time=  1.595s (3.29x)
  n= 32000 time=  5.667s (3.6x)     -> ratios trend toward 4x per 2x input = O(n^2)
FLAT    (context depth = 1, negative control):
  n=  8000 time=  0.145s
  n= 16000 time=  0.293s (2.03x)
  n= 32000 time=  0.580s (2.0x)     -> 2x per 2x input = linear

Attack Chain

  1. Exposure: An application uses an XMLCorpusView subclass (nps_chat, framenet, bnc, mte, nkjp, semcor, and similar) to read an XML corpus file whose contents an attacker can supply or influence.
  2. Control: The attacker controls the XML body and nests a tag the view's tagspec never fully matches, for example "<a>" repeated n times followed by "</a>" repeated n times.
  3. Path: read_block consumes the whole file in one call, appending to context on every start tag; the target element is never found, so the loop runs to end of file and context grows to depth n.
  4. Guard: No nesting-depth cap, context-length bound, or cumulative-work budget exists in read_block; the anchored tagspec match fails in O(1) at offset 0, so it is not the hot term, and the per-call regex timeout does not see cumulative string-build cost.
  5. Primitive: For each of the n start tags, "/".join(context) rebuilds an O(depth) string, giving a cumulative O(n^2) pure-Python CPU cost.
  6. Result: Sustained single-core CPU exhaustion; a modest file blocks a core for seconds to minutes, and an unbounded or unclosed file hangs the processing thread indefinitely.

Bypass Evidence

The seed fix for the previously published quadratic-CPU issue in this same file (CVE-2026-81723, GHSA-vp2x-qp44-57v7) is confined to _read_xml_fragment, where it added incremental in-tag / last-open-bracket tracking. The commit that shipped that fix touched the read_block match line only to change the match call form (from a module-level regex match to a precompiled tagspec match) and preserved the "/".join(context) argument byte-for-byte; it did not add any depth or length bound. This sink is therefore not covered by the seed remediation. It is also distinct from the sibling published issue CVE-2026-81725 (GHSA-8mpw-7fpc-4gqj), whose sink is a block.count(...) line tracker in Pl196xCorpusReader.read_block, a different class, mechanism, input, and fix. The strongest disproof attempts, that the anchored tagspec match is the quadratic term, that the file is not fully consumed in one call, that an end-tag sanity check aborts early, that a depth cap or the per-call regex timeout catches it, that the seed fix already covers it, and that deep nesting is entity expansion blocked by defused XML handling, were each checked and refuted: the flat negative control with identical tag count stays linear, isolating the quadratic term to the depth-dependent join; well-formed balanced input runs to end of file before any pop; no depth cap exists; the timeout is per call and does not observe cumulative pure-Python cost; and benign literal nesting is not custom-entity expansion.

Affected Versions

  • Ecosystem: PyPI (pip)
  • Package: nltk
  • Confirmed affected range: <= 3.10.3
  • Latest release checked: 3.10.3 (PyPI, nltk-3.10.3-py3-none-any.whl)
  • Fix status: not fixed (no fix present in any released version or in the current development branch)

The vulnerable join sink is present in the latest published artifact (3.10.3) and was corroborated in 3.9.1. No released version and no development-branch commit contains a fix, so the upper bound <= 3.10.3 is proven. The introduction boundary was not pinned to an exact first-affected release: the algorithm is long-standing legacy code present in all inspected supported releases, and pinning an exact introduced version would require bisecting historical wheels. The lower boundary is therefore left unestablished rather than asserted.

Suggested Fix

Bound the work performed while searching for a target element in read_block. Options that address the root cause: track the running context path incrementally (append and truncate a single cached path string alongside the context stack, rather than rejoining the whole list on every tag), or enforce an explicit maximum nesting depth / maximum accumulated tag count for a single block and raise a clear error when it is exceeded. The remediation must cover both the start-tag match at the primary join site and the empty-element variant that rebuilds "/".join(context) + "/" + name, and it should apply regardless of whether the input is well-formed and balanced or an unclosed nested run. As an interim mitigation, deployments can impose an upstream size limit on corpus XML fed to these readers and avoid parsing untrusted corpus files, though this does not remove the quadratic behavior for inputs under the limit.

Reported by zx (GitHub: @manus-pi).

Fix status (2026-09-28)

Status: IN PROGRESS (fix on an open pull request, not yet on develop).

PR: #3895 "[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)", open, head b22ebe144.

Fix commit: 002bcf714 "Bound three quadratic algorithmic-DoS vectors on untrusted input" (XMLCorpusView.read_block no longer rebuilds the context path per piece).

No probe. The advisory PoC re-run (nested tags, n=8000 vs n=32000 through read_block): on the PR head 0.7x over a 4x input (linear); on develop 2fa3f48fe 11.3x (3.08 s vs 34.9 s), so develop is still VULNERABLE. The open PR #3753 measured on its head 238f81500 also gives 10.9x: its xmldocs change targets the unclosed CDATA/comment rescan of GHSA-j8g8, not this vector.

Release: none.

Show details on source website

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 3.10.3"
      },
      "package": {
        "ecosystem": "PyPI",
        "name": "nltk"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "3.10.4"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-129232"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-400",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-11-19T23:48:18Z",
    "nvd_published_at": "2026-11-19T17:17:56Z",
    "severity": "MODERATE"
  },
  "details": "## Summary\n\nNLTK\u0027s `XMLCorpusView.read_block` rebuilds the full root-to-node context path with `\"/\".join(context)` on every start tag while it is still searching for a matching element. Because the context stack grows with XML nesting depth and the join is repeated once per start tag, a single corpus file containing deeply nested tags forces O(n^2) pure-Python work, where n is the number of nested elements. Any application that parses attacker-influenced XML corpus data through an `XMLCorpusView` subclass (for example the `nps_chat`, `framenet`, `bnc`, `mte`, `nkjp`, or `semcor` readers) can be driven to exhaust a CPU core for an extended period, producing a denial of service without any authentication or special privilege.\n\n## Root Cause\n\n`read_block` maintains a `context` list that is appended on each start tag and popped on each end tag, so it grows monotonically to the maximum nesting depth while an element is being sought. For every start tag, while no target element has been located yet (`elt_start is None`), the code recomputes the entire path string from scratch and matches it against the reader\u0027s tagspec. The tagspec is anchored (`tagspec + \"\\\\Z\"`), so a nested path such as `a/a/a/...` never completes a full match against a concrete tagspec like `Session/Posts/Post`; `elt_start` therefore stays `None` for the entire file and the per-start-tag join runs for all n tags over depths 1..n. Summing those join costs yields O(n^2). There is no nesting-depth limit, context-length bound, or cumulative-work budget in `read_block`, and the per-call regex timeout used elsewhere in the file does not observe this cumulative pure-Python string cost.\n\n```text\nnltk/corpus/reader/xmldocs.py : XMLCorpusView.read_block\n  context.append(name)                              # start-tag: stack grows with depth\n  if elt_start is None:\n      if tagspec.match(\"/\".join(context)):          # full path rebuilt per start tag -\u003e O(depth)\n          ...\n  # empty-element variant rebuilds \"/\".join(context) + \"/\" + name the same way\n```\n\n## Impact\n\nAn unauthenticated attacker who can supply or influence an XML corpus file processed by an `XMLCorpusView` subclass can cause quadratic CPU consumption. A crafted file of roughly 200 KB consumes several seconds of a single core; a few-megabyte file pins a core for minutes, and an arbitrarily large or unclosed nested file can hang the affected process indefinitely on that core. The result is a denial-of-service condition (CWE-407 / CWE-400). No confidentiality or integrity impact is demonstrated; the impact is availability of the processing thread or process. The prerequisite is that the application feed untrusted or attacker-influenced corpus XML into one of the affected readers, which is the same trust boundary already accepted for the seed issue in the same file.\n\n## Proof of Concept\n\n`Requires only the nltk package and its standard XML corpus reading path; no network or special configuration.`\n\nReproduction drives a real `SeekableUnicodeStreamReader` and the real `read_block` with an `nps_chat`-style tagspec, comparing nested input (growing context depth) against a flat negative control with an identical tag count.\n\n```python\nimport time, io\nfrom nltk.corpus.reader.xmldocs import XMLCorpusView\n\ndef measure(build, label):\n    print(label)\n    prev = None\n    for n in (4000, 8000, 16000, 32000):\n        body = build(n).encode(\"utf-8\")\n        # write to a temp file and open through an XMLCorpusView subclass tagspec\n        import tempfile, os\n        fd, path = tempfile.mkstemp(suffix=\".xml\")\n        os.write(fd, b\"\u003cSession\u003e\" + body + b\"\u003c/Session\u003e\"); os.close(fd)\n        view = XMLCorpusView(path, \"Session/Posts/Post\")\n        t = time.time()\n        try:\n            list(view)\n        except Exception:\n            pass\n        dt = time.time() - t\n        ratio = \"\" if prev is None else f\"({dt/prev:.1f}x)\"\n        print(f\"  n={n:\u003e6} time={dt:7.3f}s {ratio}\")\n        prev = dt\n        os.remove(path)\n\nmeasure(lambda n: \"\u003ca\u003e\"*n + \"\u003c/a\u003e\"*n, \"NESTED  (context depth = n):\")\nmeasure(lambda n: \"\u003ca\u003e\u003c/a\u003e\"*n,        \"FLAT    (context depth = 1, negative control):\")\n```\n\n```text\nNESTED  (context depth = n):\n  n=  4000 time=  0.162s\n  n=  8000 time=  0.484s (2.99x)\n  n= 16000 time=  1.595s (3.29x)\n  n= 32000 time=  5.667s (3.6x)     -\u003e ratios trend toward 4x per 2x input = O(n^2)\nFLAT    (context depth = 1, negative control):\n  n=  8000 time=  0.145s\n  n= 16000 time=  0.293s (2.03x)\n  n= 32000 time=  0.580s (2.0x)     -\u003e 2x per 2x input = linear\n```\n\n## Attack Chain\n\n1. **Exposure:** An application uses an `XMLCorpusView` subclass (`nps_chat`, `framenet`, `bnc`, `mte`, `nkjp`, `semcor`, and similar) to read an XML corpus file whose contents an attacker can supply or influence.\n2. **Control:** The attacker controls the XML body and nests a tag the view\u0027s tagspec never fully matches, for example `\"\u003ca\u003e\"` repeated n times followed by `\"\u003c/a\u003e\"` repeated n times.\n3. **Path:** `read_block` consumes the whole file in one call, appending to `context` on every start tag; the target element is never found, so the loop runs to end of file and `context` grows to depth n.\n4. **Guard:** No nesting-depth cap, context-length bound, or cumulative-work budget exists in `read_block`; the anchored tagspec match fails in O(1) at offset 0, so it is not the hot term, and the per-call regex timeout does not see cumulative string-build cost.\n5. **Primitive:** For each of the n start tags, `\"/\".join(context)` rebuilds an O(depth) string, giving a cumulative O(n^2) pure-Python CPU cost.\n6. **Result:** Sustained single-core CPU exhaustion; a modest file blocks a core for seconds to minutes, and an unbounded or unclosed file hangs the processing thread indefinitely.\n\n## Bypass Evidence\n\nThe seed fix for the previously published quadratic-CPU issue in this same file (CVE-2026-81723, GHSA-vp2x-qp44-57v7) is confined to `_read_xml_fragment`, where it added incremental in-tag / last-open-bracket tracking. The commit that shipped that fix touched the `read_block` match line only to change the match call form (from a module-level regex match to a precompiled tagspec match) and preserved the `\"/\".join(context)` argument byte-for-byte; it did not add any depth or length bound. This sink is therefore not covered by the seed remediation. It is also distinct from the sibling published issue CVE-2026-81725 (GHSA-8mpw-7fpc-4gqj), whose sink is a `block.count(...)` line tracker in `Pl196xCorpusReader.read_block`, a different class, mechanism, input, and fix. The strongest disproof attempts, that the anchored tagspec match is the quadratic term, that the file is not fully consumed in one call, that an end-tag sanity check aborts early, that a depth cap or the per-call regex timeout catches it, that the seed fix already covers it, and that deep nesting is entity expansion blocked by defused XML handling, were each checked and refuted: the flat negative control with identical tag count stays linear, isolating the quadratic term to the depth-dependent join; well-formed balanced input runs to end of file before any pop; no depth cap exists; the timeout is per call and does not observe cumulative pure-Python cost; and benign literal nesting is not custom-entity expansion.\n\n## Affected Versions\n\n- `Ecosystem: PyPI (pip)`\n- `Package: nltk`\n- `Confirmed affected range: \u003c= 3.10.3`\n- `Latest release checked: 3.10.3 (PyPI, nltk-3.10.3-py3-none-any.whl)`\n- `Fix status: not fixed (no fix present in any released version or in the current development branch)`\n\nThe vulnerable join sink is present in the latest published artifact (3.10.3) and was corroborated in 3.9.1. No released version and no development-branch commit contains a fix, so the upper bound `\u003c= 3.10.3` is proven. The introduction boundary was not pinned to an exact first-affected release: the algorithm is long-standing legacy code present in all inspected supported releases, and pinning an exact introduced version would require bisecting historical wheels. The lower boundary is therefore left unestablished rather than asserted.\n\n## Suggested Fix\n\nBound the work performed while searching for a target element in `read_block`. Options that address the root cause: track the running context path incrementally (append and truncate a single cached path string alongside the `context` stack, rather than rejoining the whole list on every tag), or enforce an explicit maximum nesting depth / maximum accumulated tag count for a single block and raise a clear error when it is exceeded. The remediation must cover both the start-tag match at the primary join site and the empty-element variant that rebuilds `\"/\".join(context) + \"/\" + name`, and it should apply regardless of whether the input is well-formed and balanced or an unclosed nested run. As an interim mitigation, deployments can impose an upstream size limit on corpus XML fed to these readers and avoid parsing untrusted corpus files, though this does not remove the quadratic behavior for inputs under the limit.\n\nReported by zx (GitHub: @manus-pi).\n\n## Fix status (2026-09-28)\n\nStatus: IN PROGRESS (fix on an open pull request, not yet on develop).\n\nPR: #3895 \"[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)\", open, head b22ebe144.\n\nFix commit: 002bcf714 \"Bound three quadratic algorithmic-DoS vectors on untrusted input\" (XMLCorpusView.read_block no longer rebuilds the context path per piece).\n\nNo probe. The advisory PoC re-run (nested tags, n=8000 vs n=32000 through read_block): on the PR head 0.7x over a 4x input (linear); on develop 2fa3f48fe 11.3x (3.08 s vs 34.9 s), so develop is still VULNERABLE. The open PR #3753 measured on its head 238f81500 also gives 10.9x: its xmldocs change targets the unclosed CDATA/comment rescan of GHSA-j8g8, not this vector.\n\nRelease: none.",
  "id": "GHSA-cj8f-5fp3-6m88",
  "modified": "2026-11-19T23:48:18Z",
  "published": "2026-11-19T23:48:18Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/security/advisories/GHSA-cj8f-5fp3-6m88"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-129232"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/pull/3895"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/commit/002bcf714ef8cb8baf94436f4be73e5516914412"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/nltk/nltk"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/releases/tag/v3.10.4"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L",
      "type": "CVSS_V3"
    }
  ],
  "summary": "NLTK: Quadratic CPU exhaustion in NLTK XMLCorpusView.read_block via deeply nested XML corpus tags"
}



Log in or create an account to share your comment.




Tags
Taxonomy of the tags.


Loading…

Loading…

Loading…

Drag nodes to arrange them. Double-click a related vulnerability to open it, or a source to visit its link. The Physics button on the left tunes the layout and the simulation; the legend at the bottom left hides or shows nodes by kind and by sighting type.

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.
Vulnerability timeline

Sightings and recorded dates, grouped by day · UTC

JSON
How durations are calculated

Following the VTEM framework (Black Hat USA 2015), time to patch starts when the vendor or a coordinator was informed, total time to patch at discovery, and disclosure to patch at public disclosure; vendor response time runs from the report to its acknowledgement. Time to exploit and time unpatched start at the earliest discovery or report, falling back to public disclosure. Unpatched time ends at the first recorded patch, or the calculation time when no patch is recorded. Exploitation to patch shows the interval between those two events; a published proof of concept is a public exploit, not exploitation.

Each result shows its source dates. A negative interval means the end event came first; when date-only inputs leave the order open, the result says so. Date-only inputs are approximate. The earliest evidence wins: KEV report dates and sightings are labelled as such. Records describing another vulnerability are listed but never calculated from, and a PoC alone does not establish exploitation. Missing patch evidence does not prove that no patch exists. Filters below change the event list only.

Events included in the timeline

Loading timeline…


    Loading…

    Loading…

    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.