Regex Engines: Backtracking vs. Finite Automata
A backtracking regex engine tries one path at a time, which can be fast but also exponentially slow. A finite-automata engine (like Go's) checks all paths at once, guaranteeing linear time. The footgun is using a backtracking engine on untrusted user input.
Think of a backtracking regex engine as an optimist, trying one path at a time. A finite-automata engine (like Go's or RE2) is a pessimist, exploring all paths at once. The optimist can be faster on simple matches, but a malicious pattern can cause exponential backtracking, freezing your server. The pessimist guarantees a match time linear to input size, preventing this. The footgun is using a backtracking engine (e.g., Python, Perl) on untrusted input, creating a ReDoS vulnerability.
Read the original → github.com
- #regex
- #performance
- #security
- #go
- #rust
Get five bites like this every day.
Tezvyn delivers a daily feed of 60-second tech bites with quizzes to lock in what you learn.