Wrong result due to integer overflow (in pynac?)

Reported by: Owned by: gh-DaveWitteMorris 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 15 months ago by mkoeppe

• Milestone changed from sage-9.3 to sage-9.4

Moving to 9.4, as 9.3 has been released.

comment:2 Changed 14 months ago by 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
```

comment:3 Changed 14 months ago by gh-DaveWitteMorris

• Authors set to 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 14 months ago by 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
```

comment:5 Changed 14 months ago by 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.

Last edited 14 months ago by gh-DaveWitteMorris (previous) (diff)

comment:6 Changed 14 months ago by gh-DaveWitteMorris

• Branch set to public/31585

comment:7 Changed 14 months ago by gh-DaveWitteMorris

• Commit set to fdde3d9b4a16e51f22181744036920124811a1ef
• Status changed from new to 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 14 months ago by gh-DaveWitteMorris

I think this pynac patch also fixes #25688.

comment:9 Changed 14 months ago by tscrim

• Status changed from needs_review to needs_work

Merge conflict

comment:10 Changed 14 months ago by gh-DaveWitteMorris

• Branch changed from public/31585 to public/31585r1

comment:11 Changed 14 months ago by gh-DaveWitteMorris

• Commit changed from fdde3d9b4a16e51f22181744036920124811a1ef to 5a340ce206534e0a48d48edeb48197906fb9812a

Rebased on 9.4b3.

New commits:

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

comment:12 Changed 14 months ago by mkoeppe

PR to pynac please

comment:13 Changed 14 months ago by gh-DaveWitteMorris

• Status changed from needs_work to needs_review

Yes, I will try.

comment:14 Changed 14 months ago by git

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

comment:16 Changed 14 months ago by dimpase

Has this been tested on 32-bit?

comment:17 Changed 14 months ago by 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.)

comment:18 Changed 14 months ago by dimpase

• 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 dimpase

• Branch changed from public/31585r1 to u/dimpase/31585r1
• Commit changed from 627ec10f92cf4150e4718541cfa5d9a2a2c5eeaf to 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 14 months ago by git

• 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 git

• Commit changed from d6fc516223e03ddb7b180808a6e89eb31220103e to 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 14 months ago by git

• Commit changed from 35a2ebca29431658c43a30a571b0253e64a81d31 to 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 14 months ago by dimpase

• 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 dimpase

• Status changed from needs_review to positive_review

comment:25 Changed 14 months ago by dimpase

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

comment:26 Changed 14 months ago by mkoeppe

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

comment:27 Changed 14 months ago by mkoeppe

• Status changed from positive_review to needs_work

comment:28 Changed 14 months ago by git

• Commit changed from a08180896163a8d6b3234419735e4f077b098a17 to 5d89a50796cd9a72834efc013cf1a474d758a154

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

 ​5d89a50 `trying pynac PR 379`

comment:30 Changed 14 months ago by git

• 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 dimpase

New commits:

 ​3c75f53 `correct patch suffix`

comment:32 Changed 14 months ago by mkoeppe

• Branch changed from u/dimpase/31585r1 to u/mkoeppe/31585r1

comment:33 Changed 14 months ago by mkoeppe

• Commit changed from 3c75f53afed0e0397cafcf42a5bbba0f15741c0d to a8e82dd38d98ef846b07cdf97775726239b5c788
• Status changed from needs_work to needs_review

New commits:

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

comment:34 Changed 14 months ago by git

• Commit changed from a8e82dd38d98ef846b07cdf97775726239b5c788 to 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 14 months ago by mkoeppe

• Authors changed from Dave Morris to Dave Morris, Matthias Koeppe

comment:37 Changed 14 months ago by dimpase

• Status changed from needs_review to positive_review

lgtm

Thanks!

comment:39 Changed 13 months ago by vbraun

• Branch changed from u/mkoeppe/31585r1 to eba0a9cc1cca15a9c39d84e7aaac1c762de3591f
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.