5 ms·

Regexploit: DoS-Able Regular Expressions

83 points by dedalus 6y ago

JoelJacobson 6y ago
Nice visualizations. I made an online visualization demo showing parsing and compilation of regexes -> NFA -> DFA -> minimal DFA -> LLVM IR: http://compiler.org/reason-re-nfa/src/index.html http://compiler.org/reason-re-nfa/src/index.html It doesn’t support backrefs, only simple basic regex features. Try entering (.+)[.](.+)[.](.+) to see how DFA-minimization of it looks like. You have to use [.] instead of \. as the parser doesn’t support escaping.
osaariki 6y ago
The article touches on DFA based engines and notes that they may not be the fastest in all use cases. To expand on that generally the reason for this would be that the automaton you get from the regular expression has too many states, which can happen for example with very large counters or cases where the state space includes a product of multiple counters due to non-determinism between them (backtracking engines would struggle with the latter case too though). Something an automata based engine can do (and IIRC re2 does) is that instead of constructing the full DFA, you can construct the much smaller non-deterministic finite automaton (NFA) and perform the product construction on-the-fly while caching states you've seen. However, this only helps if your input doesn't actually visit all those states. A malicious input could target your NFA engine to cause states being constantly kicked out of the cache. The slowdown here is linear though, so you're still better off than with a backtracking engine. A project I'm working on is the Symbolic Regex Engine (SRM) [1], which uses a symbolic variant of regex derivatives. This technique allows an often-minimal DFA to be constructed lazily. This is similar to NFA based engines, but results in much fewer states thus helping with the cache issue. SRM can also handle some classes of counters natively in how the automaton gets constructed, which can turn a blow-up that would be exponential in a DFA based engine into a linear one. [1]: https://github.com/AutomataDotNet/srm https://github.com/AutomataDotNet/srm
- glangdale 6y ago
  An interesting project would be to have a go at trying to automatically generate that malicious input. If I remember correctly, re2 has heuristics to see whether construction is "still worth it"; a particularly nasty input would stay just on the verge of "worth doing construction" but cost as much as possible (if you introduce too many novel states re2 will stop doing the construction at all). DFA based engines are often relatively simple under the hood, and backtrackers (like modern JIT'd libpcre) may outrace them due to having optimizations. Hyperscan (https://github.com/intel/hyperscan https://github.com/intel/hyperscan) a project I worked on for many years avoids the potential DoS attacks on backtrackers or the ones RE2 has, but surely has its own weak spots (notably, it assumes literal factors of the regular expression are rare in the input). We did build some mitigations to that, but fundamentally I bet Hyperscan could be made to slow down in a similar (linear) way to re2.
- wealthyyy 6y ago
  Security always trade-off over performance. HTTP faster than TLS.
shdon 6y ago
Personally, I've found it really helps to limit the patterns as much as possible to best match the valid input. My own rules of thumb: - Prefer character classes like \d, \s or \w over . - Prefer non-greedy .*? over greedy .* - Exclude a delimiter from the search space, like using [^>]*?> rather than .*?> or worse yet .*> - Prefer {count specifiers} over unbounded repeats. Not \d+ but \d{,3} instead
- zwp 6y ago
  Great list. I would add - Anchor when possible (^, $)
  - Y_Y 6y ago
    (If I understand correctly) This "(^,$)" should be parsed as a list of useful "anchor" symbols (resp. start and end of string) rather than a regexep itself. I wasted some time before I realised this.
    - zwp 6y ago
      Yes, that's essentially what I was trying to communicate. Since we are engine agnostic here be careful interpreting ^ or $ as start/end of _string_ though. In some regex engines this means start/end of _line_. If that's the case and if a regex validates input up to $ an attacker might be able to sneak in extra data after a newline. In Python you'd need multiline enabled but Ruby matches by default: irb(main):001:0> /^okay$/ =~ "okay\noops" => 0 # matches from position 0 (Ruby has \A and \Z for start and end of string to address this).
- Jenk 6y ago
  > - Exclude a delimiter from the search space, like using [^>]*?> rather than .*?> or worse yet .*> Or indeed: (?!>).*?
  - rstuart4133 6y ago
    Not quite. This works: (?:(?!>).)*>? But that is a very long winded way of writing: [^>]*?> which is long way of writing: [^>]*>
tyingq 6y ago
Some RE libraries have limit settings for recursion, number of times match() is called, etc. But the documentation is often hard to find for it. Also, last I checked in Perl, a simple alarm() doesn't work...the regex engine installs its own handler.

83 points by dedalus 6y ago

Nice visualizations. I made an online visualization demo showing parsing and compilation of regexes -> NFA -> DFA -> minimal DFA -> LLVM IR: http://compiler.org/reason-re-nfa/src/index.html http://compiler.org/reason-re-nfa/src/index.html It doesn’t support backrefs, only simple basic regex features. Try entering (.+)[.](.+)[.](.+) to see how DFA-minimization of it looks like. You have to use [.] instead of \. as the parser doesn’t support escaping.

osaariki 6y ago

The article touches on DFA based engines and notes that they may not be the fastest in all use cases. To expand on that generally the reason for this would be that the automaton you get from the regular expression has too many states, which can happen for example with very large counters or cases where the state space includes a product of multiple counters due to non-determinism between them (backtracking engines would struggle with the latter case too though). Something an automata based engine can do (and IIRC re2 does) is that instead of constructing the full DFA, you can construct the much smaller non-deterministic finite automaton (NFA) and perform the product construction on-the-fly while caching states you've seen. However, this only helps if your input doesn't actually visit all those states. A malicious input could target your NFA engine to cause states being constantly kicked out of the cache. The slowdown here is linear though, so you're still better off than with a backtracking engine. A project I'm working on is the Symbolic Regex Engine (SRM) [1], which uses a symbolic variant of regex derivatives. This technique allows an often-minimal DFA to be constructed lazily. This is similar to NFA based engines, but results in much fewer states thus helping with the cache issue. SRM can also handle some classes of counters natively in how the automaton gets constructed, which can turn a blow-up that would be exponential in a DFA based engine into a linear one. [1]: https://github.com/AutomataDotNet/srm https://github.com/AutomataDotNet/srm

glangdale 6y ago
An interesting project would be to have a go at trying to automatically generate that malicious input. If I remember correctly, re2 has heuristics to see whether construction is "still worth it"; a particularly nasty input would stay just on the verge of "worth doing construction" but cost as much as possible (if you introduce too many novel states re2 will stop doing the construction at all). DFA based engines are often relatively simple under the hood, and backtrackers (like modern JIT'd libpcre) may outrace them due to having optimizations. Hyperscan (https://github.com/intel/hyperscan https://github.com/intel/hyperscan) a project I worked on for many years avoids the potential DoS attacks on backtrackers or the ones RE2 has, but surely has its own weak spots (notably, it assumes literal factors of the regular expression are rare in the input). We did build some mitigations to that, but fundamentally I bet Hyperscan could be made to slow down in a similar (linear) way to re2.
wealthyyy 6y ago
Security always trade-off over performance. HTTP faster than TLS.

shdon 6y ago

Personally, I've found it really helps to limit the patterns as much as possible to best match the valid input. My own rules of thumb: - Prefer character classes like \d, \s or \w over . - Prefer non-greedy .*? over greedy .* - Exclude a delimiter from the search space, like using [^>]*?> rather than .*?> or worse yet .*> - Prefer {count specifiers} over unbounded repeats. Not \d+ but \d{,3} instead

zwp 6y ago
Great list. I would add - Anchor when possible (^, $)
- Y_Y 6y ago
  (If I understand correctly) This "(^,$)" should be parsed as a list of useful "anchor" symbols (resp. start and end of string) rather than a regexep itself. I wasted some time before I realised this.
  - zwp 6y ago
    Yes, that's essentially what I was trying to communicate. Since we are engine agnostic here be careful interpreting ^ or $ as start/end of _string_ though. In some regex engines this means start/end of _line_. If that's the case and if a regex validates input up to $ an attacker might be able to sneak in extra data after a newline. In Python you'd need multiline enabled but Ruby matches by default: irb(main):001:0> /^okay$/ =~ "okay\noops" => 0 # matches from position 0 (Ruby has \A and \Z for start and end of string to address this).
Jenk 6y ago
> - Exclude a delimiter from the search space, like using [^>]*?> rather than .*?> or worse yet .*> Or indeed: (?!>).*?
- rstuart4133 6y ago
  Not quite. This works: (?:(?!>).)*>? But that is a very long winded way of writing: [^>]*?> which is long way of writing: [^>]*>

tyingq 6y ago

Some RE libraries have limit settings for recursion, number of times match() is called, etc. But the documentation is often hard to find for it. Also, last I checked in Perl, a simple alarm() doesn't work...the regex engine installs its own handler.