I think this might have been the post they quoted.
http://stackoverflow.com/questions/38484433/in-corona-sdk-ho...
Stack Overflow Outage Postmortem
41–50 of 335 posts
Re: Stack Overflow Outage Postmortem
#42I 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?
[deleted]
Re: Stack Overflow Outage Postmortem
#43Experienced 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
Re: Stack Overflow Outage Postmortem
#44> 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
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…
> 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?
Re: Stack Overflow Outage Postmortem
#45Perfect. 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.
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.
Re: Stack Overflow Outage Postmortem
#46> It took 10 minutes to identify the cause. I'm impressed they were able to do this so quickly.
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.
Re: Stack Overflow Outage Postmortem
#47The 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.
You can't trust that the user has JavaScript enabled; and since you can't trust user input anyway, you'd have to do this server side.
Re: Stack Overflow Outage Postmortem
#48I 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?
[deleted]
Re: Stack Overflow Outage Postmortem
#49Easy to reproduce [1]. Just remove the a in the end and your timeout disappears. Anybody knows which regex engine they used?
Re: Stack Overflow Outage Postmortem
#50This 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 d…
> 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)....
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.