6 ms·

> Reducing a parser to a DFA (deterministic finite automaton) provides it with measurable performance per character parsed. If an NFA (non-deterministic finite

by wolfgke 11y ago

> Reducing a parser to a DFA (deterministic finite automaton) provides it with measurable performance per character parsed. If an NFA (non-deterministic finite automaton) is used instead, then an attacker can abuse backtracking to increase parse time, often exponentially. An NFA does not use backtracking - at least in a sensible implementation. The problem is that most implementors of RE engines prefer "obvious hands-on" implementation that uses backtracking instead of understating the elegant theory behind NFAs. Here is how to implement an NFA without using backtracking: > https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Addendum: And it is also a bad idea to convert am NFA to an DFA for parsing because the number of necessary states can explode exponentially by this transformation.

deleted 11y ago
[deleted]
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. :-/
- 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.
burntsushi 11y ago
> Addendum: And it is also a bad idea to convert am NFA to an DFA for parsing because the number of necessary states can explode exponentially by this transformation. You can skirt this problem using a lazy DFA with a bounded cache. (i.e., See the third article in Cox's series.)
btilly 11y ago
Read your link carefully. Real-world regular expression engines support backreferences, and efficiently determining whether an RE with backreferences matches a given string is an NP-complete problem. If you're going to implement this important feature in a sane way then at SOME point you're going to need to backtrack.
- burntsushi 11y ago
  The parent comments are using the term "NFA engine," not "real world engines." NFA engines indeed cannot support backreferences for exactly the reason you specified. They simply aren't powerful enough. (The top comment in this thread mischaracterized regex engines, which is a common confusion.) And there are plenty of "real world" regex engines in wide use that don't support backreferences.
  - btilly 11y ago
    The commenter also talked about "RE engines". Most RE engines that are described as being an NFA (examples include Perl's, PCRE and Java's) are implemented with backtracking exactly because you can easily add in a little state and suddenly you support backreferences. Of course the language isn't really now a proper regular expression, but everyone knows what you mean when you talk about them. And yes, I'm well aware of how many real-world regex engines there are without backreferences. However the ones with the most widespread use, do.
    - burntsushi 11y ago
      > Most RE engines that are described as being an NFA Yes, and it's a huge disservice to continue doing so. It doesn't make any sense to describe Perl's (or Java's, or Python's or PCRE) regex implementation as an NFA. > but everyone knows what you mean when you talk about them I disagree. The confusion in this space is extremely high.
      - btilly 11y ago
        You are at least 20 years too late to change terminology here. There are more people who are used to the wrong terminology than will ever hear or care about the official terminology. Complaining about it is like telling the media the difference between crackers and hackers, or like telling most programmers that what they mean by big-O really is big-Omega. The problem starts with "regular expression". Regular expressions in Java, JavaScript, Python, Perl, Ruby, or many other languages or environments, aren't regular. They support backreferences. In many of those languages, it would be a backwards incompatible change to change either the name of the engine, or its feature set. There are more users of these languages who "know" how to use regular expressions than know the actual definition. Good luck convincing Java, JavaScript and Python to make backwards incompatible changes so we can restore language terminology! Moving on, every description of regular expressions starts with the DFA and NFA terminology. All of these regular expression engines that I named, when presented with an actual regular expression, solve it like an NFA. Admittedly with a backtracking algorithm. Even though their internal states go beyond NFA, it isn't actually wrong to say that "This RE engine uses an NFA algorithm on regular expressions." Given that, it is hopeless either to get people to use "regular expression" in its original meaning, or to get people to stop calling their so-called (but not really) RE engines, NFA implementations.

by wolfgke 11y ago

deleted 11y ago

[deleted]

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

burntsushi 11y ago

> Addendum: And it is also a bad idea to convert am NFA to an DFA for parsing because the number of necessary states can explode exponentially by this transformation. You can skirt this problem using a lazy DFA with a bounded cache. (i.e., See the third article in Cox's series.)

btilly 11y ago

Read your link carefully. Real-world regular expression engines support backreferences, and efficiently determining whether an RE with backreferences matches a given string is an NP-complete problem. If you're going to implement this important feature in a sane way then at SOME point you're going to need to backtrack.

burntsushi 11y ago
The parent comments are using the term "NFA engine," not "real world engines." NFA engines indeed cannot support backreferences for exactly the reason you specified. They simply aren't powerful enough. (The top comment in this thread mischaracterized regex engines, which is a common confusion.) And there are plenty of "real world" regex engines in wide use that don't support backreferences.
- btilly 11y ago
  The commenter also talked about "RE engines". Most RE engines that are described as being an NFA (examples include Perl's, PCRE and Java's) are implemented with backtracking exactly because you can easily add in a little state and suddenly you support backreferences. Of course the language isn't really now a proper regular expression, but everyone knows what you mean when you talk about them. And yes, I'm well aware of how many real-world regex engines there are without backreferences. However the ones with the most widespread use, do.
  - burntsushi 11y ago
    > Most RE engines that are described as being an NFA Yes, and it's a huge disservice to continue doing so. It doesn't make any sense to describe Perl's (or Java's, or Python's or PCRE) regex implementation as an NFA. > but everyone knows what you mean when you talk about them I disagree. The confusion in this space is extremely high.
    - btilly 11y ago
      You are at least 20 years too late to change terminology here. There are more people who are used to the wrong terminology than will ever hear or care about the official terminology. Complaining about it is like telling the media the difference between crackers and hackers, or like telling most programmers that what they mean by big-O really is big-Omega. The problem starts with "regular expression". Regular expressions in Java, JavaScript, Python, Perl, Ruby, or many other languages or environments, aren't regular. They support backreferences. In many of those languages, it would be a backwards incompatible change to change either the name of the engine, or its feature set. There are more users of these languages who "know" how to use regular expressions than know the actual definition. Good luck convincing Java, JavaScript and Python to make backwards incompatible changes so we can restore language terminology! Moving on, every description of regular expressions starts with the DFA and NFA terminology. All of these regular expression engines that I named, when presented with an actual regular expression, solve it like an NFA. Admittedly with a backtracking algorithm. Even though their internal states go beyond NFA, it isn't actually wrong to say that "This RE engine uses an NFA algorithm on regular expressions." Given that, it is hopeless either to get people to use "regular expression" in its original meaning, or to get people to stop calling their so-called (but not really) RE engines, NFA implementations.