Medium

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

  • Disclosed: 19.11.2026
  • Updated: 20.11.2026 01:17

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.

Affected software

Click a technology to see all vulnerabilities affecting it.

PlatformPackageVulnerable versionsFixed in
Python (PyPI) nltk < 3.10.4 3.10.4

References

CVSS score 5.3/10
CVSS vector
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Weakness (CWE)
CWE-674
Platform
Python (PyPI)
Package
nltk
Disclosed
19.11.2026
Updated
20.11.2026 01:17

Sources and licenses

OSV / GitHub Advisory Database - GHSA-3h95-x772-4765 - CC BY 4.0

Vulnerability history: nltk

All published vulnerabilities of this package (Python (PyPI)), newest first. Shows whether this is a one-off slip or a package that needs watching.

All (79) in the archive
Total entries
79
First → latest
08.2019 11.2026
Without a fix
5
Exploited in attacks
0

Severity breakdown

  • Critical 5
  • High 41
  • Medium 31
  • Low 2

Disclosures per year

  1. 2019: 1
  2. 2020: 0
  3. 2021: 2
  4. 2022: 1
  5. 2023: 0
  6. 2024: 1
  7. 2025: 0
  8. 2026: 74
Severity:
  1. NLTK: Uncontrolled recursion in CCG lexicon parser causes denial of service via deeply nested category input this entry
    Medium · 5.3 CVE-2026-129224 < 3.10.4 3.10.4
  2. High CVE-2026-79674 < 3.10.3 3.10.3
  3. High · 8.8 CVE-2026-71513 >= 3.10.0, < 3.10.3 3.10.3
  4. High · 5.9 CVE-2026-62385 < 3.10.0 3.10.0
  5. High · 7.5 CVE-2026-33231 < 3.9.4 3.9.4
  6. High · 8.6 CVE-2026-0847 < 3.9.3 3.9.3
  7. Critical · 10.0 CVE-2025-14009 < 3.9.3 3.9.3
  8. High · 7.5 CVE-2024-39705 < 3.9 3.9
  9. High · 7.5 CVE-2021-3842 < 3.6.6 3.6.6
  10. High · 7.5 CVE-2021-3828 < 3.6.4 3.6.4
  11. High · 7.5 CVE-2019-14751 < 3.4.5 3.4.5

Know which vulnerabilities affect your application

With the DockRay integration and software inventory enabled, DockRay checks reported component versions against known vulnerabilities and notifies you about confirmed matches. Coverage depends on the supported technology and available advisory data.

Connect your application
DockRay newsletter

Application security in your inbox

Important vulnerabilities, actionable guidance and practical advice for your applications. Choose your technologies and follow what matters to your project.

  • A daily digest of new vulnerabilities, critical ones included.
  • Notifications about important updates.
  • Practical advice on application security and monitoring.

Leave empty to receive updates for every technology.

Free to subscribe. Unsubscribe with one click in any email.