Vulnerability-Lookup

BREW-ACRONYM-CVE-2026-126298 (GHSA-R53H-RW34-8H97)

Vulnerability from osv_homebrew – Published: 2026-11-14 09:40 – Updated: 2026-11-14 09:40 – Source website

Summary

NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)

Details

Summary

Tree.chomsky_normal_form() binarizes a parse tree and defaults to right factoring. For a node with N children the right-factor branch repeatedly removes the first element of a working list with list.pop(0), which shifts all remaining elements each time, so binarizing one wide node costs O(N^2). An application that converts an attacker-supplied treebank tree to Chomsky Normal Form can be forced into tens of seconds of single-threaded CPU by one wide flat tree. No authentication or user interaction is required.

Root Cause

In the default right-factor branch the transform executes curNode[0:] = [nodeCopy.pop(0), newNode] inside a loop over the N children of a node. list.pop(0) is O(len) because it shifts every remaining element down by one; performed N-2 times over a shrinking length-N list this sums to O(N^2). The left-factor branch instead uses nodeCopy.pop() (removing the last element), which is O(1) and linear overall, so the two branches differ only by this front-versus-back removal. No cap is placed on the child count of a node, and the public Tree.fromstring parser accepts an arbitrarily wide bracketed tree.

Affected function:
- nltk.tree.transforms.chomsky_normal_form (nltk/tree/transforms.py; right-factor sink at line 168, O(1) left control at line 179)
Public entry points: nltk.tree.Tree.chomsky_normal_form (nltk/tree/tree.py:455, default factor="right"); nltk.tree.Tree.fromstring (nltk/tree/tree.py:592).

Impact

An attacker who can influence the tree that an application normalizes to Chomsky Normal Form causes sustained single-threaded CPU consumption (availability loss). The path is network-reachable (AV:N) and needs no privileges or user interaction (PR:N, UI:N). Because the cost grows quadratically with the attacker-chosen child count, roughly 1.5 MB of treebank input costs about 14 seconds on one core and scales as N^2 above that. Confidentiality and integrity are not affected. The NLTK regular-expression wall-clock timeout wraps regex matching only and does not wrap this pure-Python list loop.

Proof of Concept

Environment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree.

import time
from nltk.tree import Tree

for N in (80000, 160000, 320000):
    s = "(S " + "(A a)" * N + ")"
    t = Tree.fromstring(s)
    start = time.perf_counter()
    t.chomsky_normal_form()          # default factor="right"
    print("right", N, round(time.perf_counter() - start, 3), "s")

right (default):  N=80000 1.972s | N=160000 5.004s (2.54x) | N=320000 14.518s (2.90x)   -> super-linear
left  (control):  N=80000 1.399s | N=160000 2.731s (1.95x) | N=320000  5.379s (1.97x)   -> linear

Attack Chain

Exposure: An application parses an attacker-influenced treebank string with the public Tree.fromstring and normalizes it with Tree.chomsky_normal_form().
Control: The attacker controls the number of children of a node (a wide flat tree such as (S (A a)(A a)...(A a))); no child-count cap exists in fromstring or the transform.
Path: Tree.chomsky_normal_form delegates to nltk.tree.transforms.chomsky_normal_form with the default factor="right".
Guard: None. There is no width bound on the loop, and the regex match timeout does not wrap this pure-Python list operation.
Primitive: curNode[0:] = [nodeCopy.pop(0), newNode] performs an O(N) front shift on each of N iterations.
Result: O(N^2) single-core CPU exhaustion; roughly 1.5 MB of input costs about 14 seconds and scales quadratically, blocking the processing thread.

Bypass Evidence

There is no guard to bypass on this path: neither Tree.fromstring nor chomsky_normal_form caps the child count, and the regular-expression wall-clock timeout wraps only regex matching, not this list loop. The finding was confirmed by fresh timing that isolates the cause: the right-factor default and the left-factor branch build the identical bounded head strings and copy the node once, so the only differing term is pop(0) versus pop(). The measured right-versus-left divergence grows with N (right rises toward a 4x per-doubling ratio while left holds near 2x), which proves a quadratic component beyond the shared linear costs. A relevant corroboration is that the inverse transform un_chomsky_normal_form was already rewritten to a single linear pass to remove exactly this quadratic class (see the comment at nltk/tree/transforms.py:195-201), while the forward default path retained the pop(0) idiom. The strongest disproof attempt (that the head-string join dominates and is linear) fails because that join is bounded and present in both branches and therefore cannot explain the branch-dependent quadratic growth.

Affected Versions

Ecosystem: PyPI (pip)
Package: nltk
Confirmed affected range: <= 3.10.3
Latest release checked: 3.10.3 (PyPI, https://pypi.org/pypi/nltk/json)
Fix status: 3.10.4

The right-factor pop(0) idiom ships in every release carrying this transform and is present in the current latest published release, 3.10.3. The lower boundary was not bisected, so the introducing version is left open.

Suggested Fix

Rewrite the right-factor binarization to avoid removing from the front of a list: iterate the children with an index cursor or a collections.deque so each step is constant time, mirroring the linear rebuild already applied to un_chomsky_normal_form. As defense in depth, bound the child count accepted for normalization and raise a clear error past a configurable maximum. No configuration-only mitigation removes the exposure for a service that normalizes untrusted trees; until a fix ships, callers should cap accepted tree width and run the transform under a CPU or time budget in an isolated worker.

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

Fix status (2026-09-28)

PR: #3909 "Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)", merged 2026-09-23, merge commit 2f53e20ce on develop.

Fix commits: 457ebe349 (linear front consume in chomsky_normal_form) and 677857dca (refuse a binarisation that would nest a tree beyond MAX_TREE_DEPTH). Follow-up #3917 (merge 9ba132e43, commit f0686dea6) walks Tree equality and conversion with an explicit stack so the deep-tree tests pass on Python 3.10 and 3.11.

Probe: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; verdict on develop 2fa3f48fe: FIXED (chomsky_normal_form scales 5.1x over a 4x input).

Severity

7.5 (High)


                    
                      CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

References

URL

Type

	https://github.com/nltk/nltk/security/advisories/…	WEB
	https://nvd.nist.gov/vuln/detail/CVE-2026-126298	ADVISORY
	https://github.com/nltk/nltk/pull/3909	WEB
	https://github.com/nltk/nltk/commit/457ebe349f8dd…	WEB
	https://github.com/nltk/nltk/commit/677857dcafd84…	WEB
	https://github.com/nltk/nltk	PACKAGE
	https://github.com/nltk/nltk/releases/tag/v3.10.4	WEB
	https://www.vulncheck.com/advisories/nltk-before-…	WEB

JSON

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`Tree.chomsky_normal_form()` binarizes a parse tree and defaults to right factoring. For a node with N children the right-factor branch repeatedly removes the first element of a working list with `list.pop(0)`, which shifts all remaining elements each time, so binarizing one wide node costs O(N^2). An application that converts an attacker-supplied treebank tree to Chomsky Normal Form can be forced into tens of seconds of single-threaded CPU by one wide flat tree. No authentication or user interaction is required.\n\n## Root Cause\n\nIn the default right-factor branch the transform executes `curNode[0:] = [nodeCopy.pop(0), newNode]` inside a loop over the N children of a node. `list.pop(0)` is O(len) because it shifts every remaining element down by one; performed N-2 times over a shrinking length-N list this sums to O(N^2). The left-factor branch instead uses `nodeCopy.pop()` (removing the last element), which is O(1) and linear overall, so the two branches differ only by this front-versus-back removal. No cap is placed on the child count of a node, and the public `Tree.fromstring` parser accepts an arbitrarily wide bracketed tree.\n\n```text\nAffected function:\n- nltk.tree.transforms.chomsky_normal_form (nltk/tree/transforms.py; right-factor sink at line 168, O(1) left control at line 179)\nPublic entry points: nltk.tree.Tree.chomsky_normal_form (nltk/tree/tree.py:455, default factor=\"right\"); nltk.tree.Tree.fromstring (nltk/tree/tree.py:592).\n```\n\n## Impact\n\nAn attacker who can influence the tree that an application normalizes to Chomsky Normal Form causes sustained single-threaded CPU consumption (availability loss). The path is network-reachable (AV:N) and needs no privileges or user interaction (PR:N, UI:N). Because the cost grows quadratically with the attacker-chosen child count, roughly 1.5 MB of treebank input costs about 14 seconds on one core and scales as N^2 above that. Confidentiality and integrity are not affected. The NLTK regular-expression wall-clock timeout wraps regex matching only and does not wrap this pure-Python list loop.\n\n## Proof of Concept\n\n```text\nEnvironment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree.\n```\n\n```python\nimport time\nfrom nltk.tree import Tree\n\nfor N in (80000, 160000, 320000):\n    s = \"(S \" + \"(A a)\" * N + \")\"\n    t = Tree.fromstring(s)\n    start = time.perf_counter()\n    t.chomsky_normal_form()          # default factor=\"right\"\n    print(\"right\", N, round(time.perf_counter() - start, 3), \"s\")\n```\n\n```text\nright (default):  N=80000 1.972s | N=160000 5.004s (2.54x) | N=320000 14.518s (2.90x)   -\u003e super-linear\nleft  (control):  N=80000 1.399s | N=160000 2.731s (1.95x) | N=320000  5.379s (1.97x)   -\u003e linear\n```\n\n## Attack Chain\n\n1. **Exposure:** An application parses an attacker-influenced treebank string with the public `Tree.fromstring` and normalizes it with `Tree.chomsky_normal_form()`.\n2. **Control:** The attacker controls the number of children of a node (a wide flat tree such as `(S (A a)(A a)...(A a))`); no child-count cap exists in `fromstring` or the transform.\n3. **Path:** `Tree.chomsky_normal_form` delegates to `nltk.tree.transforms.chomsky_normal_form` with the default `factor=\"right\"`.\n4. **Guard:** None. There is no width bound on the loop, and the regex match timeout does not wrap this pure-Python list operation.\n5. **Primitive:** `curNode[0:] = [nodeCopy.pop(0), newNode]` performs an O(N) front shift on each of N iterations.\n6. **Result:** O(N^2) single-core CPU exhaustion; roughly 1.5 MB of input costs about 14 seconds and scales quadratically, blocking the processing thread.\n\n## Bypass Evidence\n\nThere is no guard to bypass on this path: neither `Tree.fromstring` nor `chomsky_normal_form` caps the child count, and the regular-expression wall-clock timeout wraps only regex matching, not this list loop. The finding was confirmed by fresh timing that isolates the cause: the right-factor default and the left-factor branch build the identical bounded head strings and copy the node once, so the only differing term is `pop(0)` versus `pop()`. The measured right-versus-left divergence grows with N (right rises toward a 4x per-doubling ratio while left holds near 2x), which proves a quadratic component beyond the shared linear costs. A relevant corroboration is that the inverse transform `un_chomsky_normal_form` was already rewritten to a single linear pass to remove exactly this quadratic class (see the comment at nltk/tree/transforms.py:195-201), while the forward default path retained the `pop(0)` idiom. The strongest disproof attempt (that the head-string join dominates and is linear) fails because that join is bounded and present in both branches and therefore cannot explain the branch-dependent quadratic growth.\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, https://pypi.org/pypi/nltk/json)`\n- `Fix status: 3.10.4`\n\nThe right-factor `pop(0)` idiom ships in every release carrying this transform and is present in the current latest published release, 3.10.3. The lower boundary was not bisected, so the introducing version is left open.\n\n## Suggested Fix\n\nRewrite the right-factor binarization to avoid removing from the front of a list: iterate the children with an index cursor or a `collections.deque` so each step is constant time, mirroring the linear rebuild already applied to `un_chomsky_normal_form`. As defense in depth, bound the child count accepted for normalization and raise a clear error past a configurable maximum. No configuration-only mitigation removes the exposure for a service that normalizes untrusted trees; until a fix ships, callers should cap accepted tree width and run the transform under a CPU or time budget in an isolated worker.\n\nReported by zx (GitHub: @manus-pi).\n\n\n## Fix status (2026-09-28)\n\nPR: #3909 \"Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)\", merged 2026-09-23, merge commit 2f53e20ce on develop.\n\nFix commits: 457ebe349 (linear front consume in chomsky_normal_form) and 677857dca (refuse a binarisation that would nest a tree beyond MAX_TREE_DEPTH). Follow-up #3917 (merge 9ba132e43, commit f0686dea6) walks Tree equality and conversion with an explicit stack so the deep-tree tests pass on Python 3.10 and 3.11.\n\nProbe: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; verdict on develop 2fa3f48fe: FIXED (chomsky_normal_form scales 5.1x over a 4x input).",
  "id": "BREW-acronym-CVE-2026-126298",
  "modified": "2026-11-14T09:40:04Z",
  "published": "2026-11-14T09:40:04Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/security/advisories/GHSA-r53h-rw34-8h97"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-126298"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/pull/3909"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/commit/457ebe349f8dd8080224f76a64aff806dd437057"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/commit/677857dcafd84e4591865d976b562a27dfde566e"
    },
    {
      "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-before-3.10.4-quadratic-cpu-denial-of-service-via-tree-chomsky-normal-form"
    }
  ],
  "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:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)",
  "upstream": [
    "GHSA-r53h-rw34-8h97",
    "CVE-2026-126298"
  ]
}

CVE-2026-126298 (GCVE-0-2026-126298)

Vulnerability from cvelistv5 – Published: 2026-11-13 09:36 – Updated: 2026-11-13 22:30

Title

NLTK before 3.10.4 Quadratic CPU Denial of Service via Tree.chomsky_normal_form

Summary

NLTK before 3.10.4 contains a denial of service vulnerability in Tree.chomsky_normal_form that allows remote attackers to exhaust CPU through quadratic-time right-factor binarization using list.pop(0). Attackers can supply a wide flat treebank tree parsed by Tree.fromstring to force tens of seconds of single-threaded CPU consumption, blocking the processing thread.

Severity

8.7 (High)


                        
                          CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N

7.5 (High)


                        
                          CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

SSVC

Exploitation: none Automatable: yes Technical Impact: partial

CISA Coordinator · CISA-ADP (v2.0.3)

Decision recorded 2026-11-13 16:34 UTC

CWE

CWE-400 - Uncontrolled Resource Consumption

Assigner

VulnCheck CNA under the mitre root

CNA scorecard B 84/100 over 8184 records in the last 180 days details

References

2 references

URL	Tags
https://github.com/nltk/nltk/security/advisories/…	vendor-advisory
https://www.vulncheck.com/advisories/nltk-before-…	third-party-advisory

Impacted products

1 product

Vendor	Product	Version
nltk	nltk	Affected: 0 , < 3.10.4 (semver) Unaffected: 3.10.4 (semver) cpe:2.3:a:nltk:nltk::::::::

Date Public

2026-10-26 00:00

Credits

manus-pi manus-use

Show details on NVD website

JSON

To clipboard

{
  "containers": {
    "adp": [
      {
        "metrics": [
          {
            "other": {
              "content": {
                "id": "CVE-2026-126298",
                "options": [
                  {
                    "Exploitation": "none"
                  },
                  {
                    "Automatable": "yes"
                  },
                  {
                    "Technical Impact": "partial"
                  }
                ],
                "role": "CISA Coordinator",
                "timestamp": "2026-11-13T16:34:33.596773Z",
                "version": "2.0.3"
              },
              "type": "ssvc"
            }
          }
        ],
        "providerMetadata": {
          "dateUpdated": "2026-11-13T22:30:00.165Z",
          "orgId": "134c704f-9b21-4f2e-91b3-4a467353bcc0",
          "shortName": "CISA-ADP"
        },
        "title": "CISA ADP Vulnrichment"
      }
    ],
    "cna": {
      "affected": [
        {
          "defaultStatus": "unaffected",
          "packageURL": "pkg:pypi/nltk",
          "product": "nltk",
          "vendor": "nltk",
          "versions": [
            {
              "lessThan": "3.10.4",
              "status": "affected",
              "version": "0",
              "versionType": "semver"
            },
            {
              "status": "unaffected",
              "version": "3.10.4",
              "versionType": "semver"
            }
          ]
        }
      ],
      "cpeApplicability": [
        {
          "nodes": [
            {
              "cpeMatch": [
                {
                  "criteria": "cpe:2.3:a:nltk:nltk:*:*:*:*:*:*:*:*",
                  "versionEndExcluding": "3.10.4",
                  "vulnerable": true
                }
              ],
              "negate": false,
              "operator": "OR"
            }
          ]
        }
      ],
      "credits": [
        {
          "lang": "en",
          "type": "reporter",
          "value": "manus-pi"
        },
        {
          "lang": "en",
          "type": "reporter",
          "value": "manus-use"
        }
      ],
      "datePublic": "2026-10-26T00:00:00.000Z",
      "descriptions": [
        {
          "lang": "en",
          "value": "NLTK before 3.10.4 contains a denial of service vulnerability in Tree.chomsky_normal_form that allows remote attackers to exhaust CPU through quadratic-time right-factor binarization using list.pop(0). Attackers can supply a wide flat treebank tree parsed by Tree.fromstring to force tens of seconds of single-threaded CPU consumption, blocking the processing thread."
        }
      ],
      "metrics": [
        {
          "cvssV4_0": {
            "attackComplexity": "LOW",
            "attackRequirements": "NONE",
            "attackVector": "NETWORK",
            "baseScore": 8.7,
            "baseSeverity": "HIGH",
            "privilegesRequired": "NONE",
            "subAvailabilityImpact": "NONE",
            "subConfidentialityImpact": "NONE",
            "subIntegrityImpact": "NONE",
            "userInteraction": "NONE",
            "vectorString": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
            "version": "4.0",
            "vulnAvailabilityImpact": "HIGH",
            "vulnConfidentialityImpact": "NONE",
            "vulnIntegrityImpact": "NONE"
          },
          "format": "CVSS"
        },
        {
          "cvssV3_1": {
            "attackComplexity": "LOW",
            "attackVector": "NETWORK",
            "availabilityImpact": "HIGH",
            "baseScore": 7.5,
            "baseSeverity": "HIGH",
            "confidentialityImpact": "NONE",
            "integrityImpact": "NONE",
            "privilegesRequired": "NONE",
            "scope": "UNCHANGED",
            "userInteraction": "NONE",
            "vectorString": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
            "version": "3.1"
          },
          "format": "CVSS"
        }
      ],
      "problemTypes": [
        {
          "descriptions": [
            {
              "cweId": "CWE-400",
              "description": "Uncontrolled Resource Consumption",
              "lang": "en",
              "type": "CWE"
            }
          ]
        }
      ],
      "providerMetadata": {
        "dateUpdated": "2026-11-13T09:36:27.213Z",
        "orgId": "83251b91-4cc7-4094-a5c7-464a1b83ea10",
        "shortName": "VulnCheck"
      },
      "references": [
        {
          "name": "GitHub Security Advisory (GHSA-r53h-rw34-8h97)",
          "tags": [
            "vendor-advisory"
          ],
          "url": "https://github.com/nltk/nltk/security/advisories/GHSA-r53h-rw34-8h97"
        },
        {
          "name": "VulnCheck Advisory: NLTK before 3.10.4 Quadratic CPU Denial of Service via Tree.chomsky_normal_form",
          "tags": [
            "third-party-advisory"
          ],
          "url": "https://www.vulncheck.com/advisories/nltk-before-3.10.4-quadratic-cpu-denial-of-service-via-tree-chomsky-normal-form"
        }
      ],
      "title": "NLTK before 3.10.4 Quadratic CPU Denial of Service via Tree.chomsky_normal_form",
      "x_generator": {
        "engine": "vulncheck-endgame"
      }
    }
  },
  "cveMetadata": {
    "assignerOrgId": "83251b91-4cc7-4094-a5c7-464a1b83ea10",
    "assignerShortName": "VulnCheck",
    "cveId": "CVE-2026-126298",
    "datePublished": "2026-11-13T09:36:27.213Z",
    "dateReserved": "2026-11-10T20:15:54.612Z",
    "dateUpdated": "2026-11-13T22:30:00.165Z",
    "state": "PUBLISHED"
  },
  "dataType": "CVE_RECORD",
  "dataVersion": "5.2"
}

GHSA-R53H-RW34-8H97

Vulnerability from github – Published: 2026-11-14 00:07 – Updated: 2026-11-14 00:07

Summary

NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)

Details

Summary

Root Cause

Affected function:
- nltk.tree.transforms.chomsky_normal_form (nltk/tree/transforms.py; right-factor sink at line 168, O(1) left control at line 179)
Public entry points: nltk.tree.Tree.chomsky_normal_form (nltk/tree/tree.py:455, default factor="right"); nltk.tree.Tree.fromstring (nltk/tree/tree.py:592).

Impact

Proof of Concept

Environment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree.

import time
from nltk.tree import Tree

for N in (80000, 160000, 320000):
    s = "(S " + "(A a)" * N + ")"
    t = Tree.fromstring(s)
    start = time.perf_counter()
    t.chomsky_normal_form()          # default factor="right"
    print("right", N, round(time.perf_counter() - start, 3), "s")

right (default):  N=80000 1.972s | N=160000 5.004s (2.54x) | N=320000 14.518s (2.90x)   -> super-linear
left  (control):  N=80000 1.399s | N=160000 2.731s (1.95x) | N=320000  5.379s (1.97x)   -> linear

Attack Chain

Exposure: An application parses an attacker-influenced treebank string with the public Tree.fromstring and normalizes it with Tree.chomsky_normal_form().
Control: The attacker controls the number of children of a node (a wide flat tree such as (S (A a)(A a)...(A a))); no child-count cap exists in fromstring or the transform.
Path: Tree.chomsky_normal_form delegates to nltk.tree.transforms.chomsky_normal_form with the default factor="right".
Guard: None. There is no width bound on the loop, and the regex match timeout does not wrap this pure-Python list operation.
Primitive: curNode[0:] = [nodeCopy.pop(0), newNode] performs an O(N) front shift on each of N iterations.
Result: O(N^2) single-core CPU exhaustion; roughly 1.5 MB of input costs about 14 seconds and scales quadratically, blocking the processing thread.

Bypass Evidence

Affected Versions

Ecosystem: PyPI (pip)
Package: nltk
Confirmed affected range: <= 3.10.3
Latest release checked: 3.10.3 (PyPI, https://pypi.org/pypi/nltk/json)
Fix status: 3.10.4

Suggested Fix

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

Fix status (2026-09-28)

PR: #3909 "Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)", merged 2026-09-23, merge commit 2f53e20ce on develop.

Probe: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; verdict on develop 2fa3f48fe: FIXED (chomsky_normal_form scales 5.1x over a 4x input).

Severity

7.5 (High)


                  
                    CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

Show details on source website

JSON

To clipboard

{
  "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-126298"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-400",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-11-14T00:07:59Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "## Summary\n\n`Tree.chomsky_normal_form()` binarizes a parse tree and defaults to right factoring. For a node with N children the right-factor branch repeatedly removes the first element of a working list with `list.pop(0)`, which shifts all remaining elements each time, so binarizing one wide node costs O(N^2). An application that converts an attacker-supplied treebank tree to Chomsky Normal Form can be forced into tens of seconds of single-threaded CPU by one wide flat tree. No authentication or user interaction is required.\n\n## Root Cause\n\nIn the default right-factor branch the transform executes `curNode[0:] = [nodeCopy.pop(0), newNode]` inside a loop over the N children of a node. `list.pop(0)` is O(len) because it shifts every remaining element down by one; performed N-2 times over a shrinking length-N list this sums to O(N^2). The left-factor branch instead uses `nodeCopy.pop()` (removing the last element), which is O(1) and linear overall, so the two branches differ only by this front-versus-back removal. No cap is placed on the child count of a node, and the public `Tree.fromstring` parser accepts an arbitrarily wide bracketed tree.\n\n```text\nAffected function:\n- nltk.tree.transforms.chomsky_normal_form (nltk/tree/transforms.py; right-factor sink at line 168, O(1) left control at line 179)\nPublic entry points: nltk.tree.Tree.chomsky_normal_form (nltk/tree/tree.py:455, default factor=\"right\"); nltk.tree.Tree.fromstring (nltk/tree/tree.py:592).\n```\n\n## Impact\n\nAn attacker who can influence the tree that an application normalizes to Chomsky Normal Form causes sustained single-threaded CPU consumption (availability loss). The path is network-reachable (AV:N) and needs no privileges or user interaction (PR:N, UI:N). Because the cost grows quadratically with the attacker-chosen child count, roughly 1.5 MB of treebank input costs about 14 seconds on one core and scales as N^2 above that. Confidentiality and integrity are not affected. The NLTK regular-expression wall-clock timeout wraps regex matching only and does not wrap this pure-Python list loop.\n\n## Proof of Concept\n\n```text\nEnvironment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree.\n```\n\n```python\nimport time\nfrom nltk.tree import Tree\n\nfor N in (80000, 160000, 320000):\n    s = \"(S \" + \"(A a)\" * N + \")\"\n    t = Tree.fromstring(s)\n    start = time.perf_counter()\n    t.chomsky_normal_form()          # default factor=\"right\"\n    print(\"right\", N, round(time.perf_counter() - start, 3), \"s\")\n```\n\n```text\nright (default):  N=80000 1.972s | N=160000 5.004s (2.54x) | N=320000 14.518s (2.90x)   -\u003e super-linear\nleft  (control):  N=80000 1.399s | N=160000 2.731s (1.95x) | N=320000  5.379s (1.97x)   -\u003e linear\n```\n\n## Attack Chain\n\n1. **Exposure:** An application parses an attacker-influenced treebank string with the public `Tree.fromstring` and normalizes it with `Tree.chomsky_normal_form()`.\n2. **Control:** The attacker controls the number of children of a node (a wide flat tree such as `(S (A a)(A a)...(A a))`); no child-count cap exists in `fromstring` or the transform.\n3. **Path:** `Tree.chomsky_normal_form` delegates to `nltk.tree.transforms.chomsky_normal_form` with the default `factor=\"right\"`.\n4. **Guard:** None. There is no width bound on the loop, and the regex match timeout does not wrap this pure-Python list operation.\n5. **Primitive:** `curNode[0:] = [nodeCopy.pop(0), newNode]` performs an O(N) front shift on each of N iterations.\n6. **Result:** O(N^2) single-core CPU exhaustion; roughly 1.5 MB of input costs about 14 seconds and scales quadratically, blocking the processing thread.\n\n## Bypass Evidence\n\nThere is no guard to bypass on this path: neither `Tree.fromstring` nor `chomsky_normal_form` caps the child count, and the regular-expression wall-clock timeout wraps only regex matching, not this list loop. The finding was confirmed by fresh timing that isolates the cause: the right-factor default and the left-factor branch build the identical bounded head strings and copy the node once, so the only differing term is `pop(0)` versus `pop()`. The measured right-versus-left divergence grows with N (right rises toward a 4x per-doubling ratio while left holds near 2x), which proves a quadratic component beyond the shared linear costs. A relevant corroboration is that the inverse transform `un_chomsky_normal_form` was already rewritten to a single linear pass to remove exactly this quadratic class (see the comment at nltk/tree/transforms.py:195-201), while the forward default path retained the `pop(0)` idiom. The strongest disproof attempt (that the head-string join dominates and is linear) fails because that join is bounded and present in both branches and therefore cannot explain the branch-dependent quadratic growth.\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, https://pypi.org/pypi/nltk/json)`\n- `Fix status: 3.10.4`\n\nThe right-factor `pop(0)` idiom ships in every release carrying this transform and is present in the current latest published release, 3.10.3. The lower boundary was not bisected, so the introducing version is left open.\n\n## Suggested Fix\n\nRewrite the right-factor binarization to avoid removing from the front of a list: iterate the children with an index cursor or a `collections.deque` so each step is constant time, mirroring the linear rebuild already applied to `un_chomsky_normal_form`. As defense in depth, bound the child count accepted for normalization and raise a clear error past a configurable maximum. No configuration-only mitigation removes the exposure for a service that normalizes untrusted trees; until a fix ships, callers should cap accepted tree width and run the transform under a CPU or time budget in an isolated worker.\n\nReported by zx (GitHub: @manus-pi).\n\n\n## Fix status (2026-09-28)\n\nPR: #3909 \"Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)\", merged 2026-09-23, merge commit 2f53e20ce on develop.\n\nFix commits: 457ebe349 (linear front consume in chomsky_normal_form) and 677857dca (refuse a binarisation that would nest a tree beyond MAX_TREE_DEPTH). Follow-up #3917 (merge 9ba132e43, commit f0686dea6) walks Tree equality and conversion with an explicit stack so the deep-tree tests pass on Python 3.10 and 3.11.\n\nProbe: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; verdict on develop 2fa3f48fe: FIXED (chomsky_normal_form scales 5.1x over a 4x input).",
  "id": "GHSA-r53h-rw34-8h97",
  "modified": "2026-11-14T00:07:59Z",
  "published": "2026-11-14T00:07:59Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/security/advisories/GHSA-r53h-rw34-8h97"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-126298"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/pull/3909"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/commit/457ebe349f8dd8080224f76a64aff806dd437057"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nltk/nltk/commit/677857dcafd84e4591865d976b562a27dfde566e"
    },
    {
      "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-before-3.10.4-quadratic-cpu-denial-of-service-via-tree-chomsky-normal-form"
    }
  ],
  "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:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "NLTK: Quadratic-time CPU denial of service in Tree.chomsky_normal_form right-factor binarization via list.pop(0)"
}

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

Order 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.

Publication & reservation Sightings KEV catalogs Other timestamps

Loading timeline…

The MITRE ATT&CK techniques below are AI-generated suggestions, inferred from the description of the vulnerability by the CIRCL/vulnerability-attack-technique-classification-roberta-base model, served locally by ML-Gateway. They have not been verified by an analyst and are provided for guidance only.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.

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.

Action not permitted

BREW-ACRONYM-CVE-2026-126298 (GHSA-R53H-RW34-8H97)

Summary

Root Cause

Impact

Proof of Concept

Attack Chain

Bypass Evidence

Affected Versions

Suggested Fix

Fix status (2026-09-28)

CVE-2026-126298 (GCVE-0-2026-126298)

GHSA-R53H-RW34-8H97

Summary

Root Cause

Impact

Proof of Concept

Attack Chain

Bypass Evidence

Affected Versions

Suggested Fix

Fix status (2026-09-28)

Tags

Sightings

Nomenclature

Vulnerability timeline

Related by attack behaviour