4 ms·

> 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 en

> 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. :-)
  - 11y ago

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. :-)
- 11y ago