CVE-2026-126299: 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 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, so 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 carries a recursion-depth guard (MAXPARSEDEPTH = 500) that raises on deeply nested categories, but both quadratic loops run on flat input whose nesting depth stays at zero, so that guard never fires. No bound is applied to line length or category width before the text reaches these loops.

text 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; APPRE 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 who can influence the CCG lexicon string parsed by an application causes sustained single-threaded CPU consumption (availability loss). The vulnerable path is network-reachable (AV:N) and needs no privileges or user interaction (PR:N, UI:N). Because the cost grows quadratically with attacker-chosen input size, a few-megabyte payload costs tens of seconds per core, and a small number of concurrent requests can exhaust worker threads. Confidentiality and integrity are not affected. The NLTK regular-expression wall-clock timeout wraps regex matching only; it does not wrap these pure-Python slicing loops, so it provides no protection here.

Proof of Concept

text Environment: nltk 3.10.3, regex 2026.9.10, CPython. Run the parser on the shipped public API.

python import nltk.ccg.lexicon as L

Vector A: flat bracket body -> matchBrackets tail re-slice is O(n^2) n = 400000 lexa = ":- S\nw => (" + "a" n + ")\n"

Vector B: long operator chain -> augParseCategory tail re-copy is O(n^2) m = 32000 lexb = ":- a\nw => " + "a" + "/a" m + "\n"

import time for name, s in (("A", lexa), ("B", lexb)): t = time.perfcounter() try: L.fromstring(s) except Exception: pass # downstream parse error is irrelevant; the CPU is already burned print(name, round(time.perfcounter() - t, 3), "s")

text 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

1. Exposure: An application calls the public nltk.ccg.lexicon.fromstring(lexstr) (also reachable as nltk.ccg.chart.fromstring) on lexicon text the attacker can influence. 2. Control: The attacker fully controls the body width (a run of characters inside one bracket) and the operator-chain length; neither is capped by fromstring. 3. Path: fromstring splits input into lines and routes each category through nextCategory, which dispatches to matchBrackets (Vector A) or into the augParseCategory operator loop (Vector B). 4. Guard: The only relevant guard is the MAXPARSEDEPTH = 500 recursion-depth check. On flat input the recursion depth is zero, so if depth > maxdepth is never reached; the width loops run unbounded. 5. Primitive: The tail re-slice rest = rest[1:] and tail re-copy rest = app[3] execute a quadratic number of string copies. 6. Result: Sustained single-core CPU exhaustion; a few-megabyte lexicon costs tens of seconds and scales quadratically, blocking the parsing thread.

Bypass Evidence

The one protection present on this path is the recursion-depth guard MAXPARSEDEPTH = 500 (nltk/ccg/lexicon.py:22), checked at lexicon.py:153 and lexicon.py:228. It defends only against nesting depth and raises a bounded ValueError for deeply nested categories. The quadratic payloads here are flat: a single bracket body or a single operator run has nesting depth zero to one, so the depth check provably never fires while the width loops consume quadratic time. This was confirmed by running the shipped parser: the payloads complete without a ValueError or a regex TimeoutError while consuming quadratic CPU (Vector A shows a clean 4x cost per input doubling). A repository search finds no line-length or category-width cap anywhere on the fromstring path; the regex source-length limit bounds regex patterns, not lexicon text. The strongest disproof attempt (that CPython in-place string concatenation makes Vector A linear) fails because rest = rest[1:] is an unconditional copy of the remaining input that the concatenation fast path cannot elide, and the measured 4x-per-doubling ratio confirms the quadratic empirically.

Affected Versions

- Ecosystem: PyPI (pip) - Package: nltk - Confirmed affected range: <= 3.10.3 - Latest release checked: 3.10.3 (PyPI, https://pypi.org/pypi/nltk/json) - Fix status: 3.10.4

The width-slicing loops ship in every release carrying the CCG lexicon parser and are present in the current latest published release, 3.10.3. The lower boundary was not bisected, so the introducing version is left open; the behavior long predates the recent regular-expression and recursion-depth hardening.

Suggested Fix

Scan the bracket body and the operator chain with an index cursor into the original string (or a collections.deque) instead of repeatedly re-slicing or re-copying the tail, so each character is handled in constant amortized time. As defense in depth, impose an explicit bound on lexicon line length and category width at the fromstring chokepoint and raise a bounded error when it is exceeded, mirroring the existing depth guard. No configuration-only mitigation fully removes the exposure for a service that must parse untrusted lexicons; until a fix ships, callers should cap the size of accepted lexicon input and parse it under a CPU or time budget in an isolated worker.

Reported by zx (GitHub: @manus-pi).

Fix status

PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validatepath", open; head da55cab0e at the time of this note (a develop merge on top of 238f81500, the head on which the verdicts below were measured).

Fix commit: cf12a5e6a (nltk/ccg/lexicon.py: matchBrackets, nextCategory and augParseCategory thread a cursor instead of re-slicing the tail; the trailing capture group is dropped; MAXPARSELEN=100000 caps the input).

Probe: nltk/test/unit/securityprobes/ghsa89p3fcch88ph.py (on the PR). Verdict on the PR head: FIXED (scaling 4.4x over a 4x input; an over-cap chain is rejected by MAXPARSELEN). The advisory PoC re-run on develop 2fa3f48fe: vector A (bracket body, 100k vs 400k) 15.8x and vector B (operator chain, 8k vs 32k) 11.3x over a 4x input, so develop is still VULNERABLE.