Natural Language Toolkit (NLTK): ReDoS in NLTK ReviewsCorpusReader FEATURES regex

 1import multiprocessing as mp
 2import re
 3import time
 4 
 5# --- The vulnerable regex, verbatim from nltk/corpus/reader/reviews.py L70-71 ---
 6FEATURES_VULN = re.compile(r"((?:(?:\w+\s)+)?\w+)\[((?:\+|\-)\d)\]")
 7 
 8# --- Bounded variant from the fix (PR #3583): cap the per-label word run.
 9#     A generous bound (real feature labels are short noun phrases) makes the
10#     run linear while never affecting legitimate corpora. ---
11WORD_BOUND = 50
12FEATURES_FIXED = re.compile(
13    r"((?:(?:\w+\s){0,%d})?\w+)\[((?:\+|\-)\d)\]" % WORD_BOUND
14)
15 
16TIMEOUT = 20.0  # seconds, per measurement
17SIZES = [1000, 2000, 4000, 8000, 16000]  # words on a single bracket-less line
18 
19 
20def _bad_line(n_words):
21    """A long line of plain words with NO trailing bracketed annotation."""
22    return ("word " * n_words).rstrip()
23 
24 
25def _worker(pattern_str, line, q):
26    pat = re.compile(pattern_str)
27    t0 = time.perf_counter()
28    pat.findall(line)
29    q.put(time.perf_counter() - t0)
30 
31 
32def timed_findall(pattern, line, timeout=TIMEOUT):
33    """Run pattern.findall(line) in a killable process; return seconds or None (timeout)."""
34    q = mp.Queue()
35    p = mp.Process(target=_worker, args=(pattern.pattern, line, q))
36    p.start()
37    p.join(timeout)
38    if p.is_alive():
39        p.terminate()
40        p.join()
41        return None
42    return q.get() if not q.empty() else None
43 
44 
45def bench(label, pattern):
46    print(f"\n[{label}]  pattern: {pattern.pattern}")
47    print(f"  {'words':>7} {'~bytes':>8}   {'time':>12}   {'x prev':>7}")
48    prev = None
49    for n in SIZES:
50        line = _bad_line(n)
51        t = timed_findall(pattern, line)
52        if t is None:
53            print(f"  {n:>7} {len(line):>8}   {'>%.0fs TIMEOUT' % TIMEOUT:>12}   {'--':>7}")
54            prev = None
55        else:
56            ratio = f"{t/prev:.1f}x" if prev else "--"
57            print(f"  {n:>7} {len(line):>8}   {t*1000:>9.1f} ms   {ratio:>7}")
58            prev = t
59 
60 
61def parity_check():
62    """The bound must NOT change extraction on a realistic annotated line."""
63    real = (
64        "the picture quality[+2] and battery life[+1] are great but "
65        "the lens cap[-1] feels cheap and the menu system[-2] is slow"
66    )
67    a = FEATURES_VULN.findall(real)
68    b = FEATURES_FIXED.findall(real)
69    print("\n[parity] realistic annotated line — extraction must be identical")
70    print(f"  vulnerable regex -> {a}")
71    print(f"  bounded   regex  -> {b}")
72    print(f"  identical: {a == b}")
73    return a == b
74 
75 
76def main():
77    print("=" * 66)
78    print(" NLTK ReviewsCorpusReader FEATURES ReDoS PoC (quadratic backtracking)")
79    print("=" * 66)
80    print(f" per-call timeout = {TIMEOUT:.0f}s   word bound (fix) = {WORD_BOUND}")
81 
82    bench("VULNERABLE  reviews.py L70-71", FEATURES_VULN)
83    bench("BOUNDED     fix #3583", FEATURES_FIXED)
84    same = parity_check()
85 
86    print("\n" + "=" * 66)
87    print(" Vulnerable: ~4x time per input doubling  => O(n^2) quadratic ReDoS")
88    print(" Bounded:    ~2x time per input doubling  => O(n)   linear, stays in ms")
89    print(f" Extraction parity on real annotations preserved: {same}")
90    print(" A single ~100k-word bracket-less review line hangs reviews()/features()/sents().")
91    print("=" * 66)
92 
93 
94if __name__ == "__main__":
95    main()