Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
rsc opened this issue Feb 9, 2022 · 9 comments · Fixed by siderolabs/tools#173
Closed

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

rsc opened this issue Feb 9, 2022 · 9 comments · Fixed by siderolabs/tools#173

Comments

@rsc
Copy link
Contributor

rsc commented Feb 9, 2022

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.

@rsc rsc added this to the Go1.18 milestone Feb 9, 2022
@rsc rsc self-assigned this Feb 9, 2022
@gopherbot
Copy link

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

@gopherbot
Copy link

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

@ianlancetaylor
Copy link
Contributor

@gopherbot Please open backport issues.

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

@gopherbot
Copy link

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
Copy link
Contributor

And-ZJ commented Feb 10, 2022

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

@rsc
Copy link
Contributor Author

rsc commented Feb 10, 2022

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
Copy link

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

@gopherbot
Copy link

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

@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Feb 17, 2022
…xps in Parse

The regexp code assumes it can recurse over the structure of
a regexp safely. Go's growable stacks make that reasonable
for all plausible regexps, but implausible ones can reach the
“infinite recursion?” stack limit.

This CL limits the depth of any parsed regexp to 1000.
That is, the depth of the parse tree is required to be ≤ 1000.
Regexps that require deeper parse trees will return ErrInternalError.
A future CL will change the error to ErrInvalidDepth,
but using ErrInternalError for now avoids introducing new API
in point releases when this is backported.

Fixes #51112.
Fixes #51118.

Change-Id: I97d2cd82195946eb43a4ea8561f5b95f91fb14c5
Reviewed-on: https://go-review.googlesource.com/c/go/+/384616
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-on: https://go-review.googlesource.com/c/go/+/384854
TryBot-Result: Gopher Robot <gobot@golang.org>
gopherbot pushed a commit that referenced this issue Feb 17, 2022
…xps in Parse

The regexp code assumes it can recurse over the structure of
a regexp safely. Go's growable stacks make that reasonable
for all plausible regexps, but implausible ones can reach the
“infinite recursion?” stack limit.

This CL limits the depth of any parsed regexp to 1000.
That is, the depth of the parse tree is required to be ≤ 1000.
Regexps that require deeper parse trees will return ErrInternalError.
A future CL will change the error to ErrInvalidDepth,
but using ErrInternalError for now avoids introducing new API
in point releases when this is backported.

Fixes #51112.
Fixes #51117.

Change-Id: I97d2cd82195946eb43a4ea8561f5b95f91fb14c5
Reviewed-on: https://go-review.googlesource.com/c/go/+/384616
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-on: https://go-review.googlesource.com/c/go/+/384855
frezbo added a commit to frezbo/tools that referenced this issue Mar 4, 2022
Update Golang to 1.17.8

Fixes: [CVE-2022-24921](golang/go#51112)

Signed-off-by: Noel Georgi <git@frezbo.dev>
frezbo added a commit to frezbo/tools that referenced this issue Mar 4, 2022
Update Golang to 1.17.8

Fixes: [CVE-2022-24921](golang/go#51112)

Signed-off-by: Noel Georgi <git@frezbo.dev>
smira pushed a commit to smira/tools that referenced this issue Mar 4, 2022
Update Golang to 1.17.8

Fixes: [CVE-2022-24921](golang/go#51112)

Signed-off-by: Noel Georgi <git@frezbo.dev>
(cherry picked from commit b63872b)
mazay added a commit to mazay/s3sync-service that referenced this issue Mar 4, 2022
mazay added a commit to mazay/s3sync-service that referenced this issue Mar 4, 2022
* target dependabot PR to devel branch

* Bump golang from 1.17.6-alpine3.15 to 1.17.7-alpine3.15 (#118)

Bumps golang from 1.17.6-alpine3.15 to 1.17.7-alpine3.15.

---
updated-dependencies:
- dependency-name: golang
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: Yevgeniy Valeyev <z.mazay@gmail.com>

* Bump k8s.io/client-go from 0.19.3 to 0.23.4 (#119)

Bumps [k8s.io/client-go](https://github.com/kubernetes/client-go) from 0.19.3 to 0.23.4.
- [Release notes](https://github.com/kubernetes/client-go/releases)
- [Changelog](https://github.com/kubernetes/client-go/blob/master/CHANGELOG.md)
- [Commits](kubernetes/client-go@v0.19.3...v0.23.4)

---
updated-dependencies:
- dependency-name: k8s.io/client-go
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: Yevgeniy Valeyev <z.mazay@gmail.com>

* Codecov (#125)

* target dependabot PR to devel branch (#124)

* Don’t limit codecov to PRs

* sanitise URL string in the log, fixes #126

* use request URI in log

* Bump github.com/aws/aws-sdk-go from 1.35.5 to 1.43.8 (#128)

* Bump github.com/aws/aws-sdk-go from 1.43.8 to 1.43.9 (#129)

* Bump github.com/aws/aws-sdk-go from 1.43.9 to 1.43.10 (#130)

Bumps [github.com/aws/aws-sdk-go](https://github.com/aws/aws-sdk-go) from 1.43.9 to 1.43.10.
- [Release notes](https://github.com/aws/aws-sdk-go/releases)
- [Changelog](https://github.com/aws/aws-sdk-go/blob/main/CHANGELOG.md)
- [Commits](aws/aws-sdk-go@v1.43.9...v1.43.10)

---
updated-dependencies:
- dependency-name: github.com/aws/aws-sdk-go
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* Bump github.com/aws/aws-sdk-go from 1.43.10 to 1.43.11 (#131)

* run codeql on PRs and schedule

* security fix for golang/go#51112

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
mazay added a commit to mazay/s3sync-service that referenced this issue Mar 5, 2022
* target dependabot PR to devel branch

* Bump golang from 1.17.6-alpine3.15 to 1.17.7-alpine3.15 (#118)

Bumps golang from 1.17.6-alpine3.15 to 1.17.7-alpine3.15.

---
updated-dependencies:
- dependency-name: golang
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: Yevgeniy Valeyev <z.mazay@gmail.com>

* Bump k8s.io/client-go from 0.19.3 to 0.23.4 (#119)

Bumps [k8s.io/client-go](https://github.com/kubernetes/client-go) from 0.19.3 to 0.23.4.
- [Release notes](https://github.com/kubernetes/client-go/releases)
- [Changelog](https://github.com/kubernetes/client-go/blob/master/CHANGELOG.md)
- [Commits](kubernetes/client-go@v0.19.3...v0.23.4)

---
updated-dependencies:
- dependency-name: k8s.io/client-go
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Co-authored-by: Yevgeniy Valeyev <z.mazay@gmail.com>

* Codecov (#125)

* target dependabot PR to devel branch (#124)

* Don’t limit codecov to PRs

* sanitise URL string in the log, fixes #126

* use request URI in log

* Bump github.com/aws/aws-sdk-go from 1.35.5 to 1.43.8 (#128)

* Bump github.com/aws/aws-sdk-go from 1.43.8 to 1.43.9 (#129)

* Bump github.com/aws/aws-sdk-go from 1.43.9 to 1.43.10 (#130)

Bumps [github.com/aws/aws-sdk-go](https://github.com/aws/aws-sdk-go) from 1.43.9 to 1.43.10.
- [Release notes](https://github.com/aws/aws-sdk-go/releases)
- [Changelog](https://github.com/aws/aws-sdk-go/blob/main/CHANGELOG.md)
- [Commits](aws/aws-sdk-go@v1.43.9...v1.43.10)

---
updated-dependencies:
- dependency-name: github.com/aws/aws-sdk-go
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* Bump github.com/aws/aws-sdk-go from 1.43.10 to 1.43.11 (#131)

* run codeql on PRs and schedule

* security fix for golang/go#51112

* validate k8s response status before parsing config, fixes #113

* use helm-docs

* minor docs and chart update

* update only read the docs file

* update doc

* retire chart release notes

* bump appVersion

* bumpd appVersion

* update aio manifest

* adjust build triggers

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
dnomd343 added a commit to dnomd343/ClearDNS that referenced this issue Mar 28, 2022
gopherbot pushed a commit that referenced this issue Apr 4, 2022
The fix for #51112 introduced a depth check but used
ErrInternalError to avoid introduce new API in a CL that
would be backported to earlier releases.

New API accepted in proposal #51684.

This CL adds a distinct error for this case.

For #51112.
Fixes #51684.

Change-Id: I068fc70aafe4218386a06103d9b7c847fb7ffa65
Reviewed-on: https://go-review.googlesource.com/c/go/+/384617
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
@rsc rsc removed their assignment Jun 22, 2022
danbudris pushed a commit to danbudris/go that referenced this issue Sep 14, 2022
…xps in Parse

The regexp code assumes it can recurse over the structure of
a regexp safely. Go's growable stacks make that reasonable
for all plausible regexps, but implausible ones can reach the
“infinite recursion?” stack limit.

This CL limits the depth of any parsed regexp to 1000.
That is, the depth of the parse tree is required to be ≤ 1000.
Regexps that require deeper parse trees will return ErrInternalError.
A future CL will change the error to ErrInvalidDepth,
but using ErrInternalError for now avoids introducing new API
in point releases when this is backported.

Fixes golang#51112.
Fixes golang#51117.

Change-Id: I97d2cd82195946eb43a4ea8561f5b95f91fb14c5
Reviewed-on: https://go-review.googlesource.com/c/go/+/384616
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-on: https://go-review.googlesource.com/c/go/+/384855
rcrozean pushed a commit to rcrozean/go that referenced this issue Oct 5, 2022
# AWS EKS
Backported To: go-1.15.15-eks
Backported On: Thu, 22 Sept 2022
Backported By: budris@amazon.com
Backported From: release-branch.go1.16
Upstream Source Commit: golang@07ee9e6
EKS Patch Source Commit: danbudris@e88851b
Fixes: CVE-2022-24921

# Original Information

The regexp code assumes it can recurse over the structure of
a regexp safely. Go's growable stacks make that reasonable
for all plausible regexps, but implausible ones can reach the
“infinite recursion?” stack limit.

This CL limits the depth of any parsed regexp to 1000.
That is, the depth of the parse tree is required to be ≤ 1000.
Regexps that require deeper parse trees will return ErrInternalError.
A future CL will change the error to ErrInvalidDepth,
but using ErrInternalError for now avoids introducing new API
in point releases when this is backported.

Fixes golang#51112.
Fixes golang#51117.

Change-Id: I97d2cd82195946eb43a4ea8561f5b95f91fb14c5
Reviewed-on: https://go-review.googlesource.com/c/go/+/384616
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-on: https://go-review.googlesource.com/c/go/+/384855
rcrozean pushed a commit to rcrozean/go that referenced this issue Oct 12, 2022
# AWS EKS
Backported To: go-1.15.15-eks
Backported On: Thu, 22 Sept 2022
Backported By: budris@amazon.com
Backported From: release-branch.go1.16
Upstream Source Commit: golang@07ee9e6
EKS Patch Source Commit: danbudris@e88851b
Fixes: CVE-2022-24921

# Original Information

The regexp code assumes it can recurse over the structure of
a regexp safely. Go's growable stacks make that reasonable
for all plausible regexps, but implausible ones can reach the
“infinite recursion?” stack limit.

This CL limits the depth of any parsed regexp to 1000.
That is, the depth of the parse tree is required to be ≤ 1000.
Regexps that require deeper parse trees will return ErrInternalError.
A future CL will change the error to ErrInvalidDepth,
but using ErrInternalError for now avoids introducing new API
in point releases when this is backported.

Fixes golang#51112.
Fixes golang#51117.

Change-Id: I97d2cd82195946eb43a4ea8561f5b95f91fb14c5
Reviewed-on: https://go-review.googlesource.com/c/go/+/384616
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-on: https://go-review.googlesource.com/c/go/+/384855
@golang golang locked and limited conversation to collaborators Jun 22, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants