NLTK: Quadratic-time CPU denial of service in CCG lexicon parser (fromstring) on wide bracket bodies and operator chains
Summary
The public CCG lexicon parser nltk.ccg.lexicon.fromstring parses caller-influenced lexicon text with two pure-Python loops whose cost is quadratic in the input width. A service that parses an untrusted CCG lexicon string can be driven into tens of seconds of single-threaded CPU consumption by a few-megabyte input, starving the request worker. No authentication or user interaction is required.
Root Cause
matchBrackets consumes a bracket body one character at a time with inside = inside + rest[0]; rest = rest[1:]. The rest = rest[1:] tail re-slice copies the entire remaining string on every iteration, meaning a flat bracket body costs O(n^2). augParseCategory drives a while rest != "": operator loop that re-copies the regular-expression match tail (rest = app[3]) once per operator, which is also O(n^2) over a long operator chain. The parser includes a recursion-depth guard (MAX_PARSE_DEPTH = 500) that raises an error on deeply nested categories; however, both quadratic loops execute on flat input where the nesting depth remains zero, preventing the guard from firing. No limits are enforced on line length or category width before input reaches these loops.
Affected functions:
- nltk.ccg.lexicon.matchBrackets (nltk/ccg/lexicon.py:149-172; tail re-slice at line 168)
- nltk.ccg.lexicon.augParseCategory (nltk/ccg/lexicon.py:223-268; APP_RE tail re-copy at line 250)
Public entry point: nltk.ccg.lexicon.fromstring (nltk/ccg/lexicon.py:271), also re-exported as nltk.ccg.chart.fromstring.
Impact
An attacker capable of supplying input to the CCG lexicon parser can trigger sustained single-threaded CPU consumption, leading to a denial of service (availability loss). The vulnerable component is network-accessible (AV:N) and requires neither privileges nor user interaction (PR:N, UI:N). Because CPU consumption increases quadratically with attacker-controlled input size, a payload of a few megabytes can occupy tens of seconds of CPU time per core, allowing a small number of concurrent requests to exhaust worker threads. Confidentiality and integrity are unaffected. NLTK's regular-expression timeout only guards regex operations and does not cover these pure-Python slicing loops, offering no mitigation.
Proof of Concept
Environment: nltk 3.10.3, regex 2026.9.10, CPython. Run the parser on the shipped public API.
import nltk.ccg.lexicon as L
# Vector A: flat bracket body -> matchBrackets tail re-slice is O(n^2)
n = 400000
lex_a = ":- S\nw => (" + "a" * n + ")\n"
# Vector B: long operator chain -> augParseCategory tail re-copy is O(n^2)
m = 32000
lex_b = ":- a\nw => " + "a" + "/a" * m + "\n"
import time
for name, s in (("A", lex_a), ("B", lex_b)):
t = time.perf_counter()
try:
L.fromstring(s)
except Exception:
pass # downstream parse error is irrelevant; the CPU is already burned
print(name, round(time.perf_counter() - t, 3), "s")
Negative control (":- a\nw => (a/a)"): ~0.00007 s
Vector A (matchBrackets, flat body): n=50k 0.078s | 100k 0.260s | 200k 1.046s | 400k 2.083s (~4x per doubling => O(n^2))
Vector B (augParseCategory, operators): m=4k 0.078s | 8k 0.215s | 16k 0.485s | 32k 1.329s (super-linear)
Attack Chain
- Exposure: An application calls
nltk.ccg.lexicon.fromstring(lex_str)(also accessible asnltk.ccg.chart.fromstring) on lexicon text influenced by an attacker. - Control: The attacker controls the body width (characters inside a bracket) and operator-chain length, neither of which is restricted by
fromstring. - Path:
fromstringdivides input into lines and directs each category throughnextCategory, dispatching tomatchBrackets(Vector A) or to theaugParseCategoryoperator loop (Vector B). - Guard: The
MAX_PARSE_DEPTH = 500check only inspects recursion depth. Because depth is zero on flat input,if _depth > max_depthis not invoked, and width loops proceed without limits. - Primitive: The tail re-slicing
rest = rest[1:]and tail re-copyingrest = app[3]perform a quadratic number of string copy operations. - Result: Single-core CPU exhaustion occurs; a lexicon of a few megabytes consumes tens of seconds, scaling quadratically and blocking the parsing thread.
Bypass Evidence
The only protection implemented on this path is the recursion-depth guard MAX_PARSE_DEPTH = 500 (nltk/ccg/lexicon.py:22), evaluated at lexicon.py:153 and lexicon.py:228. It addresses only nesting depth and raises ValueError when deep nesting occurs. The quadratic payloads are flat: a single bracket body or operator sequence has a nesting depth of zero to one, so the depth check is bypassed while the width loops consume quadratic time. Testing against the shipped parser confirmed that payloads finish without triggering ValueError or a regex TimeoutError, scaling with a 4x factor per doubling of input size (Vector A). No line-length or category-width restriction exists on the fromstring path. CPython's in-place string concatenation fast path does not eliminate these copies because rest = rest[1:] is an unconditional copy of remaining data, as verified by the measured 4x ratio.
Affected Versions
Ecosystem: PyPI (pip)Package: nltkConfirmed affected range: <= 3.10.3Latest release checked: 3.10.3 (PyPI, https://pypi.org/pypi/nltk/json)Fix status: 3.10.4
The slicing loops exist across releases that contain the CCG lexicon parser, including release 3.10.3. The earliest affected version was not bisected.
Fix Status
- PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", open; head da55cab0e (merged develop on top of 238f81500).
- Fix commit: cf12a5e6a (in
nltk/ccg/lexicon.py,matchBrackets,nextCategory, andaugParseCategoryuse a cursor instead of tail re-slicing, the trailing capture group is removed, andMAX_PARSE_LEN=100000limits input size). - Probe:
nltk/test/unit/security_probes/ghsa_89p3_fcch_88ph.py. - Test verdict: Fixed on the PR head (scaling 4.4x across a 4x input; excess chains are rejected by
MAX_PARSE_LEN). Testing against develop 2fa3f48fe confirmed vector A (bracket body, 100k vs 400k) at 15.8x and vector B (operator chain, 8k vs 32k) at 11.3x on 4x input, indicating develop remained vulnerable prior to the fix.
Reported by zx (GitHub: @manus-pi).
What to do
Upgrade NLTK to version 3.10.4 or apply the patch in commit cf12a5e6a (PR #3753).
Suggested Workaround
As suggested by the reporter:
- Scan bracket bodies and operator chains using an index cursor into the original string (or a
collections.deque) rather than repeatedly re-slicing tails. - Apply explicit bounds on lexicon line length and category width at the
fromstringentry point, raising an error when exceeded. - Cap the maximum size of accepted lexicon data and parse untrusted inputs within an isolated worker process governed by CPU or timeout limits.
Affected software
Click a technology to see all vulnerabilities affecting it.
| Platform | Package | Vulnerable versions | Fixed in |
|---|---|---|---|
| Python (PyPI) | nltk | < 3.10.4 | 3.10.4 |
References
- https://github.com/nltk/nltk/security/advisories/GHSA-89p3-fcch-88ph
- https://nvd.nist.gov/vuln/detail/CVE-2026-126299
- https://github.com/nltk/nltk/pull/3944
- https://github.com/nltk/nltk/commit/0bb5b947bd235b950cf2f90e893a498e16da0fe3
- https://github.com/nltk/nltk/commit/cf12a5e6a
- https://github.com/nltk/nltk
- https://github.com/nltk/nltk/releases/tag/v3.10.4
- https://www.vulncheck.com/advisories/nltk-before-3.10.4-quadratic-time-denial-of-service-via-ccg-lexicon-fromstring
- CVSS vector
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H- Weakness (CWE)
CWE-400, CWE-407- Platform
- Python (PyPI)
- Package
nltk- Disclosed
- 14.11.2026
- Updated
- 15.11.2026 10:00
Sources and licenses · Edited or translated by DockRay; source rights and applicable licenses are retained.
OSV / GitHub Advisory Database - GHSA-89p3-fcch-88ph - 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.
- 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
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 74
-
NLTK: Quadratic-time CPU denial of service in CCG lexicon parser (fromstring) on wide bracket bodies and operator chains this entry
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.