4 ms·
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 essen
by hn_throwaway_99 7y ago
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 https://swtch.com/~rsc/regexp/regexp4.html . Interestingly, he wrote his own regex engine, RE2, specifically because PCRE and others did not use real automata and he needed a way to do arbitrary regex search safely.
- asdfasgasdgasdg 7y agoYes, this is one of the regexp engines the post discusses switching to as a mitigation.
- bsder 7y agoThe 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.
- Firerouge 7y agoPerhaps a parser exists that can determine if an input regex is runaway backtrack prone, and can automatically switch to a deterministic algorithm?
- ehaliewicz2 7y agoJust check if it uses backreferences, otherwise it can be implemented via NFA/DFA.
- auscompgeek 7y agoActually, it is proven that NFAs and DFAs are equally expressive. See https://en.wikipedia.org/wiki/Powerset_construction https://en.wikipedia.org/wiki/Powerset_construction
- bsder 7y ago"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.
- gautamdivgi 7y agoI 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).
- Thorrez 7y agoI 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.
- ashton314 7y agoYou might be thinking of push down automata, where N-PDAs are strictly more powerful than D-PDAs.
- nabla9 7y agoThe problem is not DFA vs NFA. “regular expression” has different meaning in programming context and formal language context. Regular expressions in regex libraries do more than match regular languages. PCRE can recognize also all context free languages and some subset of context-sensitive languages. Just having backreferences makes the problem NP-hard.
- emmelaich 7y agoI 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.
- Abishek_Muthian 7y agoJust to note Go Lang uses RE2 in its regexp[1]. [1]:https://github.com/google/re2/wiki/Syntax https://github.com/google/re2/wiki/Syntax