CVE-2026-81723: Quadratic CPU Exhaustion in NLTK’s XML Corpus Reader

At a glance#

Summary#

This one is the sequel to a previous fix. NLTK’s XML corpus reader had a regex denial-of-service problem, and upstream fixed it by making the regex linear per call (commit c9c332284, the CWE-1333 fix). Reasonable fix. But while re-testing that fix, I found the loop around the regex was still quadratic: it reads the file in 1 KiB blocks, appends each block to a growing buffer, and re-runs the regex over the entire buffer on every single iteration.

An 8 MiB malformed XML file consumed roughly 48 CPU-seconds through the public BNCCorpusReader.words() API. No source modification needed, no special setup. Just a bad file and a normal API call. The same loop structure had been sitting in the codebase since XMLCorpusView was introduced back in 2007.

Background: what the code does#

XMLCorpusView is the machinery behind several of NLTK’s corpus readers. When you ask for words from a corpus, it needs to carve the underlying XML file into fragments. _read_xml_fragment() does that carving: it reads the stream in 1 KiB blocks, accumulates them into a fragment string, and after each block checks whether the accumulated text forms a complete XML fragment using a compiled regex, _VALID_XML_RE.

The readers built on top of it include BNCCorpusReader, NPSChatCorpusReader, SemcorCorpusReader, MTECorpusReader, NKJPCorpusReader, FrameNetCorpusReader, and VerbNetCorpusReader. (XMLCorpusReader.xml() is not affected; it goes through defusedxml.safe_parse() instead.)

The bug#

Here is the loop, simplified from nltk/corpus/reader/xmldocs.py (lines 261-308):

fragment = ""
while True:
    fragment += stream.read(self._BLOCK_SIZE)      # grows by 1 KiB per iteration
    if self._VALID_XML_RE.match(fragment):         # rescans the FULL buffer each time
        return fragment
    ...
    last_open_bracket = fragment.rfind("<")
    if last_open_bracket > 0:                      # False for a single-'<' payload
        if self._VALID_XML_RE.match(fragment[:last_open_bracket]):
            return ...
    # loop continues

The earlier ReDoS fix made each individual match() call linear. That fixed the regex. It did not fix the loop. The loop calls match() once per 1 KiB block, each time against a longer buffer. For an N-byte input that is roughly N/1024 calls with average buffer length N/2, which is O(n^2) total work. Linear per call, quadratic overall.

Now feed it this payload: b'<' + b'a' * (N-1). Three things go wrong at once:

1. _VALID_XML_RE.match(fragment) never succeeds, because the unterminated tag can never match before EOF.
2. fragment.rfind("<") returns 0 (the only < is the first byte), so the guard last_open_bracket > 0 is False and the backtrack branch never runs.
3. The only way out of the loop is EOF, after all N bytes have been consumed one kilobyte at a time, each kilobyte triggering a full rescan.

There is no cap on fragment size and no cap on iteration count. The function just keeps going.

I confirmed the rescanning directly by instrumenting _VALID_XML_RE.match() to log its input size. For a 256 KiB malformed file, it was invoked 257 times on monotonically increasing buffers: 1024, 2048, 3072, … all the way to 262144 bytes, with the final call happening after EOF.

Proof of concept#

Needs nothing but pip install nltk. No corpus data required:

from pathlib import Path
from tempfile import TemporaryDirectory
from time import perf_counter
from nltk.corpus.reader.bnc import BNCCorpusReader

SIZES_KIB = (256, 512, 1024, 2048, 4096, 8192)
results = []

with TemporaryDirectory() as directory:
    root = Path(directory)
    malformed = root / "unterminated.xml"
    for kib in SIZES_KIB:
        malformed.write_bytes(b"<" + b"a" * (kib * 1024 - 1))
        t = perf_counter()
        try:
            list(BNCCorpusReader(str(root), [malformed.name]).words())
        except ValueError as e:
            assert "tag not closed" in str(e)
        results.append(perf_counter() - t)

print("KiB      seconds   growth")
for i, (kib, elapsed) in enumerate(zip(SIZES_KIB, results)):
    ratio = "-" if i == 0 else f"{elapsed / results[i - 1]:.2f}x"
    print(f"{kib:5d}  {elapsed:9.3f}  {ratio}")

The signature of a quadratic: runtime grows about 4x for every doubling of input size. On the test system, the 8 MiB input took roughly 48 CPU-seconds. Absolute numbers move with hardware; the 4x-per-doubling ratio is the tell.

Impact#

This is a denial-of-service bug, plain and simple. The bar for the attacker is low: write access to any path the reader will open. No NLTK credentials, no special privileges. Any application that processes attacker-influenced XML corpus files through an affected reader (a web service, a shared NLP pipeline, a multi-tenant box) can have its CPU pinned by a single malformed file that is only a few megabytes.

What it is not: a data-theft or code-execution bug. Confidentiality and integrity are untouched. The CVSS 4.0 vector published by VulnCheck (AV:N/AC:H/AT:P/PR:N/UI:N/VC:N/VI:N/VA:L/...) reflects that: network-reachable, but high attack complexity and availability impact rated low. A numeric score was still pending at the time of writing. If you only ever read your own trusted local corpora with NLTK, you were never at risk.

The fix#

Upstream fixed it in commit 7808692 and shipped the fix in NLTK 3.10.3. The advisory’s suggested direction was to stop rescanning the accumulated fragment from the beginning on every 1 KiB read: incremental parsing, bounded fragment accumulation, or another streaming approach, plus a regression test asserting that BNCCorpusReader.words() raises ValueError within a fixed timeout against a 2 MiB malformed input. (The existing test_xmldocs_security.py only covered the earlier ReDoS payloads and never exercised this path, which is exactly how the quadratic survived the first fix.)

If you run NLTK anywhere near untrusted input: upgrade to 3.10.3 or later.

Timeline#

What I took away from this#

The honest version: I went back to check that the first fix actually worked, and the code had a second, dumber problem hiding behind the first one. Two things stuck with me:

1. Fixing the regex is not the same as fixing the algorithm. The ReDoS patch was correct and necessary, and it still left a quadratic. When a hot loop calls a function, you have to cost the loop, not just the function.
2. Re-test the fix, don’t just review the diff. The diff for c9c332284 looked right. Running the timing script is what caught the rest. Measurement beats reading.

References#

• GHSA-vp2x-qp44-57v7 (the advisory, with full PoC)
• CVE-2026-81723 on NVD
• VulnCheck advisory: NLTK before 3.10.3
• Fix commit 7808692 / NLTK v3.10.3