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

math/big: panic in big.ParseFloat (off by one access) #37499

Closed
catenacyber opened this issue Feb 27, 2020 · 16 comments
Closed

math/big: panic in big.ParseFloat (off by one access) #37499

catenacyber opened this issue Feb 27, 2020 · 16 comments

Comments

@catenacyber
Copy link

@catenacyber catenacyber commented Feb 27, 2020

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

$ go version
go version go1.14 linux/amd64

Does this issue reproduce with the latest release?

Yes but this is rgression, does not reproduce with go1.13.8 darwin/amd64

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

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/root/.cache/go-build"
GOENV="/root/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/root/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/root/.go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/root/.go/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
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 -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build640944533=/tmp/go-build -gno-record-gcc-switches"
uname -sr: Linux 4.19.76-linuxkit
/lib/x86_64-linux-gnu/libc.so.6: GNU C Library (Ubuntu GLIBC 2.23-0ubuntu11) stable release version 2.23, by Roland McGrath et al.

What did you do?

I ran the following program

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

import (
	"fmt"
	"math/big"
)

func main() {
	str := "000000000000000010200000000000000.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
	prec := 64
	if len(str) > prec {
		prec = len(str)
	}
	val, _, err := big.ParseFloat(str, 10, uint(prec), big.ToZero)
	fmt.Printf("Hello, playground %#+v %#+v", val, err)
}

This input was found by fuzzing project jsoniter with oss-fuzz
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=20885

What did you expect to see?

No crash and output `Hello, playground +1.01999999999999999999999999999999999999999999999999999999

What did you see instead?

A panic

panic: runtime error: index out of range [101] with length 101

goroutine 1 [running]:
math/big.nat.divBasic(0xc000098a80, 0x64, 0x68, 0xc0000c8570, 0x65, 0x9c, 0xc0000b5688, 0x33, 0xff)
	/root/.go/src/math/big/nat.go:790 +0x4ee
math/big.nat.divRecursiveStep(0xc000098a80, 0x64, 0x68, 0xc0000c8570, 0x65, 0x9c, 0xc0000b5688, 0x33, 0xff, 0x1, ...)
	/root/.go/src/math/big/nat.go:840 +0x12c2
math/big.nat.divRecursiveStep(0xc0000b4a80, 0xe2, 0x146, 0xc0000c8000, 0x145, 0x14a, 0xc0000b5500, 0x64, 0x130, 0x0, ...)
	/root/.go/src/math/big/nat.go:880 +0x796
math/big.nat.divRecursive(0xc0000b4a80, 0xe2, 0x146, 0xc0000c8000, 0x146, 0x14a, 0xc0000b5500, 0x64, 0x130)
	/root/.go/src/math/big/nat.go:821 +0x17e
math/big.nat.divLarge(0xc0000b4a80, 0x145, 0x146, 0x0, 0x0, 0x0, 0xc0000b4a80, 0x145, 0x146, 0xc0000c2000, ...)
	/root/.go/src/math/big/nat.go:727 +0x3fd
math/big.nat.div(0xc0000b4a80, 0x145, 0x146, 0x0, 0x0, 0x0, 0xc0000b4a80, 0x145, 0x146, 0xc0000c2000, ...)
	/root/.go/src/math/big/nat.go:672 +0x401
math/big.(*Float).uquo(0xc0000621b0, 0xc0000621b0, 0xc000049de8)
	/root/.go/src/math/big/float.go:1358 +0xd5
math/big.(*Float).Quo(0xc0000621b0, 0xc0000621b0, 0xc00006cde8, 0x15)
	/root/.go/src/math/big/float.go:1638 +0xbf
math/big.(*Float).scan(0xc0000621b0, 0x4f97a0, 0xc00000c060, 0xa, 0x590800, 0x7f348642f108, 0x0, 0x1)
	/root/.go/src/math/big/floatconv.go:143 +0x2f0
math/big.(*Float).Parse(0xc0000621b0, 0x4e13c6, 0x1881, 0xa, 0x4008000000000000, 0xc000062180, 0xc00006cf18, 0x4a83c5)
	/root/.go/src/math/big/floatconv.go:273 +0x1a5
math/big.ParseFloat(0x4e13c6, 0x1881, 0xa, 0x1881, 0x57ac02, 0xc000038778, 0xc00006cf78, 0x40514f, 0xc0000260b8)
	/root/.go/src/math/big/floatconv.go:290 +0x81
main.main()
	/src/fuzz/lol.go:14 +0x51
exit status 2
@ALTree
Copy link
Member

@ALTree ALTree commented Feb 27, 2020

Thanks for reporting this issue.

This is a Go1.14 regression, introduced by CL 172018 (math/big: implement recursive algorithm for division).

cc @remyoudompheng @griesemer

@ALTree ALTree changed the title math/big panic in big.ParseFloat (off by one access) math/big: panic in big.ParseFloat (off by one access) Feb 27, 2020
@josharian
Copy link
Contributor

@josharian josharian commented Feb 27, 2020

@gopherbot please open a backport issue for 1.14 for this regression

@gopherbot
Copy link

@gopherbot gopherbot commented Feb 27, 2020

Backport issue(s) opened: #37501 (for 1.14).

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

@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 27, 2020

@ALTree Thanks for tracing this back to that change. @remyoudompheng do you have time to investigate this?

@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 27, 2020

Simpler test case:

func TestIssue37499(t *testing.T) {
	suf := strings.Repeat("0", 6239)
	str := "000000000000000010200000000000000." + suf
	new(Float).SetPrec(uint(len(str))).Parse(str, 10)
}

The crash disappears when making the suffix length 6240, for instance.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 28, 2020

The problem appears to be in a core routine, nat.DivBasic which appears to reach a condition that either should be guarded, or proven impossible. Here's a direct reproducer:

func TestNatDivBasic(*testing.T) {
	q := nat(nil).make(100)

	u := nat{14490654640773241866, 7065197599461811079, 7516684300872319938, 7379216531294388226, 12771029045863066370,
		8975487170083438770, 7165072256320728079, 2601429980372890614, 18385787249427020765, 15828865051783345557,
		9883336313099095959, 12203072022673974595, 3963519753570217012, 177243852244329268, 17816556994691333393,
		3045517996983920072, 15958128191619010169, 10290173851492443279, 4547374208497465023, 1153646534899737092,
		1210388270310927302, 1047323611282148691, 2381751733694643843, 4855296174091037478, 4593795963138322298,
		5396921972895960124, 8572450977963831952, 6572969522216674544, 2169580901076537179, 4652505697916682125,
		17298027769638931890, 5194520684962244482, 13712128979948456315, 18110115740839543059, 3414951711160481730,
		16964485098191909330, 9886024196137002588, 9532283778568107488, 1846554764089203863, 17505776765341502310,
		4996428143794937900, 7380506425303515742, 2102202321626968291, 1129837110936040444, 5997626561691999309,
		16805678657818760396, 2524024548970206615, 5305844873178713507, 17345502219029422766, 5331474233761248979,
		18282005732093962642, 9372176757649710139, 10528568350966376841, 8976264200820042725, 4845799911113378813,
		13118684035910186702, 10212357475009134040, 16880766828100761376, 3602513476330573299, 12421862126599083156,
		5880456379248228485, 1774046941253126834, 3393285727457174636, 15932441988847549098, 9335162877897778944,
		5047062635209493368, 1298067965522736412, 8511058734766370487, 10653865153117811300, 11896598306059356030,
		6180840617358449599, 6098150642835645650, 11471785745445111895, 15596084255689567220, 17493604840640164198,
		1151147688527017147, 7148668983233916088, 12622835459134736477, 4850632131081604735, 1774214624199500511,
		1757967809004048260, 7138472231023261229, 14370327474278631359, 4444816253935546190, 7340438302715887488,
		5643147409475331507, 10434433293465005555, 16673771629836642995, 820982733284852697, 5007011867549854570,
		5911852719620853370, 8846838606678364000, 3844601242973869896, 12843557813054760817, 4594451732169411236,
		16376284702921012097, 13094865702141265827, 4177168489727452539, 7329502793467785323, 6638869193213356561,
		13128937800410202751}

	v := nat{16634495349221963796, 10590091195427551759, 10528568350966376841, 8976264200820042725, 4845799911113378813,
		13118684035910186702, 10212357475009134040, 16880766828100761376, 3602513476330573299, 12421862126599083156,
		5880456379248228485, 1774046941253126834, 3393285727457174636, 15932441988847549098, 9335162877897778944,
		5047062635209493368, 1298067965522736412, 8511058734766370487, 10653865153117811300, 11896598306059356030,
		6180840617358449599, 6098150642835645650, 11471785745445111895, 15596084255689567220, 17493604840640164198,
		1151147688527017147, 7148668983233916088, 12622835459134736477, 4850632131081604735, 1774214624199500511,
		1757967809004048260, 7138472231023261229, 14370327474278631359, 4444816253935546190, 7340438302715887488,
		5643147409475331507, 10434433293465005555, 16673771629836642995, 820982733284852697, 5007011867549854570,
		5911852719620853370, 8846838606678364000, 3844601242973869896, 12843557813054760817, 4594451732169411236,
		16376284702921012097, 13094865702141265827, 4177168489727452539, 7329502793467785323, 6638869193213356561,
		13128937800410202751}

	if len(q) < len(u)-len(v) {
		panic("divBasic precondition violated")
	}
	q.divBasic(u, v)
}

The changes in divBasic appear to have violated some assumptions: On lines 788ff.

		if c != 0 {
			c := addVV(u[j:j+n], u[j:], v)
			u[j+n] += c
			qhat--
		}

c != 0 for j+n == len(u) in the (first) iteration, which presumably shouldn't be possible.

@remyoudompheng ?

@remyoudompheng
Copy link
Contributor

@remyoudompheng remyoudompheng commented Feb 28, 2020

I am going to look at this by tomorrow.

@dmitshur
Copy link
Member

@dmitshur dmitshur commented Mar 3, 2020

Hi @remyoudompheng, I just wanted to follow up and ask, are you still planning to look into this? Thank you.

@remyoudompheng
Copy link
Contributor

@remyoudompheng remyoudompheng commented Mar 4, 2020

I understand @griesemer comment now, indeed, the precondition of divBasic is not violated here (but it's incorrectly documented: the true precondition is "q is large enough to hold the quotient of u / v") and is properly ensured here.

The change introduced in divBasic, was to remove the assumption that u always had an extra word at the top. But I didn't expect that the code would require it. It happens every time the 1st word quotient is inaccurate on the first loop iteration, which happens when the top words are very close to each other. The example given by @griesemer can be minified further like this :

func TestNatDivBasic(t *testing.T) {                              
      q := nat(nil).make(4)                                       
                                                                  
      u := nat{16376284702921012097, 13094865702141265827,        
            4177168489727452539, 7329502793467785323,             
            6638869193213356561, 3128937800410202751}             
      v := nat{7329502793467785324,                               
            6638869193213356561, 3128937800410202751}             
      q.divBasic(u, v)                                            
      t.Logf("%v", q)                                             
}

The D3 of divBasic computes an approximate first word by looking at the first word, but it may still be off by one. In step D4

            c := subVV(u[j:j+qhl], u[j:], qhatv)
            if c != 0 {
                  c := addVV(u[j:j+n], u[j:], v)
                  u[j+n] += c
                  qhat--
            }

in case we are off-by-one, subVV will create a "negative" number, to be offset by re-adding v. So it is normal to have a carry here, the subtlely is that the second c should offset the first c, and thus not be added to u[j+n] (in the previous code, u[j+n] would be -1). It was not an issue in the previous code because qhatv was always larger than v.

I believe the appropriate patch is this one:

diff --git a/src/math/big/nat.go b/src/math/big/nat.go
index 1b771ca7c6..aab49a1416 100644
--- a/src/math/big/nat.go
+++ b/src/math/big/nat.go
@@ -740,7 +740,8 @@ func (z nat) divLarge(u, uIn, vIn nat) (q, r nat) {
 // The remainder overwrites input u.
 //
 // Precondition:
-// - len(q) >= len(u)-len(v)
+// - q is large enough to hold the quotient u / v
+//   which has length len(u)-len(v) or len(u)-len(v)+1
 func (q nat) divBasic(u, v nat) {
        n := len(v)
        m := len(u) - n
@@ -779,6 +780,8 @@ func (q nat) divBasic(u, v nat) {
                }
 
                // D4.
+               // Compute the remainder u - W^j q̂ v,
+               // the substraction may overflow if q̂ estimate was off by one.
                qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0)
                qhl := len(qhatv)
                if j+qhl > len(u) && qhatv[n] == 0 {
@@ -787,7 +790,11 @@ func (q nat) divBasic(u, v nat) {
                c := subVV(u[j:j+qhl], u[j:], qhatv)
                if c != 0 {
                        c := addVV(u[j:j+n], u[j:], v)
-                       u[j+n] += c
+                       if n < qhl {
+                               // If n == qhl, the previous carry was ignored
+                               // and offsets this one.
+                               u[j+n] += c
+                       }
                        qhat--
                }
 

i will format it as a proper review later today.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Mar 4, 2020

@remyoudompheng Thanks for the analysis. Please assign the CL to me for review when you're done, together with a test (your minified version seems good - call it TestIssue37499).

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 5, 2020

Change https://golang.org/cl/221980 mentions this issue: math/big: correct off-by-one access in divBasic

@remyoudompheng
Copy link
Contributor

@remyoudompheng remyoudompheng commented Mar 5, 2020

I switched to strings for the test case so that a single test case can be used for 32-bit and 64-bit platforms (the stringified version also fails with GOARCH=386 and go1.14).

@dmitshur
Copy link
Member

@dmitshur dmitshur commented Mar 10, 2020

Thanks for working on this @remyoudompheng. There have been new code review comments posted on CL 221980, I wanted to ask if you had a chance to see them. Thanks again!

@gopherbot gopherbot closed this in ac1fd41 Apr 8, 2020
@catenacyber
Copy link
Author

@catenacyber catenacyber commented Apr 10, 2020

Hi @remyoudompheng and @griesemer

Have you been integrating some fuzz testing for big.ParseFloat into your continuous integration process ?

@griesemer
Copy link
Contributor

@griesemer griesemer commented Apr 13, 2020

@catenacyber There isn't any around ParseFloat. Happy to review a CL.

@catenacyber
Copy link
Author

@catenacyber catenacyber commented Apr 16, 2020

Ok. Could you point me to the right place ?
Should I make a PR to https://github.com/dvyukov/go-fuzz-corpus/ ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
8 participants
You can’t perform that action at this time.