AI and data stack advisories

Severe, 6 weeks2431Projects328

2431 severe, 6 weeks · 328 projects

NLTKGHSA-v8f3-6phw-6mh9

NLTK: Quadratic-time CPU denial of service in ConllCorpusReader SRL instance builder via nested span rescan

NLTK

CVE-2026-126297 · Published Nov 14, 2026

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

Summary

ConllCorpusReader.srl_instances() builds semantic-role-labeling instances from a CoNLL corpus block. For a sentence block with P predicates and P span columns, the instance builder rescans every span column (and every span within it) once per predicate while searching for each predicate's head, giving O(P^2 * R) work. A single well-formed block that places the head span in the last column forces the full scan on every predicate, so an application that reads an attacker-supplied CoNLL SRL corpus can be driven into tens of seconds of single-threaded CPU. No authentication or user interaction is required.

Root Cause

_get_srl_instances iterates over the P predicates of a block; for each predicate it scans every span list and every span within it, using an inner break that stops only when a span tagged V or C-V containing the predicate word is found. When the sole head span is placed in the last span column, no earlier column matches, so the for ... else: continue construct traverses every span of every earlier column before matching. Over P predicates each scanning up to P columns of R spans, the cost is O(P^2 * R). The block is read whole with no size cap, and the grid-consistency check enforces only uniform column count, not a bound on P, R, or total work.

```text

Affected function:

  • nltk.corpus.reader.conll.ConllCorpusReader._get_srl_instances...

Affected versions

PackageAffectedFixed in
nltk
PyPI
< 3.10.43.10.4
Details and references

## Summary `ConllCorpusReader.srl_instances()` builds semantic-role-labeling instances from a CoNLL corpus block. For a sentence block with P predicates and P span columns, the instance builder rescans every span column (and every span within it) once per predicate while searching for each predicate's head, giving O(P^2 * R) work. A single well-formed block that places the head span in the last column forces the full scan on every predicate, so an application that reads an attacker-supplied CoNLL SRL corpus can be driven into tens of seconds of single-threaded CPU. No authentication or user interaction is required. ## Root Cause `_get_srl_instances` iterates over the P predicates of a block; for each predicate it scans every span list and every span within it, using an inner `break` that stops only when a span tagged `V` or `C-V` containing the predicate word is found. When the sole head span is placed in the last span column, no earlier column matches, so the `for ... else: continue` construct traverses every span of every earlier column before matching. Over P predicates each scanning up to P columns of R spans, the cost is O(P^2 * R). The block is read whole with no size cap, and the grid-consistency check enforces only uniform column count, not a bound on P, R, or total work. ```text Affected function: - nltk.corpus.reader.conll.ConllCorpusReader._get_srl_instances (nltk/corpus/reader/conll.py:394-424; nested rescan at lines 405-419) Public entry point: nltk.corpus.reader.conll.ConllCorpusReader.srl_instances (nltk/corpus/reader/conll.py:158-169). ``` ## Impact An attacker who can supply a CoNLL corpus that an application loads and iterates with `srl_instances()` causes sustained single-threaded CPU consumption (availability loss). The path is network-reachable through any corpus-ingestion surface (AV:N) and needs no privileges or user interaction (PR:N, UI:N). Because the cost is super-linear in attacker-chosen predicate and column counts, a roughly 1 MB crafted corpus pins a core for tens of seconds and a few megabytes reaches minutes. Confidentiality and integrity are not affected. The NLTK regular-expression wall-clock timeout wraps regex matching only and does not cover this pure-Python nested loop over the parsed grid. Exploitation requires the application to use the SRL-specific API on untrusted CoNLL data with `words`, `pos`, `tree`, and `srl` columns; a deployment that never calls `srl_instances()` is unaffected. ## Proof of Concept ```text Environment: nltk 3.10.3, CPython. Stage a crafted CoNLL corpus under an authorized data root and iterate srl_instances(). Corpus construction: one blank-line-delimited block with P predicate rows and P SRL span columns, the sole "V" head span in the last column. ``` ```python import time, os, tempfile from nltk.corpus.reader.conll import ConllCorpusReader def build_block(n): # n predicates, n SRL columns; the single V head placed in the last column # (columns: words pos tree srl...): emit n predicate rows and n SRL span # columns, with the single "V" head span placed in the final column. ... for n in (40, 80, 160, 320): root = tempfile.mkdtemp() open(os.path.join(root, "c.conll"), "w").write(build_block(n)) r = ConllCorpusReader(root, ["c.conll"], ("words", "pos", "tree", "srl")) t = time.perf_counter() list(r.srl_instances()) print(n, round(time.perf_counter() - t, 3), "s") ``` ```text Negative control (single predicate): n=40 -> 1.88 ms ; n=320 -> 4.45 ms (flat) Attack (P=R=n): n=40 -> 0.022s (10 KB) | n=80 -> 0.148s (39 KB) | n=160 -> 1.164s (156 KB) | n=320 -> 10.002s (619 KB) ``` The attack timing rises about 8x per doubling of n while the file grows only about 4x, confirming super-linear cost driven by attacker-chosen predicate and column count; the single-predicate control stays in the millisecond range. ## Attack Chain 1. **Exposure:** An application loads an attacker-supplied CoNLL corpus (columns include `s

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-126297

More NLTK advisories

All NLTK