AI and data stack advisories

Severe, 6 weeks2431Projects328

2431 severe, 6 weeks · 328 projects

NLTKGHSA-3h95-x772-4765

NLTK: Uncontrolled recursion in CCG lexicon parser causes denial of service via deeply nested category input

NLTK

CVE-2026-129224 · Published Nov 19, 2026 · updated Nov 20, 2026

Medium5.3
Fix: upgrade to 3.10.4 or later
GitHub advisory

Root Cause

The CCG lexicon parser recurses on nested parenthesised categories without any depth

bound. matchBrackets (nltk/ccg/lexicon.py:154) calls itself once per nested (, and

augParseCategory (nltk/ccg/lexicon.py:228,242) recurses once per bracketed

sub-category. Neither function tracks recursion depth nor checks

sys.getrecursionlimit(), and the public entry point fromstring

(nltk/ccg/lexicon.py:252, also re-exported via nltk.ccg.chart.fromstring) applies no

length or nesting cap before handing the text to the parser.

Impact

An application that parses an untrusted lexicon string aborts with an unhandled

RecursionError, terminating the affected parse operation or request worker

(denial of service, CWE-674). The recursion is pure Python, so CPython raises a catchable

RecursionError rather than crashing the process; there is no memory-corruption or

code-execution primitive. Confidentiality and integrity are unaffected. Plausibly, a

service that does not wrap the parse in a handler will surface the error to the caller and

drop the in-flight request.

Attack Chain

1. The application calls nltk.ccg.lexicon.fromstring(lex_str) with attacker-supplied

text such as ":- S\nw => " + "(" * 2000 + "S" + ")" * 2000 + "\n".

2. fromstring splits the input into lines; LEX_RE/RHS_RE

(nltk/ccg/lexicon.py:275-276) match and route the...

Affected versions

PackageAffectedFixed in
nltk
PyPI
< 3.10.43.10.4
Details and references

## Root Cause The CCG lexicon parser recurses on nested parenthesised categories without any depth bound. `matchBrackets` (`nltk/ccg/lexicon.py:154`) calls itself once per nested `(`, and `augParseCategory` (`nltk/ccg/lexicon.py:228,242`) recurses once per bracketed sub-category. Neither function tracks recursion depth nor checks `sys.getrecursionlimit()`, and the public entry point `fromstring` (`nltk/ccg/lexicon.py:252`, also re-exported via `nltk.ccg.chart.fromstring`) applies no length or nesting cap before handing the text to the parser. ## Impact An application that parses an untrusted lexicon string aborts with an unhandled `RecursionError`, terminating the affected parse operation or request worker (denial of service, CWE-674). The recursion is pure Python, so CPython raises a catchable `RecursionError` rather than crashing the process; there is no memory-corruption or code-execution primitive. Confidentiality and integrity are unaffected. Plausibly, a service that does not wrap the parse in a handler will surface the error to the caller and drop the in-flight request. ## Attack Chain 1. The application calls `nltk.ccg.lexicon.fromstring(lex_str)` with attacker-supplied text such as `":- S\nw => " + "(" * 2000 + "S" + ")" * 2000 + "\n"`. 2. `fromstring` splits the input into lines; `LEX_RE`/`RHS_RE` (`nltk/ccg/lexicon.py:275-276`) match and route the parenthesised category into `augParseCategory` (`nltk/ccg/lexicon.py:277`) with no depth or length guard. 3. Because the category starts with `(`, `nextCategory` dispatches to `matchBrackets`, which recurses once per nested `(`; `augParseCategory` recurses once per bracketed sub-category. Each nesting level consumes call-stack frames. 4. Once the depth exceeds the interpreter recursion limit, an unhandled `RecursionError` propagates out of the public API and aborts the parse. ## Bypass Evidence Running the dependency-free `matchBrackets` body verbatim from the shipped source at the default recursion limit (1000): a well-formed balanced input at depth 5 and 500 parses cleanly, while depth 2000 and 5000 raise an unhandled `RecursionError`. Because shallow, balanced input parses without error, the failure is depth-driven rather than a generic parse error. The crash triggers near ~1000 nesting levels at the default limit, so the payload need not be extreme. A repository-wide search confirms no depth/recursion guard exists anywhere under `nltk/ccg/` (the only recent change to this file routed regexes through `nltk.redos` and added no recursion bound). ## Suggested Fix Add a recursion-depth choke point on the lexicon-parsing path , for example a depth counter that raises a bounded `ValueError` past a configurable maximum, mirroring the existing guards on `FeatStructReader` (`nltk/featstruct.py`), `Tree.fromstring` (`MAX_TREE_DEPTH`, `nltk/tree/tree.py`), and `LogicParser` (`MAX_PARSE_DEPTH`, `nltk/sem/logic.py`). Reported by pi (GitHub: @manus-pi). ## Fix status (2026-09-28) Status: MERGED on develop (unreleased; v3.10.3 of 2026-08-12 predates the fix). PR: #3885 "Bound recursion depth in parsers and traversal helpers" (ekaf), merged 2026-09-11, merge commit e521ecafc on develop. Fix commit: 30e93eb7b (nltk/ccg/lexicon.py: matchBrackets and the category parser stop at MAX_PARSE_DEPTH=500 with ValueError). Probe: nltk/test/unit/security_probes/ghsa_3h95_x772_4765.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded (ValueError)). Release: none yet; no release tag contains e521ecafc.

CVSS 3.1
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Severity from
GitHub (reviewed advisory)
Weakness
CWE-674
Also known as
CVE-2026-129224

More NLTK advisories

All NLTK