#31585 closed defect (fixed)

Wrong result due to integer overflow (in pynac?)

Reported by: Dave Morris Owned by:
Priority: critical Milestone: sage-9.4
Component: symbolics Keywords: integer overflow, pynac
Cc: Merged in:
Authors: Dave Morris, Matthias Koeppe Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: eba0a9c (Commits, GitHub, GitLab) Commit: eba0a9cc1cca15a9c39d84e7aaac1c762de3591f
Dependencies: #31694 Stopgaps:

Status badges

Description

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.

Change History (39)

comment:1 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Moving to 9.4, as 9.3 has been released.

comment:2 Changed 16 months ago by Dave Morris

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

comment:3 Changed 16 months ago by Dave Morris

Authors: Dave Morris

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.

comment:4 Changed 16 months ago by Dave Morris

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

comment:5 Changed 16 months ago by Dave Morris

Here is a crash that is caused by the overflow when -2^32 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.

Version 0, edited 16 months ago by Dave Morris (next)

comment:6 Changed 16 months ago by Dave Morris

Branch: public/31585

comment:7 Changed 16 months ago by Dave Morris

Commit: fdde3d9b4a16e51f22181744036920124811a1ef
Status: newneeds_review

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:

f1a99fatrac 31585 pynac overflow patch
3fcf072add doctests
fdde3d9update pynac patch level

comment:8 Changed 16 months ago by Dave Morris

I think this pynac patch also fixes #25688.

comment:9 Changed 16 months ago by Travis Scrimshaw

Status: needs_reviewneeds_work

Merge conflict

comment:10 Changed 16 months ago by Dave Morris

Branch: public/31585public/31585r1

comment:11 Changed 16 months ago by Dave Morris

Commit: fdde3d9b4a16e51f22181744036920124811a1ef5a340ce206534e0a48d48edeb48197906fb9812a

Rebased on 9.4b3.


New commits:

ecb99c8trac 31585 pynac overflow patch
2d04fa4add doctests
5a340ceupdate pynac patch level

comment:12 Changed 16 months ago by Matthias Köppe

PR to pynac please

comment:13 Changed 16 months ago by Dave Morris

Status: needs_workneeds_review

Yes, I will try.

comment:14 Changed 16 months ago by git

Commit: 5a340ce206534e0a48d48edeb48197906fb9812a627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf

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

627ec10also fix /=

comment:15 Changed 16 months ago by Dave Morris

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.

comment:16 Changed 16 months ago by Dima Pasechnik

Has this been tested on 32-bit?

comment:17 Changed 16 months ago by Dave Morris

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.)

comment:18 Changed 16 months ago by Dima Pasechnik

Dependencies: #31694
Status: needs_reviewneeds_work

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

comment:19 Changed 16 months ago by Dima Pasechnik

Branch: public/31585r1u/dimpase/31585r1
Commit: 627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf45e9cbc93028e702601260efc5aaa0d5d78cbb7a

New commits:

e97c1b5update pynac to 0.7.28
3c131f7wip tarball
d6fc516add doctests - cf #31585
45e9cbcupdate pynac patch level

comment:20 Changed 16 months ago by git

Commit: 45e9cbc93028e702601260efc5aaa0d5d78cbb7ad6fc516223e03ddb7b180808a6e89eb31220103e

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

comment:21 Changed 16 months ago by git

Commit: d6fc516223e03ddb7b180808a6e89eb31220103e35a2ebca29431658c43a30a571b0253e64a81d31

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

45e9cbcupdate pynac patch level
35a2ebcRevert "update pynac patch level"

comment:22 Changed 16 months ago by git

Commit: 35a2ebca29431658c43a30a571b0253e64a81d31a08180896163a8d6b3234419735e4f077b098a17

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

11c80aaupdated tarball with PRs 377 and 378
a081808Merge branch 'u/dimpase/packages/pynac/0.7.28' of trac.sagemath.org:sage into u/dimpase/31585r1

comment:23 Changed 16 months ago by Dima Pasechnik

Reviewers: Dima Pasechnik
Status: needs_workneeds_review

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

comment:24 Changed 16 months ago by Dima Pasechnik

Status: needs_reviewpositive_review

comment:25 Changed 16 months ago by Dima Pasechnik

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

comment:26 Changed 16 months ago by Matthias Köppe

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

comment:27 Changed 16 months ago by Matthias Köppe

Status: positive_reviewneeds_work

comment:28 Changed 16 months ago by git

Commit: a08180896163a8d6b3234419735e4f077b098a175d89a50796cd9a72834efc013cf1a474d758a154

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

5d89a50trying pynac PR 379

comment:30 Changed 16 months ago by git

Commit: 5d89a50796cd9a72834efc013cf1a474d758a1543c75f53afed0e0397cafcf42a5bbba0f15741c0d

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

3c75f53correct patch suffix

comment:31 Changed 16 months ago by Dima Pasechnik

comment:32 Changed 15 months ago by Matthias Köppe

Branch: u/dimpase/31585r1u/mkoeppe/31585r1

comment:33 Changed 15 months ago by Matthias Köppe

Commit: 3c75f53afed0e0397cafcf42a5bbba0f15741c0da8e82dd38d98ef846b07cdf97775726239b5c788
Status: needs_workneeds_review

New commits:

c9c50e3build/pkgs/pynac: Upgrade to 0.7.29
f1d83c3Merge #31694
a8e82ddadd doctests - cf #31585

comment:34 Changed 15 months ago by git

Commit: a8e82dd38d98ef846b07cdf97775726239b5c788eba0a9cc1cca15a9c39d84e7aaac1c762de3591f

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

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

comment:35 Changed 15 months ago by Matthias Köppe

Authors: Dave MorrisDave Morris, Matthias Koeppe

comment:37 Changed 15 months ago by Dima Pasechnik

Status: needs_reviewpositive_review

lgtm

comment:38 Changed 15 months ago by Matthias Köppe

Thanks!

comment:39 Changed 15 months ago by Volker Braun

Branch: u/mkoeppe/31585r1eba0a9cc1cca15a9c39d84e7aaac1c762de3591f
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.