Python Regex Denial of Service: Avoid Catastrophic Backtracking

Prevent excessive backtracking when matching untrusted input.

How It Works

Some nested quantifiers can take exponential time on a long near-match. Prefer anchored and bounded patterns, limit input size, avoid nested ambiguous repetitions, and consider a regex engine with time limits for hostile inputs.

Step-by-Step Example

import re
safe_pattern = re.compile(r'[A-Za-z0-9_]{1,32}')
print(bool(safe_pattern.fullmatch('normal_name_42')))
print(bool(safe_pattern.fullmatch('x' * 100)))

Understanding the Example

• The expression "re.compile(r'[A-Za-z0-9_]{1,32}')" supplies the value stored as 'safe_pattern'. This value is then used or checked by the later statements.
• The print() call exposes the result so you can compare it with the behavior described above. Check the value and its type when experimenting.

A successful run of this example prints the following output:

True
False

Where This Fits in a Real Program

Start by writing down examples that should match and examples that must fail. Check whether you need to locate a substring, match a prefix or validate an entire field; these are different operations. Unicode and escape sequences can also change which characters are matched, so test accented text and empty input.

Practice: Try It Yourself

Python standard re does not offer a general per-match timeout argument.

For this exercise, predict the result before running the changed code. Then explain the difference between the original and modified cases using the actual values, not just whether the program completed.

Further Reading

Read the official Python documentation for complete parameters, return types and exceptions.

Common Beginner Mistakes

• Using ambiguous nested quantifiers on unbounded untrusted strings and exposing a service to denial of service.
• Replace a broad repeating pattern with a constrained identifier whitelist.

Key Takeaways

• Prevent excessive backtracking when matching untrusted input.
• Some nested quantifiers can take exponential time on a long near-match.
• Apply the demonstrated operation to the practice input and verify its result before depending on it in a larger program.