35 ms·

Stack Overflow Outage Postmortem

• laurencei 10y ago
  Could 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?
  • mrbgty 10y ago
    more likely select all copy + paste
  • allannienhuis 10y ago
    on a site like stackoverflow, I would think they get malicious requests like that all the time. Even if it wasn't malicious (perhaps an otherwise benign script gone amuk), I bet something like this happens very often. It would be interesting to find out if something like this goes into their automated regression tests. :)
  • KyleBrandt 10y ago
    We don't think it was intentional. Maybe copy and paste, or something an editor did. To clarify the "comment" was not a Stack Overflow comment, but rather a comment in a code block inside a question.
    • amenod 10y ago
      I am genuinly curious: how did you fix it? Did you remove the spaces first and then tried to use substring / trimming with proper testing done, or did you just implement it in place? I have faced similar dilemmas in the past, but I usually go with "put out the fire, then find the correct solution" approach.
      • KyleBrandt 10y ago
        Implement in place to put the fire out. Pushed to half the web servers, made sure it fixed the problem, then rolled it out the rest. Coding under fire :P
        • skeletonjelly 10y ago
          How did you test this on half? Accessing the single web server directly I'm guessing? Probably not public
    • pcunite 10y ago
      May we see this code comment? Sounds interesting.
  • bluedino 10y ago
    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?
    • mason55 10y ago
      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
      • gbrayut 10y ago
        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 https://twitter.com/Nick_Craver/status/755793398544601088
• selckin 10y ago
  Is this the sort of thing that https://github.com/google/re2 https://github.com/google/re2 was made to solve?
  • chubot 10y ago
    Yes, see my other post in this thread... Russ Cox is the author of RE2 and one of the articles I linked goes into its implementation.
  • deleted 10y ago
    [deleted]
  • nikias 10y ago
    Also implemented in the go stdlib https://golang.org/pkg/regexp https://golang.org/pkg/regexp
    • burntsushi 10y ago
      And Rust! https://github.com/rust-lang-nursery/regex https://github.com/rust-lang-nursery/regex
    • infogulch 10y ago
      And it doesn't have any problems with this particular regex: https://play.golang.org/p/7UFkG3qrpS https://play.golang.org/p/7UFkG3qrpS
      • cyphar 10y ago
        It's been mathematically proven that engines of the form that Go has will always run in linear time for any regular expression, on any input. It's one of the more famous things about regex in general.
    • artursapek 10y ago
      Yeah, the go team seems to be (rightfully) proud of their regexp implementation.
• yeukhon 10y ago
  This 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.
  • jrbancel 10y ago
    > But regular expression, to be honest, is usually something I hardly think about performance. This is actually not an uncommon problem. I recently experienced a backend system going down because of catastrophic backtracking. There is a reason why proper regex libraries have a timeout on the match methods. For example: https://msdn.microsoft.com/en-us/library/hh160204(v=vs.110).aspx https://msdn.microsoft.com/en-us/library/hh160204(v=vs.110)....
    • revelation 10y ago
      A time limit on something like this is so extremely awkward to use. My first problem would be that I'm concerned the implementation doesn't have the resolution; a "reasonable" time limit would be what, 1us for a regex match? Which brings us to the second point: what's this, wall clock time, CPU time? I risk testing this with low load on my dev computer only to have it fail in production because high CPU load means the match just took longer (but wasn't running into a corner case). I think a reasonable "timeout" would be to give an upper limit for character array accesses, like 20*strlen.
• dkopi 10y ago
  Perfect. 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_Service_-_ReDoS https://www.owasp.org/index.php/Regular_expression_Denial_of... https://en.wikipedia.org/wiki/ReDoS https://en.wikipedia.org/wiki/ReDoS The post also links to this video: https://vimeo.com/112065252 https://vimeo.com/112065252
  • Someone1234 10y ago
    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.
    • zymhan 10y ago
      Yeah, I'm trying to figure out how you even get 20,000 spaces into a Stack Exchange post, and how it would render in your browser.
      • jandrese 10y ago
        Browsers typically collapse whitespace, so it probably would render as a single space.
        • KyleBrandt 10y ago
          was in code tags, so had a very long horizontal scroll bar :P
        • dingaling 10y ago
          I frequently complete eBay feedback 'comments' fields[0] with a variety of Unicode spaces and Firefox at least doesn't seem to collapse them. [0] eBay insists on something being entered and when it was a routine transaction with a vendor I seldom have anything useful to say.
• Scea91 10y ago
  I 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.
• antoineMoPa 10y ago
  Google cache saved me during these 34 minutes.
  • tedmiston 10y ago
    Mac app Dash allows downloading & browsing Stack Overflow offline by language. 834 MB for Python. https://kapeli.com/dash https://kapeli.com/dash
    • antoineMoPa 10y ago
      Funny, I was coding on a Chromebook with 525M left in "/".
• chubot 10y ago
  Ha! 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://github.com/andychu/bwk https://swtch.com/~rsc/regexp/regexp1.html 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 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)
  • abecedarius 10y ago
    Since those all have a lot more code than is needed to show the basic idea of an NFA-based matcher: https://github.com/darius/sketchbook/blob/master/regex/nfa_simplest.py https://github.com/darius/sketchbook/blob/master/regex/nfa_s...
  • mamcx 10y ago
    Sadly not much Thompson's libraries are implemented. I have tried to find one for F# but are just toy projects.
    • chubot 10y ago
      It doesn't actually take that many lines of code to implement a linear time NFA engine. Most of the code is actually in the regex compiler. That is, there are only a few actual "instructions" or node types in a regex engine (alternation, concatenation, etc.). The rest is just compiling the bizarre syntax to a those nodes/instructions. (And dealing with Unicode if you need that.) The whole awk implementation is 958 lines, so it can't be that bad. It supports a fairly featureful regex language (though no capturing AFAICT).
• monochromatic 10y ago
  > 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
  • deleted 10y ago
    [deleted]
  • Nadya 10y ago
    199,990,000 * # of people visiting StackOverflow home page The result is likely at least 1,000* 199,990,000 at any given point.
  • Marazan 10y ago
    Per homepage load.
  • wheaties 10y ago
    SO is I/O bound most of the time. If you've set up your system to handle high workloads of I/O bound traffic, then hitting CPU bounds throws a real wrench in your cogs. To put this another way, SO is one of the most traffic'd sites on the internet. So a page that's loaded 10k+ times a second is going to push that number much, much, higher. If the CPU can't clear 10k+ req in under the regular time it takes, everything starts to back up.
    • mh- 10y ago
      > To put this another way, SO is one of the most traffic'd sites on the internet. I've seen this said several times here, but never bothered to ask.. by what measure is this true?
      • gortok 10y ago
        Alexa has it at #50: http://www.alexa.com/siteinfo/stackoverflow.com http://www.alexa.com/siteinfo/stackoverflow.com Quantcast has a similar ranking for it: https://www.quantcast.com/stackoverflow.com#trafficCard https://www.quantcast.com/stackoverflow.com#trafficCard
• redbeard0x0a 10y ago
  In the past, I have done Load Balancer status checks against a special /status endpoint. I queried all the connected services (i.e. DB, Redis, etc) with a super fast query (i.e. `SELECT version();`). Monitoring CPU/MEM usage for scaling was separate. Comparing this to checking the home page, what is the best way to setup a health check for your load balancers?
  • chiph 10y ago
    I think you've got the right approach - a vertical slice through the app that checks every layer. You want to know if a user can get useful info from your site, and it tracks (separately!) the common path their query would follow. The danger is that the endpoint becomes public knowledge and comes under a DDOS attack. Putting an IP address filter on that endpoint is usually enough to stop that.
    • redbeard0x0a 10y ago
      The concept I try to go for with that status check is 'Can this node connect to everything so it can successfully respond to http requests'. However my approach wouldn't identify an overloaded server, which might be a good thing if we need to scale up - taking down an overloaded server is just going to make the other servers that much more overloaded. I'm aways up for hearing about other ways people solve health checks.
      • orf 10y ago
        Just because it can connect to everything doesn't mean it can successfully respond though.
      • jocro 10y ago
        > taking down an overloaded server is just going to make the other servers that much more overloaded Emphatically agree, but it's important in the first place to design and deploy your infrastructure such that basic increases of scale are accounted for - prevention is the most important piece of the puzzle. Get that right and an overloaded server is symptomatic of something else, in which case taking down access to the unruly resource is first priority. IMO, the big takeaway here is that they were load balancing simply by only hitting the top level - selectivity is somewhat tedious to build but worth it in the long run.
• davidwparker 10y ago
  This is great- regex errors always reminds me of this classic Jeff Atwood post (cofounder of StackOverflow): https://blog.codinghorror.com/regular-expressions-now-you-have-two-problems/ https://blog.codinghorror.com/regular-expressions-now-you-ha...
• fweespeech 10y ago
  The lesson seems to be "Always run trim() before running regex" and "validate content as much as possible before running regex".
  • undersuit 10y ago
    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.
    • shdon 10y ago
      Which also wouldn't have been caught by the regex, because it was designed to do the same as Trim. Given the input, all that whitespace was not actually supposed to be removed and the regex worked, it was just a degenerate case that slowed it down to a crawl. Trim would not slow down on this input.
      • undersuit 10y ago
        Trim won't work, otherwise SO would be using trim. The regex did work in all cases, but it was slow under certain conditions. The slowness caused a separate system to shutdown the site. The regex worked fine, 100% within expectations.
        • shdon 10y ago
          No, the regex was an actual trim. And they have indeed switched to that. The edge case that caused the slow performance was a lot of whitespace that did not appear at the start or end of the string. The regex would not remove that, nor would trim, but trim is much more efficient in doing the exact same thing. The regex may have been correct, but I doubt the expectations of the developer were met and it most definitely was the wrong tool for the job.
  • revelation 10y ago
    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.
• kilroy123 10y ago
  > It took 10 minutes to identify the cause. I'm impressed they were able to do this so quickly.
  • bluedino 10y ago
    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....'
  • ww520 10y ago
    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.
    • KyleBrandt 10y ago
      Yes, we took a stackdump and saw the traces leading to that regex.
      • skeletonjelly 10y ago
        How large was the stack dump? I'm impressed you identified it this quickly considering the time it would take to get this to disk.
        • Nick-Craver 10y ago
          We have an internal tool where we can dump stack traces almost instantly by attaching to a running process. We can't open source it due to using Microsoft lab code which was never licensed itself. However, clrmd (https://github.com/Microsoft/clrmd https://github.com/Microsoft/clrmd and https://www.nuget.org/packages/Microsoft.Diagnostics.Runtime https://www.nuget.org/packages/Microsoft.Diagnostics.Runtime) means an open source version is hopefully on the horizon. As an example, here's the result of me piddling in 2 hours with LinqPad: https://gist.github.com/NickCraver/d6292c0c7f93767686e8c5c89ed45c54 https://gist.github.com/NickCraver/d6292c0c7f93767686e8c5c89... Process attachment is in the clrmd roadmap, but isn't stable yet.
• johnwheeler 10y ago
  ugh. i would've just sat there wondering WTF. then proceed to initiate daily backup recovery.
  • benten10 10y ago
    Haha, really! Maybe I'm less-experienced (1.5 yrs), but it would have taken me significantly more than the 15 mins(was it?) that it took them to diagnose the problem. Props to the team, and Thank All 0.33G Gods I was not on call!
• unethical_ban 10y ago
  Not understanding why backtracking happened. Once it hit a non space, non end character, move on. Nothing before can match the regex.
  • sklivvz1971 10y ago
    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.
    • unethical_ban 10y ago
      I guess I need to buff up on my automata, but I would have thought that for positional delimiters, there would be optimizations. If the pattern is \s+$, then I can look from the back of the line, see if there is a space, and if so, go backward until I find a non-space character.
      • viraptor 10y ago
        That's just special casing the end of line. If it was "\s+x" you'd still have the same problem.
• StavrosK 10y ago
  I 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?
  • Confusion 10y ago
    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?
    • deleted 10y ago
      [deleted]
  • deleted 10y ago
    [deleted]
  • phasmantistes 10y ago
    Most simple regular expression evaluators are basically state machines. They hold a few variables: a) what part of the regex am I currently trying to match b) what point in the string am I currently starting at c) how much of the string has this piece of the regex consumed so far Then the state machine basically has three transitions: * if (b+c) terminally matches (a), increment both (a) and (b) and reset (c) * if (b+c) matches (a), but more could be consumed, increment (c) and check again * if (b+c) doesn't match (a), increment (b) and reset (c) So yeah, you could put in short cuts for things like "well this didn't match because the next piece of the regex is matching on a line ending", but keeping it simple is straightforward and generally smiled upon.
    • burntsushi 10y ago
      If you are really using a state machine and every match in the regex is at the end of the haystack, then you can reverse the state machine and use the same algorithm you described in reverse. :-) (Rust's regex engine does this.)
• revelation 10y ago
  They implemented trim with a regex? Neither Java nor .NET do that. The postmortem here should probably be "why are you reimplementing trim".
  • jandrese 10y ago
    Most likely answer: The built-in trim isn't Unicode aware or has buggy behavior when dealing with Unicode.
    • Someone1234 10y ago
      Assuming they're still using ASP.net 4+, it is very unicode aware/safe. I don't know why a developer would reinvent Trim() but I do know it isn't a .Net limitation.
      • gbrayut 10y ago
        This code was written 5 years ago, and back then the trim function was different.
        • deleted 10y ago
          [deleted]
    • gnud 10y ago
      .NET builtin trim lets you specify which 'char' values to trim [1]. .NET is notoriously tied to UTF-16 (a char is 16 bit), and you have to handle surrogate pairs very carefully, but I can't really imagine that being any better with the built-in System.Text.RegularExpressions.Regex 1: https://msdn.microsoft.com/en-us/library/d4tt83f9(v=vs.110).aspx https://msdn.microsoft.com/en-us/library/d4tt83f9(v=vs.110)....
  • michaelcampbell 10y ago
    My guess is developer cleverness. As the article mentions they ended up with a less clever solution.
  • 10y ago
• percept 10y ago
  Productivity plummets worldwide (regex attack vector)
• tibiapejagala 10y ago
  I 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).
  • alexchamberlain 10y ago
    There are a few implementations that are linear, but compilation time is then exponential instead.
    • tibiapejagala 10y ago
      Which is still a big win because * regex pattern is controlled by site, while regex input is external * regex pattern is compiled once, while it is being run for every input
• zkhalique 10y ago
  This 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.
• mplewis 10y ago
  I think this might have been the post they quoted. http://stackoverflow.com/questions/38484433/in-corona-sdk-how-to-join-tiles-into-one-word-using-matrix-game-breakout http://stackoverflow.com/questions/38484433/in-corona-sdk-ho...
  • zuck9 10y ago
    Yeah, Nick "deleted 20507 characters in body" five hours ago: http://stackoverflow.com/posts/38484433/revisions http://stackoverflow.com/posts/38484433/revisions
  • bhandziuk 10y ago
    > deleted 20507 characters in body - Nick Craver You are very likely right. Though it looks like they permanently deleted those characters because they don't show up on the edit history.
  • Nick-Craver 10y ago
    Yep.
    • 0xmohit 10y ago
      Odd that this was the first post by the user. Mere coincidence?
      • artursapek 10y ago
        I imagine that's very common on SO (users with very few, or just 1, post)
• jakozaur 10y ago
  Experienced something similar myself. Was even thinking about creating regular expression library which just allow "safe" and fast expression. The trick would be to not allow only expression that can be translated easily to state automate. Good regex: "Phone number [0-9]* " Bad regex: ";Name=.;" as . can also match ";" and it can lead to bad backtracking. You should rewrite this regex to ";Name=[^;];" RE2 is probably best implementation so far, but because it's tries so hard to preserve backward compatibility with all regular expression it is not that fast in average case: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
• grashalm 10y ago
  Easy to reproduce [1]. Just remove the a in the end and your timeout disappears. Anybody knows which regex engine they used? [1] http://regexr.com/3drn3 http://regexr.com/3drn3
  • jandrese 10y ago
    I had a tough time reproducing it in Perl, although I think I managed to get it. % perl -v This is perl 5, version 18, subversion 2 (v5.18.2) built for x86_64-linux-gnu-thread-multi % ls -l testfile 125380092 Jul 20 16:41 testfile % time ./regextest testfile ./regextest testfile 0.36s user 0.03s system 99% cpu 0.398 total (Remove the a at the end) % time ./regextest testfile ./regextest testfile 0.13s user 0.03s system 99% cpu 0.156 total I had to make a much larger input file than I expected before I was able to really see the difference. Given the O(n^2) nature of the bug, I was expecting it to take much longer.
  • deadowl 10y ago
    I wanted to figure that out. I found a meta post stating the SO uses C#, so that might narrow it down.
  • hehheh 10y ago
    I could not reproduce the slowness in Perl, but I could in JavaScript (specifically node.js). There are many, many modules that use /\s+$/, including at least one form validator.
• jimjimjim 10y ago
  paging jwz. something something two problems.
• smrtinsert 10y ago
  "This regular expression has been replaced with a substring function." This should be the title of a book on software engineering.
  • AceJohnny2 10y ago
    This regular expression has been replaced with a substring function. God I wish all my bugs were this easy to fix and deploy
    • meshko 10y ago
      i wish people would stop using regular expressions in situations where they can be replaced with a substring function.
      • zamalek 10y ago
        Nick explained on Reddit why the regex was used[1]: > While I can't speak for the original motivation from many moons ago, .Trim() still doesn't trim \u200c. It's useful in most cases, but not the complete strip we need here. This would have probably been my train of thought (assuming that I consider regex to be a valid solution): Trim() would have been the correct solution, were it not for that behavior. Substring is therefore the correct solution. Problem is, IndexOf only accepts a char array (not a set of some form, i.e. HashSet). You'd need to write the <Last>IndexOfNonWhitespace methods yourself. Use a regex and make sure that it doesn't backtrace, because it's expressive and regex "is designed to solve this type of problem." The real problem/solution here isn't substring, it's finding where to substring. I consider regex too dangerous to use in any circumstance, but I can certainly see why someone would find it attractive at first. [1]: https://www.reddit.com/r/programming/comments/4tt6ce/stack_exchange_was_down_because_of_an_innocent/d5kis12 https://www.reddit.com/r/programming/comments/4tt6ce/stack_e...
        • meshko 10y ago
          Oh totally. I assumed that unicode bs immediately. And anyone would make this mistake easily. That's the point -- gotta have it imprinted in the brains, that regexes are for finding things in files, not for your production code. I've used them myself, but I'd like to think that when i type that regex in i stop and thing whether i will be feeding raw user inputs into it.
• _RPM 10y ago
  They have limits on everything (comments per second, edits per second, upvotes per day, reputation earned per day, etc), it seems like they should have an upper bound character limit on what they accept too.
  • hamandcheese 10y ago
    There are some very long Stack Overflow answers that contain a wealth of information. If there were a limit, it would likely need to be far greater than 20k characters anyway (the number of whitespace characters that caused the outage).
  • JeremyBanks 10y ago
    They do. It's 30K characters. Occasionally you see genuine posts bumping up against it.
• animex 10y ago
  We had a similar issue arising from regex parsing of our SES routes on our SaaS Platform. We had made some changes to our generated SES file which caused it to balloon to 4x in size (tens of thousands of lines). Our only clue that something had gone wrong was suddenly extremely high IIS usage. With some help from Microsoft support, we managed to trace the stack during the high-cpu event to an ISAPI filter and ultimately our 3rd party SES plugin. We managed to fix the problem by being more efficient with our regex generation and reduce the number of rules the plugin was processing but it was eye-opening how much CPU was being consumed by regex processing.
• smegel 10y ago
  > 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 backtracks, and tries matching \s+$ starting from the second space, checking 19,999 characters. The match fails again, and it backtracks to start at the third space, etc. That's not how backtracking works. A regex engine will only backtrack to try and make the rest of the regex match, i.e. it will take characters of the RHS of the string, not try and start "from the second character off the start of the string". I mean, if the engine tried matching from the second space, what would be matching the first space? Something has to. Which meant, that even if the regex engine was incredibly stupid and could not figure out that a greedy block of \s was never going to contain a non-\s, it would only have to check 20,001 times, not 199000 (or whatever it was). I can't reproduce this "bug" in either Perl or Python. The time taken to match a 30,000 block of space either followed by $ or XX$ was basically identical for \s+$. There does appear to be normal backtracking going on, roughly doubling the search time for large strings terminating in non-\s. This is expected, as it has to check 20,000 during the first gobble, then 20,000 as it backtracks from the right 20,000 times. $ time perl -e '(" " x 100000000 . "X") =~ /\s+$/ && print "MATCH"' real 0m0.604s user 0m0.509s sys 0m0.094s $ time perl -e '(" " x 100000000) =~ /\s+$/ && print "MATCH"' MATCH real 0m0.286s user 0m0.197s sys 0m0.089s
  • burntsushi 10y ago
    > 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.) Assuming the OP was using this type of method, then this difference exactly explains why you can't reproduce it. I can: >>> import re >>> haystack = (' ' * 20000) + 'a' >>> re.match('\s+$', haystack) <-- is wicked fast >>> re.search('\s+$', haystack) <-- chugs a bit indeed, this chugs a bit too: >>> re.match('.*?\s+$', haystack) So technically, the OP left out this little detail, but it's a pretty common thing to find in regex libraries. In fact, Rust's library treats all searches as if they were re.search and provides no re.match function, instead preferring to require an explicit `^` to remove the implicit `.STAR?` prefix.
• estrabd 10y ago
  TIL what language Stack Overflow is written in.
  • na_ka_na 10y ago
    what language is that? Couldn't find it in the post.
    • boyter 10y ago
      C#
• alexbecker 10y ago
  I remember the day I learned that Python's "re" module uses backtracking for non-extended regexes. My tests covered lots of corner cases in the regex logic, but were too short for me to notice the performance penalty. Luckily I only caused a partial outage in production. I actually got to talk to Raymond Hettinger (Python core team) about why re uses a potentially exponential-time algorithm for regexes when there is a famous linear-time algorithm, and (I suspect) most programmers would assume linear complexity. As it turns out, there was an attempt to re-write re to fix this, but the re-write never managed to present exactly the same (extremely large) API as the existing module. He advised me that "the standard library is where code goes to die."
  • deadowl 10y ago
    I looked at that module a while back. The goto statements make it very difficult to analyze. It seems to integrate well with the signals module, which could be used to interrupt a large class of ReDoS attempts, but determining whether all potential regexps could be interrupted using signals, with the goto statements, is a difficult task.
  • mark-r 10y ago
    I vaguely remember a replacement for Python's re module, but I can't remember the name, and Googling for it is an exercise in frustration. Edit: it's "regex" - https://pypi.python.org/pypi/regex https://pypi.python.org/pypi/regex. I have no idea if it behaves better with backtracking, a cursory glance at the documentation doesn't indicate any changes in that area.
    • d0mine 10y ago
      regex module shows the same behavior as re module in this case: $ python -mtimeit -s "s=' '*20000; import regex as re" "re.search(r'\s+$', s)" # ends with spaces is fast 10000 loops, best of 3: 201 usec per loop $ python -mtimeit -s "s=' '*20000+'non-space'; import regex as re" "re.search(r'\s+$', s)" # ends with a non-space is slow 10 loops, best of 3: 3.39 sec per loop
  • cyphar 10y ago
• johncoltrane 10y ago
  A few months ago, a Stack Overflow representative asked me if their presence at a dev conference was justified. My positive answer more or less revolved around the importance SO took in the daily life of programmers everywhere. If only she was there to witness the effect of a 34 minute downtime on an open space full of mobile/back/front developers.
  • glup 10y ago
    Google's cached versions of SO answers are generally up to date, no? Nice try, lazy developers!
    • 0xmohit 10y ago
      Alternatively, you can refer to StackPrinter [0] (especially if arriving via a search engine). [0] http://www.stackprinter.com/ http://www.stackprinter.com/
  • collyw 10y ago
    There are plenty of other sites that seem to scrape Stack Overflow questions and answers.
• StevePerkins 10y ago
  I'm surprised that a developer was able to fix StackOverflow without being able to look up the error message on StackOverflow.
  • gnahckire 10y ago
    hah! The catch 22
  • yaakov 10y ago
    Well, StackOverflow devs are able to cheat and load up the site on their local machine if they want to
    • mevile 10y ago
      I'm not sure I like the idea of being able to connect to a prod db from a dev instance, but whatever floats your boat.
      • progval 10y ago
        There are public dumps of Stack Overflow's database. https://archive.org/details/stackexchange https://archive.org/details/stackexchange
      • flukus 10y ago
        Who says they have to? The can just restore a recent backup.
      • jsmeaton 10y ago
        I doubt they'd allow that either - but database exports are a thing or they could just query the database or elasticsearch themselves.
    • bboreham 10y ago
      Anyone can download the underlying data and look at it on their local machine. https://archive.org/details/stackexchange https://archive.org/details/stackexchange
• zzzcpan 10y ago
  Seems like there is still no better way to deal with these kind of mistakes than preemptive Erlang-style lightweight processes.
• hstun 10y ago
  But... how did they search for a fix without resorting to Stack Overflow? :)
• junke 10y ago
  Nice 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 strings which respectively match and don't match shows that the result is immediate in both cases. (defparameter *scanner* (ppcre:create-scanner '(:sequence (:register (:greedy-repetition 1 nil :whitespace-char-class)) (:register (:greedy-repetition 0 1 :non-whitespace-char-class))))) (let ((length 40000)) (defparameter *no-match* (let ((string (make-string length :initial-element #\space))) (setf (char string (1- (length string))) #\+) string)) (defparameter *match* (make-string length :initial-element #\space))) (defun end-white-match (string) (ppcre:do-scans (ms me rs re *scanner* string) (when (and ms (= (aref re 1) (aref rs 1))) (return (values ms me))))) (time (end-white-match *match*)) 0, 40000 ;; Evaluation took: ;; 0.000 seconds of real time ;; 0.000000 seconds of total run time (0.000000 user, 0.000000 system) ;; 100.00% CPU ;; 25,139,832 processor cycles ;; 0 bytes consed (time (end-white-match *no-match*)) NIL ;; Evaluation took: ;; 0.000 seconds of real time ;; 0.000000 seconds of total run time (0.000000 user, 0.000000 system) ;; 100.00% CPU ;; 11,105,364 processor cycles ;; 0 bytes consed
  • emn13 10y ago
    So, you're saying that if you enjoy tricky gotchas and puzzle-solving over reliability, then the perl-aping regex implementations have your back?
    • junke 10y ago
      I am saying that I have been nerd sniped. Actually I tend do stay away from regexes.
• wfunction 10y ago
  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?
• onetwotree 10y ago
  It 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.
  • carterehsmith 10y ago
    As an alternative, in Java, there is FindBugs plugin "find-sec-bugs" that flags potentially-long-running regexes. In my current project, it found two of those in Google Zxing library.
  • zzzcpan 10y ago
    For people who already care enough about this there is Ragel.
  • thaumasiotes 10y ago
    > It 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. Obviously. If the "regex" includes a backreference, it requires backtracking. If it includes only regular operations (I can't call any other nonregular operations that people might expect to mind), it doesn't. This is information that can be trivially surfaced by a parser.
    • onetwotree 10y ago
      I wonder why regex libraries don't do this then? Isn't /\s+$/ backreference free? Or does including the anchor change that?
      • thaumasiotes 10y ago
        It's backreference free. Backtracking to process it is just bad design. Here's a state machine that recognizes /^.*\s+$/: 1: initial state (non-matching) 2: matching state all states transition to 2 on \s, and to 1 on \S. Done. Taking this a little further, we can observe that since the transition table is identical for every state, there's no real need to have states at all -- you get the same effect by just checking the last character.
• avar 10y ago
  My rephrasing of their follow-up actions: * "Audit our regular expressions and post validation workflow for any similar issues" * ==> "Not even people who've worked for years on the guts of regex engines can easily predict the runtime of a given regex, but somehow our engineers will be expected to do that". * "Add controls to our load balancer to disable the healthcheck – as we believe everything but the home page would have been accessible if it wasn’t for the the health check" * ==> "Our lb check was checking /index, that failed because /index was slow: Lesson learned, let's not lb check anything at all"
  • harigov 10y ago
    Regex engines usually have an option to set upper limit on the time they take to match so they don't end up in expensive loops. A simple solution could be to setup such time limits.
  • lnanek2 10y ago
    I think an audit on regex usage would be fine in this case because it is silly to be using an expensive regex on the server for every home page display. It should be done when the data item is created, not when it is displayed. Even if they need to support full round trip back to the originally entered data for editing purposes, they could have an extra column in the table for that purpose only, or they could case the displayed output for the post in something like Redis. I assume, just like those PHP forums of old, they change so much about the page based on the logged in user they can't actually fully cache the home page for all users. So an audit should just lead them to remove the regex on display anyway, not try to figure out the run time of it.
  • hehheh 10y ago
    I don't think they're disabling health checks in general, just adding a way to temporarily disable checks when they are misbehaving.
    • Nick-Craver 10y ago
      Correct. I'll be adding this functionality into Opserver so that we can override the health check in HAProxy when we know better.
• ozten 10y ago
  My blog post[1] on how to test for catastrophic backtracking using RegEx buddy. [1] https://blog.mozilla.org/webdev/2010/11/15/avoiding-catastrophic-backtracking-in-apache-rewriterule-patterns/ https://blog.mozilla.org/webdev/2010/11/15/avoiding-catastro...
• deleted 10y ago
  [deleted]
• shanemhansen 10y ago
  Yesterday I couldn't use hipchat for a couple hours because it would lock up a cpu and fail to load. After doing some free debugging for them I realized they were locking up trying to extract urls out of some text with a regex. Simplified code: https://gist.github.com/shanemhansen/c4e5580f7d4c6265769b0df61d6d8759 https://gist.github.com/shanemhansen/c4e5580f7d4c6265769b0df... Pasting that content into hipchat will probably lock up your browser and webview based clients. Beware. Lesson learned: don't parse user input with a regex.
• Retr0spectrum 10y ago
  For more bugs caused by quadratic complexity: http://accidentallyquadratic.tumblr.com/ http://accidentallyquadratic.tumblr.com/
• bshimmin 10y ago
  In reading this post, I realised this was the first time I'd ever visited the Stack Overflow homepage.
• mwpmaybe 10y ago
  This is why I always do: s/^\s+//; s/\s+$//; Instead of: s/^\s+|\s+$//; Weirdly, I've "known" this since I started writing Perl in the mid-'90. Not sure where I originally read it (or was told it). Funny how that works. I try to write my regexes such that they anchor at the front of the strong or the back, or they describe the whole string; never an either-or anchoring type situation like this example. Spaces at beginning of string (100,000 iterations): Rate onestep twostep onestep 62500/s -- -2% twostep 63694/s 2% -- real 0m3.093s user 0m3.066s sys 0m0.018s Spaces at end of string (100,000 iterations): Rate twostep onestep twostep 55249/s -- -9% onestep 60976/s 10% -- real 0m3.453s user 0m3.421s sys 0m0.022s Spaces in middle of string (only 500 iterations because I don't want to sit here for four hours): Rate onestep twostep onestep 7.11/s -- -100% twostep 16667/s 234333% -- real 1m10.741s user 1m10.207s sys 0m0.228s
  • burntsushi 10y ago
    You can see in my other post that this doesn't always work. For example, Python's regex engine chokes on `\s+$` if you use `re.search`, but works fine if you use `re.match`. It's likely that Perl has an optimization for `\s+$` but not `^\s+|\s+$` (the former regex only ever matches at the end of the string, which is amenable to optimizations).
    • mwpmaybe 10y ago
      I did see your other post, and upvoted it. This rule of thumb has served me well between different regex dialects and implementations, but it's not surprising that there are some specific cases that are "broken" for lack of a better word. I haven't done much Python but the documentation for re.search() and re.match() is very clear: use search to find an expression anywhere in a string, use match to find an expression at the beginning of a string. It appears to ignore anchors in both cases? Left undetermined then is how to anchor an expression at the end of a string. You say re.match() works, but this is pretty confusingly described, and it's easy to see how the ambiguity can lead to problems for even the most experienced programmers.
• davidron 10y ago
  The whole postmortem focuses on a regular expression bug and how that bug was fixes and completely ignores the fact that if the home page becomes unavailable, the load balancer logic will shut down the entire site.
  • deleted 10y ago
    [deleted]
• davidron 10y ago
  The whole postmortem focuses on a regular expression bug and how that bug was fixes and completely ignores the fact that if the home page becomes unavailable, the load balancer logic will shut down the entire site.
• lambda 10y ago
  Hmm. I wonder why one of the followup mitigations is not to move to a non-backtracking regex engine by default. Most of what you want to do with a regex can be done with an NFA or DFA based engine. That which can't be done with an NFA or DFA based engine is generally better handled with a parser than a regex. There are plenty of good DFA based regex matchers out there; RE2, the Rust regex crate, GNU grep, etc. At a glance, it even looks like glibc uses a DFA, though it supports POSIX REs which support backreferences so it must use backtracking at least for REs that contain backreferences. Predictable hash collisions were a big sources of DOS attacks in web scripting languages which use tables a lot, until they started rolling out randomized hashing algorithms to prevent easily predictable hash collisions. It seems like it would be best for languages and libraries to move to DFA based regexps, at least for anything that doesn't contain backreferences, to mitigate these kinds of issues from being easy to exploit.
• OJFord 10y ago
  > It took 10 minutes to identify the cause, Impressive, considering: > cause was a malformed post that caused one of our > regular expressions to consume high CPU ... called on > each home page view ... Since the home page is what our > load balancer uses for the health check, the entire site > became unavailable since the load balancer took the > servers out of rotation.
• rmdoss 10y ago
  Very interesting bug. People forget some times how expensive a regex can be compared to simple pattern matching.
• berkut 10y ago
  If it was in a comment, why was the home page loading it? preemptive caching?
• jng 10y ago
  Any more proof needed that caching should become a system-provided service over the next 10-20 years, the same way memory management did in the past 10-20 years?
• nanis 10y ago
  As perlfaq4[1] shows: > You can do that with a pair of substitutions: > s/^\s+//; > s/\s+$//; It then notes, in an understated manner: > You can also write that as a single substitution, > although it turns out the combined statement is > slower than the separate ones. That might not > matter to you, though: > s/^\s+|\s+$//g; [1]: http://perldoc.perl.org/perlfaq4.html#How-do-I-strip-blank-space-from-the-beginning%2fend-of-a-string%3f http://perldoc.perl.org/perlfaq4.html#How-do-I-strip-blank-s...
  • cygx 10y ago
    In light of the given issue, it might be a good idea to update the example code to use \s++ instead...
• NetStrikeForce 10y ago
  Someone wiser than me said once that if you have a problem and want to fix it with a regex then you now have two problems :-)
• Waterluvian 10y ago
  I want to believe that a cat fell asleep on the space bar. Then eventually woke up and posted.
• lazyant 10y ago
  "the entire site became unavailable since the load balancer took the servers out of rotation." I don't care about the regexp, this is bad SRE, you can't just take servers out of rotation without some compensation action. Never mind that it looks like all web servers where taken out of rotation, even one server down could cause a cascading effect (more traffic directed to the healthy ones that end up dying, in a traffic-based failure). One action for example after n servers have gone down, (besides getting up other m servers) is to put (at least some) servers in a more basic mode (read only/static, some features disabled), not guaranteed but that could have prevented this and other type of down times.
  • fermuch 10y ago
    I was thinking the same while reading that part, and I also find it very scary. Why would you even _let_ the load balancer take off _all_ of your servers?
  • CWuestefeld 10y ago
    I have the same concern - including with our own system. As far as I know, all LBs are designed with this faulty logic. That's the case with our in-house F5 BigIPs, and I believe also for AWS's ELBs. Sure, it makes sense to cut malfunctioning servers out of the production pool when discovered. But at the point where you've dumped out every production server, you've just created the worst possible situation - you're absolutely guaranteed not to be able to serve any traffic. At the point you get to zero functioning servers, a better response would be to restore all servers to the pool and just hope. That would be bad, but less so. What we've done on our internal systems is to set things up so that when the last server is dropped, it fails over to a passive pool that is really just the normal production pool with no health checks. But I'm not aware of any LB that supports this directly, we had to glue together some ugly configurations to get this to work.
• rosstex 10y ago
  Wow, I didn't notice today! I must not have been coding very much.
• mtokunaga 10y ago
  " This regular expression has been replaced with a substring function." I came to rely on Regex so much that I almost feel we'd be the next.
• rixed 10y ago
  Regex was not the main issue. The main issues were: 1. Rendering a page fails/does not terminate if some non essential subtask (rendering a single code block) fails/does not terminate. 2. They do not try to detect bad data (the way they certainly try to detect bad code) 3. Load balancing based on the rendering time of a single page Code bugs triggered by bad data will happen again, with or without regular expressions.
  • brokenmachine 10y ago
    > 2. They do not try to detect bad data (the way they certainly try to detect bad code) It was actually the sanitization function regex that became unresponsive. So they killed the page by trying to stop bad data coming in. Agreed on your other points though.
• brongondwana 10y ago
  Time to pop this old chestnut out: https://blog.fastmail.com/2014/12/14/on-duty/ https://blog.fastmail.com/2014/12/14/on-duty/ "At one stage, we decided to try to avoid having to be woken for some types of failure by using Heartbeat, a high availability solution for Linux, on our frontend servers. The thing is, our servers are actually really reliable, and we found that heartbeat failed more often than our systems - so the end result was reduced reliability! It's counter-intuitive, but automated high-availability often isn't." One of these days we'll finish our new system and I'll blog about that, which is that the automated systems are allowed to take ONE corrective action without paging, at which point they flag that the system is in compromised state. Any further test failures trigger an immediate wake of the on-call.
• adrianratnapala 10y ago
  Backtracking regexes matchers are a Bad Idea. It's true you need them to implement backreferences. But I've never used such a thing. If I were creating a runtime for some new language, I would simply ignore that part of the POSIX standard.
• porjo 10y ago
  > 20,000+19,999+19,998+…+3+2+1 = 199,990,000 = 200,010,000, not that anyone's counting :)
• cyphar 10y ago
  I'm still confused why people would use a backtracking regex engine in cases when they don't need recursive regex extensions (or other questionable extensions like back references). A "correct" (from the CS perspective) regex engine wouldn't have had this or many other problems that people encounter when doing regular expression matching. If they had piped out to sed or awk this wouldn't have happened, since GNU grep, sed and awk use a proper regex engine.
• JBiserkov 10y ago
  The Stack status page contains 3 script tags before the HTML tag. This is what I saw on my Kindle 3 Keyboard: This page contains the following errors: error on line 2 at column 36: Extra content at the end of the document Below is a rendering of the page up to the first error. var __pbpa = true;
• rocho 10y ago
  By the way, this is the post that broke StackOverflow: http://stackoverflow.com/questions/38484433/join-tiles-in-corona-sdk-into-one-word-for-a-breakout-game-grid http://stackoverflow.com/questions/38484433/join-tiles-in-co...
• deleted 10y ago
  [deleted]
• hamzalive 10y ago
  200010000 not 199990000 probably the author looped on a 0-based index. n*(n+1)/2 is even better ^^ Nice post mortem though
• babuskov 10y ago
  > This regular expression has been replaced with a substring function. I always cringe when I see regex used for such simple string checks. In fact, Stackoverflow is full of accepted answers that "solve" problems that way.
• Osiris 10y ago
  Why isn't the trim applied when the post is created and not every time that it's displayed?
• ozim 10y ago
  For me awesome part is cliché that is quite popular on SO takes down SO. And resolution to replace RegExp with substring completes the picture. Just cannot stop laughing. "Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems."
• brokencube 10y ago
  Correct me if I'm wrong, but couldn't this could have been fixed by making the match possessive: ^[\s\u200c]++|[\s\u200c]++$ That should stop any runaway backtracking?
• stop1234 10y ago
  Yes, one of the best postmortems, especially the technical part. Am sure it was simple but curious to know what the replacement substr code is.
• MalcolmDiggs 10y ago
  Regex: ruining your life since 1956.
• GnarlyWhale 10y ago
  Favourite comment from the Reddit thread on the matter: "Well, that should stave off the imposer syndrome for another couple of days." -u/minno
• random3 10y ago
  > Add controls to our load balancer to disable the healthcheck – as we believe everything but the home page would have been accessible if it wasn’t for the the health check Wouldn't regular users, trying to access the homepage have yielded the same effect?
• deleted 10y ago
  [deleted]
• dear1777 10y ago
  Hmmn, if it was one request, how did it cause other web servers in the farm go down?