Productivity plummets worldwide (regex attack vector)
Stack Overflow Outage Postmortem
31–40 of 335 posts
Re: Stack Overflow Outage Postmortem
#32> It took 10 minutes to identify the cause. I'm impressed they were able to do this so quickly.
I'm guessing they have the right tools to identify the problem. Wish they went into that a little bit more.
Probably went like this: 'web server crashed. so did another. what page did they crash on? ok, let's take a look at the post on that page. what in the....'
Re: Stack Overflow Outage Postmortem
#33I wondered about this for some time.
Simple regex (as in formal language theory) are matched in O(n) time by finite automaton.
Extended regex like PCRE are more powerful, but most of the time are implemented by backtracking engines, where really bad regex pattern might go exponential, but even simple pattern as in postmortem can go O(n^2).
Do implementations optimize simple regex patterns to O(n) matching? Even I wrote x86 JIT regex compiler for fun some time ago. Compilation time was really bad, but matching was O(n).
Re: Stack Overflow Outage Postmortem
#34Not understanding why backtracking happened. Once it hit a non space, non end character, move on. Nothing before can match the regex.
It finds a space, tries to match the rest of the string, fails, rolls back to it and goes forward one, finds a space...
The trick is that there's no guarantee, in general, that a match failing at character N is due to character N, so the regex engine backtracks.
Re: Stack Overflow Outage Postmortem
#35I don't understand something: the regex expected a space character, followed by the end of the string. If the last character wasn't a space, this could never match. Why did the engine keep backtracking, even though it's easy to figure out that it could never match the regex?
Perhaps there simply isn't a separate code path for the presence of an end-of-string anchor and the regex is evaluated left-to-right like any other?
Re: Stack Overflow Outage Postmortem
#36Perfect. 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
Well in this case a post contained 20K whitespaces, so I wouldn't jump to the conclusion that it was a mistake rather than intentional.
Re: Stack Overflow Outage Postmortem
#37The lesson seems to be "Always run trim() before running regex" and "validate content as much as possible before running regex".
Trim would not have worked, the post started with '-- play happy sound for player to enjoy', had 20000 characters of whitespace, and then some other character.
Re: Stack Overflow Outage Postmortem
#38> 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
I presume the strip function happens on every request for the page, which as the homepage for stackoverflow, means 199,990,000 times quite a lot of requests a second.
It's gonna hurt
Re: Stack Overflow Outage Postmortem
#39The lesson seems to be "Always run trim() before running regex" and "validate content as much as possible before running regex".
Or just reject this input. The server isn't the time and place to do data cleanup.
Can always fix this on the frontend with JavaScript for free if it's an actual problem.
Re: Stack Overflow Outage Postmortem
#40This is great. I just want to add something that might not be well-known: StackOverflow is all hosted from ONE web app server! It handles all the writes.