Opened 17 months ago
Closed 13 months ago
#31585 closed defect (fixed)
Wrong result due to integer overflow (in pynac?)
Reported by:  ghDaveWitteMorris  Owned by:  

Priority:  critical  Milestone:  sage9.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: 
Description
Volker Braun pointed out in ticket:31479#comment:12 that sage gives the following wrong answer on a 32bit machine after the bugfix 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 64bit machine.
Change History (39)
comment:1 Changed 15 months ago by
 Milestone changed from sage9.3 to sage9.4
comment:2 Changed 14 months ago by
I reproduced the bug by installing sage in a 32bit 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 14 months ago by
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 14 months ago by
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 14 months ago by
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.
comment:6 Changed 14 months ago by
 Branch set to public/31585
comment:7 Changed 14 months ago by
 Commit set to fdde3d9b4a16e51f22181744036920124811a1ef
 Status changed from new to needs_review
The pynac bugs on this ticket do not currently affect 64bit sage. (This is because pynac does not store 2^63
as a long integer
, even though it could fit into that space on a 64bit machine.) However, they will affect 64bit machines after the branch on #31986 is merged. (See the explanation and examples there.) Hence, a 64bit 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

comment:8 Changed 14 months ago by
I think this pynac patch also fixes #25688.
comment:10 Changed 14 months ago by
 Branch changed from public/31585 to public/31585r1
comment:11 Changed 14 months ago by
 Commit changed from fdde3d9b4a16e51f22181744036920124811a1ef to 5a340ce206534e0a48d48edeb48197906fb9812a
comment:12 Changed 14 months ago by
PR to pynac please
comment:14 Changed 14 months ago by
 Commit changed from 5a340ce206534e0a48d48edeb48197906fb9812a to 627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf
Branch pushed to git repo; I updated commit sha1. New commits:
627ec10  also fix /=

comment:15 Changed 14 months ago by
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 14 months ago by
Has this been tested on 32bit?
comment:17 Changed 14 months ago by
The original patch seemed to be fine, but I haven't tested the final commit yet. I hope to run doctests on my 32bit debian virtual machine tomorrow. (I had trouble updating to 9.4b3, so I did make distclean
and it is still building.)
comment:18 Changed 14 months ago by
 Dependencies set to #31694
 Status changed from needs_review to needs_work
OK, it should be made on top of #31694, anyway, no rush. I'll test and update.
comment:19 Changed 14 months ago by
 Branch changed from public/31585r1 to u/dimpase/31585r1
 Commit changed from 627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf to 45e9cbc93028e702601260efc5aaa0d5d78cbb7a
comment:20 Changed 14 months ago by
 Commit changed from 45e9cbc93028e702601260efc5aaa0d5d78cbb7a to d6fc516223e03ddb7b180808a6e89eb31220103e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:21 Changed 14 months ago by
 Commit changed from d6fc516223e03ddb7b180808a6e89eb31220103e to 35a2ebca29431658c43a30a571b0253e64a81d31
comment:22 Changed 14 months ago by
 Commit changed from 35a2ebca29431658c43a30a571b0253e64a81d31 to a08180896163a8d6b3234419735e4f077b098a17
comment:23 Changed 14 months ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_work to needs_review
OK, all should be ready now for one last look.
comment:24 Changed 14 months ago by
 Status changed from needs_review to positive_review
comment:25 Changed 14 months ago by
running GH Actions tests on this https://github.com/sagemath/sagetracmirror/actions/runs/978774922 (basically to test #31694)
comment:26 Changed 14 months ago by
PR with standardconforming code at https://github.com/pynac/pynac/pull/379
comment:27 Changed 14 months ago by
 Status changed from positive_review to needs_work
comment:28 Changed 14 months ago by
 Commit changed from a08180896163a8d6b3234419735e4f077b098a17 to 5d89a50796cd9a72834efc013cf1a474d758a154
Branch pushed to git repo; I updated commit sha1. New commits:
5d89a50  trying pynac PR 379

comment:29 Changed 14 months ago by
comment:30 Changed 14 months ago by
 Commit changed from 5d89a50796cd9a72834efc013cf1a474d758a154 to 3c75f53afed0e0397cafcf42a5bbba0f15741c0d
Branch pushed to git repo; I updated commit sha1. New commits:
3c75f53  correct patch suffix

comment:31 Changed 14 months ago by
update  https://github.com/sagemath/sagetracmirror/actions/runs/982441436
New commits:
3c75f53  correct patch suffix

comment:32 Changed 14 months ago by
 Branch changed from u/dimpase/31585r1 to u/mkoeppe/31585r1
comment:33 Changed 14 months ago by
 Commit changed from 3c75f53afed0e0397cafcf42a5bbba0f15741c0d to a8e82dd38d98ef846b07cdf97775726239b5c788
 Status changed from needs_work to needs_review
comment:34 Changed 14 months ago by
 Commit changed from a8e82dd38d98ef846b07cdf97775726239b5c788 to eba0a9cc1cca15a9c39d84e7aaac1c762de3591f
Branch pushed to git repo; I updated commit sha1. New commits:
eba0a9c  build/bin/writedockerfile.sh: Disable the gfan testsuite (does not terminate on 32bit)

comment:35 Changed 14 months ago by
comment:36 Changed 14 months ago by
comment:38 Changed 13 months ago by
Thanks!
comment:39 Changed 13 months ago by
 Branch changed from u/mkoeppe/31585r1 to eba0a9cc1cca15a9c39d84e7aaac1c762de3591f
 Resolution set to fixed
 Status changed from positive_review to closed
Moving to 9.4, as 9.3 has been released.