Skip to content

Commit 722778f

Browse files
authored
Merge commit from fork
Fix algorithmic-complexity DoS: PorterStemmer, corpus readers, tokenizers, distance/alignment family (GHSA-ww6m umbrella; vp2x, 8mpw)
2 parents 13b9c01 + 375841c commit 722778f

16 files changed

Lines changed: 736 additions & 61 deletions

File tree

‎.github/workflows/ci.yml‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -183,6 +183,21 @@ jobs:
183183
# drop it; also collected by "Run pytest".
184184
pytest -rsx nltk/test/unit/test_recursivedescent_dos.py nltk/test/unit/test_parser_dos.py nltk/test/unit/test_recursion_dos.py
185185
186+
- name: Run algorithmic-complexity DoS security regression tests
187+
shell: bash
188+
env:
189+
PYTHONSAFEPATH: "1"
190+
run: |
191+
# Security regression suite for the algorithmic-complexity DoS cluster
192+
# (GHSA-ww6m-cw3f-q94g umbrella: PorterStemmer; GHSA-vp2x XMLCorpusView,
193+
# GHSA-8mpw TEICorpusView -- all directions -- and read_sexpr_block;
194+
# plus the repo-wide sweep: TweetTokenizer/RIBES/Syllable/TextTiling/
195+
# CHILDES single-input sinks and the metrics.distance / aline /
196+
# gale_church two-string O(n*m) sinks. CWE-407/CWE-400). Own fast,
197+
# early step so a change to the main pytest invocation can't silently
198+
# drop it; also collected by "Run pytest".
199+
pytest -rsx nltk/test/unit/test_quadratic_dos.py nltk/test/unit/test_distance.py
200+
186201
- name: Run pytest
187202
shell: bash
188203
env:

‎nltk/classify/textcat.py‎

Lines changed: 12 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -119,14 +119,21 @@ def lang_dists(self, text):
119119

120120
distances = {}
121121
profile = self.profile(text)
122-
# For all the languages
122+
# Precompute each trigram's rank (position) once. The original called
123+
# ``list(profile.keys()).index(trigram)`` (and the same on each language
124+
# profile) for every trigram, which is O(m^2 * languages) and lets a
125+
# few-KB unicode-diverse string burn tens of seconds (CWE-407). Dict
126+
# insertion order equals list order, so the ranks -- and the resulting
127+
# out-of-place distance -- are identical to ``calc_dist``.
128+
text_ranks = {trigram: i for i, trigram in enumerate(profile)}
123129
for lang in self._corpus._all_lang_freq.keys():
124-
# Calculate distance metric for every trigram in
125-
# input text to be identified
130+
lang_ranks = {t: i for i, t in enumerate(self._corpus.lang_freq(lang))}
126131
lang_dist = 0
127132
for trigram in profile:
128-
lang_dist += self.calc_dist(lang, trigram, profile)
129-
133+
if trigram in lang_ranks:
134+
lang_dist += abs(lang_ranks[trigram] - text_ranks[trigram])
135+
else:
136+
lang_dist += maxsize
130137
distances[lang] = lang_dist
131138

132139
return distances

‎nltk/corpus/reader/childes.py‎

Lines changed: 17 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -375,19 +375,29 @@ def _get_words(
375375
results = []
376376
for xmlsent in xmldoc.findall(".//{%s}u" % NS):
377377
sents = []
378+
# These `find` calls scan the whole utterance subtree and return the
379+
# same element no matter which word we are on. Computing them once
380+
# per utterance (instead of per word) keeps an utterance with W words
381+
# O(W) rather than O(W^2) -- otherwise a crafted CHILDES file makes
382+
# words(replace=True)/MLU() quadratic (CWE-407).
383+
if replace:
384+
_repl_cond = xmlsent.find(f".//{{{NS}}}w/{{{NS}}}replacement")
385+
_repl_word = xmlsent.find(f".//{{{NS}}}w/{{{NS}}}replacement/{{{NS}}}w")
386+
_wk = xmlsent.find(f".//{{{NS}}}w/{{{NS}}}wk")
387+
else:
388+
_repl_cond = _repl_word = _wk = None
378389
# select speakers
379390
if speaker == "ALL" or xmlsent.get("who") in speaker:
380391
for xmlword in xmlsent.findall(".//{%s}w" % NS):
381392
infl = None
382393
suffixStem = None
383394
suffixTag = None
384-
# getting replaced words
385-
if replace and xmlsent.find(f".//{{{NS}}}w/{{{NS}}}replacement"):
386-
xmlword = xmlsent.find(
387-
f".//{{{NS}}}w/{{{NS}}}replacement/{{{NS}}}w"
388-
)
389-
elif replace and xmlsent.find(f".//{{{NS}}}w/{{{NS}}}wk"):
390-
xmlword = xmlsent.find(f".//{{{NS}}}w/{{{NS}}}wk")
395+
# getting replaced words (behaviour-preserving: same elements
396+
# as the original per-word finds, incl. the truthiness test).
397+
if _repl_cond is not None and len(_repl_cond):
398+
xmlword = _repl_word
399+
elif _wk is not None and len(_wk):
400+
xmlword = _wk
391401
# get text
392402
if xmlword.text:
393403
word = xmlword.text

‎nltk/corpus/reader/pl196x.py‎

Lines changed: 48 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -5,20 +5,28 @@
55
# URL: <https://www.nltk.org/>
66
# For license information, see LICENSE.TXT
77

8+
from nltk import redos
89
from nltk.corpus.reader.api import *
910
from nltk.corpus.reader.xmldocs import XMLCorpusReader
1011
from nltk.pathsec import open as pathsec_open
1112

12-
PARA = re.compile(r"<p(?: [^>]*){0,1}>(.*?)</p>")
13-
SENT = re.compile(r"<s(?: [^>]*){0,1}>(.*?)</s>")
13+
# These ``.*?`` patterns are applied with ``findall`` to (untrusted) corpus
14+
# blocks. On a malformed block -- e.g. many ``<p>`` with no ``</p>`` -- findall
15+
# tries each opening tag as a start and the lazy body scans to the end of the
16+
# block, which is O(k*n) = quadratic (CWE-407; part of GHSA-8mpw). Neither the
17+
# stdlib nor the ``regex`` optimiser linearises findall's multi-start scan, so
18+
# compile them through ``redos`` for a wall-clock backstop that bounds the CPU a
19+
# crafted block can burn instead of letting it grow without limit.
20+
PARA = redos.compile(r"<p(?: [^>]*){0,1}>(.*?)</p>")
21+
SENT = redos.compile(r"<s(?: [^>]*){0,1}>(.*?)</s>")
1422

15-
TAGGEDWORD = re.compile(r"<([wc](?: [^>]*){0,1}>)(.*?)</[wc]>")
16-
WORD = re.compile(r"<[wc](?: [^>]*){0,1}>(.*?)</[wc]>")
23+
TAGGEDWORD = redos.compile(r"<([wc](?: [^>]*){0,1}>)(.*?)</[wc]>")
24+
WORD = redos.compile(r"<[wc](?: [^>]*){0,1}>(.*?)</[wc]>")
1725

18-
TYPE = re.compile(r'type="(.*?)"')
19-
ANA = re.compile(r'ana="(.*?)"')
26+
TYPE = redos.compile(r'type="(.*?)"')
27+
ANA = redos.compile(r'ana="(.*?)"')
2028

21-
TEXTID = re.compile(r'text id="(.*?)"')
29+
TEXTID = redos.compile(r'text id="(.*?)"')
2230

2331

2432
class TEICorpusView(StreamBackedCorpusView):
@@ -45,23 +53,47 @@ def __init__(
4553
def read_block(self, stream):
4654
block = stream.readlines(self._pagesize)
4755
block = concat(block)
48-
while (block.count("<text id") > block.count("</text>")) or block.count(
49-
"<text id"
50-
) == 0:
56+
# Track the '<text id' / '</text>' counts incrementally. Re-running
57+
# ``block.count(...)`` over the whole growing block on every appended
58+
# line is O(n^2) -- a file with no closing '</text>' makes the loop
59+
# swallow the whole file quadratically (CWE-407). Each marker contains
60+
# no newline and ``readline()`` splits on newlines, so a marker can
61+
# never straddle a line boundary and per-line counts are exact.
62+
open_count = block.count("<text id")
63+
close_count = block.count("</text>")
64+
while (open_count > close_count) or (open_count == 0):
5165
tmp = stream.readline()
5266
if len(tmp) <= 0:
5367
break
5468
block += tmp
69+
open_count += tmp.count("<text id")
70+
close_count += tmp.count("</text>")
5571

5672
block = block.replace("\n", "")
5773

58-
textids = TEXTID.findall(block)
5974
if self._textids:
60-
for tid in textids:
61-
if tid not in self._textids:
62-
beg = block.find(tid) - 1
63-
end = block[beg:].find("</text>") + len("</text>")
64-
block = block[:beg] + block[beg + end :]
75+
# Keep only the <text> elements whose id is requested, in a single
76+
# forward pass. ``str.find`` with a monotonically advancing cursor is
77+
# O(n) total; the original per-id ``block.find(tid)`` + string rebuild
78+
# was O(k*n) quadratic on many unwanted elements (CWE-407, part of
79+
# GHSA-8mpw).
80+
kept = []
81+
pos = 0
82+
while True:
83+
beg = block.find("<text id", pos)
84+
if beg < 0:
85+
kept.append(block[pos:])
86+
break
87+
q1 = block.find('"', beg)
88+
q2 = block.find('"', q1 + 1) if q1 >= 0 else -1
89+
tid = block[q1 + 1 : q2] if 0 <= q1 < q2 else ""
90+
close = block.find("</text>", beg)
91+
end = len(block) if close < 0 else close + len("</text>")
92+
kept.append(block[pos:beg])
93+
if tid in self._textids:
94+
kept.append(block[beg:end])
95+
pos = end
96+
block = "".join(kept)
6597

6698
output = []
6799
for para_str in PARA.findall(block):

‎nltk/corpus/reader/util.py‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -621,6 +621,14 @@ def read_sexpr_block(stream, block_size=16384, comment_char=None):
621621

622622
if comment_char:
623623
COMMENT = re.compile("(?m)^%s.*$" % re.escape(comment_char))
624+
# When a single s-expression spans more than one block, we grow ``block``
625+
# and re-parse it. Growing by a *fixed* amount re-parses (and, with a
626+
# comment_char, re-substitutes) the whole growing buffer on every step,
627+
# which is O(n^2) on one oversized s-expression (CWE-407). Doubling the read
628+
# size instead makes the number of re-parses O(log n) and the total work a
629+
# geometric sum O(n), with no change to the parsed result (the stream is
630+
# seeked back to the parsed offset regardless of any over-read).
631+
read_size = block_size
624632
while True:
625633
try:
626634
# If we're stripping comments, then make sure our block ends
@@ -645,7 +653,8 @@ def read_sexpr_block(stream, block_size=16384, comment_char=None):
645653
return tokens
646654
except ValueError as e:
647655
if e.args[0] == "Block too small":
648-
next_block = stream.read(block_size)
656+
read_size *= 2 # exponential growth -> O(log n) re-parses, O(n) total
657+
next_block = stream.read(read_size)
649658
if next_block:
650659
block += next_block
651660
continue

‎nltk/corpus/reader/xmldocs.py‎

Lines changed: 22 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -280,16 +280,32 @@ def _read_xml_fragment(self, stream):
280280
another block.
281281
"""
282282
fragment = ""
283+
# Track whether the fragment currently ends inside an unterminated
284+
# '<...' tag, updated over just the newly-read block. While it does, the
285+
# fragment can never be well-formed, so the ``_VALID_XML_RE`` match below
286+
# (which backtracks over ``[^>]*`` across the whole buffer looking for a
287+
# '>') is skipped -- re-running it on every 1 KiB block otherwise makes a
288+
# single oversized tag O(n^2) (CWE-407). Skipping it is behaviour-
289+
# preserving: an in-tag fragment always fails that match anyway.
290+
in_tag = False
291+
last_lt = -1 # absolute index in ``fragment`` of the most recent '<'
283292

284293
if isinstance(stream, SeekableUnicodeStreamReader):
285294
startpos = stream.tell()
286295
while True:
287296
# Read a block and add it to the fragment.
297+
block_start = len(fragment)
288298
xml_block = stream.read(self._BLOCK_SIZE)
289299
fragment += xml_block
300+
for offset, ch in enumerate(xml_block):
301+
if ch == "<":
302+
in_tag = True
303+
last_lt = block_start + offset
304+
elif ch == ">":
305+
in_tag = False
290306

291307
# Do we have a well-formed xml fragment?
292-
if self._VALID_XML_RE.match(fragment):
308+
if not in_tag and self._VALID_XML_RE.match(fragment):
293309
return fragment
294310

295311
# Do we have a fragment that will never be well-formed?
@@ -304,9 +320,11 @@ def _read_xml_fragment(self, stream):
304320
raise ValueError("Unexpected end of file: tag not closed")
305321

306322
# If not, then we must be in the middle of a <..tag..>.
307-
# If appropriate, backtrack to the most recent '<'
308-
# character.
309-
last_open_bracket = fragment.rfind("<")
323+
# If appropriate, backtrack to the most recent '<' character. Use
324+
# the incrementally-tracked index rather than ``fragment.rfind('<')``
325+
# so this stays O(1) per block instead of re-scanning the whole
326+
# growing buffer (CWE-407).
327+
last_open_bracket = last_lt
310328
if last_open_bracket > 0:
311329
if self._VALID_XML_RE.match(fragment[:last_open_bracket]):
312330
if isinstance(stream, SeekableUnicodeStreamReader):

‎nltk/metrics/aline.py‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,14 @@
4646

4747
inf = float("inf")
4848

49+
#: Maximum input length accepted by :func:`align`. ``align`` fills an
50+
#: ``(m+1)x(n+1)`` numpy matrix with a very expensive per-cell cost (five
51+
#: ``sigma_*`` calls, each scanning ~30 phonetic features), so it is O(n*m) time
52+
#: and memory over two untrusted strings -- a CPU/memory DoS (CWE-407). Phonetic
53+
#: strings are short; ``align("a"*400, "a"*400)`` already runs for over a minute.
54+
#: Raise this if you genuinely need to align long, trusted strings.
55+
MAX_ALIGN_INPUT_LEN = 512
56+
4957
# Default values for maximum similarity scores (Kondrak 2002: 54)
5058
C_skip = -10 # Indels
5159
C_sub = 35 # Substitutions
@@ -1376,6 +1384,16 @@ def align(str1, str2, epsilon=0):
13761384
_validate_segments(str1, "str1")
13771385
_validate_segments(str2, "str2")
13781386

1387+
longest = max(len(str1), len(str2))
1388+
if longest > MAX_ALIGN_INPUT_LEN:
1389+
raise ValueError(
1390+
f"align: input length {longest} exceeds MAX_ALIGN_INPUT_LEN "
1391+
f"({MAX_ALIGN_INPUT_LEN}). align fills an O(n*m) matrix with a heavy "
1392+
"per-cell cost over two untrusted strings (CWE-407); a long input is "
1393+
"a CPU/memory DoS. Raise nltk.metrics.aline.MAX_ALIGN_INPUT_LEN if "
1394+
"you need to align longer trusted strings."
1395+
)
1396+
13791397
m = len(str1)
13801398
n = len(str2)
13811399
# This includes Kondrak's initialization of row 0 and column 0 to all 0s.

‎nltk/metrics/distance.py‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,32 @@
2424

2525
from nltk.pathsec import open as _secure_open
2626

27+
#: Maximum input length accepted by the super-linear two-string distance
28+
#: functions in this module: the O(n*m) time-and-memory :func:`edit_distance` /
29+
#: :func:`edit_distance_align` (they build a full ``(n+1)x(m+1)`` DP matrix) and
30+
#: the O(n**2) :func:`jaro_similarity`. Both operate on two untrusted strings, so
31+
#: an unbounded length is a CPU/memory DoS (CWE-407, CWE-400): e.g.
32+
#: ``edit_distance("a"*40000, "b"*40000)`` allocates tens of GB and runs for
33+
#: hours. CVE-2026-12926 hardened ``jaro_similarity``'s inner loop from O(n**3)
34+
#: to O(n**2) but left the length unbounded, so the quadratic DoS survived; this
35+
#: cap closes it and the matching ``edit_distance`` hole. A real distance query
36+
#: is short; raise this if you genuinely need to compare very long, trusted
37+
#: strings.
38+
MAX_DISTANCE_INPUT_LEN = 2000
39+
40+
41+
def _check_distance_input_len(s1, s2, func_name):
42+
"""Reject oversized inputs to the O(n*m)/O(n**2) distance functions."""
43+
longest = max(len(s1), len(s2))
44+
if longest > MAX_DISTANCE_INPUT_LEN:
45+
raise ValueError(
46+
f"{func_name}: input length {longest} exceeds MAX_DISTANCE_INPUT_LEN "
47+
f"({MAX_DISTANCE_INPUT_LEN}). This function is super-linear in the "
48+
"input length over two untrusted strings (CWE-407/CWE-400); a long "
49+
"input is a CPU/memory DoS. Raise nltk.metrics.distance."
50+
"MAX_DISTANCE_INPUT_LEN if you need to compare longer trusted strings."
51+
)
52+
2753

2854
def _edit_dist_init(len1, len2):
2955
lev = []
@@ -87,6 +113,7 @@ def edit_distance(s1, s2, substitution_cost=1, transpositions=False):
87113
:type transpositions: bool
88114
:rtype: int
89115
"""
116+
_check_distance_input_len(s1, s2, "edit_distance")
90117
# set up a 2-D array
91118
len1 = len(s1)
92119
len2 = len(s2)
@@ -186,6 +213,7 @@ def edit_distance_align(s1, s2, substitution_cost=1):
186213
:type substitution_cost: int
187214
:rtype: List[Tuple(int, int)]
188215
"""
216+
_check_distance_input_len(s1, s2, "edit_distance_align")
189217
# set up a 2-D array
190218
len1 = len(s1)
191219
len2 = len(s2)
@@ -334,6 +362,12 @@ def jaro_similarity(s1, s2):
334362
if s1 == s2:
335363
return 1.0
336364

365+
# CVE-2026-12926 cut the inner membership test from O(n) to O(1) (below),
366+
# but the surrounding double loop is still O(n**2) and had no length bound,
367+
# so two long near-matching strings remained a CPU DoS. Cap the length to
368+
# close that residual (CWE-407).
369+
_check_distance_input_len(s1, s2, "jaro_similarity")
370+
337371
# First, store the length of the strings
338372
# because they will be re-used several times.
339373
len_s1, len_s2 = len(s1), len(s2)

0 commit comments

Comments
 (0)