I still haven't figured out why regex engines font use state machines where possible (i.e. in the absence of back references and such). Is that not an obvious optimization?
Stack Overflow Outage Postmortem
111–120 of 335 posts
Re: Stack Overflow Outage Postmortem
#112Earlier quoted context omitted.
System not responsive. Look at the CPU load. Look at the process peaking at 100%. Force dump the stack track of the process couple times. Hmm. All of them stuck in the regex engine. Look back up the stack track to see who calls it. Oh, it's on the home page's text cleansing code. Something like that.
This is exactly what we did to diagnose (source: I was on the call). The only tricky part was figuring out which post it was, since it wasn't in the stacktrace. To do that, we grabbed the 3000 most recent posts and ran the regex against them. By that point we already had the code fix (another dev working on it in parallel), but if we hadn't we also could have gotten back up by just deleting the post.
Any idea if it was a malicious attempt? It kind of sounds like it was.
Re: Stack Overflow Outage Postmortem
#113Is this the sort of thing that https://github.com/google/re2 was made to solve?
Also implemented in the go stdlib https://golang.org/pkg/regexp
Re: Stack Overflow Outage Postmortem
#114Ha! The same bug happened internally at my company. In that case it was a regex matching a URL taking so much CPU as to cause a DOS of a proxy server. I won't be surprised if it's happened to someone here too. This is very timely, because minutes ago, I made a link to Russ Cox's articles in my Kernighan awk repo: https://github.com/andychu/bwk https://swtch.com/~rsc/regexp/regexp1.html If you are not familiar with th…
The key quote here is: "Regular expressions are one of computer science's shining examples of how using good theory leads to good programs ..." "Today, regular expressions have also become a shining example of how ignoring good theory leads to bad programs. The regular expression implementations used by today's popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools." The…
Unfortunately, there is a hint as to how this has happened:
"This strategy is no longer practical: users have come to rely on backreferences for at least occasional use, and backreferences are part of the POSIX standard for regular expressions."
What better excuse is there for a poor implementation than standards compliance? In many ways, using regex with backtracking by default is like programming in Lisp without tail-call optimizations. If the POSIX standard is going to require backreferences, then it should also require a non-backtracking implementation for regular expressions without backreferences, just like the Scheme specification requires implementations to support tail-call optimization.
The comparison is valid because they both can create a quadratic runtime from a linear time algorithm.
Re: Stack Overflow Outage Postmortem
#115> If the string to be matched against contains 20,000 space characters in a row, but not at the end, then the Regex engine will start at the first space, check that it belongs to the \s character class, move to the second space, make the same check, etc. After the 20,000th space, there is a different character, but the Regex engine expected a space or the end of the string. Realizing it cannot match like this it back…
> I mean, if the engine tried matching from the second space, what would be matching the first space? Something has to. Some regex engines provide an API call that puts an implicit `.STAR?` at the beginning of the regex so that the semantics of the match are "match anywhere" as opposed to "match only from the start of the string." (This is in fact the difference between Python's `match` and `search` methods.) Assumin…
By .? you mean .* ?
Re: Stack Overflow Outage Postmortem
#116Earlier quoted context omitted.
Imagine if they had only posted 10,000 or 15,000 characters, and it just slowed the site down. How fast would it have been noticed? Hours? Days?
Good monitoring (which I expect the SO guys to have) would have triggered on a spike in 95% or 99% response times so probably almost as quickly
Actually we average less than 10% CPU on the web tier... so anything over that warrants investigation. Graph of CPU during today's issue at https://twitter.com/Nick_Craver/status/755793398544601088
Re: Stack Overflow Outage Postmortem
#117> If the string to be matched against contains 20,000 space characters in a row, but not at the end, then the Regex engine will start at the first space, check that it belongs to the \s character class, move to the second space, make the same check, etc. After the 20,000th space, there is a different character, but the Regex engine expected a space or the end of the string. Realizing it cannot match like this it back…
> I mean, if the engine tried matching from the second space, what would be matching the first space? Something has to. Some regex engines provide an API call that puts an implicit `.STAR?` at the beginning of the regex so that the semantics of the match are "match anywhere" as opposed to "match only from the start of the string." (This is in fact the difference between Python's `match` and `search` methods.) Assumin…
I guess this must have been the scenario. Perl also defaults to re.search but does not exhibit the pathological case, maybe because it knows it can't find a $ in a block of \s.
Re: Stack Overflow Outage Postmortem
#118It seems like there should be a way to determine whether a regex can be compiled using the classic O(n) DFA algorithm or with whatever madness PCREs use to support backtracking and so on.
Anybody know if any regex engines attempt this?
Obviously you can still shoot yourself in the foot, but it's somewhat more difficult to do so in a situation like this where the regex in question "looks" cheap.
Re: Stack Overflow Outage Postmortem
#119"This regular expression has been replaced with a substring function." This should be the title of a book on software engineering.
"I had a problem, solved it with RegExp, now I have two problems"
Re: Stack Overflow Outage Postmortem
#120Nice bug. I tried to replicate this and indeed, the time to notice that no match is found is growing very fast with the length of the input. Using a substring check is a good fix, but I tried to change the regex to fix this and: if instead of an end anchor, you can add an optional non-whitespace character at the end of the pattern, then you only have to check whether the optional part is empty. Testing with very long…
So, you're saying that if you enjoy tricky gotchas and puzzle-solving over reliability, then the perl-aping regex implementations have your back?
I am saying that I have been nerd sniped. Actually I tend do stay away from regexes.