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 (MAX_PARSE_DEPTH = 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.
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 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
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 the public
nltk.ccg.lexicon.fromstring(lex_str)(also reachable asnltk.ccg.chart.fromstring) on lexicon text the attacker can influence. - 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. - Path:
fromstringsplits input into lines and routes each category throughnextCategory, which dispatches tomatchBrackets(Vector A) or into theaugParseCategoryoperator loop (Vector B). - Guard: The only relevant guard is the
MAX_PARSE_DEPTH = 500recursion-depth check. On flat input the recursion depth is zero, soif _depth > max_depthis never reached; the width loops run unbounded. - Primitive: The tail re-slice
rest = rest[1:]and tail re-copyrest = app[3]execute a quadratic number of string copies. - 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 MAX_PARSE_DEPTH = 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: