AI and data stack advisories

Severe, 6 weeks2431Projects328

2431 severe, 6 weeks · 328 projects

NLTKGHSA-89p3-fcch-88ph

NLTK: resource exhaustion

NLTK

CVE-2026-126299 · Published Nov 14, 2026

High7.5
Fix: upgrade to 3.10.4 or later
GitHub advisory

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

PackageAffectedFixed in
nltk
PyPI
< 3.10.43.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

More NLTK advisories

All NLTK