High

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

  • Disclosed: 14.11.2026
  • Updated: 14.11.2026 10:00

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.

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

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")
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 srl) and iterates it with the public ConllCorpusReader(...).srl_instances().
  2. Control: The attacker controls the predicate count P, the span-column count, and the placement of the single head span; the block is read whole with no size cap.
  3. Path: srl_instances() calls _get_srl_instances, which pairs each predicate against the span columns via a doubly-nested scan.
  4. Guard: The inner break on the first matching V or C-V head is defeated by placing the sole head span in the last column, so every earlier column is scanned in full. The path-containment sandbox bounds where files load, not how much work a block costs.
  5. Primitive: The nested rescan performs O(P^2 * R) span comparisons with no work cap or timeout.
  6. Result: Sustained single-core CPU exhaustion; a roughly 1 MB corpus costs tens of seconds and scales super-linearly, blocking the processing thread.

Bypass Evidence

The only short-circuit on this path is the inner break that fires when a predicate's V or C-V head span is found. It is defeated by construction: placing the sole head span in the last span column means no earlier column matches, so the for ... else: continue traverses every span of every earlier column for every predicate. This was confirmed in source (nltk/corpus/reader/conll.py:405-419) and reproduced end-to-end through the real public srl_instances() API, where the attack timing scales super-linearly while a single-predicate control stays flat. The path-containment sandbox is a file-location control and imposes no bound on parse cost, and the regular-expression timeout does not wrap this loop. The strongest disproof attempts (that Python range membership is O(1) so the loop is linear, and that the break fires early) both fail: the O(1) membership test is evaluated once per span, and the number of spans traversed is exactly what the last-column head placement maximizes.

Affected Versions

  • Ecosystem: PyPI (pip)
  • Package: nltk
  • Confirmed affected range: <= 3.10.3
  • Latest release checked: 3.10.3 (PyPI, https://pypi.org/pypi/nltk/json)
  • Fix status: 3.10.4

The nested rescan ships in every release carrying this reader and is present in the current latest published release, 3.10.3. The lower boundary was not bisected, so the introducing version is left open; the behavior predates the recent regular-expression hardening.

Suggested Fix

Replace the per-predicate linear search over all span columns with a single pass that indexes head spans by word position (for example, build a map from word index to the owning span column once, then look up each predicate in constant time), reducing the total cost to about O(P * R). As defense in depth, bound the predicate and span counts accepted from a single block and process untrusted corpora under a CPU or time budget. No configuration-only mitigation removes the exposure for a service that must read untrusted CoNLL SRL data; until a fix ships, callers should cap accepted corpus size and isolate the parsing worker.

Reported by zx (GitHub: @manus-pi).

Fix status (2026-09-28)

PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", open; head da55cab0e at the time of this note (a develop merge on top of 238f81500, the head on which the verdicts below were measured).

Fix commit: cf12a5e6a "Patch seven algorithmic-DoS and path/exec GHSA classes across all affected modules" (ConllCorpusReader._get_srl_instances builds a one-pass wordnum to spanlist index instead of rescanning per predicate).

Probe: nltk/test/unit/security_probes/ghsa_v8f3_6phw_6mh9.py (on the PR). Verdict on the PR head: FIXED (srl_instances scaled 3.9x over 4x predicates). The same probe run against develop 2fa3f48fe: VULNERABLE (45.8x over 4x predicates).

What to do

Upgrade to NLTK version 3.10.4 or later. If upgrading immediately is not possible, cap accepted corpus file sizes and isolate corpus parsing workers.

Affected software

Click a technology to see all vulnerabilities affecting it.

PlatformPackageVulnerable versionsFixed in
Python (PyPI) nltk < 3.10.4 3.10.4

References

CVSS score 7.5/10
CVSS vector
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Weakness (CWE)
CWE-400, CWE-407
Platform
Python (PyPI)
Package
nltk
Disclosed
14.11.2026
Updated
14.11.2026 10:00

Sources and licenses · Edited or translated by DockRay; source rights and applicable licenses are retained.

OSV / GitHub Advisory Database - GHSA-v8f3-6phw-6mh9 - CC BY 4.0

Vulnerability history: nltk

All published vulnerabilities of this package (Python (PyPI)), newest first. Shows whether this is a one-off slip or a package that needs watching.

All (79) in the archive
Total entries
79
First → latest
08.2019 11.2026
Without a fix
5
Exploited in attacks
0

Severity breakdown

  • Critical 5
  • High 41
  • Medium 31
  • Low 2

Disclosures per year

  1. 2019: 1
  2. 2020: 0
  3. 2021: 2
  4. 2022: 1
  5. 2023: 0
  6. 2024: 1
  7. 2025: 0
  8. 2026: 74
Severity:
  1. NLTK: Quadratic-time CPU denial of service in ConllCorpusReader SRL instance builder via nested span rescan this entry
    High · 7.5 CVE-2026-126297 < 3.10.4 3.10.4
  2. High CVE-2026-79674 < 3.10.3 3.10.3
  3. High · 8.8 CVE-2026-71513 >= 3.10.0, < 3.10.3 3.10.3
  4. High · 5.9 CVE-2026-62385 < 3.10.0 3.10.0
  5. High · 7.5 CVE-2026-33231 < 3.9.4 3.9.4
  6. High · 8.6 CVE-2026-0847 < 3.9.3 3.9.3
Show more (6) Showing 40 of 46

Know which vulnerabilities affect your application

With the DockRay integration and software inventory enabled, DockRay checks reported component versions against known vulnerabilities and notifies you about confirmed matches. Coverage depends on the supported technology and available advisory data.

Connect your application
DockRay newsletter

Application security in your inbox

Important vulnerabilities, actionable guidance and practical advice for your applications. Choose your technologies and follow what matters to your project.

  • A daily digest of new vulnerabilities, critical ones included.
  • Notifications about important updates.
  • Practical advice on application security and monitoring.

Leave empty to receive updates for every technology.

Free to subscribe. Unsubscribe with one click in any email.