Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Details of the Cloudflare outage on July 2, 2019

blog.cloudflare.com

Post reply on HN
Print view View original

111–120 of 159 posts

Re: Details of the Cloudflare outage on July 2, 2019

#111

Post by ehaliewicz2 »

Firerouge wrote: post #108
bsder wrote: post #106

Earlier quoted context omitted.

The problem is that a deterministic regex engine (deterministic finite automata or DFA) is strictly less powerful than a non-deterministic one (NFA). DFA's can't backtrack, for example. In addition, DFA's can be quite a bit slower for certain inputs and matches.

Perhaps a parser exists that can determine if an input regex is runaway backtrack prone, and can automatically switch to a deterministic algorithm?

Just check if it uses backreferences, otherwise it can be implemented via NFA/DFA.

Re: Details of the Cloudflare outage on July 2, 2019

#112

Post by auscompgeek »

bsder wrote: post #106
hn_throwaway_99 wrote: post #96

One thing that was interesting to me: The outage was caused by a regex that ended up doing a lot of backtracking, which caused PCRE, the regex engine, to essentially handle a runaway expression. This reminded me of a HN post from a couple months back by the author of Google Code Search, and how it worked: https://swtch.com/~rsc/regexp/regexp4.html . Interestingly, he wrote his own regex engine, RE2, specifically beca…

The problem is that a deterministic regex engine (deterministic finite automata or DFA) is strictly less powerful than a non-deterministic one (NFA). DFA's can't backtrack, for example. In addition, DFA's can be quite a bit slower for certain inputs and matches.

Actually, it is proven that NFAs and DFAs are equally expressive. See https://en.wikipedia.org/wiki/Powerset_construction

Re: Details of the Cloudflare outage on July 2, 2019

#113

Post by emmelaich »

hn_throwaway_99 wrote: post #96

One thing that was interesting to me: The outage was caused by a regex that ended up doing a lot of backtracking, which caused PCRE, the regex engine, to essentially handle a runaway expression. This reminded me of a HN post from a couple months back by the author of Google Code Search, and how it worked: https://swtch.com/~rsc/regexp/regexp4.html . Interestingly, he wrote his own regex engine, RE2, specifically beca…

I think it's not uncommon. I've seen it in two places recently.

1. A test job in CI/CD pipeline suddenly taking a very long time and lots of cpu

2. A data cleansing / checking job in a Java webapp occasionally turning the machine to molasses.

In both occurrences the regex had been around for a while; what happened is that the data was different. e.g. Lots of trailing whitespace.

Re: Details of the Cloudflare outage on July 2, 2019

#114

Post by gautamdivgi »

bsder wrote: post #106
hn_throwaway_99 wrote: post #96

One thing that was interesting to me: The outage was caused by a regex that ended up doing a lot of backtracking, which caused PCRE, the regex engine, to essentially handle a runaway expression. This reminded me of a HN post from a couple months back by the author of Google Code Search, and how it worked: https://swtch.com/~rsc/regexp/regexp4.html . Interestingly, he wrote his own regex engine, RE2, specifically beca…

The problem is that a deterministic regex engine (deterministic finite automata or DFA) is strictly less powerful than a non-deterministic one (NFA). DFA's can't backtrack, for example. In addition, DFA's can be quite a bit slower for certain inputs and matches.

I thought NFAs and DFAs are equivalent, i.e. an NFA can be reduced to a DFA (at least what I remember of undergraduate theory of computation).

Re: Details of the Cloudflare outage on July 2, 2019

#116

Post by Thorrez »

bsder wrote: post #106
hn_throwaway_99 wrote: post #96

One thing that was interesting to me: The outage was caused by a regex that ended up doing a lot of backtracking, which caused PCRE, the regex engine, to essentially handle a runaway expression. This reminded me of a HN post from a couple months back by the author of Google Code Search, and how it worked: https://swtch.com/~rsc/regexp/regexp4.html . Interestingly, he wrote his own regex engine, RE2, specifically beca…

The problem is that a deterministic regex engine (deterministic finite automata or DFA) is strictly less powerful than a non-deterministic one (NFA). DFA's can't backtrack, for example. In addition, DFA's can be quite a bit slower for certain inputs and matches.

I don't know what you mean by "DFA's can't backtrack". Maybe you mean DFAs don't support backreferences, which is true, but NFAs don't support backreferences either.

I believe if r is the size of the regex and d is the size of the data, an NFA is O(r) to compile and O(rd) to execute, while a DFA is O(2^r) to compile and O(d) to execute. So DFAs are slower to compile, but faster to execute.

Re: Details of the Cloudflare outage on July 2, 2019

#118

Post by xigency »

glangdale wrote: post #86

Well, if I still worked on Hyperscan, this would be my "what am I, a potted plant?" moment. I think Cloudflare is pretty determined to avoid x86-only implementations of anything, though. It's entertaining to see people making the same mistakes that have been widely known about in network security well before there was Hyperscan, RE2, etc.

There are always those potted plant moments. For some reason regular expressions / regex implementations seem to always be in that hole.

Re: Details of the Cloudflare outage on July 2, 2019

#119

Post by Thorrez »

charrondev wrote: post #88
regnerba wrote: post #39

Earlier quoted context omitted.

In this case yes, however they also indicate this is how they do their staged rollouts in general. So if they are releasing any other software update that goes through the staged rollout free customers are tested first. If that change broke something, free customers get that first. Which seems fair to me.

In my experience it’s generally best to roll out changes on testing, staging, and then clients in order of how much they pay, especially if you have SLAs with the highest paying customers. Impact is generally lower, both to the client, and to your bank account.

That sounds strange to me. If you introduce a bug then roll back very quickly, it will only affect high paying customers. If you introduce a bug then roll back a while later, it will impact high paying and low paying customers equally. Why would you want this scenario? If you flip it it seems strictly better to me.

Re: Details of the Cloudflare outage on July 2, 2019

#120

Post by Buge »

stevens32 wrote: post #85

For the regex novices here, would anyone mind explaining what that pattern is meant to match? More specifically, what `. (?:. =.*)` is meant to do?

It's meant to match any number of any characters, then match an equal sign, then match any number of any characters. But it's very badly written. It should instead simply be written

    .*=.*
BTW, your comment got mangled by HN's markdown formatting.
Post reply on HN