NLTK: resource exhaustion
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.
```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; APP_RE tail re-copy at line 250)
Public entry...
Affected versions
| Package | Affected | Fixed in |
|---|---|---|
| nltk PyPI | < 3.10.4 | 3.10.4 |
Details and references
## 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. ```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; 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 ```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 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") ``` ```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(lex_str)` (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 `MAX_PARSE_DEPTH = 500` recursion-depth check. On flat input the recursion depth is zero, so `if _depth > max_depth` is never reached; the width loops run unbounded. 5. **Primitive:** The tail re-sl
- CVSS 3.1
- CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
- Severity from
- GitHub (reviewed advisory)
- Weakness
- CWE-400, CWE-407
- Also known as
- CVE-2026-126299
- github.com/nltk/nltk/security/advisories/GHSA-89p3-fcch-88ph
- nvd.nist.gov/vuln/detail/CVE-2026-126299
- github.com/nltk/nltk/pull/3944
- github.com/nltk/nltk/commit/0bb5b947bd235b950cf2f90e893a498e16da0fe3
- github.com/nltk/nltk/commit/cf12a5e6a
- github.com/nltk/nltk
- github.com/nltk/nltk/releases/tag/v3.10.4
- www.vulncheck.com/advisories/nltk-before-3.10.4-quadratic-time-denial-of-service-via-ccg-lexicon-fromstring