[deleted]
Details of the Cloudflare outage on July 2, 2019
121–130 of 159 posts
Re: Details of the Cloudflare outage on July 2, 2019
#122> It might also be obvious that once state 4 was reached (after x= was matched) the regular expression had matched and the algorithm could terminate without considering the final x at all.
That's true if you just want a boolean result. But if you want to get the matched string (which it appears the actual code does), then you need to continue, because it's using greedy matching.
Re: Details of the Cloudflare outage on July 2, 2019
#123One 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.
You might be thinking of push down automata, where N-PDAs are strictly more powerful than D-PDAs.
Re: Details of the Cloudflare outage on July 2, 2019
#124Might be late, but has anyone in CloudFlare tried to switch away from regex to something more efficient and powerful? Tools like re2c can convert 100s of regexs and CFG into a single optimized state machine (which includes no back tracking, as far as I remember). It should easily handle 10s of millions transactions per second per core if the complete state machine fits into the CPU level 3 cache (or lower), with a bi…
The article says they're going to either switch to RE2 or Rust's regex, both of which use a DFA (a state machine) and have no backtracking.
But you do bring up a good point. RE2 and Rust both compile the regex in the same process that executes it. Compiling the regex as part of your build process then pushing the compiled form could have advantages.
Re: Details of the Cloudflare outage on July 2, 2019
#125>A protection that would have helped prevent excessive CPU use by a regular expression was removed by mistake during a refactoring of the WAF weeks prior—a refactoring that was part of making the WAF use less CPU. Faster karma than normal i think.
Taking the safeties off to go faster... yes, you will go faster, but it might be right off a cliff. This is a good lesson on Chesterton’s Fence. I’ve been thinking for a while that we really need the (default behavior) ability to annotate commits after the fact, so that we have a durable commentary that can evolve over time. We should be able to go back and add strongly worded things like “yes this looks broken but i…
Can't you just add comments to the actual code saying those things? I've seen code comments saying those exact things.
Re: Details of the Cloudflare outage on July 2, 2019
#126Earlier quoted context omitted.
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.
The idea is that the fix itself is being tested. If you knew your 'rollback' will work for certain, then you'd just deploy it to everyone asap. But since you don't, you test it and as a potential outcome of your test is no fix or making things worse, you don't test it on your highest-value customers. Imagine what your postmortem would read like if your fix made an even bigger mess.
Re: Details of the Cloudflare outage on July 2, 2019
#127I used to be really into regex and I'm now rusty, but wouldn't the desired representation of .* .* =.* be something closer to [^=]\* [^=]\* =[^=]\* ? I feel like it could be optimized further but this would be the first step, and wouldn't most experienced regex authors use that from the beginning, nipping the whole backtracking problem in the bud and making the regex much more performant?
The original one would match "==", your suggestion would not. To get a clean regex they should switch to
.*=.*
Re: Details of the Cloudflare outage on July 2, 2019
#128One 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…
Just to note Go Lang uses RE2 in its regexp[1].
Re: Details of the Cloudflare outage on July 2, 2019
#129Earlier quoted context omitted.
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.
The idea is that the fix itself is being tested. If you knew your 'rollback' will work for certain, then you'd just deploy it to everyone asap. But since you don't, you test it and as a potential outcome of your test is no fix or making things worse, you don't test it on your highest-value customers. Imagine what your postmortem would read like if your fix made an even bigger mess.
Oh, I misunderstood you originally. I thought you said rollout from highest to lowest. You're actually saying lowest to highest.
Re: Details of the Cloudflare outage on July 2, 2019
#130Earlier 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.
Actually, it is proven that NFAs and DFAs are equally expressive. See https://en.wikipedia.org/wiki/Powerset_construction
"You are technically correct. The best kind of correct."
In theory, your statement is perfectly correct. However, quoting that reference:
"However, if the NFA has n states, the resulting DFA may have up to 2^n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs."
This means that in practice, DFAs are larger, slower, and sometimes can't be run at all if complex enough.
However, this was my mistake. I remembered (vaguely) the 2^n issue and didn't follow up to make sure I was accurate.
And I completely spaced on the fact that neither NFA's nor DFA's handle backreferences without extension.