5 ms·

Actually, my mistake is that I was examining a particular pathological case for NFAs, that DFAs handle fine: something like /.+aaaaaaaaaa/. In this case, the

by amalcon 11y ago

Actually, my mistake is that I was examining a particular pathological case for NFAs, that DFAs handle fine: something like /.+aaaaaaaaaa/. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of "all eleven states". For that regex, the worst case is O(min(len(regex),len(input))*len(input)). This is quadratic in the input length, until a certain point. Which formula is correct then depends on whether the regex or the input is longer. In other cases (e.g. /(aa|ab|ac|ad|ae|af|ag|...)+/), you blow up to the maximum number of states immediately, and for a matching string stay in the same number of states the whole time. Therefore, it is technically correct to leave out the len(input) parameter if you are considering arbitrary regular expressions. > You can skirt around that with a lazy DFA This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process.

burntsushi 11y ago
> something like /.+aaaaaaaaaa/. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of "all eleven states". That's just false for the NFA algorithm. I'm not sure where your confusion lay, unfortunately. There are no pathological cases for the NFA algorithm. Zero. Zip. Nada. It's guaranteed O(mn) time. See Cox's articles. They explain. It is true of course that certain regexes run slower than others using the NFA algorithm, but this is because of constant factors, not because of any degradation in runtime complexity. When implementing the NFA algorithm, you can allocate all of the space you need upfront and then execute a search guaranteeing no additional allocation. Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. (I think this is isomorphic to your example, assuming `a{11}$`.) > This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process. Sounds pretty complex to me. Certainly more complex and fiddly IMO than implementing a lazy DFA. (I've done both.)
- amalcon 11y ago
  > It's guaranteed O(mn) time. I'm apparently completely failing to communicate my point here, because you seem to think I'm contradicting this. I am not. I'll maybe try to work through the example. For the purposes of this example, we have a fixed regular expression of /.+aaaaaaaaaa/. Processing the string 'a' takes one operation. Processing the string 'aa' takes three operations. Processing the string 'aaa' takes six operations. Processing a string of 'aaaa' takes ten operations. This is a quadratic progression. The DFA, however, has only eleven states. Yes, there is a bound to the number of operations of 11*length. Yes, this means that big-O says it's linear. No, an attacker can't simply supply a 30-character string and lock up your system the way they might be able to for a backtracking approach. That's beside the point. An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach. An attacker may still be able to exploit this in a way that would not be an issue with a DFA, e.g. by attempting to exhaust memory by issuing many simultaneous expensive requests when your system is provisioned to handle average requests. > Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. Yes, there are pathological cases, which is why you don't use that approach with untrusted regexes. I've never disagreed with this. This isn't even one of them, however. The DFA would have n+3 states: an initial state, a reject-loop state, a state for when we have seen the initial zero, and one state for when we have seen each of n additional zeroes or ones. I'm not sure how one would end up with more states than that: perhaps by not consolidating equivalent states in the NFA first? Edit: Apparently you're using the convention that one searches for a match anywhere in the input string, which while common isn't what I'm used to. This doesn't change anything: it just makes most transitions that would otherwise go to the reject-loop state go to the initial state instead. It's possible to get a pathological DFA, but one needs to work harder at it than this.
  - burntsushi 11y ago
    > Yes, there is a bound to the number of operations of 11{star}length. Yes, this means that big-O says it's linear. ... that's been exactly my position this entire time. I guess I just don't understand why you are calling the NFA algorithm quadratic. Calling it quadratic because there exists a particular progression that moves the runtime complexity in a quadratic fashion up to a predetermined linear bound seems really confusing. Overall, attackers can't make the entire algorithm run in quadratic time in the length of the input or the regex. That's what matters. With all that said, I agree with your final conclusion of course, that the NFA algorithm is going to be slower than running a pre-built DFA. But I think attributing this to quadratic behavior is just confusing. I personally think of it more as the NFA having to maintain multiple simultaneous states and being forced to follow epsilon transitions over and over again. In contrast, a DFA will only ever be in one state and it will cache all of the epsilon transitions in its states. > An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach. Cox's formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input). I mean, this isn't theoretical. You can go look at an implementation of the NFA algorithm by either Cox or myself, and it's pretty clear that some fixed allocation (based on the size of the compiled regex) happens up front, and no further allocation happens during the actual search. You can't make it blow up and take quadratic time. > This isn't even one of them, however, because the NFA has no loop. The DFA would have n+3 states: an initial state, a reject-loop state, a state for when we have seen the initial zero, and one state for when we have seen each of n additional zeroes or ones. It's exponential because it requires counting. You don't actually know when you've seen the initial zero, since you can see any number of 0s or 1s before it, and exactly N number of 0s or 1s after it, and then following that, the end of the string. (That final `$` is probably crucial to requiring an exponential number of states.) It's a pretty standard example: https://en.wikipedia.org/wiki/Regular_expression#Expressive_power_and_compactness https://en.wikipedia.org/wiki/Regular_expression#Expressive_... See also: https://github.com/google/re2/blob/master/re2/testing/dfa_test.cc#L166 https://github.com/google/re2/blob/master/re2/testing/dfa_te... This blurb from Wikipedia is also relevant: > On the other hand, it is known that every deterministic finite automaton accepting the language Lk must have at least 2k states. Luckily, there is a simple mapping from regular expressions to the more general nondeterministic finite automata (NFAs) that does not lead to such a blowup in size; for this reason NFAs are often used as alternative representations of regular languages. This exactly matches my experience and what Cox says.

by amalcon 11y ago

burntsushi 11y ago

> something like /.+aaaaaaaaaa/. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of "all eleven states". That's just false for the NFA algorithm. I'm not sure where your confusion lay, unfortunately. There are no pathological cases for the NFA algorithm. Zero. Zip. Nada. It's guaranteed O(mn) time. See Cox's articles. They explain. It is true of course that certain regexes run slower than others using the NFA algorithm, but this is because of constant factors, not because of any degradation in runtime complexity. When implementing the NFA algorithm, you can allocate all of the space you need upfront and then execute a search guaranteeing no additional allocation. Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. (I think this is isomorphic to your example, assuming `a{11}$`.) > This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process. Sounds pretty complex to me. Certainly more complex and fiddly IMO than implementing a lazy DFA. (I've done both.)

amalcon 11y ago
> It's guaranteed O(mn) time. I'm apparently completely failing to communicate my point here, because you seem to think I'm contradicting this. I am not. I'll maybe try to work through the example. For the purposes of this example, we have a fixed regular expression of /.+aaaaaaaaaa/. Processing the string 'a' takes one operation. Processing the string 'aa' takes three operations. Processing the string 'aaa' takes six operations. Processing a string of 'aaaa' takes ten operations. This is a quadratic progression. The DFA, however, has only eleven states. Yes, there is a bound to the number of operations of 11*length. Yes, this means that big-O says it's linear. No, an attacker can't simply supply a 30-character string and lock up your system the way they might be able to for a backtracking approach. That's beside the point. An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach. An attacker may still be able to exploit this in a way that would not be an issue with a DFA, e.g. by attempting to exhaust memory by issuing many simultaneous expensive requests when your system is provisioned to handle average requests. > Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. Yes, there are pathological cases, which is why you don't use that approach with untrusted regexes. I've never disagreed with this. This isn't even one of them, however. The DFA would have n+3 states: an initial state, a reject-loop state, a state for when we have seen the initial zero, and one state for when we have seen each of n additional zeroes or ones. I'm not sure how one would end up with more states than that: perhaps by not consolidating equivalent states in the NFA first? Edit: Apparently you're using the convention that one searches for a match anywhere in the input string, which while common isn't what I'm used to. This doesn't change anything: it just makes most transitions that would otherwise go to the reject-loop state go to the initial state instead. It's possible to get a pathological DFA, but one needs to work harder at it than this.
- burntsushi 11y ago
  > Yes, there is a bound to the number of operations of 11{star}length. Yes, this means that big-O says it's linear. ... that's been exactly my position this entire time. I guess I just don't understand why you are calling the NFA algorithm quadratic. Calling it quadratic because there exists a particular progression that moves the runtime complexity in a quadratic fashion up to a predetermined linear bound seems really confusing. Overall, attackers can't make the entire algorithm run in quadratic time in the length of the input or the regex. That's what matters. With all that said, I agree with your final conclusion of course, that the NFA algorithm is going to be slower than running a pre-built DFA. But I think attributing this to quadratic behavior is just confusing. I personally think of it more as the NFA having to maintain multiple simultaneous states and being forced to follow epsilon transitions over and over again. In contrast, a DFA will only ever be in one state and it will cache all of the epsilon transitions in its states. > An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach. Cox's formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input). I mean, this isn't theoretical. You can go look at an implementation of the NFA algorithm by either Cox or myself, and it's pretty clear that some fixed allocation (based on the size of the compiled regex) happens up front, and no further allocation happens during the actual search. You can't make it blow up and take quadratic time. > This isn't even one of them, however, because the NFA has no loop. The DFA would have n+3 states: an initial state, a reject-loop state, a state for when we have seen the initial zero, and one state for when we have seen each of n additional zeroes or ones. It's exponential because it requires counting. You don't actually know when you've seen the initial zero, since you can see any number of 0s or 1s before it, and exactly N number of 0s or 1s after it, and then following that, the end of the string. (That final `$` is probably crucial to requiring an exponential number of states.) It's a pretty standard example: https://en.wikipedia.org/wiki/Regular_expression#Expressive_power_and_compactness https://en.wikipedia.org/wiki/Regular_expression#Expressive_... See also: https://github.com/google/re2/blob/master/re2/testing/dfa_test.cc#L166 https://github.com/google/re2/blob/master/re2/testing/dfa_te... This blurb from Wikipedia is also relevant: > On the other hand, it is known that every deterministic finite automaton accepting the language Lk must have at least 2k states. Luckily, there is a simple mapping from regular expressions to the more general nondeterministic finite automata (NFAs) that does not lead to such a blowup in size; for this reason NFAs are often used as alternative representations of regular languages. This exactly matches my experience and what Cox says.