6 ms·

Something interesting that isn't covered in this blog entry but is relevant to many of us is the importance of deterministic parsers for DOS / DDOS prevention.

Something interesting that isn't covered in this blog entry but is relevant to many of us is the importance of deterministic parsers for DOS / DDOS prevention. APIs that make use of parsers, be they regular expression parsers, or parsers for more complex grammars such as CFGs, can be abused if the underlying parser is nondeterministic. 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. This has been used, quite famously, in standards conforming XML parsers which have some very ugly backtracking issues dealing with entities and entity references. More commonly, people who decide to add regular expression validation to their APIs are often surprised to discover that an attacker can take up all sorts of server time while the API is trying to validate a carefully crafted degenerate case message. Many regular expression libraries out there are NFA, including the ones built into some popular high-level language runtimes.

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
  > 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.
viperscape 11y ago
I take it sexp parsers are technically dfa?
- pjscott 11y ago
  S-expressions are a classic example of something that can't be matched with a DFA or NFA. In order to know how many parens are currently open (and therefore needing to be matched with closing parens) it would need an unbounded number of states.
  - jstimpfle 11y ago
    On the other hand, it's just a matter of maintaining the number of open parentheses. Similar fact, one can't count string lengths in linear time (because lengths can be arbitrarily large). But for concerns of implementation it's just O(n).
haberman 11y ago
Great point, thanks! I'll add it to the article when I get the chance.

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

viperscape 11y ago

I take it sexp parsers are technically dfa?

pjscott 11y ago
S-expressions are a classic example of something that can't be matched with a DFA or NFA. In order to know how many parens are currently open (and therefore needing to be matched with closing parens) it would need an unbounded number of states.
- jstimpfle 11y ago
  On the other hand, it's just a matter of maintaining the number of open parentheses. Similar fact, one can't count string lengths in linear time (because lengths can be arbitrarily large). But for concerns of implementation it's just O(n).

haberman 11y ago

Great point, thanks! I'll add it to the article when I get the chance.