3 ms·

It is incredibly relevant if you want to process uset-provided expressions. Otherwise you expose yourself to a DoS attack. The Rust regex crate is also DFA bas

It is incredibly relevant if you want to process uset-provided expressions. Otherwise you expose yourself to a DoS attack. The Rust regex crate is also DFA based and safe for untrusted inputs.

SonOfLilit 4y ago
Nice to know about Rust. From reading the docs the situation seems to be more complicated and more impressive: https://docs.rs/regex/latest/regex/#untrusted-input https://docs.rs/regex/latest/regex/#untrusted-input
Someone 4y ago
.NET added timeouts to handle that. It’s a per-regex setting with a global default (https://docs.microsoft.com/en-us/dotnet/api/system.text.regularexpressions.regex.matchtimeout?view=net-6.0 https://docs.microsoft.com/en-us/dotnet/api/system.text.regu...).
- nsajko 4y ago
  I guess that adding timeouts can significantly decrease the run time efficiency?
  - Someone 4y ago
    It can, but this isn’t a hard timeout. From the description (“The MatchTimeout property defines the approximate maximum time interval for a Regex instance to execute”), it seems they have their regex engine periodically (say after handling every 10,000 instructions of the compiled regex) check whether they went over the limit.
    - orra 4y ago
      Plus, as a general point, .NET has pretty decent performance. It's no C++, but at the same time substantial effort is put into optimisation. In fact for both .NET v5 and v7, they specifically did work to improve the performance of regexes. For example there is a new non-backtracking option. https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/ https://devblogs.microsoft.com/dotnet/regular-expression-imp...
masklinn 4y ago
There’s also the postgres regex engine, I don’t know how it works under the hood but it’s very resistant to catastrophic backtracking despite features which normally translate to nfa (e.g. backrefs).
- nsajko 4y ago
  > features which normally translate to nfa (e.g. backrefs) You're very wrong, backreferences in general can't be translated to finite automata (NFA is short for nondeterministic finite automaton). See these comments: https://news.ycombinator.com/item?id=18431610 https://news.ycombinator.com/item?id=18431610 https://news.ycombinator.com/item?id=27877743 https://news.ycombinator.com/item?id=27877743
  - masklinn 4y ago
    Maybe try to read my comment again because I don't think you understood what I wrote.
    - nsajko 4y ago
      You say: > resistant to catastrophic backtracking despite features which normally translate to nfa I interpret this as you equating NFA with backtracking engines, which would be incorrect. Is my interpretation wrong?

It is incredibly relevant if you want to process uset-provided expressions. Otherwise you expose yourself to a DoS attack. The Rust regex crate is also DFA based and safe for untrusted inputs.

SonOfLilit 4y ago

Nice to know about Rust. From reading the docs the situation seems to be more complicated and more impressive: https://docs.rs/regex/latest/regex/#untrusted-input https://docs.rs/regex/latest/regex/#untrusted-input

Someone 4y ago

.NET added timeouts to handle that. It’s a per-regex setting with a global default (https://docs.microsoft.com/en-us/dotnet/api/system.text.regularexpressions.regex.matchtimeout?view=net-6.0 https://docs.microsoft.com/en-us/dotnet/api/system.text.regu...).

nsajko 4y ago
I guess that adding timeouts can significantly decrease the run time efficiency?
- Someone 4y ago
  It can, but this isn’t a hard timeout. From the description (“The MatchTimeout property defines the approximate maximum time interval for a Regex instance to execute”), it seems they have their regex engine periodically (say after handling every 10,000 instructions of the compiled regex) check whether they went over the limit.
  - orra 4y ago
    Plus, as a general point, .NET has pretty decent performance. It's no C++, but at the same time substantial effort is put into optimisation. In fact for both .NET v5 and v7, they specifically did work to improve the performance of regexes. For example there is a new non-backtracking option. https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/ https://devblogs.microsoft.com/dotnet/regular-expression-imp...

masklinn 4y ago

There’s also the postgres regex engine, I don’t know how it works under the hood but it’s very resistant to catastrophic backtracking despite features which normally translate to nfa (e.g. backrefs).

nsajko 4y ago
> features which normally translate to nfa (e.g. backrefs) You're very wrong, backreferences in general can't be translated to finite automata (NFA is short for nondeterministic finite automaton). See these comments: https://news.ycombinator.com/item?id=18431610 https://news.ycombinator.com/item?id=18431610 https://news.ycombinator.com/item?id=27877743 https://news.ycombinator.com/item?id=27877743
- masklinn 4y ago
  Maybe try to read my comment again because I don't think you understood what I wrote.
  - nsajko 4y ago
    You say: > resistant to catastrophic backtracking despite features which normally translate to nfa I interpret this as you equating NFA with backtracking engines, which would be incorrect. Is my interpretation wrong?