# Wrong result due to integer overflow (in pynac?)

Reported by: Owned by: Dave Morris critical sage-9.4 symbolics integer overflow, pynac Dave Morris, Matthias Koeppe Dima Pasechnik N/A eba0a9c eba0a9cc1cca15a9c39d84e7aaac1c762de3591f #31694

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

### comment:1 Changed 19 months ago by Matthias Köppe

Milestone: sage-9.3 → sage-9.4

Moving to 9.4, as 9.3 has been released.

### comment:2 Changed 18 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 18 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 18 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 18 months ago by Dave Morris

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.

Last edited 18 months ago by Dave Morris (previous) (diff)

### comment:6 Changed 18 months ago by Dave Morris

Branch: → public/31585

### comment:7 Changed 18 months ago by Dave Morris

Commit: → fdde3d9b4a16e51f22181744036920124811a1ef new → needs_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:

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

### comment:8 Changed 18 months ago by Dave Morris

I think this pynac patch also fixes #25688.

### comment:9 Changed 18 months ago by Travis Scrimshaw

Status: needs_review → needs_work

Merge conflict

### comment:10 Changed 18 months ago by Dave Morris

Branch: public/31585 → public/31585r1

### comment:11 Changed 18 months ago by Dave Morris

Commit: fdde3d9b4a16e51f22181744036920124811a1ef → 5a340ce206534e0a48d48edeb48197906fb9812a

Rebased on 9.4b3.

New commits:

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

### comment:13 Changed 18 months ago by Dave Morris

Status: needs_work → needs_review

Yes, I will try.

### comment:14 Changed 18 months ago by git

Commit: 5a340ce206534e0a48d48edeb48197906fb9812a → 627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf

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

 ​627ec10 `also fix /=`

### comment:15 Changed 18 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 18 months ago by Dima Pasechnik

Has this been tested on 32-bit?

### comment:17 Changed 18 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 18 months ago by Dima Pasechnik

Dependencies: → #31694 needs_review → needs_work

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

### comment:19 Changed 18 months ago by Dima Pasechnik

Branch: public/31585r1 → u/dimpase/31585r1 627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf → 45e9cbc93028e702601260efc5aaa0d5d78cbb7a

New commits:

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

### comment:20 Changed 18 months ago by git

Commit: 45e9cbc93028e702601260efc5aaa0d5d78cbb7a → d6fc516223e03ddb7b180808a6e89eb31220103e

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

### comment:21 Changed 18 months ago by git

Commit: d6fc516223e03ddb7b180808a6e89eb31220103e → 35a2ebca29431658c43a30a571b0253e64a81d31

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

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

### comment:22 Changed 18 months ago by git

Commit: 35a2ebca29431658c43a30a571b0253e64a81d31 → a08180896163a8d6b3234419735e4f077b098a17

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`

### comment:23 Changed 18 months ago by Dima Pasechnik

Reviewers: → Dima Pasechnik needs_work → needs_review

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

### comment:24 Changed 18 months ago by Dima Pasechnik

Status: needs_review → positive_review

### comment:25 Changed 18 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 17 months ago by Matthias Köppe

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

### comment:27 Changed 17 months ago by Matthias Köppe

Status: positive_review → needs_work

### comment:28 Changed 17 months ago by git

Commit: a08180896163a8d6b3234419735e4f077b098a17 → 5d89a50796cd9a72834efc013cf1a474d758a154

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

 ​5d89a50 `trying pynac PR 379`

### comment:30 Changed 17 months ago by git

Commit: 5d89a50796cd9a72834efc013cf1a474d758a154 → 3c75f53afed0e0397cafcf42a5bbba0f15741c0d

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

 ​3c75f53 `correct patch suffix`

### comment:31 Changed 17 months ago by Dima Pasechnik

New commits:

 ​3c75f53 `correct patch suffix`

### comment:32 Changed 17 months ago by Matthias Köppe

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

### comment:33 Changed 17 months ago by Matthias Köppe

Commit: 3c75f53afed0e0397cafcf42a5bbba0f15741c0d → a8e82dd38d98ef846b07cdf97775726239b5c788 needs_work → needs_review

New commits:

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

### comment:34 Changed 17 months ago by git

Commit: a8e82dd38d98ef846b07cdf97775726239b5c788 → eba0a9cc1cca15a9c39d84e7aaac1c762de3591f

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

### comment:35 Changed 17 months ago by Matthias Köppe

Authors: Dave Morris → Dave Morris, Matthias Koeppe

### comment:37 Changed 17 months ago by Dima Pasechnik

Status: needs_review → positive_review

lgtm

Thanks!

### comment:39 Changed 17 months ago by Volker Braun

Branch: u/mkoeppe/31585r1 → eba0a9cc1cca15a9c39d84e7aaac1c762de3591f → fixed positive_review → closed
Note: See TracTickets for help on using tickets.