math/big: panic in big.ParseFloat (off by one access) #37499
Comments
|
Thanks for reporting this issue. This is a Go1.14 regression, introduced by CL 172018 (math/big: implement recursive algorithm for division). |
ALTree
changed the title
ALTree
added
the
NeedsInvestigation
|
@gopherbot please open a backport issue for 1.14 for this regression |
|
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. |
|
@ALTree Thanks for tracing this back to that change. @remyoudompheng do you have time to investigate this? |
|
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. |
|
The problem appears to be in a core routine, 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
|
|
I am going to look at this by tomorrow. |
|
Hi @remyoudompheng, I just wanted to follow up and ask, are you still planning to look into this? Thank you. |
|
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 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. |
|
@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 |
|
Change https://golang.org/cl/221980 mentions this issue: |
|
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). |
|
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! |
|
Hi @remyoudompheng and @griesemer Have you been integrating some fuzz testing for |
|
@catenacyber There isn't any around ParseFloat. Happy to review a CL. |
|
Ok. Could you point me to the right place ? |
What version of Go are you using (
go version)?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 envOutputWhat did you do?
I ran the following program
https://play.golang.org/p/rNIIVshF9_2
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
The text was updated successfully, but these errors were encountered: