3 ms·

Re: the first part, that's fair. > Cox's formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respec

by 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. :-)
- amalcon 11y ago
  Huh, I didn't consider the possibility of pre-allocating space for the entire state list. That's a cute trick, making it less memory efficient in the average case (though more efficient CPU-wise by avoiding malloc) but also addressing my exact concern. Nice. edit: I guess I should have just looked that up sooner. Sorry for any hassle or aggravations.
  - burntsushi 11y ago
    Interesting. I had never even considered not pre-allocating space for it... :-) In a "real" implementation, you also need space to store sub-capture locations. You get to reuse this space on each execution of the regex, so it's a really nice win. There are also certain crazy people in this world who have encoded the NFA algorithm into a code generation tool, which enables it to run completely malloc-free and entirely on the stack. :-)

by amalcon 11y ago

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. :-)

amalcon 11y ago
Huh, I didn't consider the possibility of pre-allocating space for the entire state list. That's a cute trick, making it less memory efficient in the average case (though more efficient CPU-wise by avoiding malloc) but also addressing my exact concern. Nice. edit: I guess I should have just looked that up sooner. Sorry for any hassle or aggravations.
- burntsushi 11y ago
  Interesting. I had never even considered not pre-allocating space for it... :-) In a "real" implementation, you also need space to store sub-capture locations. You get to reuse this space on each execution of the regex, so it's a really nice win. There are also certain crazy people in this world who have encoded the NFA algorithm into a code generation tool, which enables it to run completely malloc-free and entirely on the stack. :-)