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

The Natural Language Toolkit (NLTK) provides modules for processing and parsing various linguistic formalisms, including Combinatory Categorial Grammar (CCG). Within the nltk.ccg.lexicon module, the fromstring function (also re-exported as nltk.ccg.chart.fromstring) parses plain-text lexicon specifications into structured Python grammar objects. When an application exposes this functionality to untrusted user input, the lexicon parser serves as a direct parsing attack surface.

In NLTK versions prior to 3.10.4, nltk.ccg.lexicon contains an inefficient algorithmic complexity vulnerability classified under CWE-407 and CWE-400 (Uncontrolled Resource Consumption). Specifically, the internal helper functions matchBrackets, nextCategory, and augParseCategory iterate over input category strings by repeatedly slicing the unparsed remainder of the string and concatenating characters into new immutable string instances.

Because Python strings are immutable sequences in memory, each slicing and concatenation operation allocates a new buffer and copies the remaining characters. When given a wide, flat category specification of length $n$, the parser executes $O(n)$ steps where each step copies up to $O(n)$ bytes, resulting in $O(n^2)$ time complexity.

Prior to version 3.10.4, the CCG parser included a recursion limit (MAX_PARSE_DEPTH = 500) designed to prevent RecursionError exceptions on deeply nested parentheses, as well as a regular expression timeout wrapper (redos.compile) to prevent catastrophic backtracking. However, neither mechanism restricts horizontal string width on flat inputs, allowing an attacker to bypass existing guards and exhaust CPU resources.

The quadratic runtime behavior stems from two independent execution paths within nltk/ccg/lexicon.py that manipulate string state by copying tail substrings rather than advancing an index cursor.

Vector A: Bracket Parsing in matchBrackets

When nextCategory encounters an opening parenthesis (, it delegates extraction of the bracketed expression to matchBrackets(string, _depth=0, max_depth=None). In the vulnerable implementation, matchBrackets strips the leading parenthesis via rest = string[1:] and initializes an accumulator inside = "(". It then enters a while loop that inspects rest character by character until a matching ) is found.

For every non-parenthesis character in a flat bracket body (such as (aaaa...)), the else branch executes inside = inside + rest[0] followed by rest = rest[1:]. In CPython, slicing rest[1:] on a string of length $n$ at iteration $i$ allocates a new string object and copies $n - i$ characters. Across $n$ characters, the total number of character copy operations is:

$$\sum_{i=1}^{n} (n - i) = \frac{n(n - 1)}{2} = O(n^2)$$

Simultaneously, inside = inside + rest[0] repeatedly reallocates the growing prefix string, compounding the quadratic memory copying overhead.

Vector B: Operator Chain Slicing in augParseCategory

A second quadratic path occurs when parsing chained category application operators (such as a/a/a/a...) inside augParseCategory and nextCategory. The module defines two compiled regular expressions to tokenize category primitives and application operators:

NEXTPRIM_RE = redos.compile(r"""([A-Za-z]+(?:\[[A-Za-z,]+\])?)(.*)""")
APP_RE = redos.compile(r"""([\\/])([.,_]?)([.,]?)(.*)""")

Both regular expressions conclude with a greedy capture group (.*) intended to capture the unparsed remainder of the category string. During operator chain parsing, augParseCategory loops while rest != "", matching APP_RE against rest and rebinding rest = app[3], followed by calling nextCategory(rest), which matches NEXTPRIM_RE and returns its trailing (.*) group as the new rest.

Whenever the regular expression engine populates the (.*) group and Python extracts it via .groups(), CPython allocates a new string containing a full copy of the unparsed tail. For a flat chain containing $m$ operators, extracting the trailing substring at each operator token requires $O(m)$ string copies of average length $O(m)$, yielding $O(m^2)$ time complexity.

> [!NOTE] > Because both vectors maintain a parenthesis nesting depth of 0 or 1, the _depth counter in matchBrackets and augParseCategory never exceeds 1. Consequently, the if _depth > max_depth: check (MAX_PARSE_DEPTH = 500) is never triggered.

The vulnerability was remediated in commits 0bb5b947bd235b950cf2f90e893a498e16da0fe3 and cf12a5e6a439fe1d722acd53d4309911faaaaf78 (merged via Pull Request #3944). The patch eliminates string slicing and trailing regex capture groups in favor of integer cursor indexing, list comprehension joins, and an explicit input length ceiling.

Regular Expression Modifications

In the vulnerable code, NEXTPRIM_RE and APP_RE captured the entire remainder of the string using (.*):

# Vulnerable regular expressions in nltk/ccg/lexicon.py
NEXTPRIM_RE = redos.compile(r"""([A-Za-z]+(?:\[[A-Za-z,]+\])?)(.*)""")
APP_RE = redos.compile(r"""([\\/])([.,_]?)([.,]?)(.*)""")

The patched code removes the trailing (.*) capture group from both expressions and introduces MAX_PARSE_LEN = 100_000 as a configurable upper bound on category string length:

# Patched constants and regular expressions in nltk/ccg/lexicon.py
MAX_PARSE_DEPTH = 500
MAX_PARSE_LEN = 100_000
 
# Trailing (.*) removed; parser threads an integer cursor instead
NEXTPRIM_RE = redos.compile(r"""([A-Za-z]+(?:\[[A-Za-z,]+\])?)""")
APP_RE = redos.compile(r"""([\\/])([.,_]?)([.,]?)""")

Cursor Refactoring in matchBrackets and nextCategory

In matchBrackets, the patch replaces rest = string[1:] and string concatenation with an integer index i (initialized to pos + 1) and a Python list inside = ["("]. Characters are appended to the list in $O(1)$ amortized time and joined once via "".join(inside) upon reaching the closing parenthesis:

def matchBrackets(string, pos=0, _depth=0, max_depth=None):
    if max_depth is None:
        max_depth = MAX_PARSE_DEPTH
    if _depth > max_depth:
        raise ValueError(
            f"CCG category nesting exceeds max_depth ({max_depth}); "
            "the input may be adversarially deep. Raise "
            "nltk.ccg.lexicon.MAX_PARSE_DEPTH to allow it."
        )
    n = len(string)
    # Defense-in-depth length check against oversized categories
    if n - pos > MAX_PARSE_LEN:
        raise ValueError(
            f"CCG category length exceeds MAX_PARSE_LEN "
            f"({MAX_PARSE_LEN}); the input may be "
            "adversarially long. Raise "
            "nltk.ccg.lexicon.MAX_PARSE_LEN to allow it."
        )
    inside = ["("]
    i = pos + 1
 
    # Iterate using integer index 'i' instead of slicing 'rest[1:]'
    while i < n and string[i] != ")":
        if string[i] == "(":
            (part, i) = matchBrackets(string, i, _depth + 1, max_depth)
            inside.append(part)
        else:
            inside.append(string[i])
            i += 1
    if i < n and string[i] == ")":
        inside.append(")")
        # Join accumulated tokens once in O(n) time and return updated cursor
        return ("".join(inside), i + 1)
    raise AssertionError("Unmatched bracket in string '" + string[pos:] + "'")

Similarly, nextCategory and augParseCategory were updated to pass pos to NEXTPRIM_RE.match(string, pos) and APP_RE.match(line, pos), advancing pos = m.end() in $O(1)$ time without allocating intermediate substrings:

def nextCategory(string, pos=0, _depth=0, max_depth=None):
    if pos < len(string) and string[pos] == "(":
        return matchBrackets(string, pos, _depth, max_depth)
    # Match in-place at index 'pos' without slicing string
    m = NEXTPRIM_RE.match(string, pos)
    if m is None:
        m.groups()  # preserve original AttributeError on malformed input
    return (m.group(1), m.end(1))

Assessment of Fix Completeness

The refactoring reduces single-level bracket scanning and operator chain tokenization from $O(n^2)$ to $O(n)$ time complexity. One subtle nuance remains in matchBrackets: when nested brackets are present, the parent call appends the child's returned part string and later joins it, while augParseCategory subsequently slices cat_string[1:-1] to recursively parse the inner category. For deeply nested structures, this copies substrings at each nesting level $d$, resulting in $O(n \cdot d)$ complexity. However, because MAX_PARSE_DEPTH restricts $d \le 500$ and MAX_PARSE_LEN restricts $n \le 100,000$, worst-case execution is strictly bounded and the fix is effective.

Exploiting CVE-2026-126299 requires an application to pass attacker-controlled text into nltk.ccg.lexicon.fromstring or nltk.ccg.chart.fromstring. No authentication or special configuration is required at the library level. Even if the supplied category definition eventually fails downstream grammar validation (for example, referencing an undefined primitive category), the quadratic CPU consumption occurs during the initial lexical scanning phase prior to semantic validation.

Proof of Concept

The following script demonstrates both attack vectors on NLTK versions <= 3.10.3. Vector A supplies a single lexicon entry containing a 400,000-character flat bracketed category, while Vector B supplies a 32,000-element slash-operator chain:

import time
import nltk.ccg.lexicon as L
 
# Vector A: Flat bracket body triggering matchBrackets tail re-slicing
n = 400000
lex_a = ":- S\nw => (" + "a" * n + ")\n"
 
# Vector B: Long operator chain triggering augParseCategory tail re-copying
m = 32000
lex_b = ":- a\nw => " + "a" + "/a" * m + "\n"
 
print("[*] Running algorithmic DoS evaluation on NLTK CCG parser...")
for name, s in (("Vector A (Flat Bracket Body)", lex_a), ("Vector B (Operator Chain)", lex_b)):
    t = time.perf_counter()
    try:
        L.fromstring(s)
    except Exception:
        # Downstream grammar errors occur only after CPU exhaustion
        pass
    elapsed = time.perf_counter() - t
    print(f"[-] {name} parsed in: {elapsed:.3f} s")

Empirical Scaling Behavior

Benchmark measurements on unpatched NLTK versions confirm quadratic time growth relative to input size:

• Vector A (matchBrackets): Increasing $n$ from $50,000$ ($0.078\text{ s}$) to $100,000$ ($0.260\text{ s}$), $200,000$ ($1.046\text{ s}$), and $400,000$ ($2.083\text{ s}$) demonstrates super-linear scaling where doubling the character count approximately quadruples execution time.
• Vector B (augParseCategory): Increasing $m$ from $4,000$ ($0.078\text{ s}$) to $8,000$ ($0.215\text{ s}$), $16,000$ ($0.485\text{ s}$), $32,000$ ($1.329\text{ s}$), and $40,000$ ($6.850\text{ s}$) exhibits rapid CPU saturation as memory allocation sizes exceed CPU cache tiers.

The primary impact of CVE-2026-126299 is a denial of service (DoS) via CPU and memory bandwidth exhaustion. Because CPython execution is bound by the Global Interpreter Lock (GIL), triggering a pure-Python $O(n^2)$ loop in matchBrackets or augParseCategory monopolizes the Python worker process or thread for the duration of the parse.

In web services or NLP microservices deployed behind synchronous WSGI servers (such as Gunicorn or uWSGI) or asynchronous event loops (such as FastAPI/Uvicorn where fromstring is called on the main event loop thread), a small number of concurrent requests containing payloads of a few hundred kilobytes to a few megabytes can block all available worker processes. This prevents the application from servicing legitimate requests until the parser terminates or the worker is killed by an external supervisor.

Under CVSS v3.1, the vulnerability is scored at 7.5 (High) (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H). Under CVSS v4.0, VulnCheck assigns a score of 8.7 (High) (CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N). Both scores reflect that the flaw is network-exploitable without privileges or user interaction when the CCG parser is exposed, impacting system availability without compromising confidentiality or integrity.

According to FIRST EPSS metrics, CVE-2026-126299 currently holds an EPSS score of 0.00582 (48.34th percentile), and it is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog.

Upgrading NLTK

Users and administrators should upgrade the nltk package to version 3.10.4 or later, which incorporates the linear-time cursor parser and enforces the MAX_PARSE_LEN = 100_000 ceiling by default:

pip install --upgrade "nltk>=3.10.4"

Workarounds and Defense-in-Depth

For environments where an immediate upgrade to NLTK 3.10.4 is not feasible, developers should implement strict pre-validation before invoking nltk.ccg.lexicon.fromstring or nltk.ccg.chart.fromstring:

1. Enforce Input Length Limits: Reject lexicon strings or individual lines exceeding a conservative character threshold (for example, 1,000 characters per line or 10,000 characters total) prior to calling NLTK.
2. Restrict Operator and Bracket Counts: Validate that individual category definitions do not contain an excessive number of slash operators (/, \) or character sequences inside parentheses.
3. Process Isolation and Timeouts: Execute untrusted grammar parsing jobs inside separate worker processes (such as multiprocessing or Celery workers) configured with hard wall-clock execution timeouts and memory limits, ensuring that a stalled parser can be terminated via SIGKILL without stalling the primary application server.