Comment by aalleavitch
6 years ago
I’d like to imagine that as long as we live, poorly written regular expressions will continue to be the cause of breaking issues.
6 years ago
I’d like to imagine that as long as we live, poorly written regular expressions will continue to be the cause of breaking issues.
StackOverflow also had an outage a few years ago that was caused by exponential blow-up of a backtracking regular expression.
https://stackstatus.net/post/147710624694/outage-postmortem-...
That blow up is quadratic, not exponential: "This is not classic catastrophic backtracking (talk on backtracking) (performance is O(n²), not exponential, in length), but it was enough."
Some years ago I tried to create an exponential time regex in Perl, and only managed a quadratic time one after a bit of experimenting.
But, as you said, quadratic is often already fatal on realistic data.