Go: cmd/go2go: fuzzing triggers various crashes in type checker

Created on 17 Jun 2020 · 28Comments · Source: golang/go

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

My local go version used for the fuzzing:

$ go version
go version devel +4ba19b0188 Wed Jun 17 00:44:16 2020 +0000 linux/amd64

Does this issue reproduce with the latest release?

Yes with a recent git checkout dev.go2go

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

linux/amd64

What did you do?

I tried fuzzing the type checker from the dev.go2go branch for a short period of time (roughly around 45 minutes) and was able to generate a variety of crashes. Here are six samples.

I realize this is still early days, and I suspect it is much more useful to have crashes or panics from code that actual humans wrote, but posting these examples of crashes in case there is interest in hardending against more corner cases, or perhaps using some as test cases in the future.

I was running fzgo, which is a prototype of making fuzzing a first class citizen in the go command (#19109).

The engine underneath fzgo is @dvyukov's go-fuzz. I can post the fuzz function later if interested, but it was a cut down and slightly tweaked fuzz function adapted from https://github.com/dvyukov/go-fuzz-corpus/tree/master/gotypes.

These all crash on the current go2goplay.golang.org:

Crash 1: invalid memory address or nil pointer dereference

go/types.(*Checker).instantiate

package main
type nt(type )interface{g}
type ph(type e nt,g(d))s
func(*ph(e,e))h(d)

http://go2goplay.golang.org/p/7Jk4PT9GX3k

Crash 2: invalid memory address or nil pointer dereference

go/types.optype

package main
type Numeric interface{t}
func t(type T Numeric)(s[]T){0(){s[0][0]}}

https://go2goplay.golang.org/p/46EZOUKBLLu

Crash 3: invalid memory address or nil pointer dereference

go/types.IsInterface

package main
type d*interface{d.p}

https://go2goplay.golang.org/p/HChlkK2A_Di

Crash 4: invalid memory address or nil pointer dereference

go/types.(*Interface).Complete

package main
type Numeric interface{t}
func t(type T Numeric)(s[]T){if(0){*s[0]}}

https://go2goplay.golang.org/p/TwoY4k9kR1w

Crash 5: panic: multiplication of zero with infinity

math/big.(*Float).Mul

package main
func X(){7E700000000*0}

https://go2goplay.golang.org/p/avwOXp4HJrC

Crash 6: panic: assertion failed

go/types.(*Checker).shift

package main
func X(){0<<7E6000000000}

https://go2goplay.golang.org/p/pv_BlSJ9v5W

(Side note: it would be nice to be able to issue commands like go test -fuzz=. ./... (#19109) on the stdlib and elsewhere ;-)

NeedsInvestigation

Source

thepudds

Most helpful comment

@thepudds Thanks. I will look at these eventually, they are useful to test the corners of the implementation (keep in mind, this is still a prototype, and some pieces are pretty rough and known to be not correct for all cases).

griesemer on 21 Jun 2020

👍2

All 28 comments

These are all non-urgent, but I agree the tools shouldn't crash. Will get to these eventually. If you find more similar crashes, please add to this issue, rather than creating many more.

Thanks for reporting!

griesemer on 17 Jun 2020

Hi Robert, that makes sense, and will do.

Thanks for your work here!

thepudds on 17 Jun 2020

I've got some more examples of some crashes that I found manually messing around with things, and this issue seemed like an appropriate place to put them.

Crash 7: panic: assertion failed

package main
type foo interface { bar() }
type x(type A) struct{ foo }
func main() { var _ foo = x(int){} }

https://go2goplay.golang.org/p/1VztHp6nDlp

Crash 8: fatal error: stack overflow

package main
type foo(type A) interface { type A }
func bar(type A foo(A))(a A) {}
func main() {}

https://go2goplay.golang.org/p/fX5PYaFHB1Z

Crash 9: internal compiler error: typecheck DCLFIELD

package main
type foo(type A) interface { type foo(A) }
func main() { var _ = new(foo(int)) }

https://go2goplay.golang.org/p/8-gvXzWvuky

This last one isn't necessarily a crash, but I don't know how to categorize it because it seems like some sort of unknown error class.

Crash 10: looping while expanding type

package main
type w(type A) struct{}
func (_ w(A)) Wrap() w(w(A)) { return w(w(A)){} }
func main() { var _ w(struct{}) }

https://go2goplay.golang.org/p/Vfv72Q_yFoS

zeebo on 17 Jun 2020

👍1

EDIT: it looks like this panic occurs when any function doesn't have a body, so for example: https://go2goplay.golang.org/p/Q4yf9FPaydk

package main

func main()

The usage of //go:linkname below triggers it. Apologies if this is a duplicate.

Here's another one discovered by @zeebo while we were discussing gaining access to the runtime's map hasher functions:

Works fine in normal playground: https://play.golang.org/p/WWVqIxtH7b1
Crashes go2go playground: https://go2goplay.golang.org/p/WWVqIxtH7b1

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x10 pc=0x61ad46]

goroutine 1 [running]:
go/go2go.(*translator).translateBlockStmt(0xc00015b9b0, 0x0)
    /usr/local/go-faketime/src/go/go2go/rewrite.go:454 +0x26
go/go2go.(*translator).translateFuncDecl(0xc00015b9b0, 0xc0000c2230)
    /usr/local/go-faketime/src/go/go2go/rewrite.go:448 +0xc5
go/go2go.(*translator).translate(0xc00015b9b0, 0xc0000c2280)
    /usr/local/go-faketime/src/go/go2go/rewrite.go:376 +0x391
go/go2go.rewriteAST(0xc0000b0240, 0xc0000813b0, 0x0, 0x0, 0xc000081d10, 0xc0000c2280, 0x1, 0xc000081360, 0xc000081d10)
    /usr/local/go-faketime/src/go/go2go/rewrite.go:188 +0x109
go/go2go.RewriteBuffer(0xc0000813b0, 0x7ffcd64eedd8, 0x1e, 0xc0000f8000, 0x477, 0x677, 0x0, 0xc000086a20, 0xc0000869f0, 0xc0000869c0, ...)
    /usr/local/go-faketime/src/go/go2go/go2go.go:132 +0x2c5
main.translateFile(0xc0000813b0, 0x7ffcd64eedd8, 0x1e)
    /usr/local/go-faketime/src/cmd/go2go/translate.go:26 +0xa9
main.main()
    /usr/local/go-faketime/src/cmd/go2go/main.go:64 +0x2ea

Go build failed.

mdlayher on 17 Jun 2020

Here is another batch of crashes from fuzzing. (For numbering, I am treating the five from @zeebo and @mdlayher above as part of the numbering sequence, and hence am starting with 12 here).

This is still with:

go version devel +4ba19b0188 Wed Jun 17 00:44:16 2020 +0000 linux/amd64

Crash 12: panic: unreachable

go/types.(*Checker).assignment

package main
var u, i [func(u, c) {}(0, len)]c

https://go2goplay.golang.org/p/zZxlD1B7QpN

Crash 13: panic: internal error: final action list grew

go/types.(*Checker).processFinals

package main
type o(type T) func(*o([]T)) interface {
    T
    error
    error
}

https://go2goplay.golang.org/p/fUILIW9WD5E

Crash 14: fatal error: stack overflow

go/types.(*unifier).nify
(nify -> nify -> nify -> ...)

package main
func F(type *T)(func(T) T) { F(func(T) t {}) }

https://go2goplay.golang.org/p/BaXFnTQjzE4

Crash 15: panic: assertion failed

go/types.makeSubstMap

package main
func y() { var a interface{ p() } = G(string){} }
type G(type X) s
func (G) p()

https://go2goplay.golang.org/p/R9gtjp611eP

Crash 16: panic: assertion failed

go/types.(*subster).typ

package main
type Foo(type T) r
func r(type T)() Foo((Foo(T)))

https://go2goplay.golang.org/p/pXrh7-AoAZi

Crash 17: panic: duplicate method c

go/types.(*Interface).Complete

package main
type Y interface{ c() }
type Z interface {
    c() Y
    Y
}
func F(type T Z)(T)

https://go2goplay.golang.org/p/Q9iDpXeF3u-

Crash 18: panic: nil typ

go/types.(*subster).typ

package main
type o(type T) []func(_ o([]_))

https://go2goplay.golang.org/p/cTESh52u3h6

Crash 19: panic: assertion failed

go/types.(*Checker).rawExpr

package main
type Z [][[]Z{}[0][0]]c

https://go2goplay.golang.org/p/p9olLU-mRQG

thepudds on 19 Jun 2020

Sorry, Crash 15 is probably a duplicate of @zeebo's first crash in https://github.com/golang/go/issues/39634#issuecomment-645545299, but I will leave it here regardless (including to avoid renumbering 😅)

thepudds on 19 Jun 2020

Of the first batch, crashes 3, 5, and 6 are real. The others (1, 2, 4) don't crash anymore on dev.go2go. 3, 5, and 6 are unrelated to generics and may also crash in the regular type checker (try go vet on them). If so, please file individual bugs against the regular go/types package.

griesemer on 19 Jun 2020

👍1

@zeebo Crashes 7, 8, 9, and 10 don't reproduce in dev.go2go with the type checker. I haven't tried the translator.

griesemer on 19 Jun 2020

Hi @griesemer thanks for taking a look at these.

In case it is more convenient for you or otherwise helps, I put the fuzz-induced crashes from this issue into a set of test cases that exercise go/types, and which you can see here in the standard playground:

https://play.golang.org/p/rtBwSht8Urf

4 of the 14 crash in go1.14.4, while the other 10 pass in go1.14.4. Here are the current results from the standard playground:

go1.14.4

--- PASS: TestGoTypesGo2Go (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-1 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-2 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-3 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-4 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-5 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-6 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-12 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-13 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-14 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-15 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-16 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-17 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-18 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-19 (0.00s)
PASS

I haven't yet run them on the latest dev.go2go.

Also, running those in the standard Go Playground executes the tests. However, go2goplay.golang.org seems to have a bug or limitation such that it does not recognize and run those as tests (perhaps related to whatever the root cause might be for #39675).

thepudds on 19 Jun 2020

Hi @griesemer here is the state of crash/pass/skip in the latest commit on dev.go2go, using the fuzzing-originated unit tests I had placed in https://play.golang.org/p/rtBwSht8Urf (same playground link as immediately prior comment).

go version devel +6cf535a27b Fri Jun 19 04:37:09 2020 +0000 linux/amd64

dev.go2go (6cf535a27b Fri Jun 19 04:37:09 2020)

    --- PASS: TestGoTypesGo2Go/issue-39634-crash-1 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-2 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-3 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-4 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-5 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-6 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-12 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-13 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-14         # fatal error: stack overflow
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-15 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-16 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-17 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-18 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-19 (0.00s)

Progress!

Summary

The 5x FAIL tests are still crashing in latest dev.go2go
The 4x SKIP tests also crash in go1.14.4
The 5x that are now PASS in the latest commit might have been fixed by the changes for #39664, #39693, or #39672.
- (Those issues cover manually created examples from other gophers, and were reported after this issue. From quick skim of commit one-liners, I don't immediately see which one would fix Crash 17, but presumably it was a different manifestation of one of the other fixes, and in any event it's passing now).

edit: sorry, this comment was initially missing crash-14, which still fails with a stack overflow.

thepudds on 19 Jun 2020

Crash 14 is caused by
https://github.com/golang/go/blob/0a030888da0f33ef75111f079258ab78b1c3eb64/src/go/types/unify.go#L95
y is *types.Basic which have types.Invalid kind, so expand just returns y

and
https://github.com/golang/go/blob/0a030888da0f33ef75111f079258ab78b1c3eb64/src/go/types/unify.go#L150-L157
recursive call.

Change
https://github.com/golang/go/blob/0a030888da0f33ef75111f079258ab78b1c3eb64/src/go/types/unify.go#L94-L95
to

    x = expand(x)
    if basicX, ok := x.(*Basic); ok && basicX.Kind() == Invalid {
        return false
    }

    y = expand(y)
    if basicY, ok := y.(*Basic); ok && basicY.Kind() == Invalid {
        return false
    }

prevents endless recursion

tdakkota on 20 Jun 2020

👍2

That's great @tdakkota! Thanks for looking at that!

thepudds on 20 Jun 2020

@tdakkota Thanks for analyzing the problem. The correct fix (forthcoming) is a bit more subtle, though. Checking for the invalid type solves this specific case, but is insufficient in general. For instance, this test case will still recurse infinitely:

func F(type T)(func(T) T) { F(func(T) int {}) }

griesemer on 20 Jun 2020

Hi @griesemer, here is a third batch of fuzz-induced crashes (Crash 20 through Crash 27 for this issue).

For now, I am just posting the unit test form in this link to the standard playground:

https://play.golang.org/p/qXP94Ai_vQq

If you are looking at stack overflows, this new batch includes two new variations of stack overflows.

This new batch of Crashes 20-27 does not crash in Go 1.14.4. Here are the results from running these via 'go test' in the latest dev.go2go:

dev.go2go (0a030888da Sat Jun 20 04:46:40 2020)

    --- PASS: TestGoTypesGo2Go/issue-39634-crash-1 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-2 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-3 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-4 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-5 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-6 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-12 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-13 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-14         # fatal error: stack overflow
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-15 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-16 (0.00s)
    --- PASS: TestGoTypesGo2Go/issue-39634-crash-17 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-18 (0.00s)
    --- SKIP: TestGoTypesGo2Go/issue-39634-crash-19 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-20 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-21 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-22         # fatal error: stack overflow
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-23         # fatal error: stack overflow
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-24 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-25 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-26 (0.00s)
    --- FAIL: TestGoTypesGo2Go/issue-39634-crash-27 (0.00s)

edit: updated playground link with slightly cleaner version of unit tests. (Original link here).

thepudds on 21 Jun 2020

Hi @griesemer, here is the third batch of fuzz-induced crashes again, but now expanded out in markdown.

Crash 20 and Crash 21 might be duplicates at this point. (Previously, Crash 21 used to crash in go/types.(*Interface).Complete, but now it looks like both 20 and 21 crash in go/types.(*Checker).completeInterface). Also, Crash 24 and 25 might be duplicates of each other.

Finally, I am including go2go playground links here, but the reported behavior in this comment is for 0a030888da (and the go2go playground is older than that).

go version devel +0a030888da Sat Jun 20 04:46:40 2020 +0000 linux/amd64

Crash 20: invalid memory address or nil pointer dereference

go/types.(*Checker).completeInterface

package main
type Z interface{ Z }
func F(type t Z)() { F(t{}) }

https://go2goplay.golang.org/p/wAHpBNS7ZPn

Crash 21: invalid memory address or nil pointer dereference

go/types.(*Checker).completeInterface

package main
type Z interface{ Z }
func F(type *T Z)() { (F(Z)) }

https://go2goplay.golang.org/p/H64m4NteTx5

Crash 22: fatal error: stack overflow

go/types.(*instance).expand
(expand -> instantiate -> TypeParam -> Under -> Named -> expand -> ...)

package main
type T(type _ interface{ a() }) int
type A(type P) T(A(int))

https://go2goplay.golang.org/p/CoxvTTa5xP1

Crash 23: fatal error: stack overflow

go/types.Comparable
(Comparable -> Comparable -> Comparable -> ...)

package main
type T1(type P) struct{ f T2(P) }
type T2(type P) T1(int)
func _() {
    var x T1(int)
    x == x
}

https://go2goplay.golang.org/p/75sK6SAI2c6

Crash 24: panic: assertion failed

go/types.(*unifier).nify

package main
type C(type P) P
func (r C(P)) m() { y := C.m() }

https://go2goplay.golang.org/p/kWYVyRvSGDd

Crash 25: panic: assertion failed

go/types.(*unifier).nify

package main
type T1(type A) int
func (t T1(A)) m1() {}
var x T1.m1

https://go2goplay.golang.org/p/m5k0NKSMK26

Crash 26: panic: assertion failed

go/types.isParameterized

package main
type Y = interface{ F(type Z)() }
func F(type Z)() Y { F() }

https://go2goplay.golang.org/p/BWt_Xe6iwsE

Crash 27: panic: interface is incomplete

go/types.(*Interface).assertCompleteness

package main
func e(type T)() interface{ (x) }
func x() { e() }

https://go2goplay.golang.org/p/Uw5dQZz7Q7M

thepudds on 21 Jun 2020

griesemer on 21 Jun 2020

👍2

Change https://golang.org/cl/240901 mentions this issue: [dev.go2go] go/types: don't modify Named.underlying when checking validity

gopherbot on 4 Jul 2020

Change https://golang.org/cl/240902 mentions this issue: [dev.go2go] go/types: don't rely on completed interfaces in isParameterized predicate

gopherbot on 4 Jul 2020

Change https://golang.org/cl/240903 mentions this issue: [dev.go2go] go/types: make sure arrays, slices always have an element type

gopherbot on 4 Jul 2020

Change https://golang.org/cl/240904 mentions this issue: [dev.go2go] go/types: don't crash instantiating arrays/slices that are not fully set up

gopherbot on 4 Jul 2020

Change https://golang.org/cl/241037 mentions this issue: [dev.go2go] go/types: avoid endless recursion in self-recursive newty…

gopherbot on 5 Jul 2020

Change https://golang.org/cl/241122 mentions this issue: [dev.go2go] go/types: don't crash instantiating defined types that are not fully set up

gopherbot on 7 Jul 2020

Change https://golang.org/cl/241123 mentions this issue: [dev.go2go] go/types: add test for crash 15 from issue 39634

gopherbot on 7 Jul 2020

Change https://golang.org/cl/245737 mentions this issue: [dev.go2go] go/types: don't crash in lookup of incomplete interface

gopherbot on 30 Jul 2020

Change https://golang.org/cl/245738 mentions this issue: [dev.go2go] go/types: don't crash in assignment due to prior errors

gopherbot on 30 Jul 2020

Change https://golang.org/cl/245739 mentions this issue: [dev.go2go] go/types: generic types in selector expressions must be instantiated

gopherbot on 30 Jul 2020

Change https://golang.org/cl/245740 mentions this issue: [dev.go2go] go/types: remove incorrect assert and replace with explanatory comment

gopherbot on 30 Jul 2020

Change https://golang.org/cl/245742 mentions this issue: [dev.go2go] go/types: add testcase for crash 9 of #39634

gopherbot on 30 Jul 2020

Was this page helpful?

0 / 5 - 0 ratings

Related issues

x/net/webdav: fails on broken links

enoodle · 3Comments

Proposal: supporting “symlinks” in GOPATH

myitcv · 3Comments

x/net/proxy: Non-SOCKS ALL_PROXY results in proxy: unknown scheme: http

bbodenmiller · 3Comments

proposal: sync: Map.Delete method should return bool, indicating if key was deleted or not

lkarlslund · 3Comments

cannot find package "golang.org/x/sys/unix"

jayhuang75 · 3Comments

Go: cmd/go2go: fuzzing triggers various crashes in type checker

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

Does this issue reproduce with the latest release?

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

What did you do?

Crash 1: invalid memory address or nil pointer dereference

Crash 2: invalid memory address or nil pointer dereference

Crash 3: invalid memory address or nil pointer dereference

Crash 4: invalid memory address or nil pointer dereference

Crash 5: panic: multiplication of zero with infinity

Crash 6: panic: assertion failed

Most helpful comment

All 28 comments

Crash 7: panic: assertion failed

Crash 8: fatal error: stack overflow

Crash 9: internal compiler error: typecheck DCLFIELD

Crash 10: looping while expanding type

Crash 12: panic: unreachable

Crash 13: panic: internal error: final action list grew

Crash 14: fatal error: stack overflow

Crash 15: panic: assertion failed

Crash 16: panic: assertion failed

Crash 17: panic: duplicate method c

Crash 18: panic: nil typ

Crash 19: panic: assertion failed

go1.14.4

dev.go2go (6cf535a27b Fri Jun 19 04:37:09 2020)

Summary

dev.go2go (0a030888da Sat Jun 20 04:46:40 2020)

Crash 20: invalid memory address or nil pointer dereference

Crash 21: invalid memory address or nil pointer dereference

Crash 22: fatal error: stack overflow

Crash 23: fatal error: stack overflow

Crash 24: panic: assertion failed

Crash 25: panic: assertion failed

Crash 26: panic: assertion failed

Crash 27: panic: interface is incomplete

Related issues

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

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