CVE-2026-126299: Quadratic Algorithmic Complexity Denial of Service in NLTK CCG Lexicon Parser

Vulnerability ID: CVE-2026-126299
CVSS Score: 7.5
Published: 2026-11-14

An algorithmic complexity vulnerability (CWE-407) in the Natural Language Toolkit (NLTK) before version 3.10.4 allows remote unauthenticated attackers to cause a denial of service via crafted Combinatory Categorial Grammar (CCG) lexicon strings. The parser in nltk.ccg.lexicon.fromstring performs repeated immutable string slicing, concatenation, and regex tail capturing, resulting in O(n^2) CPU consumption when processing wide, flat category definitions.

TL;DR

NLTK versions prior to 3.10.4 suffer from a quadratic time complexity vulnerability in the CCG lexicon parser (nltk.ccg.lexicon.fromstring). Flat category definitions with long bracket bodies or operator chains bypass recursion depth checks and trigger O(n^2) string copying, exhausting single-threaded CPU resources.

⚠️ Exploit Status: POC

Technical Details

• CVE ID: CVE-2026-126299 (GHSA-89p3-fcch-88ph)
• Vulnerability Class: CWE-407: Inefficient Algorithmic Complexity / CWE-400: Uncontrolled Resource Consumption
• CVSS Score: 7.5 High (CVSS v3.1) / 8.7 High (CVSS v4.0)
• Attack Vector: Network (Unauthenticated crafted CCG lexicon input)
• Affected Component: nltk.ccg.lexicon.fromstring (matchBrackets, nextCategory, augParseCategory)
• Exploit Status: Public Proof-of-Concept (PoC) Available
• EPSS Score: 0.58% (48.34th Percentile)
• Patched Version: nltk 3.10.4

Affected Systems

• Natural Language Toolkit (NLTK) Python Library (PyPI: nltk)
• nltk: >= 0.8, <= 3.10.3 (Fixed in: 3.10.4)

Code Analysis

Commit: 0bb5b94

Replace quadratic tail re-slicing and regex remainder capture in nltk.ccg.lexicon with cursor-based indexing and MAX_PARSE_LEN guard.

diff --git a/nltk/ccg/lexicon.py b/nltk/ccg/lexicon.py
index 0e4bbe244d..bc67c327bf 100644
--- a/nltk/ccg/lexicon.py
+++ b/nltk/ccg/lexicon.py
@@ -21,6 +21,11 @@
 #: uncaught RecursionError (CWE-674).  Configurable.
 MAX_PARSE_DEPTH = 500

+#: Maximum length of a single category string the parser will accept.
+#: A category longer than any real grammar is treated as adversarial input
+#: (defense in depth against quadratic parsing). Configurable.
+MAX_PARSE_LEN = 100_000
+
 # ------------
 # Regular expressions used for parsing components of the lexicon
 # ------------
@@ -28,14 +33,16 @@
 # Parses a primitive category and subscripts
 PRIM_RE = redos.compile(r"""([A-Za-z]+)(\[[A-Za-z,]+\])?""")

-# Separates the next primitive category from the remainder of the
-# string
-NEXTPRIM_RE = redos.compile(r"""([A-Za-z]+(?:\[[A-Za-z,]+\])?)(.*)""")
+# Matches the next primitive category (name and optional subscript). The parser
+# threads a position cursor for the remainder, so no trailing group is captured;
+# a captured remainder made parsing quadratic in the category length.
+NEXTPRIM_RE = redos.compile(r"""([A-Za-z]+(?:\[[A-Za-z,]+\])?)""")

-# Separates the next application operator from the remainder.
+# Matches the next application operator (slash and optional modality). The parser
+# threads a position cursor for the remainder, so no trailing group is captured.
 # The modifier slot also accepts `_`, marking a variable direction
 # (e.g. `(S\_NP)/(S\_NP)` for a polymorphic adverb).
-APP_RE = redos.compile(r"""([\\/])([.,_]?)([.,]?)(.*)""")
+APP_RE = redos.compile(r"""([\\/])([.,_]?)([.,]?)""")

Commit: cf12a5e

Merge pull request #3944 fixing quadratic CCG category parsing in nltk.ccg.lexicon.

Mitigation Strategies

• Upgrade NLTK to version 3.10.4 or later to replace quadratic string slicing with linear-time cursor indexing.
• Enforce strict input size and line length limits on user-supplied CCG grammar specifications before passing them to nltk.ccg.lexicon.fromstring.
• Isolate CCG lexicon parsing into dedicated worker processes with strict CPU time limits to prevent GIL starvation in web applications.

Remediation Steps:

1. Audit application dependencies and source code to identify usage of nltk.ccg.lexicon.fromstring or nltk.ccg.chart.fromstring.
2. Upgrade the nltk package via pip: pip install --upgrade 'nltk>=3.10.4'.
3. If parsing unusually large, trusted grammars that legitimately exceed 100,000 characters per category, adjust nltk.ccg.lexicon.MAX_PARSE_LEN accordingly while maintaining perimeter size controls.

References

• CVE-2026-126299 Official CVE Record
• NVD - CVE-2026-126299 Detail
• GitHub Security Advisory GHSA-89p3-fcch-88ph
• VulnCheck Advisory: NLTK Before 3.10.4 Quadratic-Time DoS via CCG Lexicon fromstring
• NLTK Fix Commit 0bb5b947bd235b950cf2f90e893a498e16da0fe3
• NLTK Merge Commit cf12a5e6a439fe1d722acd53d4309911faaaaf78
• NLTK Pull Request #3944
• NLTK Release v3.10.4
• MITRE ATT&CK Search for CVE-2026-126299

Read the full report for CVE-2026-126299 on our website for more details including interactive diagrams and full exploit analysis.