{"id":"GHSA-w3pv-xfw4-ghr7","summary":"NLTK: Uncontrolled recursion in semantic-logic type parser causes denial of service via nested type strings","details":"## Root Cause\nThe semantic-logic type parser `read_type` (`nltk/sem/logic.py:866`) recurses on both\nhalves of every `\u003ca,b\u003e` complex type (`nltk/sem/logic.py:882-884`) with no depth or length\nbound — only an `isinstance` assertion and a parenthesis-balance assertion. The\n`LogicParser.MAX_PARSE_DEPTH` guard (`nltk/sem/logic.py:107,294`) protects the expression\nparser but never runs on the `read_type` path, which is reached directly by the public\n`Type.fromstring` classmethod and by signature-string type checking.\n\n## Impact\nAn application that parses an untrusted type string, or type-checks an expression against\nan attacker-influenced signature, aborts with an unhandled `RecursionError`, terminating\nthe affected operation or request worker (denial of service, CWE-674). The recursion is\npure Python, yielding a catchable `RecursionError` rather than memory corruption or code\nexecution. Confidentiality and integrity are unaffected. Exposure is narrower than a\ngeneral-purpose parser because the input must reach a type-string or signature parameter.\n\n## Attack Chain\n1. The application calls `nltk.sem.logic.Type.fromstring(s)` (`nltk/sem/logic.py:736`) — or\n   `Expression.typecheck(signature)` / `Expression.fromstring(expr, type_check=True,\n   signature=...)`, which reach `read_type` for each type-string signature value\n   (`nltk/sem/logic.py:1080`) — with a deeply nested type string such as\n   `\"\u003c\" * n + \"e,e\" + \"\u003e\" * n`.\n2. `Type.fromstring` passes the string straight to `read_type` with no length or depth\n   check (only assertions on type and parenthesis balance).\n3. `read_type` recurses on both halves of each `\u003ca,b\u003e` level, consuming one stack frame per\n   nesting level; the `MAX_PARSE_DEPTH` guard on the separate `LogicParser` class does not\n   execute here.\n4. Once the depth exceeds the interpreter recursion limit, an unhandled `RecursionError`\n   propagates out of the public API.\n\n## Bypass Evidence\nRunning the shipped `read_type`/`ComplexType`/`Type` source verbatim at the default\nrecursion limit: depth 5 parses cleanly to a `ComplexType` (both assertions satisfied at\nevery level), while depth 5000 raises an unhandled `RecursionError`. The clean shallow\nparse shows the failure is depth-driven rather than an assertion failure. A code review\nconfirms the `MAX_PARSE_DEPTH` bound lives on the `LogicParser` class and is not applied to\n`read_type`, whose own module docstring for that guard explicitly names uncontrolled\nrecursion (CWE-674) as the risk it addresses.\n\n## Suggested Fix\nApply a recursion-depth bound to `read_type` (a depth argument raising a bounded\n`ValueError` past a configurable maximum), matching the intent of the existing\n`LogicParser.MAX_PARSE_DEPTH` guard so that both the expression and type-string paths are\nprotected.\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: 2f4f0d47e (nltk/sem/logic.py: read_type is bounded by LogicParser.MAX_PARSE_DEPTH) with a8036c5e7 (fixes a NameError in that bound).\n\nProbe: nltk/test/unit/security_probes/ghsa_w3pv_xfw4_ghr7.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded (LogicalExpressionException)).\n\nRelease: none yet; no release tag contains e521ecafc.","aliases":["CVE-2026-129226"],"modified":"2026-11-20T00:00:04.082273888Z","published":"2026-11-19T23:51:48Z","database_specific":{"cwe_ids":["CWE-674"],"severity":"MODERATE","github_reviewed":true,"github_reviewed_at":"2026-11-19T23:51:48Z","nvd_published_at":"2026-11-19T18:18:07Z"},"references":[{"type":"WEB","url":"https://github.com/nltk/nltk/security/advisories/GHSA-w3pv-xfw4-ghr7"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-129226"},{"type":"WEB","url":"https://github.com/nltk/nltk/pull/3885"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/2f4f0d47e2c452c89cabc2a5f761332d51066ea8"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/a8036c5e7f820ac09c96b969d6e7f19bfa6e6aeb"},{"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-w3pv-xfw4-ghr7/GHSA-w3pv-xfw4-ghr7.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"}]}