5 ms·

There are still pathological cases for NFAs: they are just quadratic in runtime and linear in (additional) storage, instead of exponential in runtime. That's f

by amalcon 11y ago

There are still pathological cases for NFAs: they are just quadratic in runtime and linear in (additional) storage, instead of exponential in runtime. That's frequently good enough, but sometimes you really want the linear runtime and constant memory usage of a DFA.

xyzzyz 11y ago
The problem is that the "constant" memory usage of a DFA may well be exponential in the size of the corresponding NFA/pattern.
- amalcon 11y ago
  Sure. You want to do this when an attacker controls the input, and a benevolent but fallible actor controls the expression. It's not useful when the attacker controls the expression.
- nanolith 11y ago
  It could be larger, but it would be a known constraint with known runtime characteristics. There is value in this, especially with regards to understanding the worst-case performance.
burntsushi 11y ago
It's a little better than that. A proper implementation of the NFA algorithm is always linear with respect to the search text and assuming the size of the regex is constant. More precisely, the time complexity is O(mn), where m ~ len(regex) and n ~ len(text).
- amalcon 11y ago
  While that's technically correct (the number of states in the NFA represents an upper bound on the number of states the simulation can be in at a time), this is one of those times when big-O can be misleading. In practice, there's a lot of variation between inputs. A typical case will leave you in only a handful of states at once, but a carefully constructed input can put you into many states. This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA. There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It's not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it's still good enough for most cases.
  - burntsushi 11y ago
    > This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA. If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former. And certainly, "linear additional memory usage" is not relative to the input either. > There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It's not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it's still good enough for most cases. Sure, but now you have to deal with exponential state blow up. :-) You can skirt around that with a lazy DFA, and you're now technically back to O(mn) (same as the NFA algorithm in the worst case), but in the common case, you end up pretty close to the performance of a DFA constructed offline. As "evidence" of my claim, you might peruse these unscientific benchmarks: https://github.com/jneem/regex-benchmarks https://github.com/jneem/regex-benchmarks (The first group uses an offline DFA and the latter two groups are both lazy DFAs. Of course, this is just an anecdote!) My view on this is pretty biased because my goal is not to just be able to deal with untrusted input, but to also deal with untrusted regexes. It's hard to satisfy the latter case with an offline DFA. :-/
    - wolfgke 11y ago
      > If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former. I think he rather means O(len(regex)^2 * len(input)). For the reason: The number of states of an NFA is O(len(regex)) =: m. When parsing with an NFA (standard algorithm) you iterate through all states we are currently in (up to m). On the current input character each state we are in can go into up to m new states for the next state. This is up to m^2 transformations to check.
      - burntsushi 11y ago
eru 11y ago
Do you have more background on that? As far as I know, burntsushi is entirely correct, NFAs take a constant amount of space to run, and a linear amount of time (all in relation to the length of the input text). Of course, backreferences and other stuff take you out of the realm of regular languages. Avoid these.

by amalcon 11y ago

xyzzyz 11y ago

The problem is that the "constant" memory usage of a DFA may well be exponential in the size of the corresponding NFA/pattern.

amalcon 11y ago
Sure. You want to do this when an attacker controls the input, and a benevolent but fallible actor controls the expression. It's not useful when the attacker controls the expression.
nanolith 11y ago
It could be larger, but it would be a known constraint with known runtime characteristics. There is value in this, especially with regards to understanding the worst-case performance.

burntsushi 11y ago

It's a little better than that. A proper implementation of the NFA algorithm is always linear with respect to the search text and assuming the size of the regex is constant. More precisely, the time complexity is O(mn), where m ~ len(regex) and n ~ len(text).

amalcon 11y ago
While that's technically correct (the number of states in the NFA represents an upper bound on the number of states the simulation can be in at a time), this is one of those times when big-O can be misleading. In practice, there's a lot of variation between inputs. A typical case will leave you in only a handful of states at once, but a carefully constructed input can put you into many states. This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA. There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It's not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it's still good enough for most cases.
- burntsushi 11y ago
  > This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA. If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former. And certainly, "linear additional memory usage" is not relative to the input either. > There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It's not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it's still good enough for most cases. Sure, but now you have to deal with exponential state blow up. :-) You can skirt around that with a lazy DFA, and you're now technically back to O(mn) (same as the NFA algorithm in the worst case), but in the common case, you end up pretty close to the performance of a DFA constructed offline. As "evidence" of my claim, you might peruse these unscientific benchmarks: https://github.com/jneem/regex-benchmarks https://github.com/jneem/regex-benchmarks (The first group uses an offline DFA and the latter two groups are both lazy DFAs. Of course, this is just an anecdote!) My view on this is pretty biased because my goal is not to just be able to deal with untrusted input, but to also deal with untrusted regexes. It's hard to satisfy the latter case with an offline DFA. :-/
  - wolfgke 11y ago
    > If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former. I think he rather means O(len(regex)^2 * len(input)). For the reason: The number of states of an NFA is O(len(regex)) =: m. When parsing with an NFA (standard algorithm) you iterate through all states we are currently in (up to m). On the current input character each state we are in can go into up to m new states for the next state. This is up to m^2 transformations to check.
    - burntsushi 11y ago

eru 11y ago

Do you have more background on that? As far as I know, burntsushi is entirely correct, NFAs take a constant amount of space to run, and a linear amount of time (all in relation to the length of the input text). Of course, backreferences and other stuff take you out of the realm of regular languages. Avoid these.