{"id":"GHSA-cw6x-m8jw-qmrh","summary":"NLTK: Uncontrolled recursion in nltk.featstruct.FeatStructReader causes unhandled RecursionError (DoS) via deeply nested feature-structure input","details":"### Summary\n\n`nltk.featstruct.FeatStructReader` (used by `FeatStruct(str)` and by `FeatureGrammar.fromstring()`) parses feature-structure strings such as `[a=1]` with a recursive-descent parser that has no nesting-depth limit. A small, trivially-crafted input (~700 bytes) with deeply nested brackets drives the parser past Python's recursion limit and raises an **unhandled `RecursionError`** instead of the library's normal, catchable `ValueError`/`LogicalExpressionException`. Any application that parses user-supplied feature-structure or feature-grammar text (e.g. NLP teaching tools, grammar \"playgrounds\", unification-grammar-based NLU pipelines) can be crashed by an unauthenticated input with no special privileges. This is a Denial of Service issue (CWE-674, Uncontrolled Recursion), not a memory-safety or code-execution issue.\n\nThis appears to be the same bug class as two issues already fixed elsewhere in the codebase — `nltk/jsontags.py` (`JSONTaggedDecoder.decode_obj`, guarded by `MAX_DECODE_DEPTH = 200`) and `nltk/sem/logic.py` (`LogicParser`, guarded by `MAX_PARSE_DEPTH = 200`) — but `nltk/featstruct.py` does not have an equivalent guard.\n\n### Details\n\nThe recursive call chain (current `develop` branch, `nltk/featstruct.py`):\n\n1. `FeatStructReader.fromstring()` ([`featstruct.py:2184`](nltk/featstruct.py#L2184)) calls `read_partial()` → `_read_partial()` ([`featstruct.py:2250`](nltk/featstruct.py#L2250)).\n2. `_read_partial()` dispatches to `_read_partial_featdict()`, which calls `_read_value()` ([`featstruct.py:2436`](nltk/featstruct.py#L2436)) for each feature's value.\n3. `_read_value()` calls `read_value()` ([`featstruct.py:2442`](nltk/featstruct.py#L2442)), which matches the value against `VALUE_HANDLERS` ([`featstruct.py:2478`](nltk/featstruct.py#L2478)).\n4. If the value itself starts with `[` (a nested feature structure), the matched handler is `read_fstruct_value` ([`featstruct.py:2479`](nltk/featstruct.py#L2479), defined at [`featstruct.py:2495`](nltk/featstruct.py#L2495)):\n   ```python\n   def read_fstruct_value(self, s, position, reentrances, match):\n       return self.read_partial(s, position, reentrances)\n   ```\n   This calls `read_partial()` again, which re-enters `_read_partial()` — the same function from step 1.\n\nThis closes a recursive cycle (`_read_partial → _read_value → read_value → read_fstruct_value → read_partial → _read_partial → ...`) with **no depth counter, no `MAX_*_DEPTH` constant, and no `try/except RecursionError`** anywhere in the class. Each additional `[` in the input adds one more full cycle of Python stack frames. Once the input nests deeply enough, Python's own recursion-limit protection fires and raises `RecursionError`, which is not a subclass of `ValueError` (the exception type this parser's own `_error()` helper raises for normal, well-formed parse errors) and therefore propagates uncaught through this API.\n\nFor comparison, `nltk/sem/logic.py`'s `LogicParser` was hardened against exactly this class of issue:\n```python\n#: Maximum expression-nesting depth the recursive-descent parser will\n#: descend to. Deeply nested input would otherwise recurse until Python\n#: raises an uncaught RecursionError and crashes the caller\n#: (uncontrolled recursion, CWE-674); past this depth a normal\n#: LogicalExpressionException is raised instead. Configurable.\nMAX_PARSE_DEPTH = 200\n```\n(`nltk/sem/logic.py:102-107`), and `nltk/jsontags.py`'s `JSONTaggedDecoder` similarly has `MAX_DECODE_DEPTH = 200` with an explicit depth check. `nltk/featstruct.py` has no analogous protection.\n\n`FeatureGrammar.fromstring()` (`nltk/grammar.py`) parses feature structures embedded in FCFG grammar rules via the same `FeatStructReader`, so the same crash is reachable through grammar-string parsing as well as through `FeatStruct()` directly.\n\n### PoC\n\nVerified against the current `develop` branch in a clean virtualenv (Python 3.12, NLTK installed from this checkout via `pip install -e .`):\n\n```python\nfrom nltk.featstruct import FeatStruct\n\ndepth = 167\npayload = \"[a=\" * depth + \"1\" + \"]\" * depth   # 669 bytes\nFeatStruct(payload)\n```\n\nResult:\n```\nTraceback (most recent call last):\n  ...\n  File \".../nltk/featstruct.py\", line 2310, in _read_partial_featdict\n    value, position = self._read_value(name, s, position, reentrances)\n  File \".../nltk/featstruct.py\", line 2440, in _read_value\n    return self.read_value(s, position, reentrances)\n  File \".../nltk/featstruct.py\", line 2446, in read_value\n    return handler_func(s, position, reentrances, match)\n  [... repeats ~167 times ...]\nRecursionError: maximum recursion depth exceeded\n```\n\n- Crash threshold: nesting depth 167 (binary-searched between 50 and 200).\n- Payload size: 669 bytes — fits trivially in a single HTTP request body/query parameter.\n- Time to crash: \u003c2ms — no resource exhaustion is needed, only recursion depth.\n\nMinimal reproduction (no server required):\n```bash\npython3 -c \"\nfrom nltk.featstruct import FeatStruct\nFeatStruct('[a=' * 200 + '1' + ']' * 200)\n\"\n```\n\nIllustrative server-side context (not part of NLTK itself, but representative of how the bug becomes reachable):\n```python\nfrom flask import Flask, request\nfrom nltk.featstruct import FeatStruct\n\napp = Flask(__name__)\n\n@app.route(\"/parse\", methods=[\"POST\"])\ndef parse_grammar():\n    return {\"result\": str(FeatStruct(request.json[\"grammar\"]))}\n```\nA POST of `{\"grammar\": \"[a=\" * 200 + \"1\" + \"]\" * 200}` to this endpoint raises the uncaught `RecursionError` inside the request handler.\n\n### Impact\n\n**Vulnerability type:** Denial of Service via uncontrolled recursion (CWE-674). This is not a memory-corruption bug and does not lead to code execution or data disclosure — Python's own recursion-limit safety net converts what would be a C-level stack overflow into a catchable (but here, uncaught) `RecursionError`.\n\n**Who is affected:** Any application that passes externally-supplied text into `nltk.featstruct.FeatStruct()` or `nltk.grammar.FeatureGrammar.fromstring()` — for example, NLP/computational-linguistics teaching tools, unification-grammar demo services, or NLU pipelines that accept user-authored feature grammars. This is a narrower slice of NLTK's user base than, e.g., tokenization or POS tagging, since feature-structure/unification-grammar parsing is a more specialized part of the library.\n\n**Practical severity depends on deployment:**\n- In typical WSGI-style web frameworks (Flask/Django/FastAPI behind gunicorn/uwsgi), an uncaught exception inside a request handler is caught at the framework/server boundary: the single request fails (HTTP 500), the worker process itself survives, and unaffected requests are unimpacted.\n- In single-threaded or per-task-unprotected contexts (e.g. a queue-consuming worker without per-task exception isolation), the uncaught `RecursionError` can terminate the entire process; without a process supervisor that auto-restarts it, this is a persistent outage until manually restarted. An attacker who repeats the payload can keep such a worker in a crash loop for as long as the attack continues.\n\n**Suggested fix:** Add a depth counter and a `MAX_PARSE_DEPTH`-style constant to `FeatStructReader`, mirroring the existing fix in `nltk/sem/logic.py`, and raise the library's normal `ValueError`-based parse error once the limit is exceeded instead of letting `RecursionError` propagate.","aliases":["CVE-2026-81724","PYSEC-2026-3739"],"modified":"2026-09-10T03:51:15.361788366Z","published":"2026-09-02T14:33:22Z","database_specific":{"cwe_ids":["CWE-674"],"severity":"MODERATE","github_reviewed":true,"github_reviewed_at":"2026-09-02T14:33:22Z","nvd_published_at":null},"references":[{"type":"WEB","url":"https://github.com/nltk/nltk/security/advisories/GHSA-cw6x-m8jw-qmrh"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-81724"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/43c7b78cc8ea37e5cd3a129e27e32c415ea21cf1"},{"type":"PACKAGE","url":"https://github.com/nltk/nltk"},{"type":"WEB","url":"https://github.com/nltk/nltk/releases/tag/v3.10.3"},{"type":"WEB","url":"https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3739.yaml"},{"type":"WEB","url":"https://www.vulncheck.com/advisories/nltk-before-3.10.3-denial-of-service-via-uncontrolled-recursion"}],"affected":[{"package":{"name":"nltk","ecosystem":"PyPI","purl":"pkg:pypi/nltk"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.3"}]}],"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.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":{"last_known_affected_version_range":"\u003c= 3.10.2","source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-cw6x-m8jw-qmrh/GHSA-cw6x-m8jw-qmrh.json"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V3","score":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L"},{"type":"CVSS_V4","score":"CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N"}]}