", " " else WORD
with pytest.raises(TimeoutError):
pat.findall(tag * 60000)
class TestReadSexprBlockQuadratic:
def test_correctness_preserved(self):
assert read_sexpr_block(io.StringIO("(a (b c)) (d e)")) == [
"(a (b c))",
"(d e)",
]
assert read_sexpr_block(io.StringIO("foo bar (x y)")) == ["foo", "bar", "(x y)"]
assert read_sexpr_block(io.StringIO("# c\n(a b)"), comment_char="#") == [
"(a b)"
]
def test_unclosed_sexpr_is_subquadratic(self):
# Pre-patch: an oversized single s-expression is re-parsed from position
# 0 on every fixed-size grow -> O(n^2). Exponential read growth makes it
# O(n). A ratio test is robust to the (high) linear constant: 4x input
# should cost ~4x (linear), not ~16x (quadratic).
t1 = _elapsed(lambda: read_sexpr_block(io.StringIO("(" * 200_000)))
t4 = _elapsed(lambda: read_sexpr_block(io.StringIO("(" * 800_000)))
assert t4 < 10 * t1 + 0.5
# ==========================================================================
# GENERAL ALGORITHMIC-DoS BATCH (fixed) -- single-untrusted-input O(n^2)
# ==========================================================================
class TestTweetTokenizerDigitDoS:
def test_benign_tokenize_unchanged(self):
from nltk.tokenize.casual import TweetTokenizer
assert TweetTokenizer().tokenize("Hi @u http://x.com :) 555-1234 #tag") == [
"Hi",
"@u",
"http://x.com",
":)",
"555-1234",
"#tag",
]
def test_digit_run_is_bounded(self, monkeypatch):
# Pre-patch: the phone sub-pattern backtracks O(n^2) on a digit run
# (~40 KB → HANG). Now bounded by the regex wall-clock timeout.
import nltk.redos as redos_mod
monkeypatch.setattr(redos_mod, "DEFAULT_TIMEOUT", 0.5)
from nltk.tokenize.casual import TweetTokenizer
with pytest.raises(TimeoutError):
TweetTokenizer().tokenize("1" * 80000)
class TestRibesResidualDoS:
def test_benign_alignment_and_score(self):
from nltk.translate.ribes_score import sentence_ribes, word_rank_alignment
assert word_rank_alignment(["the", "cat"], ["the", "cat"]) == [0, 1]
assert sentence_ribes([["the", "cat", "sat"]], ["the", "cat", "sat"]) == 1.0
def test_long_low_cardinality_is_bounded(self):
# Residual: the window cap = len(reference), so low-cardinality tokens
# never early-break and the loop runs to n (O(n^2)-O(n^3)). Now capped.
from nltk.translate.ribes_score import word_rank_alignment
with pytest.raises(ValueError):
word_rank_alignment(["a"] * 3000, ["a"] * 3000)
class TestSyllableTokenizerDoS: # SyllableTokenizer -- has MULTIPLE directions
def test_benign_syllabification_unchanged(self):
from nltk.tokenize import SyllableTokenizer
assert SyllableTokenizer().tokenize("justification") == [
"jus",
"ti",
"fi",
"ca",
"tion",
]
assert SyllableTokenizer().tokenize("foobar") == ["foo", "bar"]
def test_low_vowel_run_is_linear_and_unbounded(self):
# A run with <=1 vowel (e.g. a long digit string) hits the O(n) early
# return *before* the length guard, so it must still succeed unchanged.
# This is the regression guard for the guard-placement bug: a blanket
# length check at the top of tokenize() wrongly rejected `'9'*10000`.
from nltk.tokenize import SyllableTokenizer
text = "9" * 10000
assert SyllableTokenizer().tokenize(text) == [text]
def test_direction1_vowelless_syllables_are_linear(self, monkeypatch):
# Pre-patch: `validate_syllables` rebuilt the whole list
# (`valid_syllables[:-1] + [...]`) for every vowelless syllable, so a
# token like 'aebcd'*n cost O(n^2). In-place merge makes it linear.
#
# This is a wall-clock ratio test, so it must be robust to CI timing
# noise: (1) a base size large enough that a single tokenize is well
# above timer resolution (a 4000-rep base measured ~0.01s -- noise
# dominated -- and made the ratio explode on a free-threaded runner); and
# (2) the MEDIAN of a few runs, robust to both a fast and a slow outlier.
# Linear -> t4 ~ 4*t1; the pre-fix O(n^2) -> t4 ~ 16*t1, so an 8x
# threshold separates them with wide margin.
import statistics
from nltk.tokenize import SyllableTokenizer
monkeypatch.setattr(SyllableTokenizer, "MAX_TOKEN_LEN", 10**9)
def _median(n):
return statistics.median(
_elapsed(lambda: SyllableTokenizer().tokenize("aebcd" * n))
for _ in range(3)
)
t1 = _median(8000)
t4 = _median(32000) # 4x the input
assert t4 < 8 * t1 + 0.5
def test_direction2_giant_multivowel_token_is_bounded(self):
# A multi-vowel token passes the early return and reaches the O(n)
# per-character materialisation; the length guard caps it (CWE-407).
from nltk.tokenize import SyllableTokenizer
with pytest.raises(ValueError):
SyllableTokenizer().tokenize("a" * 5000)
class TestDistanceQuadraticDoS: # nltk.metrics.distance -- edit_distance + jaro
def test_benign_results_unchanged(self):
from nltk.metrics import distance
assert distance.edit_distance("kitten", "sitting") == 3
assert distance.edit_distance("rain", "shine") == 3
assert distance.edit_distance_align("rain", "shine") == [
(0, 0),
(1, 1),
(2, 2),
(3, 3),
(4, 4),
(4, 5),
]
assert round(distance.jaro_similarity("MARTHA", "MARHTA"), 4) == 0.9444
assert distance.jaro_similarity("", "") == 1.0
def test_edit_distance_length_is_bounded(self):
# O(n*m) time AND memory over two args: `edit_distance("a"*40000,
# "b"*40000)` allocates tens of GB and runs for hours. Now length-capped.
from nltk.metrics import distance
n = distance.MAX_DISTANCE_INPUT_LEN + 1
with pytest.raises(ValueError):
distance.edit_distance("a" * n, "b" * n)
def test_edit_distance_align_length_is_bounded(self):
from nltk.metrics import distance
n = distance.MAX_DISTANCE_INPUT_LEN + 1
with pytest.raises(ValueError):
distance.edit_distance_align("a" * n, "b" * n)
def test_jaro_length_is_bounded(self):
# CVE-2026-12926 fixed jaro's inner loop O(n^3)->O(n^2) but left the
# length unbounded, so two long near-matching strings stayed a quadratic
# DoS. The length cap closes that residual.
from nltk.metrics import distance
n = distance.MAX_DISTANCE_INPUT_LEN + 1
with pytest.raises(ValueError):
distance.jaro_similarity("a" * n, "b" * n)
def test_asymmetric_long_arg_is_bounded(self):
# The cap keys off the *longest* arg, so a short-vs-huge call (which still
# allocates an O(n) matrix row-count over the huge side) is caught too.
from nltk.metrics import distance
with pytest.raises(ValueError):
distance.edit_distance("a", "b" * (distance.MAX_DISTANCE_INPUT_LEN + 1))
class TestAlineQuadraticDoS: # nltk.metrics.aline.align
def test_benign_alignment_unchanged(self):
pytest.importorskip("numpy")
from nltk.metrics import aline
# sibling of jaro in the same distance family; align two short words.
assert len(aline.align("driy", "tres")) > 0
def test_length_is_bounded(self):
pytest.importorskip("numpy")
from nltk.metrics import aline
n = aline.MAX_ALIGN_INPUT_LEN + 1
with pytest.raises(ValueError):
aline.align("a" * n, "a" * n)
class TestGaleChurchQuadraticDoS: # nltk.translate.gale_church.align_blocks
def test_benign_alignment_unchanged(self):
from nltk.translate.gale_church import align_blocks
assert align_blocks([5, 5, 5], [7, 7, 7]) == [(0, 0), (1, 1), (2, 2)]
assert align_blocks([10, 5, 5], [12, 20]) == [(0, 0), (1, 1), (2, 1)]
def test_block_count_is_bounded(self):
# `backlinks[(i, j)]` is stored for every cell and never pruned, so two
# texts split into many tiny "sentences" cost O(n*m) time+memory.
from nltk.translate.gale_church import MAX_ALIGN_BLOCKS, align_blocks
with pytest.raises(ValueError):
align_blocks([5] * (MAX_ALIGN_BLOCKS + 1), [5] * 10)
class TestTextTilingDoS:
def test_oversized_document_is_bounded(self):
from nltk.tokenize import TextTilingTokenizer
with pytest.raises(ValueError):
TextTilingTokenizer().tokenize("x" * 2_000_000)
class TestChildesReplaceDoS:
def _write(self, tmp_path, nwords):
ns = "http://www.talkbank.org/ns/talkbank"
ws = "".join(f"