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

Jump to bottom

regexp: timeout in ReplaceAll #54583

Closed
catenacyber opened this issue Aug 22, 2022 · 6 comments
Closed

regexp: timeout in ReplaceAll #54583

catenacyber opened this issue Aug 22, 2022 · 6 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Unplanned

Comments

@catenacyber
Copy link
Contributor

What version of Go are you using (go version)?

$ go version
go version go1.17.6 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/catena/Library/Caches/go-build"
GOENV="/Users/catena/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/catena/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/catena/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.17.6"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/catena/go/src/github.com/catenacyber/go/src/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/pp/dc1dtf9x2js3v0jx_m010nqr0000gn/T/go-build4237848497=/tmp/go-build -gno-record-gcc-switches -fno-common"
GOROOT/bin/go version: go version go1.17.6 darwin/amd64
GOROOT/bin/go tool compile -V: compile version go1.17.6
uname -v: Darwin Kernel Version 21.3.0: Wed Jan  5 21:37:58 PST 2022; root:xnu-8019.80.24~20/RELEASE_X86_64
ProductName:	macOS
ProductVersion:	12.2.1
BuildVersion:	21D62
lldb --version: lldb-1316.0.9.41
Apple Swift version 5.6 (swiftlang-5.6.0.323.62 clang-1316.0.20.8)
gdb --version: GNU gdb (GDB) 9.1

What did you do?

Run https://go.dev/play/p/MQ6jQYNTuLo?v=gotip

What did you expect to see?

The program finishing and printing Hello

What did you see instead?

timeout running program

Program exited.

Found by https://github.com/catenacyber/ngolo-fuzzing on oss-fuzz
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=49460

Not sure this is a real bug, but it looks like some function uses too much recursivity...
@junyer
Copy link
Contributor

junyer commented Aug 22, 2022

@rsc, this seems likely to be #11181 redux.

@dr2chase dr2chase added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Aug 24, 2022
@seankhliao seankhliao added this to the Unplanned milestone Aug 27, 2022
@catenacyber
Copy link
Contributor Author

any news on this ?

@junyer
Copy link
Contributor

junyer commented Feb 20, 2023

FWIW, the RE2 fuzzer does this to make RE2::GlobalReplace() replace only the first match (if any) and thus avoid wasting time on pathological cases. I imagine that the Go regexp package would need only minor modifications in order to support something similar.

@catenacyber
Copy link
Contributor Author

Interesting, are you also saying that ReplaceAll is intrinsically quadratic ?

@junyer
Copy link
Contributor

junyer commented Feb 20, 2023

Yes, see #11181 (comment) for a summary of the situation.

@catenacyber
Copy link
Contributor Author

I had read it, but I do not think I fully understand it.
But I understand your reply, so I know what to do, thanks

@golang golang locked and limited conversation to collaborators Feb 20, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@dr2chase @junyer @gopherbot @seankhliao @catenacyber