Stack Overflow Outage Postmortem • Hacker News Board

Re: Stack Overflow Outage Postmortem

#311

Post by chubot » Thu, Jul 21, 2016, 4:30 PM UTC

cyphar wrote: post #266

chubot wrote: post #198

Earlier quoted context omitted.

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 li…

I'd look at GNU sed if you wanted a very featureful substitution engine that IIRC is also linear time.

Hm it seems to be a copy of the GNU libc regex engine. And coreutils, grep, and awk also package the same engine in user space! That's really annoying.

But yes it looks like it uses a struct re_dfa_t for matching, and some special flags for backreferences? That seems to indicate that they are using linear time maybe with a fallback? Hm.

I think the general turn of events was that libc supported BRE at first, which was implemented using the DFA algorithm. Then Perl implemented a backtracking engine and Perl syntax for REs, and Python/Ruby/etc. wanted to be compatible with Perl, so they also implemented backtracking as well. Because Perl has other features like forward and back assertions that require backtracking.

And then perhaps libc got EREs with backreferences which they bolted onto the existing infrastructure?

Anyway, thanks for the pointer... I may look into these more in the future.

musl libc also uses the TRE regex engine, which apparently uses the DFA algorithm.

Re: Stack Overflow Outage Postmortem

#312

Post by random3 » Thu, Jul 21, 2016, 4:34 PM UTC

> 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?

Re: Stack Overflow Outage Postmortem

#313

Post by chubot » Thu, Jul 21, 2016, 4:37 PM UTC

cyphar wrote: post #264

jandrese wrote: post #100

Earlier quoted context omitted.

It's a little unfair to complain that they're slower than 30 year old regex engines when the old regex engines were so feature limited that they were nearly useless.

They're only missing one feature: back references. This feature is not needed for the majority of regular expressions, so the 30 year old engines are actually remarkably useful and don't have these pathologies. And actually it was the introduction of back references (in Perl) that causes you to have to implement backtracking regular expression engines.

In addition to back references, Perl also has forward and back assertions, IF/ELSE, and recursion IIRC. I'm not sure if anyone actually USES those features, but they are there.

Python adopted back references as well as forward and back assertions, but not the other stuff.

Perl really turned regular expressions into something else entirely...

Re: Stack Overflow Outage Postmortem

#314

Post by GnarlyWhale » Thu, Jul 21, 2016, 4:40 PM UTC

OJFord wrote: post #165

zymhan wrote: post #45

Earlier quoted context omitted.

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.

It was in a multiline code block, so it just had a tonne of horizontal scroll. See the edit: http://stackoverflow.com/revisions/38484433/2

"deleted 20507 characters in body"

Hahaha

Re: Stack Overflow Outage Postmortem

#315

Post by vitd » Thu, Jul 21, 2016, 4:43 PM UTC

randominion wrote: post #254

zymhan wrote: post #45

Earlier quoted context omitted.

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.

I can tell you how. A shitty Belkin KVM in certain configurations can allow this to happen. There's a bug which keeps generating chr(32) characters when you activate the keyboard shortcut (scroll lock twice), and try to switch to another machine. It will keep pumping out those spaces on whatever fields was selected at the time, so if you take your time before you switch back, you are going to be in for a lot of fun.…

Nice find! Another one I heard about was that Microsoft's Windows keyboards, when used on a Mac, will sometimes insert a Control-P into the middle of your typing if you press the Windows key. Most apps just ignore it, but apparently not all!

Re: Stack Overflow Outage Postmortem

#316

Post by paulddraper » Thu, Jul 21, 2016, 7:06 PM UTC

zaphar wrote: post #303

paulddraper wrote: post #239

Earlier quoted context omitted.

You can only safely abort a "task" if the task has specifically be designed that way, or if the task is a process.

Which is of course part of his point. Anything that processes arbitrary user input should be designed in a way that is abortable in some way. As this particular case shows even the attempts to sanitize input can be vectors for a DOS against them.

Everything processes user input. Whether a numeric user id or some text.

Re: Stack Overflow Outage Postmortem

#317

Post by tibiapejagala » Thu, Jul 21, 2016, 7:35 PM UTC

alexchamberlain wrote: post #265

tibiapejagala wrote: post #33

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 wro…

There are a few implementations that are linear, but compilation time is then exponential instead.

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

Re: Stack Overflow Outage Postmortem

#318

Post by nickpsecurity » Thu, Jul 21, 2016, 7:43 PM UTC

paulddraper wrote: post #316

zaphar wrote: post #303

Earlier quoted context omitted.

Which is of course part of his point. Anything that processes arbitrary user input should be designed in a way that is abortable in some way. As this particular case shows even the attempts to sanitize input can be vectors for a DOS against them.

Everything processes user input. Whether a numeric user id or some text.

That's going a bit far. User input is usually handled by a small percentage of modules. Those should guard against malicious or faulty input where possible.

That's not even the issue here, though. The issue is tgat the input is processed via an algorithm thst is easy to hang and/or format that's hard to parse. On top of that, no isolation or monitor to catch the fault. Each of these can be done differently... are in many programs... to avoid or better mitigate such risks. Developers often dont.

Re: Stack Overflow Outage Postmortem

#319

Post by [deleted] » Thu, Jul 21, 2016, 8:05 PM UTC

gbrayut wrote: post #260

Someone1234 wrote: post #132

Earlier quoted context omitted.

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.

This code was written 5 years ago, and back then the trim function was different.

[deleted]

Re: Stack Overflow Outage Postmortem

#320

Post by Piskvorrr » Thu, Jul 21, 2016, 10:48 PM UTC

dingo_bat wrote: post #306

Piskvorrr wrote: post #281

Earlier quoted context omitted.

Runaway automatic search-and-replace? There's no way to distinguish intent .

Runaway search and replace won't put a single 200 width whitespace character AFAICT

That's the meaning of "runaway" - Notepad++ had a search&replace that went into a somewhat random, long and uninterruptible loop if you were replacing using some types of regex and searhing forward in the file - you had to search backwards.