BREW-ACRONYM-CVE-2026-126300 (GHSA-FFR9-MGRR-WCVR)

Vulnerability from osv_homebrew – Published: 2026-11-14 09:40 – Updated: 2026-11-14 09:40 – Source website
VLAI
Summary
NLTK: Quadratic CPU exhaustion in TreebankWordTokenizer.span_tokenize via list.pop(0) in quote-restore loop
Details

Summary

TreebankWordTokenizer.span_tokenize in the NLTK tokenizer package contains an unguarded O(n^2) processing loop in its quote-restoration step. When the method is invoked on text containing a long run of double-quote characters (for example '"' * n), it performs a list.pop(0) operation once per quote token, and because list.pop(0) is O(length), the total cost grows with the square of the input length. An attacker who can supply untrusted text to this public span-tokenization API can force a single request to saturate one CPU core for a prolonged period, degrading availability. No authentication, special configuration, or user interaction is required.

Root Cause

Inside span_tokenize, when the input contains double or repeated quotes, the code builds matched, a list with one entry per quote occurrence, and then reconstructs tokens in a comprehension that calls matched.pop(0) for each token that is a quote. Removing the first element of a Python list is an O(len(list)) operation because all remaining elements are shifted. For an all-quote input the tokenizer produces n quote tokens and matched has n entries, so pop(0) is called n times, each time on a list of shrinking but still linear length, giving cumulative O(n^2) CPU work. The violated invariant is bounded per-input work: there is no length cap on span_tokenize or the underlying tokenize, so untrusted input length translates into quadratic processing time. The neighboring align_tokens call is linear and is not the quadratic term.

Affected function: TreebankWordTokenizer.span_tokenize
Source: nltk/tokenize/treebank.py
  - branch selector at line 203
  - matched list built at line 205
  - quadratic sink matched.pop(0) at line 209
  - linear align_tokens call at line 215

Impact

An attacker who controls text passed to TreebankWordTokenizer.span_tokenize can trigger quadratic CPU work. In the reviewed release, an all-quote input of 128,000 characters takes about 1.76 seconds and 256,000 characters about 6.57 seconds on a single core, with cost growing as the square of the length. Memory use is linear. The demonstrated capability is single-core CPU exhaustion producing denial of service or latency degradation in any network-reachable component that uses span tokenization on untrusted input, such as offset, annotation, or highlighting pipelines. There is no confidentiality or integrity impact. The plausible operational consequence, where multiple concurrent requests are used, is worker-pool exhaustion; this is inferred from the measured per-request cost and was not executed against a live deployment.

Proof of Concept

Requires only the released nltk package; no corpus download is needed.

  1. Instantiate TreebankWordTokenizer.
  2. Call span_tokenize on an all-double-quote string of increasing length and time each call.
  3. Compare against an equal-token-count control input that avoids the quote branch.
import time
from nltk.tokenize import TreebankWordTokenizer

tok = TreebankWordTokenizer()
for n in (32000, 64000, 128000, 256000):
    payload = '"' * n
    start = time.perf_counter()
    list(tok.span_tokenize(payload))
    print("quote-run", n, round(time.perf_counter() - start, 3))

control = "a " * 128000  # comparable token count, avoids the pop(0) branch
start = time.perf_counter()
list(tok.span_tokenize(control))
print("control", round(time.perf_counter() - start, 3))

quote-run 32000 0.23
quote-run 64000 0.52
quote-run 128000 1.76
quote-run 256000 6.57   (about 4x per doubling => O(n^2))
control 0.16            (roughly 11x faster, isolates pop(0))

Attack Chain

  1. Exposure: TreebankWordTokenizer is exported from nltk.tokenize and span_tokenize is a public, documented method reachable by any service that span-tokenizes untrusted text.
  2. Control: The attacker fully controls the text argument; a run of double-quote characters such as '"' * n survives to the quote branch unchanged.
  3. Path: The branch selector at line 203 ('"' in text or "''" in text) is satisfied by the payload, entering the vulnerable branch; matched is built at line 205 with n entries and the reconstruction comprehension runs at line 209.
  4. Guard: There is no length cap on span_tokenize or tokenize. The regex timeout backstop in nltk/redos.py only wraps regular-expression operations and does not cover the pure-Python list.pop(0) sink; a 256,000-character input ran to completion in 6.57 seconds with no timeout raised.
  5. Primitive: matched.pop(0) executed once per quote token, each call O(len(matched)), yields cumulative O(n^2) CPU work.
  6. Result: A single request with a large quote-run input exhausts one CPU core for a sustained period, degrading service availability.

Bypass Evidence

No guard blocks this path. Direct inspection found no MAX_TOKEN_LEN or length check in nltk/tokenize/treebank.py, in contrast to the sibling sonority_sequencing.py which does cap token length. The strongest refutations were attempted and failed: (1) the hypothesis that tokenize collapses repeated quotes so few pop(0) calls occur was disproven by observing that tokenize('"' * n) yields exactly n quote tokens and timing showing about 4x growth per doubling, while an equal-token-count non-quote control ran roughly 11x faster; (2) the hypothesis that the project regex-timeout backstop already caps this cost was disproven by running a 256,000-character input to normal completion in 6.57 seconds with no TimeoutError, confirming the backstop wraps only regex operations and not list.pop(0); (3) the hypothesis that this line was already audited was disproven, since the project quadratic-DoS test suite explicitly clears the neighboring align_tokens line reached through span_tokenize but contains no test for the pop(0) loop, an audited-neighbor pattern where the adjacent line was checked and this one was missed. The seed remediation touched a different module and no advisory covers this sink.

Affected Versions

  • Ecosystem: pip
  • Package: nltk
  • Confirmed affected range: >= 3.2.5, <= 3.10.3
  • Latest release checked: 3.10.3 (PyPI)
  • Fix status: not fixed

The vulnerable pop(0) loop is present and unguarded in the current released artifact 3.10.3, verified by direct source inspection and by reproducing the quadratic curve through fresh execution. The lower bound of 3.2.5 reflects when the affected quote-restoration code shipped; the disclosure-relevant fact is that the latest published release is affected and no fix has been released.

Suggested Fix

Replace the O(n) list.pop(0) pattern with an O(1) consumption strategy, for example iterating over matched with an index or an iterator, or using collections.deque with popleft(), so that the quote-restoration step runs in linear time overall. Additionally, consider enforcing a configurable maximum input length in span_tokenize consistent with the caps applied to sibling tokenizers, and ensure the fix covers all callers that pass untrusted text. As an interim mitigation, deployments that expose span tokenization of untrusted input can cap request and input sizes at the application boundary to bound the worst-case length.

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

Fix status (2026-09-28)

Two pull requests carry a fix.

PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", open; head da55cab0e at the time of this note (a develop merge on top of 238f81500, the head on which the verdicts below were measured). Fix commit: cf12a5e6a (the quote-restore loop in tokenize/treebank.py and tokenize/destructive.py iterates forward instead of list.pop(0)).

PR: #3895 "[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)", open, head b22ebe144. Fix commit: e20c40e26 "Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)".

No probe. The advisory PoC re-run (span_tokenize over 32k and 128k double quotes): #3753 head 3.5x over a 4x input, #3895 head 3.2x, both linear. On develop 2fa3f48fe the 128k run did not finish within 120 s, so develop is still VULNERABLE.

Severity
5.3 (Medium)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
References
To clipboard 

{
  "affected": [
    {
      "ecosystem_specific": {
        "fix": "bump",
        "range_state": "fixed",
        "resource": "nltk",
        "resource_purl": "pkg:pypi/nltk@3.10.4",
        "upstream_fixed_in": "3.10.4"
      },
      "package": {
        "ecosystem": "Homebrew",
        "name": "acronym",
        "purl": "pkg:brew/acronym"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "2.0.0"
            },
            {
              "fixed": "2.0.0_6"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "database_specific": {
    "confidence": "high",
    "source": "matched",
    "strategy": "registry",
    "upstream_evidence": [
      {
        "ecosystem": "PyPI",
        "key": "pkg:pypi/nltk@3.10.4",
        "name": "nltk",
        "resource": "nltk",
        "strategy": "registry",
        "subject_version": "3.10.4"
      }
    ]
  },
  "details": "## Summary\n\n`TreebankWordTokenizer.span_tokenize` in the NLTK tokenizer package contains an unguarded O(n^2) processing loop in its quote-restoration step. When the method is invoked on text containing a long run of double-quote characters (for example `\u0027\"\u0027 * n`), it performs a `list.pop(0)` operation once per quote token, and because `list.pop(0)` is O(length), the total cost grows with the square of the input length. An attacker who can supply untrusted text to this public span-tokenization API can force a single request to saturate one CPU core for a prolonged period, degrading availability. No authentication, special configuration, or user interaction is required.\n\n## Root Cause\n\nInside `span_tokenize`, when the input contains double or repeated quotes, the code builds `matched`, a list with one entry per quote occurrence, and then reconstructs tokens in a comprehension that calls `matched.pop(0)` for each token that is a quote. Removing the first element of a Python list is an O(len(list)) operation because all remaining elements are shifted. For an all-quote input the tokenizer produces n quote tokens and `matched` has n entries, so `pop(0)` is called n times, each time on a list of shrinking but still linear length, giving cumulative O(n^2) CPU work. The violated invariant is bounded per-input work: there is no length cap on `span_tokenize` or the underlying `tokenize`, so untrusted input length translates into quadratic processing time. The neighboring `align_tokens` call is linear and is not the quadratic term.\n\n```text\nAffected function: TreebankWordTokenizer.span_tokenize\nSource: nltk/tokenize/treebank.py\n  - branch selector at line 203\n  - matched list built at line 205\n  - quadratic sink matched.pop(0) at line 209\n  - linear align_tokens call at line 215\n```\n\n## Impact\n\nAn attacker who controls text passed to `TreebankWordTokenizer.span_tokenize` can trigger quadratic CPU work. In the reviewed release, an all-quote input of 128,000 characters takes about 1.76 seconds and 256,000 characters about 6.57 seconds on a single core, with cost growing as the square of the length. Memory use is linear. The demonstrated capability is single-core CPU exhaustion producing denial of service or latency degradation in any network-reachable component that uses span tokenization on untrusted input, such as offset, annotation, or highlighting pipelines. There is no confidentiality or integrity impact. The plausible operational consequence, where multiple concurrent requests are used, is worker-pool exhaustion; this is inferred from the measured per-request cost and was not executed against a live deployment.\n\n## Proof of Concept\n\n`Requires only the released nltk package; no corpus download is needed.`\n\n1. Instantiate `TreebankWordTokenizer`.\n2. Call `span_tokenize` on an all-double-quote string of increasing length and time each call.\n3. Compare against an equal-token-count control input that avoids the quote branch.\n\n```python\nimport time\nfrom nltk.tokenize import TreebankWordTokenizer\n\ntok = TreebankWordTokenizer()\nfor n in (32000, 64000, 128000, 256000):\n    payload = \u0027\"\u0027 * n\n    start = time.perf_counter()\n    list(tok.span_tokenize(payload))\n    print(\"quote-run\", n, round(time.perf_counter() - start, 3))\n\ncontrol = \"a \" * 128000  # comparable token count, avoids the pop(0) branch\nstart = time.perf_counter()\nlist(tok.span_tokenize(control))\nprint(\"control\", round(time.perf_counter() - start, 3))\n```\n\n```text\nquote-run 32000 0.23\nquote-run 64000 0.52\nquote-run 128000 1.76\nquote-run 256000 6.57   (about 4x per doubling =\u003e O(n^2))\ncontrol 0.16            (roughly 11x faster, isolates pop(0))\n```\n\n## Attack Chain\n\n1. **Exposure:** `TreebankWordTokenizer` is exported from `nltk.tokenize` and `span_tokenize` is a public, documented method reachable by any service that span-tokenizes untrusted text.\n2. **Control:** The attacker fully controls the `text` argument; a run of double-quote characters such as `\u0027\"\u0027 * n` survives to the quote branch unchanged.\n3. **Path:** The branch selector at line 203 (`\u0027\"\u0027 in text` or `\"\u0027\u0027\" in text`) is satisfied by the payload, entering the vulnerable branch; `matched` is built at line 205 with n entries and the reconstruction comprehension runs at line 209.\n4. **Guard:** There is no length cap on `span_tokenize` or `tokenize`. The regex timeout backstop in `nltk/redos.py` only wraps regular-expression operations and does not cover the pure-Python `list.pop(0)` sink; a 256,000-character input ran to completion in 6.57 seconds with no timeout raised.\n5. **Primitive:** `matched.pop(0)` executed once per quote token, each call O(len(matched)), yields cumulative O(n^2) CPU work.\n6. **Result:** A single request with a large quote-run input exhausts one CPU core for a sustained period, degrading service availability.\n\n## Bypass Evidence\n\nNo guard blocks this path. Direct inspection found no `MAX_TOKEN_LEN` or length check in `nltk/tokenize/treebank.py`, in contrast to the sibling `sonority_sequencing.py` which does cap token length. The strongest refutations were attempted and failed: (1) the hypothesis that `tokenize` collapses repeated quotes so few `pop(0)` calls occur was disproven by observing that `tokenize(\u0027\"\u0027 * n)` yields exactly n quote tokens and timing showing about 4x growth per doubling, while an equal-token-count non-quote control ran roughly 11x faster; (2) the hypothesis that the project regex-timeout backstop already caps this cost was disproven by running a 256,000-character input to normal completion in 6.57 seconds with no `TimeoutError`, confirming the backstop wraps only regex operations and not `list.pop(0)`; (3) the hypothesis that this line was already audited was disproven, since the project quadratic-DoS test suite explicitly clears the neighboring `align_tokens` line reached through `span_tokenize` but contains no test for the `pop(0)` loop, an audited-neighbor pattern where the adjacent line was checked and this one was missed. The seed remediation touched a different module and no advisory covers this sink.\n\n## Affected Versions\n\n- `Ecosystem: pip`\n- `Package: nltk`\n- `Confirmed affected range: \u003e= 3.2.5, \u003c= 3.10.3`\n- `Latest release checked: 3.10.3 (PyPI)`\n- `Fix status: not fixed`\n\nThe vulnerable `pop(0)` loop is present and unguarded in the current released artifact 3.10.3, verified by direct source inspection and by reproducing the quadratic curve through fresh execution. The lower bound of 3.2.5 reflects when the affected quote-restoration code shipped; the disclosure-relevant fact is that the latest published release is affected and no fix has been released.\n\n## Suggested Fix\n\nReplace the O(n) `list.pop(0)` pattern with an O(1) consumption strategy, for example iterating over `matched` with an index or an iterator, or using `collections.deque` with `popleft()`, so that the quote-restoration step runs in linear time overall. Additionally, consider enforcing a configurable maximum input length in `span_tokenize` consistent with the caps applied to sibling tokenizers, and ensure the fix covers all callers that pass untrusted text. As an interim mitigation, deployments that expose span tokenization of untrusted input can cap request and input sizes at the application boundary to bound the worst-case length.\n\nReported by zx (GitHub: @manus-pi).\n\n## Fix status (2026-09-28)\n\nTwo pull requests carry a fix.\n\nPR: #3753 \"[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path\", open; head da55cab0e at the time of this note (a develop merge on top of 238f81500, the head on which the verdicts below were measured). Fix commit: cf12a5e6a (the quote-restore loop in tokenize/treebank.py and tokenize/destructive.py iterates forward instead of list.pop(0)).\n\nPR: #3895 \"[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)\", open, head b22ebe144. Fix commit: e20c40e26 \"Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)\".\n\nNo probe. The advisory PoC re-run (span_tokenize over 32k and 128k double quotes): #3753 head 3.5x over a 4x input, #3895 head 3.2x, both linear. On develop 2fa3f48fe the 128k run did not finish within 120 s, so develop is still VULNERABLE.",
  "id": "BREW-acronym-CVE-2026-126300",
  "modified": "2026-11-14T09:40:04Z",
  "published": "2026-11-14T09:40:04Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/security/advisories/GHSA-ffr9-mgrr-wcvr"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-126300"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/pull/3895"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/commit/e20c40e26ec9306de885703f6e53250695f1f49b"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/nltk/nltk"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/releases/tag/v3.10.4"
    },
    {
      "type": "WEB",
      "url": "https://www.vulncheck.com/advisories/nltk-from-3.2.5-before-3.10.4-cpu-exhaustion-via-treebankwordtokenizer-span-tokenize"
    }
  ],
  "schema_version": "1.7.3",
  "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 TreebankWordTokenizer.span_tokenize via list.pop(0) in quote-restore loop",
  "upstream": [
    "GHSA-ffr9-mgrr-wcvr",
    "CVE-2026-126300"
  ]
}



Log in or create an account to share your comment.




Tags
Taxonomy of the tags.




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.

Loading timeline…




    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.