Catastrophic Backtracking (ReDoS)

import re
import time

# 1) The classic vulnerable shapes
#    Avoid these patterns:
#      (a+)+        nested quantifiers
#      (a|a)*       alternation where both branches match same chars
#      (.*a){10}    repeated greedy capture with a constant suffix
#      ^(\\w+)*$    quantified group that can match in many ways

vuln = re.compile(r'^(a+)+$')
def time_match(rx, s):
    t = time.perf_counter()
    rx.match(s)
    return time.perf_counter() - t

for n in (10, 20, 25, 28):
    s = 'a' * n + 'b'              # 'b' forces backtracking through every split
    print(f'len={n:>3}  took={time_match(vuln, s):.3f}s')

# 2) Same shape, safe rewrite — anchor + character class, no nesting
safe = re.compile(r'^a+$')
print(f'safe: len=200 took={time_match(safe, "a" * 200 + "b"):.6f}s')

# 3) Real-world ReDoS pattern from the wild: an email validator
bad_email = re.compile(r'^([a-zA-Z0-9_.+-]+)+@([a-zA-Z0-9-]+)+\.([a-zA-Z0-9-.]+)+$')
# Use an attack string like: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaa!'
# It will pin the CPU on most engines.

# Safer email check: keep it loose, validate by SENDING a token instead.
good_email = re.compile(r'^[^\s@]+@[^\s@]+\.[^\s@]+$')

# 4) Defensive practices that prevent ReDoS
# a) Length-cap inputs before matching
def safe_match(rx, s, max_len=1000):
    if len(s) > max_len: return None
    return rx.match(s)

# b) Prefer character classes over alternations when they overlap
# c) Avoid nested quantifiers — refactor (a+)+ to a+
# d) Use re2 (Google's library) when patterns are user-supplied
#    pip install pyre2
# import re2 as re                    # linear-time DFA-style engine

# e) Set a wall-clock budget if you must run untrusted regex
def with_timeout(fn, seconds=1.0):
    import signal
    def handler(*_): raise TimeoutError()
    signal.signal(signal.SIGALRM, handler)
    signal.alarm(int(seconds))
    try: return fn()
    finally: signal.alarm(0)

// Catastrophic backtracking from nested quantifiers like (a+)+\$ + 'aaaaaaaaaa!'
// Defences:
//   - Avoid nested quantifiers.
//   - Prefer atomic groups / possessive quantifiers (PCRE).
//   - In Node, use safe-regex / a timeout (e.g. RE2).
//   - In JS, use the built-in /v flag + write greedy quantifiers carefully.