Use a non-backtracking NFA/DFA regex engine where possible

[DemiMarie]

Stack Exchange suffered an outage due to a regular expression that used quadratic time.

This is a feature request for using a DFA/NFA engine whenever possible – that is, on all regexps that don't have backreferences or any other non-regular features. Note that backreferences almost certainly cannot be handled by any efficient algorithm in general – the matching problem for regular expressions plus backreferences is NP hard.

[Priya91]

@DemiMarie .NET supports the non-backtracking atomic groups (?>). We can have a DFA engine in .NET Regex (been in backlog for sometime now) and allow options to chose this over the NFA, but again that doesn't prevent the regex stack overflow from happening, if the regex author is not careful with the quantifiers or unexpected input patterns.

[Priya91]

Putting it in backlog of features for Regex space.

[ViktorHofer]

Stack Exchange suffered an outage due to a regular expression that used quadratic time.

Why isn't Stack Exchange using timeouts on their regex expressions to avoid unwanted computations?

[danmoseley]

@NickCraver you may have some thoughts to share?

[NickCraver]

Why isn't Stack Exchange using timeouts on their regex expressions to avoid unwanted computations?

We have for many years in our web tier, but this isn't the default .NET behavior and these happening were in a section of code that doesn't respect the web.config setting (e.g. defaultRegexMatchTimeout="00:00:20"). I gave feedback on making this easier for developers, but ultimately others didn't agree: https://github.com/dotnet/corefx/issues/15173

In my opinion the lack of a intuitive way to set this (or even default it to something reasonable) is bad. The API was ported back from desktop "because it was there" (as far as I can tell), and I don't agree with this at all. The messaging has been that app domains are dead in .NET Core (kinda true, kinda not) yet the only way to set this is there. It's just a really weird message to developers and approach overall. The old API was bad, porting it makes sense in some ways but it's still severely lacking from a usability perspective. Environmental variables (that's effectively what this is) you have to look up will never be intuitive solutions. For something like this which is security critical, lack of discoverability is doubly bad.

I still believe there should be a static method on Regex to set this, regardless of the implementation underneath.

[ViktorHofer]

but this isn't the default .NET behavior

We had a discussion about this some weeks ago and unfortunately we can't change the default behavior which uses an infinite timeout without breaking someone.

I still believe there should be a static method on Regex to set this, regardless of the implementation underneath.

We will consider this if we make substantial changes to Regex i.e. introducing a new engine.