TopolearnOne bad pattern on untrusted input can pin a CPU for minutes, a real denial-of-service vector.
Python's re is a backtracking engine: when part of a pattern fails, it goes back and tries the other ways earlier quantifiers could have matched. Usually that's cheap. But with nested or overlapping quantifiers, the number of ways can grow exponentially with input length when the overall match fails.
Classic culprits:
(a+)+$on"aaaa...a!": the inner and outer+can split the run of a's in exponentially many ways.(\w+\s?)+$,(.*,)*,(a|aa)+: alternatives or repetitions that can match the same text in several ways.
Matching succeeds fast; it's the failure path that explodes. Each extra character can double the time, which makes it a denial-of-service vector (ReDoS) when users control the input.
Fixes:
- Make the pieces mutually exclusive:
[^,]*,instead of.*,; remove the redundant inner quantifier (a+$). - Use possessive quantifiers (
*+,++,?+) or atomic groups(?>...), available since Python 3.11. They match greedily and never give back characters, which removes the backtracking states. - Limit input length before matching.
- For untrusted patterns or inputs, use an engine with linear-time guarantees, such as the third-party
google-re2binding.
Note that re has no timeout; a runaway match cannot be interrupted except by killing the thread's process.
Example
import re
import time
def timed(pattern, text):
t = time.perf_counter()
result = re.match(pattern, text)
return result is not None, round(time.perf_counter() - t, 3)
evil = "a" * 24 + "!"
ok, slow = timed(r"(a+)+$", evil)
print(ok, slow > 0.05) # False True (exponential)
ok, fast = timed(r"(?:a++)+$", evil) # possessive inner quantifier
print(ok, fast < 0.01) # False True
ok, fast = timed(r"a+$", evil) # just remove the nesting
print(ok, fast < 0.01) # False True
print(re.match(r"(?>a+)ab", "aaab")) # None: atomic group gives nothing back
print(re.match(r"a+ab", "aaab")) # <re.Match object; span=(0, 4), match='aaab'>Remember
- Nested or overlapping quantifiers can make failing matches exponential
- Possessive quantifiers and atomic groups (3.11+) remove backtracking
- Bound input size or use a linear-time engine for untrusted input
Watch out for
- Testing a pattern only on inputs that match; catastrophic cases show up on near-misses.