Opened 19 months ago
Closed 15 months ago
#31585 closed defect (fixed)
Wrong result due to integer overflow (in pynac?)
Reported by:  Dave Morris  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 17 months ago by
Milestone:  sage9.3 → sage9.4 

comment:2 Changed 16 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 16 months ago by
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
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
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.
comment:6 Changed 16 months ago by
Branch:  → public/31585 

comment:7 Changed 16 months ago by
Commit:  → fdde3d9b4a16e51f22181744036920124811a1ef 

Status:  new → 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:10 Changed 16 months ago by
Branch:  public/31585 → public/31585r1 

comment:11 Changed 16 months ago by
Commit:  fdde3d9b4a16e51f22181744036920124811a1ef → 5a340ce206534e0a48d48edeb48197906fb9812a 

comment:14 Changed 16 months ago by
Commit:  5a340ce206534e0a48d48edeb48197906fb9812a → 627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf 

Branch pushed to git repo; I updated commit sha1. New commits:
627ec10  also fix /=

comment:15 Changed 16 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:17 Changed 16 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 16 months ago by
Dependencies:  → #31694 

Status:  needs_review → needs_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
Branch:  public/31585r1 → u/dimpase/31585r1 

Commit:  627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf → 45e9cbc93028e702601260efc5aaa0d5d78cbb7a 
comment:20 Changed 16 months ago by
Commit:  45e9cbc93028e702601260efc5aaa0d5d78cbb7a → d6fc516223e03ddb7b180808a6e89eb31220103e 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:21 Changed 16 months ago by
Commit:  d6fc516223e03ddb7b180808a6e89eb31220103e → 35a2ebca29431658c43a30a571b0253e64a81d31 

comment:22 Changed 16 months ago by
Commit:  35a2ebca29431658c43a30a571b0253e64a81d31 → a08180896163a8d6b3234419735e4f077b098a17 

comment:23 Changed 16 months ago by
Reviewers:  → Dima Pasechnik 

Status:  needs_work → needs_review 
OK, all should be ready now for one last look.
comment:24 Changed 16 months ago by
Status:  needs_review → positive_review 

comment:25 Changed 16 months ago by
running GH Actions tests on this https://github.com/sagemath/sagetracmirror/actions/runs/978774922 (basically to test #31694)
comment:26 Changed 16 months ago by
PR with standardconforming code at https://github.com/pynac/pynac/pull/379
comment:27 Changed 16 months ago by
Status:  positive_review → needs_work 

comment:28 Changed 16 months ago by
Commit:  a08180896163a8d6b3234419735e4f077b098a17 → 5d89a50796cd9a72834efc013cf1a474d758a154 

Branch pushed to git repo; I updated commit sha1. New commits:
5d89a50  trying pynac PR 379

comment:29 Changed 16 months ago by
comment:30 Changed 16 months ago by
Commit:  5d89a50796cd9a72834efc013cf1a474d758a154 → 3c75f53afed0e0397cafcf42a5bbba0f15741c0d 

Branch pushed to git repo; I updated commit sha1. New commits:
3c75f53  correct patch suffix

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

comment:32 Changed 15 months ago by
Branch:  u/dimpase/31585r1 → u/mkoeppe/31585r1 

comment:33 Changed 15 months ago by
Commit:  3c75f53afed0e0397cafcf42a5bbba0f15741c0d → a8e82dd38d98ef846b07cdf97775726239b5c788 

Status:  needs_work → needs_review 
comment:34 Changed 15 months ago by
Commit:  a8e82dd38d98ef846b07cdf97775726239b5c788 → 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 15 months ago by
Authors:  Dave Morris → Dave Morris, Matthias Koeppe 

comment:36 Changed 15 months ago by
comment:39 Changed 15 months ago by
Branch:  u/mkoeppe/31585r1 → eba0a9cc1cca15a9c39d84e7aaac1c762de3591f 

Resolution:  → fixed 
Status:  positive_review → closed 
Moving to 9.4, as 9.3 has been released.