{"id":"GHSA-63wh-5r5m-wxr7","summary":"NLTK: Uncontrolled recursion in Tree.fromlist causes denial of service via deeply nested list input","details":"## Root Cause\n`Tree.fromlist` (`nltk/tree/tree.py:767`) converts a nested list into a `Tree` by recursing\nonce per nesting level (`nltk/tree/tree.py:780`) with no depth bound — its only validation\nis `type(l) == list and len(l) \u003e 0`. The sibling constructor `Tree.fromstring` was hardened\nwith a `MAX_TREE_DEPTH` cap (`nltk/tree/tree.py:31,695`) that rejects adversarially deep\ninput with a bounded `ValueError`, but that guard was not applied to `fromlist`, which\nbuilds `Tree` objects identically.\n\n## Impact\nAn application that builds a `Tree` from an attacker-controlled nested list — for example\n`Tree.fromlist(json.loads(untrusted))` — aborts with an unhandled `RecursionError`,\nterminating the affected operation or request worker (denial of service, CWE-674). Any\nlater recursive traversal of an over-deep tree (`height`, `pformat`, equality) fails the\nsame way. The recursion is pure Python, yielding a catchable `RecursionError` rather than\nmemory corruption or code execution. Confidentiality and integrity are unaffected.\n\n## Attack Chain\n1. The application obtains an attacker-controlled deeply nested list, typically by decoding\n   an untrusted JSON payload, and calls `nltk.tree.Tree.fromlist(l)`.\n2. `fromlist` checks only that the argument is a non-empty list; it applies no depth cap.\n3. `fromlist` recurses once per nesting level, consuming call-stack frames; the\n   `MAX_TREE_DEPTH` guard used by `fromstring` is never invoked on this path.\n4. Once the nesting depth exceeds the interpreter recursion limit, an unhandled\n   `RecursionError` propagates out of the public API.\n\n## Bypass Evidence\nRunning the shipped `fromlist` body verbatim at the default recursion limit: depth 5 builds\ncleanly while depth 5000 raises an unhandled `RecursionError`. The realistic JSON-delivery\nobjection does not hold: CPython's C JSON decoder tolerates far deeper nesting than the\npure-Python `fromlist` recursion, so there is a wide window (measured from roughly depth 500\nup to ~1500 at the default limit) in which `json.loads` succeeds and `fromlist` is the\ncomponent that raises. Notably the `fromlist` crash threshold (~500) coincides with the\nproject's own `MAX_TREE_DEPTH = 500` — the exact depth already deemed adversarial on the\nstring path is left unbounded on the list path.\n\n## Suggested Fix\nApply the existing `MAX_TREE_DEPTH` bound (or an equivalent depth counter) inside\n`Tree.fromlist`, so the list-construction path rejects adversarially deep input with the\nsame bounded `ValueError` already raised by `Tree.fromstring`.\n\nReported by pi (GitHub: @manus-pi).\n\n## Fix status (2026-09-28)\n\nStatus: MERGED on develop (unreleased; v3.10.3 of 2026-08-12 predates the fix).\n\nPR: #3885 \"Bound recursion depth in parsers and traversal helpers\" (ekaf), merged 2026-09-11, merge commit e521ecafc on develop.\n\nFix commit: ae4c5c900 (nltk/tree/tree.py: Tree.fromlist is bounded by MAX_TREE_DEPTH with ValueError).\n\nProbe: nltk/test/unit/security_probes/ghsa_63wh_5r5m_wxr7.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded (ValueError)).\n\nRelease: none yet; no release tag contains e521ecafc.","aliases":["CVE-2026-129227"],"modified":"2026-11-20T00:00:04.076531672Z","published":"2026-11-19T23:51:08Z","database_specific":{"severity":"MODERATE","github_reviewed":true,"github_reviewed_at":"2026-11-19T23:51:08Z","nvd_published_at":"2026-11-19T18:18:07Z","cwe_ids":["CWE-674"]},"references":[{"type":"WEB","url":"https://github.com/nltk/nltk/security/advisories/GHSA-63wh-5r5m-wxr7"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-129227"},{"type":"WEB","url":"https://github.com/nltk/nltk/pull/3885"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/ae4c5c900a81608026a43bd4ed17ff048c447c8c"},{"type":"PACKAGE","url":"https://github.com/nltk/nltk"},{"type":"WEB","url":"https://github.com/nltk/nltk/releases/tag/v3.10.4"}],"affected":[{"package":{"name":"nltk","ecosystem":"PyPI","purl":"pkg:pypi/nltk"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.4"}]}],"versions":["0.8","0.9","0.9.3","0.9.4","0.9.5","0.9.6","0.9.7","0.9.8","0.9.9","2.0.1","2.0.1rc1","2.0.1rc2-git","2.0.1rc3","2.0.1rc4","2.0.2","2.0.3","2.0.4","2.0.5","2.0b4","2.0b5","2.0b6","2.0b7","2.0b8","2.0b9","3.0.0","3.0.0b1","3.0.0b2","3.0.1","3.0.2","3.0.3","3.0.4","3.0.5","3.1","3.10.0","3.10.1","3.10.2","3.10.3","3.2","3.2.1","3.2.2","3.2.3","3.2.4","3.2.5","3.3","3.4","3.4.1","3.4.2","3.4.3","3.4.4","3.4.5","3.5","3.5b1","3.6","3.6.1","3.6.2","3.6.3","3.6.4","3.6.5","3.6.6","3.6.7","3.7","3.8","3.8.1","3.9","3.9.1","3.9.2","3.9.3","3.9.4","3.9b1"],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/11/GHSA-63wh-5r5m-wxr7/GHSA-63wh-5r5m-wxr7.json","last_known_affected_version_range":"\u003c= 3.10.3"}}],"schema_version":"1.9.2","severity":[{"type":"CVSS_V3","score":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L"}]}