Stack Overflow Outage Postmortem
stackstatus.net
Stack Overflow Outage Postmortem
1–10 of 335 posts
Re: Stack Overflow Outage Postmortem
#2Could this has been a deliberate/malicious act? Why else would someone post 20,000 consecutive characters of whitespace on a comment line?
Also, the "homepage" of StackOverflow does not show any 'comments' - it is just the top questions? Why was the page loading any comments in the first place?
Re: Stack Overflow Outage Postmortem
#3Is this the sort of thing that https://github.com/google/re2 was made to solve?
Re: Stack Overflow Outage Postmortem
#4Could this has been a deliberate/malicious act? Why else would someone post 20,000 consecutive characters of whitespace on a comment line? Also, the "homepage" of StackOverflow does not show any 'comments' - it is just the top questions? Why was the page loading any comments in the first place?
more likely select all copy + paste
Re: Stack Overflow Outage Postmortem
#5This seems like a hard-to-expect edge case for real. I think catching edge case is needed (means more rigorous testing). This is the equivalence of algorithm complexity analysis. How bad can my algorithm be? But regular expression, to be honest, is usually something I hardly think about performance. I don't know about others, but most of the my input are small enough. How big of an input should I test? If I were to deal with a lot of characters, I would be doing substring replacement.
Re: Stack Overflow Outage Postmortem
#6Perfect.
Awesome bug. Awesome Post Mortem.
This was just fun to read.
While this might have been caused by mistake - these types of bugs can be (and are) abused by hackers.
https://www.owasp.org/index.php/Regular_expression_Denial_of... https://en.wikipedia.org/wiki/ReDoS
The post also links to this video: https://vimeo.com/112065252
Re: Stack Overflow Outage Postmortem
#7I like this because it shows how important it is to understand the inner workings of the tools in your toolbox. It could serve as a nice example in some 'Languages and Grammars' course at the University for additional motivation.
Re: Stack Overflow Outage Postmortem
#8Google cache saved me during these 34 minutes.
Re: Stack Overflow Outage Postmortem
#9Ha! 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 this issue, basically Perl popularized bad computer science... "regexes" are not regular languages.
They say that this particular case triggered quadratic behavior, not exponential, but the point is that there is a linear time algorithm to do this.
The file b.c in the awk repo implements the linear time algorithm:
https://github.com/andychu/bwk/blob/master/b.c
(and rsc's site has some nice sample code too, as well as caveats with regard to capturing and so forth)
Re: Stack Overflow Outage Postmortem
#10> So the Regex engine has to perform a “character belongs to a certain character class” check (plus some additional things) 20,000+19,999+19,998+…+3+2+1 = 199,990,000 times, and that takes a while.
199,990,000 isn't really all that many. I'm a little surprised it didn't just cause a momentary blip in performance.
edit: whoops, i guess that's per page load