NLTK: Uncontrolled recursion in CCG lexicon parser causes denial of service via deeply nested category input
Published 19 Nov 2026 · Updated 20 Nov 2026
Is your project on an affected nltk?
Look after several Python apps? Indie watches up to 15 repos, private ones too, for $5 a month. See Indie
Affected package
- Affected
- <3.10.4
- Fixed in
- 3.10.4
pip install 'nltk>=3.10.4'Details
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.
Is GHSA-3h95-x772-4765 in any of your client repos?
Checking one package by hand is fine. Checking it across forty client projects is not. NPMscan reads the lockfiles in every GitHub repo you pick, finds each project with an affected nltk, and gives you the command that fixes it.
More advisories for nltk
- HighCVE-2026-128135NLTK: ZIP package extraction follows in-root hardlinks and overwrites files outside the NLTK data root · 19 Nov 2026
- MediumCVE-2026-128136NLTK: AllowlistUnpickler does not deny numpy submodule-local file-I/O sinks · 19 Nov 2026
- MediumCVE-2026-128137NLTK corpus-reader view methods bypass the scoped root sandbox via intermediate-directory symlinks · 19 Nov 2026
- CriticalCVE-2026-128138NLTK incomplete fix: additional JVM/JAR sandbox bypass through unvalidated launcher tokens in java() command arguments · 19 Nov 2026
- HighCVE-2026-128139NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service · 19 Nov 2026
- MediumCVE-2026-128140NLTK: Downloader cyclic collection indices cause an infinite closure walk · 19 Nov 2026
References
Advisory data from OSV.dev (opens OSV.dev in a new tab), refreshed daily.