Greedy vs Non-Greedy Matching and ReDoS

A deep understanding of regex quantification is the dividing line between brittle, inefficient scripts and high-performance, secure parsing engines. Python's re module uses a Non-deterministic Finite Automaton (NFA) with backtracking.

Improper quantifier choices not only introduce logic bugs (such as capturing across multiple HTML tags or quoted strings), but can also expose production services to Regular Expression Denial of Service (ReDoS) through catastrophic backtracking.

1. Greedy vs Lazy (Non-Greedy) Quantifiers

By default, Python quantifiers are Greedy: they match as many characters as possible before checking whether the remainder of the pattern succeeds.

Appending a ? to any quantifier converts it into a Lazy (Non-Greedy) quantifier: it matches as few characters as possible, expanding one character at a time only when necessary to satisfy the rest of the pattern.

Quantifier Comparison Table

2. Better Than Lazy: The Negated Character Class Pattern

While .*? fixes overshooting, lazy matching still incurs repeated backtracking checks at every single character step.

A cleaner, more performant alternative is the Negated Character Class ([^...]*):

Why is [^"]* superior? It consumes characters in a single forward scan without backtracking, running significantly faster in CPython.

3. Catastrophic Backtracking and ReDoS Vulnerabilities

Because Python's regex engine uses a backtracking NFA, nested quantifiers with overlapping alternatives can cause the number of execution paths to explode exponentially ($O(2^N)$). This vulnerability is known as Regular Expression Denial of Service (ReDoS).

4. ReDoS Mitigation Techniques

1. 1
   Avoid Nested Ambiguous Quantifiers: Never nest quantifiers on overlapping character sets (e.g. (x+)+, (\d+|\s+)*, (a|b|ab)*).
2. 2
   Use Strict Anchor Demarcations: Bound patterns with specific delimiters.
3. 3
   Unroll the Loop: When matching delimiters, rewrite (A|B)* into A*(BA*)* where $A$ and $B$ are mutually exclusive sets.
4. 4
   Enforce Input Timeouts: When parsing untrusted user inputs in web applications, enforce maximum string length limits (e.g. input_str[:1000]).

5. Architectural Summary Table

Multiple Choice Questions

1.

What turns a standard greedy quantifier (such as * or +) into a lazy (non-greedy) quantifier in Python regular expressions? A. Prefixing with ! B. Appending a question mark ? (e.g., *? or +?) C. Wrapping in square brackets [+] D. Adding the flag re.LAZY

2.

Given the target string "<b>bold</b> and <i>italic</i>", what is the result of applying re.findall(r"<.*>", string)? A. ['<b>', '</b>', '<i>', '</i>'] B. ['<b>bold</b> and <i>italic</i>'] C. ['<b>bold</b>', '<i>italic</i>'] D. []

3.

Why is the negated character class r'"([^"]*)"' preferred over the lazy quantifier r'"(.*?)"' for extracting quoted strings? A. Negated character classes are deterministic and scan forward in C without character-by-character backtracking, running substantially faster. B. Lazy quantifiers cannot handle uppercase letters. C. Negated character classes automatically strip whitespace. D. Lazy quantifiers only work in Python 2.

4.

What is "Catastrophic Backtracking" in regular expressions? A. When an unclosed parenthesis causes a syntax error. B. When nested or overlapping quantifiers force a backtracking regex engine to evaluate an exponential number of permutations upon a non-matching input, freezing the CPU (ReDoS). C. When disk space runs out during pattern compilation. D. When memory is freed prematurely.

5.

Which of the following regex patterns contains a high risk of catastrophic backtracking (ReDoS)? A. ^[a-zA-Z0-9_-]+$ B. ^([a-z]+)+$ C. ^\d{4}-\d{2}-\d{2}$ D. ^https?://[^/]+