Wrong result due to integer overflow (in pynac?)

[gh-DaveWitteMorris]

Volker Braun pointed out in ticket:31479#comment:12 that sage gives the following wrong answer on a 32-bit machine after the bug-fix patch of #31479 is applied:

sage: a,b,c,d = var("a b c d")
sage: ((a + b + c)^30 * (3*b + d - 5/d)^3).expand().subs(a=0,b=2,c=-1)
d^3 + 18*d^2 + 1739461754973*d - 8697308774865/d + 450/d^2 - 125/d^3 + 36

This answer is congruent modulo 2^32 to d^3 + 18*d^2 + 93*d - 465/d + 450/d^2 - 125/d^3 + 36, which is the correct answer, so it seems clear that the problem comes from an integer overflow error. Perhaps the overflow error can also be produced on a 64-bit machine.

[mkoeppe]

Moving to 9.4, as 9.3 has been released.

[gh-DaveWitteMorris]

I reproduced the bug by installing sage in a 32-bit debian virtual machine, and found a much simpler example of the overflow:

sage: (2*x).subs(x=-2^31)
0

More generally:

sage: for n in range(10):
....:     print(n, (n*x).subs(x=-2^31)/2^31)
0 0
1 -1
2 0
3 -1
4 0
5 -1
6 0
7 -1
8 0
9 -1

[gh-DaveWitteMorris]

I think the problem is an incorrect calculation of absolute value:

sage: abs(x).subs(x=-2^31)
-2147483648

To decide whether a multiplication might cause an overflow, pynac compares the absolute values of the factors to a certain bound. In the example of comment:2, the absolute value of a factor is negative, so it is less than the bound, even though the factor is actually very large.

And I think the incorrect absolute value comes from the C++ std::labs function. The documentation of that function says "If the result cannot be represented as a long int (such as labs(LONG_MIN) in an implementation with two's complement signed values), it causes undefined behavior."

I should be able to write a pynac patch soon that tests my theory. Even if it isn't the bug we are looking for, this bug in the absolute value needs to be fixed.

[gh-DaveWitteMorris]

The same problem comes up in pynac's numeric::negative method, so that will need to be fixed too:

sage: (-x).subs(x=-2^31)
-2147483648

[gh-DaveWitteMorris]

Here is a crash that is caused by the overflow when -2^31 is divided by -1:

sage: (1 - 2^31*x)*x
    <snip>
Unhandled SIGFPE: An unhandled floating point exception occurred. ...

Patches to fix all of these should be coming soon.

[gh-DaveWitteMorris]

The pynac bugs on this ticket do not currently affect 64-bit sage. (This is because pynac does not store -2^63 as a long integer, even though it could fit into that space on a 64-bit machine.) However, they will affect 64-bit machines after the branch on #31986 is merged. (See the explanation and examples there.) Hence, a 64-bit user can test the PR of this ticket by first merging the branch of #31986 (and executing sage -f pynac), and replacing -2^31 with -2^63, as in the examples in the description of #31986.

Followup tickets: #31984 and #31986.

I will try to post this (and my other pynac patches) to the pynac github repository soon. My previous attempts failed because I know almost nothing about git, but now I understand that I need a fork, instead of a clone, so I hope to be successful.

---

New commits:

​f1a99fa	trac 31585 pynac overflow patch
​3fcf072	add doctests
​fdde3d9	update pynac patch level

[gh-DaveWitteMorris]

I think this pynac patch also fixes #25688.

[tscrim]

Merge conflict

[gh-DaveWitteMorris]

Rebased on 9.4b3.

---

New commits:

​ecb99c8	trac 31585 pynac overflow patch
​2d04fa4	add doctests
​5a340ce	update pynac patch level

[mkoeppe]

PR to pynac please

[gh-DaveWitteMorris]

Yes, I will try.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​627ec10

also fix /=

[gh-DaveWitteMorris]

I previously neglected to fix the /= operator, which can also overflow.

I created ​pynac PR #378. It's my first PR to anywhere other than the trac server, so please let me know if I goofed anything up.

[dimpase]

Has this been tested on 32-bit?

[gh-DaveWitteMorris]

The original patch seemed to be fine, but I haven't tested the final commit yet. I hope to run doctests on my 32-bit debian virtual machine tomorrow. (I had trouble updating to 9.4b3, so I did make distclean and it is still building.)

[dimpase]

OK, it should be made on top of #31694, anyway, no rush. I'll test and update.

[dimpase]

New commits:

​e97c1b5	update pynac to 0.7.28
​3c131f7	wip tarball
​d6fc516	add doctests - cf #31585
​45e9cbc	update pynac patch level

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​45e9cbc	update pynac patch level
​35a2ebc	Revert "update pynac patch level"

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​11c80aa	updated tarball with PRs 377 and 378
​a081808	Merge branch 'u/dimpase/packages/pynac/0.7.28' of trac.sagemath.org:sage into u/dimpase/31585r1

[dimpase]

OK, all should be ready now for one last look.

[dimpase]

running GH Actions tests on this ​https://github.com/sagemath/sagetrac-mirror/actions/runs/978774922 (basically to test #31694)

[mkoeppe]

PR with standard-conforming code at ​https://github.com/pynac/pynac/pull/379

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5d89a50

trying pynac PR 379

[dimpase]

tests at ​https://github.com/sagemath/sagetrac-mirror/actions/runs/982168057

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3c75f53

correct patch suffix

[dimpase]

update - ​https://github.com/sagemath/sagetrac-mirror/actions/runs/982441436

---

New commits:

​3c75f53

correct patch suffix

[mkoeppe]

New commits:

​c9c50e3	build/pkgs/pynac: Upgrade to 0.7.29
​f1d83c3	Merge #31694
​a8e82dd	add doctests - cf #31585

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​eba0a9c

build/bin/write-dockerfile.sh: Disable the gfan testsuite (does not terminate on 32bit)

[dimpase]

tests run on ​https://github.com/sagemath/sagetrac-mirror/actions/runs/986545913

[dimpase]

lgtm

[mkoeppe]

Thanks!