Or just stop using terrible regular expression engines with superlinear runtime?
E.g. Rust's regex crate has linear runtime is thus not susceptible to "ReDoS".
E.g. Rust's regex crate has linear runtime is thus not susceptible to "ReDoS".
> This is even before any of the really cheap shots, like observing that the entire bug class is based on unreliable premises: that there are no timeouts or resource limits anywhere else in the system (almost always false, particularly in web development), and that the regular expression engine itself is susceptible to pathological runtime behavior (plenty aren’t).
Is this what you were thinking of? Or am I still missing something?
I'd be curious to see ReDoS reports against programs using regex engines that provide a linear time guarantee.
You're not missing anything: I meant to write more about this, but I forgot and snuck that little paragraph at the last minute in instead.
I think I could have worded this better -- the observation was meant to be that (1) the regular expression's superlinear behavior is not part of the public interface of languages like Python, and (2) lots of these "vulnerabilities" show up in code ends up in a task queue somewhere, meaning that it's subject to timeouts and other resource constraints that ReDoS reporters don't bother to check for.
For (1), what I mean is that Python (or an implementation of Python) could switch to a non-backtracking engine for the subset of compatible regular expressions, and nothing about Python's interface would change.
(1) is in theory right, but it's very rare to see it done. The only one I'm aware of actually doing a "switch between linear time and unbounded backtracking" is Tcl, and I'm not familiar enough with it to know if it actually gives any guarantees.
The difficulty in (1) is rooted in: 1) implementation complexity, 2) performance and 3) match semantics. (1)+(2) are related, and indeed, if you want your linear time engine to compete with your backtracker engine, you're going to need to do a fair bit of work. (3) is also quite tricky. Cox's RE2 paves the path for how to get linear time engines to mostly agree with backtrackers, but there may be some corner cases where there is some disagreement. So for something like Python, (3) may be quite difficult to overcome.
Popping up a level, I'm not sure how relevant all of this is to your overall point. As the author of Rust's regex crate, I actually generally agree with your post, insomuch as catastrophic backtracking is handled as a security vulnerability. I'm mostly just picking at nits and elaborating here.
But I then trimmed that section so this point is mostly irrelevant to the larger post, as you said!
Oof, yes. I know this pain.