regexp: stack overflow (process exit) handling deeply nested regexp

[rsc]

On 64-bit system, a large enough regexp can be deeply nested enough to cause goroutine stack overflows (the kind where the runtime says no more stack for you and exits). Specifically, strings.Repeat("(", 1<<20)+strings.Repeat(")", 1<<20) is enough.

I ran a test inside Google using C++ RE2 limiting the nesting depth of accepted expressions. A max depth of 200 did not break any of our tests. (A max depth of 100 did break one library that was mechanically generating a truly awful regular expression.)

To fix the problem I intend to cap the maximum depth of a regexp accepted by syntax.Parse at 1000, >5X what is needed by Google C++ and really about 100X what is reasonable.

Depth means the depth of the parse tree: (((((a))))) has depth 5, as does a***** in POSIX mode. (In Perl mode that's a syntax error.)

This will need to be backported to Go 1.16 and Go 1.17 as well.

[gopherbot]

Change https://go.dev/cl/384616 mentions this issue: regexp/syntax: reject very deeply nested regexps in Parse

[gopherbot]

Change https://go.dev/cl/384617 mentions this issue: regexp/syntax: add and use ErrInvalidDepth

[ianlancetaylor]

@gopherbot Please open backport issues.

Limit regexp recursion to avoid crashing on deeply nested regexp. Per issue description, this should be backported.

[gopherbot]

Backport issue(s) opened: #51117 (for 1.16), #51118 (for 1.17).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://go.dev/wiki/MinorReleases.

[And-ZJ]

I'm sorry to ask. Is this a security issue? If someone accepts external input as a regexp?

[rsc]

If someone accepts external input without imposing size limits, then yes. You need >1MB regexps to trigger this.
We are treating this as a PUBLIC-track security issue.

[gopherbot]

Change https://go.dev/cl/384854 mentions this issue: regexp/syntax: reject very deeply nested regexps in Parse

[gopherbot]

Change https://go.dev/cl/384854 mentions this issue: [release-branch.go1.17] regexp/syntax: reject very deeply nested regexps in Parse

[gopherbot]

Change https://go.dev/cl/384855 mentions this issue: [release-branch.go1.16] regexp/syntax: reject very deeply nested regexps in Parse