{"id":"GHSA-xfcv-m889-fmqg","summary":"NLTK: Uncontrolled recursion in DependencyGraph traversal causes denial of service via deep dependency chains","details":"## Root Cause\nThe dependency-graph traversal helpers recurse over dependency links without any depth\nbound or visited set. `DependencyGraph._tree` (`nltk/parse/dependencygraph.py:404`)\nrecurses once per dependency link, `triples` (`nltk/parse/dependencygraph.py:432`) is a\nrecursive generator, and `get_cycle_path` (`nltk/parse/dependencygraph.py:520`) recurses\nover dependencies. The neighbouring `contains_cycle` method was deliberately rewritten as\nan iterative depth-first search, but these sibling helpers on the public traversal path\nwere left recursive with no depth counter.\n\n## Impact\nAn application that parses an untrusted CoNLL/Malt-TAB dependency structure and then walks\nit via `tree()` or `triples()` aborts with an unhandled `RecursionError`, terminating the\naffected operation or request worker (denial of service, CWE-674). The recursion is pure\nPython, so the result is a catchable `RecursionError`, not memory corruption or code\nexecution. Confidentiality and integrity are unaffected. `get_cycle_path` additionally\nlacks a visited set and will not terminate on a genuine cycle.\n\n## Attack Chain\n1. The application constructs `DependencyGraph(conll_str)` from attacker-supplied text\n   where token *k*'s head is token *k+1*, forming a linear dependency chain of length *N*.\n   Graph construction (`_parse`) is iterative and completes without error.\n2. The application calls the public `DependencyGraph.tree()`\n   (`nltk/parse/dependencygraph.py:408`), which invokes `_tree(root)`.\n3. `_tree` recurses once per chain link with no depth guard and no visited set, consuming\n   one stack frame per link (the list comprehension costs roughly two frames per level).\n4. Once the chain length exceeds the interpreter recursion limit, an unhandled\n   `RecursionError` propagates out of the public API. `triples()` fails the same way.\n\n## Bypass Evidence\nAgainst the shipped source at the default recursion limit, a chain of length 5 walks\ncleanly through `tree()`, while a chain of length 5000 raises an unhandled\n`RecursionError`; `triples()` fails identically. The minimal trigger is roughly *N*=500\ntokens at the default recursion limit — a modest, realistic parse. Because the graph\nbuilds iteratively in both cases, the fault is isolated to the recursive traversal rather\nthan to parsing. A repository-wide search confirms no depth guard exists in this file; the\niterative rewrite was applied only to `contains_cycle`.\n\n## Suggested Fix\nConvert `_tree`, `triples`, and `get_cycle_path` to iterative traversals, or add a\nrecursion-depth bound (and, for `get_cycle_path`, a visited set) analogous to the\niterative rewrite already applied to `contains_cycle`.\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: a74682757 (nltk/parse/dependencygraph.py: _tree, tree and triples stop at MAX_DEPTH=200 with ValueError).\n\nProbe: nltk/test/unit/security_probes/ghsa_xfcv_m889_fmqg.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded in tree() (ValueError)).\n\nRelease: none yet; no release tag contains e521ecafc.","aliases":["CVE-2026-129225"],"modified":"2026-11-20T00:00:04.079126201Z","published":"2026-11-19T23:52:20Z","database_specific":{"nvd_published_at":"2026-11-19T18:18:07Z","cwe_ids":["CWE-674"],"severity":"MODERATE","github_reviewed":true,"github_reviewed_at":"2026-11-19T23:52:20Z"},"references":[{"type":"WEB","url":"https://github.com/nltk/nltk/security/advisories/GHSA-xfcv-m889-fmqg"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-129225"},{"type":"WEB","url":"https://github.com/nltk/nltk/pull/3885"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/a74682757cee8c11128ad277d2f2bd0b8e1884ff"},{"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-xfcv-m889-fmqg/GHSA-xfcv-m889-fmqg.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"}]}