cmd/compile: missing bounds checks in 1.11

[leitzler]

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

go version go1.11 linux/amd64

Does this issue reproduce with the latest release?

Yes

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

GOARCH="amd64"
GOBIN=""
GOCACHE="/home/pontus/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/pontus/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build210363627=/tmp/go-build -gno-record-gcc-switches"

What did you do?

I've narrowed it down to this code: https://play.golang.org/p/3543rqBvJ74

package main

import (
	"fmt"
)

type S struct {
}

type X []S

func (x *X) Pop() S {
	out := (*x)[len(*x)-1]
	*x = (*x)[:len(*x)-1]
	return out
}

func main() {
	mx := X{S{}}
	fmt.Printf("Pre: %v, len: %v\n", mx, len(mx))
	mx.Pop()
	fmt.Printf("Mid: %v, len: %v\n", mx, len(mx))
	mx.Pop()
	fmt.Printf("Post: %v, len: %v\n", mx, len(mx))
}

What did you expect to see?

The playground output:

Pre: [{}], len: 1
Mid: [], len: 0
panic: runtime error: index out of range

That's what go version 1.10 darwin/amd64 outputs too.

What did you see instead?

Pre: [{}], len: 1
Mid: [], len: 0
Post: [], len: -1

[mariecurried]

Duplicate of #27251?

[leitzler]

Yeah, might be so.

Obviously can't handle copy well afterwards. Adding it leads to segmentation faults:

    z := make([]S, 10)                                                                                                                                         
    copy(z, mx)

Outputs:

unexpected fault address 0xbfffffffe1
fatal error: fault
[signal SIGSEGV: segmentation violation code=0x1 addr=0xbfffffffe1 pc=0x451ea9]

goroutine 1 [running]:
runtime.throw(0x4b6134, 0x5)
	/usr/local/go/src/runtime/panic.go:608 +0x72 fp=0xc000090d50 sp=0xc000090d20 pc=0x426e52
runtime.sigpanic()
	/usr/local/go/src/runtime/signal_unix.go:397 +0x275 fp=0xc000090da0 sp=0xc000090d50 pc=0x439d35
runtime: unexpected return pc for runtime.memmove called from 0x3d544145535f4744
stack: frame={sp:0xc000090da0, fp:0xc000090da8} stack=[0xc000090000,0xc000091000)
000000c000090ca0:  0000000000427a43 <runtime.gwrite+275>  00000000004b5e77 
000000c000090cb0:  0000000000000001  0000000000000001 
000000c000090cc0:  000000c000090d34  000000000000000c 
000000c000090cd0:  000000c000090d20  00000000004281d8 <runtime.printstring+120> 
000000c000090ce0:  0000000000427017 <runtime.fatalthrow+87>  000000c000090cf0 
000000c000090cf0:  000000000044d610 <runtime.fatalthrow.func1+0>  000000c000000300 
000000c000090d00:  0000000000426e52 <runtime.throw+114>  000000c000090d20 
000000c000090d10:  000000c000090d40  0000000000426e52 <runtime.throw+114> 
000000c000090d20:  000000c000090d28  000000000044d590 <runtime.throw.func1+0> 
000000c000090d30:  00000000004b6134  0000000000000005 
000000c000090d40:  000000c000090d90  0000000000439d35 <runtime.sigpanic+629> 
000000c000090d50:  00000000004b6134  0000000000000005 
000000c000090d60:  69622f3d4c4c4548  5500687361622f6e 
000000c000090d70:  000000bfffffffe1  000000c000000300 
000000c000090d80:  766e3d524f544944  4c00000000006d69 
000000c000090d90:  000000c000090f88  0000000000451ea9 <runtime.memmove+1609> 
000000c000090da0: <3d544145535f4744 >5300003074616573 
000000c000090db0:  0100323d4c564c48  4c00000003000000 
000000c000090dc0:  703d454d414e474f  4400007375746e6f 
000000c000090dd0:  3a3d59414c505349  0100000000302e30 
000000c000090de0:  0000000000000000  0000000000000001 
000000c000090df0:  fffffffffffffffe  000000000054e620 
000000c000090e00:  0000000000000000  000000c0000120bf 
000000c000090e10:  fffffffffffffffe  0000000000000001 
000000c000090e20:  000000c0000120bf  fffffffffffffffe 
000000c000090e30:  0000000000000001  000000c0000120bf 
000000c000090e40:  fffffffffffffffe  0000000000000001 
000000c000090e50:  000000c0000120bf  ffffffffffffffff 
000000c000090e60:  0000000000000001  000000c0000120bf 
000000c000090e70:  0000000000000000  0000000000000001 
000000c000090e80:  000000c0000120bf  0000000000000001 
000000c000090e90:  0000000000000001  000000000049c0c0 
000000c000090ea0:  000000c00000a0e0 
runtime.memmove(0x5300003074616573, 0x100323d4c564c48, 0x4c00000003000000)
	/usr/local/go/src/runtime/memmove_amd64.s:500 +0x649 fp=0xc000090da8 sp=0xc000090da0 pc=0x451ea9
exit status 2

[as]

It seems that this can be used to corrupt arbitrary memory.

Output:

start: a/b/c 0 [0/0]0xc000077f50 0
end1 <---- outputs a '\0' here
a 0xc000077f58
b 0xc000077f70
c 0xc000077f50
end: a/b/c 8101815670912281193 [-49/0]0xc000077f81 7523094288207667809

Program:

package main
import "fmt"

func pop(x *[]byte) interface{}{
	out := (*x)[len(*x)-1]
	*x = (*x)[:len(*x)-1]
	return out
}

func main() {
	a := 0
	b := []byte{}
	c := 0
	
	println("start: a/b/c", a,b,c)
	
	for i := 0; i < 0x31; i++{
		pop(&b)
		b[i] = 'a'+byte(i)
	}
	// can print individual char
	fmt.Printf("end1 %c\n", b[5])
	
	println("a", &a)
	println("b", &b)
	println("c", &c)
	b[len(b)-1] = 'x'
	
	println("end: a/b/c", a,b,c)
}

[theckman]

Bisected it down to e0d37a3:

• cmd/compile: function compiled without bounds checking and -1 index access #27251 (comment)

[rasky]

There's a probably an off-by-one somewhere... I need to look at it but I'm off this week.

[ghost]

https://play.golang.org/p/Ooi-BHysN21

Most of a test case for the above issue, if this helps anyone. Needs some cleanup still.

[FiloSottile]

@gopherbot please file this for backport against 1.11. This is a regression.

@ALTree please make a cherry-pick CL once your change is merged in master.

[gopherbot]

Backport issue(s) opened: #27390 (for 1.11).

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

[randall77]

Here's a simple repro:

package main
//go:noinline
func f(a []int) {
	_ = a[len(a)-1]
}
func main() {
	f(nil)
}

This should panic, but it doesn't.

Definitely an error in prove. At some point we derive the following fact, in the bounds-check-failed direction of the branch:

len(a) -1 U>= len(a)

That is, the index is unsigned >= the length of the array (i.e. negative, or too big). This is correct.

Then the fence-post logic kicks in. If x-1 >= y, then x > y, right?

len(a) U> len(a)

That's a contradiction, a value can't be greater than itself. Prove then assumes that the bounds-check-failed direction is unreachable. Hence the bug.

Here's the relevant fencepost logic:

		if x, delta := isConstDelta(v); x != nil && delta == -1 {
			// x-1 >= w && x > min  ⇒  x > w
			//
			// Useful for i > 0; s[i-1].
			lim, ok := ft.limits[x.ID]
			if ok && lim.min > opMin[v.Op] {
				ft.update(parent, x, w, d, gt)
			}

This is all seems reasonable with signed logic. But the bug is that (A) lim.min is 0, and (B) that opMin[v.Op] is -1<<63, the signed minimum for that op.

I think we need signed/unsigned versions of this fencepost logic.

[gopherbot]

Change https://golang.org/cl/132476 mentions this issue: cmd/compile: fix fencepost logic in prove pass

[randall77]

Mailed a CL. I don't think Giovanni's CL is to blame, really. His CL just adds some facts like len(a)>=0 that triggered a latent bug.
I don't know yet if that latent bug is independently triggerable. If it is it might warrant a 1.10 patch.

[gopherbot]

Change https://golang.org/cl/132495 mentions this issue: cmd/compile: fix fence-post implications for unsigned domain.

[rasky]

Eheh we did the same analysis at the same time and mailed an identical CL 👍 🥇

[rasky]

I agree the bug is latent. I'm not sure it can be triggered in 1.10 because the prove pass is simpler there, but it doesn't sound too risky to backport anyway just in case.

[rasky]

Actually, the fence-post implications were introduced by Austin in CL87480 which was early in the Go 1.11 cycle, so no 1.10 backport is required.