cmd/compile: missing bounds checks in 1.11 #27289

leitzler · 2018-08-27T21:51:26Z

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

The text was updated successfully, but these errors were encountered:

mariecurried · 2018-08-27T22:13:06Z

Duplicate of #27251?

leitzler · 2018-08-27T22:57:59Z

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 · 2018-08-27T23:35:56Z

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 · 2018-08-28T09:46:32Z

Bisected it down to e0d37a3:

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

rasky · 2018-08-28T18:17:46Z

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

ghost · 2018-08-28T21:08:42Z

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 · 2018-08-30T21:58:03Z

@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 · 2018-08-30T21:58:13Z

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 · 2018-08-30T23:15:01Z

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 · 2018-08-31T00:21:23Z

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

randall77 · 2018-08-31T00:25:33Z

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 · 2018-08-31T00:28:49Z

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

rasky · 2018-08-31T00:29:19Z

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

rasky · 2018-08-31T00:36:07Z

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 · 2018-08-31T00:39:24Z

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.

josharian changed the title ~~Bounds check broken in 1.11?~~ cmd/compile: missing bounds checks in 1.11 Aug 28, 2018

josharian added this to the Go1.11.1 milestone Aug 28, 2018

josharian assigned ALTree Aug 28, 2018

josharian added the release-blocker label Aug 28, 2018

FiloSottile modified the milestones: Go1.11.1, Go1.12 Aug 30, 2018

gopherbot mentioned this issue Aug 30, 2018

cmd/compile: missing bounds checks in 1.11 [1.11 backport] #27390

Closed

gopherbot closed this as completed in 09ea3c0 Aug 31, 2018

alexanderbez mentioned this issue Nov 5, 2018

[WIP] Update to TM v0.26.0 - Part II cosmos/cosmos-sdk#2681

Merged

5 tasks

mvdan mentioned this issue Jan 9, 2019

slice: negative indexing doesn't panics #29629

Closed

golang locked and limited conversation to collaborators Aug 31, 2019

gopherbot added the FrozenDueToAge label Aug 31, 2019

rsc unassigned ALTree Jun 23, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: missing bounds checks in 1.11 #27289

cmd/compile: missing bounds checks in 1.11 #27289

leitzler commented Aug 27, 2018

mariecurried commented Aug 27, 2018

leitzler commented Aug 27, 2018

as commented Aug 27, 2018

theckman commented Aug 28, 2018

rasky commented Aug 28, 2018

ghost commented Aug 28, 2018

FiloSottile commented Aug 30, 2018

gopherbot commented Aug 30, 2018

randall77 commented Aug 30, 2018

gopherbot commented Aug 31, 2018

randall77 commented Aug 31, 2018

gopherbot commented Aug 31, 2018

rasky commented Aug 31, 2018

rasky commented Aug 31, 2018

rasky commented Aug 31, 2018

cmd/compile: missing bounds checks in 1.11 #27289

cmd/compile: missing bounds checks in 1.11 #27289

Comments

leitzler commented Aug 27, 2018

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?

What did you expect to see?

What did you see instead?

mariecurried commented Aug 27, 2018

leitzler commented Aug 27, 2018

as commented Aug 27, 2018

theckman commented Aug 28, 2018

rasky commented Aug 28, 2018

ghost commented Aug 28, 2018

FiloSottile commented Aug 30, 2018

gopherbot commented Aug 30, 2018

randall77 commented Aug 30, 2018

gopherbot commented Aug 31, 2018

randall77 commented Aug 31, 2018

gopherbot commented Aug 31, 2018

rasky commented Aug 31, 2018

rasky commented Aug 31, 2018

rasky commented Aug 31, 2018

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

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