Skip to content
Threat Brief

← All advisories

CVE-2026-126298

High 7.5No known exploitationFix available

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

Vendor advisory: GHSA-r53h-rw34-8h97

Record last updated

CVSS score

7.5

High on a 0 to 10 scale

EPSS, chance of exploitation in 30 days

0.6%

Higher than 48% of scored CVEs. A prediction, not evidence.

CISA remediation deadline

None

Not in the KEV catalog

Description

## 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. ```text Affected function: - nltk.tree.trans…

Weakness: CWE-400, CWE-407

Patching and mitigation

Patch status
Fix available (source: Microsoft MSRC)
Fix documented (source date)
Mitigation
None documented
Vendor guidance
msrc.microsoft.com (opens in a new tab)

Affected products

VendorProductAffected versionsFixed inPer
Microsoftazl4 python-nltk 1:3.9.1-9.azl4 on Azure Linux 4.0Not documentedNot documentedMicrosoft MSRC
pipnltkall versions up to and including 3.10.33.10.4GitHub Advisory Database

Timeline

  1. Advisory

    Microsoft advisory published

    Source: Microsoft MSRC (opens in a new tab)

  2. Advisory change

    Microsoft advisory revised (2.0): Information published.

    Source: Microsoft MSRC (opens in a new tab)

  3. Patch

    Fix documented by Microsoft MSRC

    Source: Microsoft MSRC (opens in a new tab)

Vendor guidance and references