{"id":"GHSA-3h95-x772-4765","summary":"NLTK: Uncontrolled recursion in CCG lexicon parser causes denial of service via deeply nested category input","details":"## Root Cause\nThe CCG lexicon parser recurses on nested parenthesised categories without any depth\nbound. `matchBrackets` (`nltk/ccg/lexicon.py:154`) calls itself once per nested `(`, and\n`augParseCategory` (`nltk/ccg/lexicon.py:228,242`) recurses once per bracketed\nsub-category. Neither function tracks recursion depth nor checks\n`sys.getrecursionlimit()`, and the public entry point `fromstring`\n(`nltk/ccg/lexicon.py:252`, also re-exported via `nltk.ccg.chart.fromstring`) applies no\nlength or nesting cap before handing the text to the parser.\n\n## Impact\nAn application that parses an untrusted lexicon string aborts with an unhandled\n`RecursionError`, terminating the affected parse operation or request worker\n(denial of service, CWE-674). The recursion is pure Python, so CPython raises a catchable\n`RecursionError` rather than crashing the process; there is no memory-corruption or\ncode-execution primitive. Confidentiality and integrity are unaffected. Plausibly, a\nservice that does not wrap the parse in a handler will surface the error to the caller and\ndrop the in-flight request.\n\n## Attack Chain\n1. The application calls `nltk.ccg.lexicon.fromstring(lex_str)` with attacker-supplied\n   text such as `\":- S\\nw =\u003e \" + \"(\" * 2000 + \"S\" + \")\" * 2000 + \"\\n\"`.\n2. `fromstring` splits the input into lines; `LEX_RE`/`RHS_RE`\n   (`nltk/ccg/lexicon.py:275-276`) match and route the parenthesised category into\n   `augParseCategory` (`nltk/ccg/lexicon.py:277`) with no depth or length guard.\n3. Because the category starts with `(`, `nextCategory` dispatches to `matchBrackets`,\n   which recurses once per nested `(`; `augParseCategory` recurses once per bracketed\n   sub-category. Each nesting level consumes call-stack frames.\n4. Once the depth exceeds the interpreter recursion limit, an unhandled `RecursionError`\n   propagates out of the public API and aborts the parse.\n\n## Bypass Evidence\nRunning the dependency-free `matchBrackets` body verbatim from the shipped source at the\ndefault recursion limit (1000): a well-formed balanced input at depth 5 and 500 parses\ncleanly, while depth 2000 and 5000 raise an unhandled `RecursionError`. Because shallow,\nbalanced input parses without error, the failure is depth-driven rather than a generic\nparse error. The crash triggers near ~1000 nesting levels at the default limit, so the\npayload need not be extreme. A repository-wide search confirms no depth/recursion guard\nexists anywhere under `nltk/ccg/` (the only recent change to this file routed regexes\nthrough `nltk.redos` and added no recursion bound).\n\n## Suggested Fix\nAdd a recursion-depth choke point on the lexicon-parsing path — for example a depth\ncounter that raises a bounded `ValueError` past a configurable maximum, mirroring the\nexisting guards on `FeatStructReader` (`nltk/featstruct.py`), `Tree.fromstring`\n(`MAX_TREE_DEPTH`, `nltk/tree/tree.py`), and `LogicParser` (`MAX_PARSE_DEPTH`,\n`nltk/sem/logic.py`).\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: 30e93eb7b (nltk/ccg/lexicon.py: matchBrackets and the category parser stop at MAX_PARSE_DEPTH=500 with ValueError).\n\nProbe: nltk/test/unit/security_probes/ghsa_3h95_x772_4765.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-129224"],"modified":"2026-11-20T00:00:04.077530309Z","published":"2026-11-19T23:52:54Z","database_specific":{"severity":"MODERATE","github_reviewed":true,"github_reviewed_at":"2026-11-19T23:52:54Z","nvd_published_at":"2026-11-19T19:17:21Z","cwe_ids":["CWE-674"]},"references":[{"type":"WEB","url":"https://github.com/nltk/nltk/security/advisories/GHSA-3h95-x772-4765"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-129224"},{"type":"WEB","url":"https://github.com/nltk/nltk/pull/3885"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/30e93eb7b69021293e019042fe0cedb99c95b054"},{"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-3h95-x772-4765/GHSA-3h95-x772-4765.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"}]}