NLTK: Uncontrolled recursion in Tree.fromlist causes denial of service via deeply nested list input
Root Cause
Tree.fromlist (nltk/tree/tree.py:767) converts a nested list into a Tree by recursing
once per nesting level (nltk/tree/tree.py:780) with no depth bound , its only validation
is type(l) == list and len(l) > 0. The sibling constructor Tree.fromstring was hardened
with a MAX_TREE_DEPTH cap (nltk/tree/tree.py:31,695) that rejects adversarially deep
input with a bounded ValueError, but that guard was not applied to fromlist, which
builds Tree objects identically.
Impact
An application that builds a Tree from an attacker-controlled nested list , for example
Tree.fromlist(json.loads(untrusted)) , aborts with an unhandled RecursionError,
terminating the affected operation or request worker (denial of service, CWE-674). Any
later recursive traversal of an over-deep tree (height, pformat, equality) fails the
same way. The recursion is pure Python, yielding a catchable RecursionError rather than
memory corruption or code execution. Confidentiality and integrity are unaffected.
Attack Chain
1. The application obtains an attacker-controlled deeply nested list, typically by decoding
an untrusted JSON payload, and calls nltk.tree.Tree.fromlist(l).
2. fromlist checks only that the argument is a non-empty list; it applies no depth cap.
3. fromlist recurses once per nesting level, consuming call-stack frames; the...
Affected versions
| Package | Affected | Fixed in |
|---|---|---|
| nltk PyPI | < 3.10.4 | 3.10.4 |
Details and references
## Root Cause `Tree.fromlist` (`nltk/tree/tree.py:767`) converts a nested list into a `Tree` by recursing once per nesting level (`nltk/tree/tree.py:780`) with no depth bound , its only validation is `type(l) == list and len(l) > 0`. The sibling constructor `Tree.fromstring` was hardened with a `MAX_TREE_DEPTH` cap (`nltk/tree/tree.py:31,695`) that rejects adversarially deep input with a bounded `ValueError`, but that guard was not applied to `fromlist`, which builds `Tree` objects identically. ## Impact An application that builds a `Tree` from an attacker-controlled nested list , for example `Tree.fromlist(json.loads(untrusted))` , aborts with an unhandled `RecursionError`, terminating the affected operation or request worker (denial of service, CWE-674). Any later recursive traversal of an over-deep tree (`height`, `pformat`, equality) fails the same way. The recursion is pure Python, yielding a catchable `RecursionError` rather than memory corruption or code execution. Confidentiality and integrity are unaffected. ## Attack Chain 1. The application obtains an attacker-controlled deeply nested list, typically by decoding an untrusted JSON payload, and calls `nltk.tree.Tree.fromlist(l)`. 2. `fromlist` checks only that the argument is a non-empty list; it applies no depth cap. 3. `fromlist` recurses once per nesting level, consuming call-stack frames; the `MAX_TREE_DEPTH` guard used by `fromstring` is never invoked on this path. 4. Once the nesting depth exceeds the interpreter recursion limit, an unhandled `RecursionError` propagates out of the public API. ## Bypass Evidence Running the shipped `fromlist` body verbatim at the default recursion limit: depth 5 builds cleanly while depth 5000 raises an unhandled `RecursionError`. The realistic JSON-delivery objection does not hold: CPython's C JSON decoder tolerates far deeper nesting than the pure-Python `fromlist` recursion, so there is a wide window (measured from roughly depth 500 up to ~1500 at the default limit) in which `json.loads` succeeds and `fromlist` is the component that raises. Notably the `fromlist` crash threshold (~500) coincides with the project's own `MAX_TREE_DEPTH = 500` , the exact depth already deemed adversarial on the string path is left unbounded on the list path. ## Suggested Fix Apply the existing `MAX_TREE_DEPTH` bound (or an equivalent depth counter) inside `Tree.fromlist`, so the list-construction path rejects adversarially deep input with the same bounded `ValueError` already raised by `Tree.fromstring`. Reported by pi (GitHub: @manus-pi). ## Fix status (2026-09-28) Status: MERGED on develop (unreleased; v3.10.3 of 2026-08-12 predates the fix). PR: #3885 "Bound recursion depth in parsers and traversal helpers" (ekaf), merged 2026-09-11, merge commit e521ecafc on develop. Fix commit: ae4c5c900 (nltk/tree/tree.py: Tree.fromlist is bounded by MAX_TREE_DEPTH with ValueError). Probe: nltk/test/unit/security_probes/ghsa_63wh_5r5m_wxr7.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded (ValueError)). Release: none yet; no release tag contains e521ecafc.
- CVSS 3.1
- CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
- Severity from
- GitHub (reviewed advisory)
- Weakness
- CWE-674
- Also known as
- CVE-2026-129227