CVE-2026-126298
High 7.5No known exploitationFix availableNLTK 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
High on a 0 to 10 scale
EPSS, chance of exploitation in 30 days
Higher than 48% of scored CVEs. A prediction, not evidence.
CISA remediation deadline
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
| Vendor | Product | Affected versions | Fixed in | Per |
|---|---|---|---|---|
| Microsoft | azl4 python-nltk 1:3.9.1-9.azl4 on Azure Linux 4.0 | Not documented | Not documented | Microsoft MSRC |
| pip | nltk | all versions up to and including 3.10.3 | 3.10.4 | GitHub Advisory Database |
Timeline
Advisory
Microsoft advisory published
Advisory change
Microsoft advisory revised (2.0): Information published.
Patch
Fix documented by Microsoft MSRC
Vendor guidance and references
- Microsoft Security Update Guide (opens in a new tab)vendor-advisory
- GitHub Advisory GHSA-r53h-rw34-8h97 (opens in a new tab)github-advisory