2 ms·

> 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'l

by 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.
- amalcon 11y ago
  Re: the first part, that's fair. > Cox's formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input). Not constant, bounded. Theoretical CS doesn't care about the difference, but in practice it matters a lot. People provision hardware for the median case (really more like the 90th percentile), because provisioning for the worst case is really expensive. When something is bounded, but not constant, there exists the possibility of a resource exhaustion attack. > 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. I misinterpreted this one, because the convention I'm used to is that the expression is expected to match the entire input. I prefer this convention for its elegance, but it's much less common in practice than the Perl-like convention where you need to specify that you want that behavior. I also didn't sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you're correct about this with the convention you are using.
  - burntsushi 11y ago
    > Not constant, bounded. If I can do this: re = regexp(".+aaaaaaaaaaa") state = malloc(len(re)) match1 = exec(re, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") match2 = exec(re, "aaa") match3 = exec(re, "aaaaaaaaaaa") ... And I also claim that `exec` is guaranteed to never call `malloc` in any of its executions (or otherwise allocate). Do you consider that constant or bounded? It looks like it's constant to me. If you're talking about CPU resources, then the absolute worst case in the NFA algorithm is requiring `len(re)` operations per position in the input. I guess this is what you're referring to as bounded? If so, then it is a linear bound. :-) An attacker can't make matching take more than linear time. I feel like this entire conversation has been one roundabout exploration of "DFAs are faster than NFAs." :-/ > I also didn't sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you're correct about this with the convention you are using. You had me doubting myself there for a second, so kudos. :-)

by amalcon 11y ago

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.

amalcon 11y ago
Re: the first part, that's fair. > Cox's formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input). Not constant, bounded. Theoretical CS doesn't care about the difference, but in practice it matters a lot. People provision hardware for the median case (really more like the 90th percentile), because provisioning for the worst case is really expensive. When something is bounded, but not constant, there exists the possibility of a resource exhaustion attack. > 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. I misinterpreted this one, because the convention I'm used to is that the expression is expected to match the entire input. I prefer this convention for its elegance, but it's much less common in practice than the Perl-like convention where you need to specify that you want that behavior. I also didn't sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you're correct about this with the convention you are using.
- burntsushi 11y ago
  > Not constant, bounded. If I can do this: re = regexp(".+aaaaaaaaaaa") state = malloc(len(re)) match1 = exec(re, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") match2 = exec(re, "aaa") match3 = exec(re, "aaaaaaaaaaa") ... And I also claim that `exec` is guaranteed to never call `malloc` in any of its executions (or otherwise allocate). Do you consider that constant or bounded? It looks like it's constant to me. If you're talking about CPU resources, then the absolute worst case in the NFA algorithm is requiring `len(re)` operations per position in the input. I guess this is what you're referring to as bounded? If so, then it is a linear bound. :-) An attacker can't make matching take more than linear time. I feel like this entire conversation has been one roundabout exploration of "DFAs are faster than NFAs." :-/ > I also didn't sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you're correct about this with the convention you are using. You had me doubting myself there for a second, so kudos. :-)