<regex>: regex_search() throws regex_error(error_complexity) when a long string is used with a lookahead regex

[TheStormN]

Describe the bug

We a trying to upgrade the compiler to the latest MSVC version. First time we did hit this issue #5792. After it was fixed and new MSVC version published, we've upgraded again to 14.51 and now we are getting another issue, this time with regex_error(error_complexity) when a lookahead regex is being used with a really long search string.

Note that if I make the path string shorter, everything is working good. While this might be an expected limitation, we didn't have issues with Visual Studio 2022. Also on Linux with GCC 13 this code is working properly.

Command-line test case

#include <iostream>
#include <regex>

int main()
{
	try {
		std::regex pattern(R"((?:.+[\/\\])?(?:.+?)_(.+?)_(.+?)@(.+?)\.(?:exe|app))");
		std::smatch matches;
		std::string requestStringParams(R"(D:\some\really\long\path\dir\dir\dir\dir\dir\dir\dir\dir\dir\dir\dir\dir\dir\dir\dir\dir\myapp.exe https://mysite.com/doaction/?action=56)");
		std::regex_search(requestStringParams, matches, pattern);
		std::cout << "no exception\n";
	}
	catch (const std::regex_error& ex) {
		std::cout << "regex_error with code " << ex.code() << "\n";
	}

	return 0;
}

This prints "regex_error with code 11".

Expected behavior

Should print "no exception".

STL version

Microsoft (R) C/C++ Optimizing Compiler Version 19.51.36248 for x64

Additional context

Might be related to issue #5792 but the exception is with different error code.

[StephanTLavavej]

Your regex doesn't contain any lookahead assertions. Those look like (?=positive_lookahead_assertion) and (?!negative_lookahead_assertion), which require what follows to match (or not) without consuming the characters. For example, R"(\b(\d{4})\b)" will capture 4 digits surrounded by word boundaries, while R"(\b(?=1[7-9])(\d{4})\b)" will still capture 4 digits but require them to start with 17, 18, or 19.

Instead, your regex contains a mix of capture groups like (.+?) and non-capture groups like (?:exe|app), one of which is optional (the (?:.+[\/\\])?). I haven't looked into the code and how the overhauled complexity limits are interacting with your regex, but I can see that your regex is extremely demanding regarding backtracking, because you have unconstrained .+ that matches one-or-more of anything. You're telling the quantifiers to be non-greedy (the .+?) when a match is possible, but this potentially implies a lot of backtracking since if it can't find a match that involves the underscore _, at sign @, etc. occurring in the right positions, the non-greedy quantifiers need to be retried with different substrings of the text.

I strongly recommend avoiding writing regexes like this. Instead, try to write regexes that are more strict about what they consume, and inherently avoid consuming too many characters, instead of relying on non-greedy quantifiers. For example, you can write [^/\\]+[/\\] to match one or more non-slash characters, followed by a slash character (allowing both forward and back slashes; there is no need to escape the forward slash in a character class, it is never special). This will never consume a slash for the first quantified part, whereas .+[\/\\] is potentially willing to do so (and in fact that one is non-greedy).

It depends on what you're trying to match but I get the feeling that this can be rewritten to be much clearer and much more efficient for all implementations, including our overhauled one. I'm kinda surprised that this even worked with the old implementation at all.

[TheStormN]

While I agree that this regex example is horrible, there are more than 100 PRs merged into the codebase every day with more than 300 devs working on it. Believe me, there are many other horrible things getting in there. :D Unfortunately there is no easy way to control that many people to produce good quality at least from my standpoint, as I'm not on manager or director level. Everybody is chasing some kind of deadline of new feature...

The thing is that my colleague PR about upgrading MSVC is being reverted 2 times already because of such kind of issues surfacing. While we can go and try to fix some of the things which popup soon after the upgrade, there is no way to know what other strange things rest in some more rarely hit code.

[muellerj2]

This is the ReDoS protection kicking in. The problem is that this particular regex requires a running time quadratic in the size of the input string, and because this regex is regex_search()ed and thus essentially applied at any position in the input string, this results in a cubic amount of work.

We changed how the number of steps is measured and how the limit is calculated in MSVC Build Tools 14.51. It seems that these changes result in a stricter limit for your particular regex. But ReDoS protection would also have kicked in in 14.50 and earlier, just for somewhat longer strings.

If I may ask, why are you using regex_search() here if the regex starts with what is essentially .+ anyway? Why is regex_match() not sufficient? That change alone would already bring this down to quadratic complexity.

[muellerj2]

Let me suggest an alternative regex that removes most of the backtracking complexity: (?:[^/\\]+[/\\])*[^/\\_]+_([^/\\_]+)_([^/\\@]+)@([^/\\.]+)\.(?:exe|app). This assumes that the number of occurences of the special characters _, @ and . is fixed; if they can appear more often, the regex must be adjusted accordingly.

Small warning: This regex can result in a stack overflow in MSVC Build Tools 14.50 or earlier.