NLTK: resource exhaustion
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.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,...
Affected versions
| Package | Affected | Fixed in |
|---|---|---|
| nltk PyPI | < 3.10.4 | 3.10.4 |
Details and references
## 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.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 ```text Environment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree. ``` ```python 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") ``` ```text 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 1. **Exposure:** An application parses an attacker-influenced treebank string with the public `Tree.fromstring` and normalizes it with `Tree.chomsky_normal_form()`. 2. **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. 3. **Path:** `Tree.chomsky_normal_form` delegates to `nltk.tree.transforms.chomsky_normal_form` with the default `factor="right"`. 4. **Guard:** None. There is no width bound on the loop, and the regex match timeout does not wrap this pure-Python list operation. 5. **Primitive:** `curNode[0:] = [nodeCopy.pop(0), newNode]` performs an O(N) front shift on each of N iterations. 6. **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 bo
- CVSS 3.1
- CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
- Severity from
- GitHub (reviewed advisory)
- Weakness
- CWE-400, CWE-407
- Also known as
- CVE-2026-126298
- github.com/nltk/nltk/security/advisories/GHSA-r53h-rw34-8h97
- nvd.nist.gov/vuln/detail/CVE-2026-126298
- github.com/nltk/nltk/pull/3909
- github.com/nltk/nltk/commit/457ebe349f8dd8080224f76a64aff806dd437057
- github.com/nltk/nltk/commit/677857dcafd84e4591865d976b562a27dfde566e
- github.com/nltk/nltk
- github.com/nltk/nltk/releases/tag/v3.10.4
- www.vulncheck.com/advisories/nltk-before-3.10.4-quadratic-cpu-denial-of-service-via-tree-chomsky-normal-form