Do not assume signed integer overflow behavior

[gpshead]

BPO	1621
Nosy	@loewis, @jcea, @mdickinson, @pitrou, @vstinner, @avassalotti, @matejcik, @jwilk, @alex, @davidmalcolm, @vadmium, @serhiy-storchaka, @ztane, @zhangyangyu, @sir-sigurd, @miss-islington
PRs	bpo-1621: Avoid signed integer overflow in set_table_resize(). #9059 [3.7] bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) #9198 [3.6] bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) #9199 bpo-34656: Avoid relying on signed overflow in _pickle memos. #9261 bpo-34656: Avoid relying on signed overflow in _pickle memos. #9261
Dependencies	bpo-13312: test_time fails: strftime('%Y', y) for negative year bpo-27473: bytes_concat seems to check overflow using undefined behaviour bpo-29145: failing overflow checks in replace_*
Files	config.patch overflow-error.patch overflow-error2.patch overflow-error3.patch: Fix whitespace change and comment. overflow-error4.patch: Fix -fwrapv check, thanks tiran fix-overflows-try1.patch fix-overflows-try2.patch: Better patch fix-overflows-try3.patch fix-overflows-final.patch csv.patch issue1621_hashes_and_sets.patch trapv.patch: Committed & superseded set-overflow.patch: Superseded slice-step.patch: => python/issues-test-cpython#36946; supersedes trapv.patch tuple_and_list.patch thread.patch: => Issue 33632 array-size.patch: Superseded tuple_and_list_v2.patch ctypes_v2.patch: Supersedes array-size.patch unicode.patch: Committed tuple_and_list_v3.patch: Committed overflow_fix_in_listextend.patch: Superseded

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2018-10-19.22:55:35.437>
created_at = <Date 2007-12-14.00:43:47.318>
labels = ['type-security', '3.7', '3.8']
title = 'Do not assume signed integer overflow behavior'
updated_at = <Date 2018-10-19.22:55:35.436>
user = 'https://github.com/gpshead'

bugs.python.org fields:

activity = <Date 2018-10-19.22:55:35.436>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2018-10-19.22:55:35.437>
closer = 'vstinner'
components = []
creation = <Date 2007-12-14.00:43:47.318>
creator = 'gregory.p.smith'
dependencies = ['13312', '27473', '29145']
files = ['8950', '9205', '9207', '9209', '9210', '9211', '9238', '9239', '9242', '9307', '23237', '43728', '43729', '43785', '43827', '43838', '43839', '43842', '43855', '43856', '43862', '43956']
hgrepos = []
issue_num = 1621
keywords = ['patch']
message_count = 128.0
messages = ['58602', '58609', '58610', '58611', '58617', '58620', '58684', '58711', '59611', '59612', '59616', '59619', '59692', '59693', '59694', '59696', '59699', '60078', '60079', '60102', '60103', '60105', '60107', '60109', '60110', '60111', '60114', '60115', '60116', '60118', '60120', '60121', '60124', '60125', '60126', '60146', '60246', '60254', '60260', '61272', '61286', '61291', '61319', '61320', '61757', '61758', '61759', '61760', '61761', '61762', '61763', '61765', '61766', '61767', '61768', '61770', '61774', '61784', '61785', '61788', '61791', '61792', '62616', '87689', '87690', '87693', '87694', '87704', '87707', '87708', '87712', '87730', '87731', '87908', '141871', '144490', '144492', '144499', '144501', '144503', '144505', '144524', '147958', '213729', '270084', '270460', '270461', '270463', '270562', '270580', '270582', '270807', '270809', '270823', '270827', '270869', '270977', '271057', '271058', '271084', '271118', '271136', '271143', '271144', '271150', '271223', '271735', '271759', '271763', '271766', '271768', '271769', '271800', '271803', '272077', '272078', '285466', '303330', '317087', '325091', '325105', '325109', '325113', '325128', '325284', '328068', '328069', '328070']
nosy_count = 22.0
nosy_names = ['loewis', 'nnorwitz', 'jcea', 'mark.dickinson', 'pitrou', 'vstinner', 'alexandre.vassalotti', 'donmez', 'matejcik', 'jwilk', 'alex', 'dmalcolm', 'python-dev', 'deadshort', 'martin.panter', 'serhiy.storchaka', 'ztane', 'fweimer', 'Jeffrey.Walton', 'xiang.zhang', 'sir-sigurd', 'miss-islington']
pr_nums = ['9059', '9198', '9199', '9261', '9261']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'security'
url = 'https://bugs.python.org/issue1621'
versions = ['Python 3.6', 'Python 3.7', 'Python 3.8']

[gpshead]

The resolution to http://bugs.python.org/issue1608 looks like it'll add
a -fwrapv gcc flag when building python. This works around the issue
nicely on one compiler (gcc) but doesn't fix our fundamentally broken code.

We should fix all dependencies on integer overflow behavior, starting by
making everything compile properly with gcc's -Wstrict-overflow and
-Werror flags.

[tiran]

My gcc 4.1 doesn't have the -Wstrict-overflow option.

gcc-Version 4.1.3 2007092 (prerelease) (Ubuntu 4.1.2-16ubuntu2)

[tiran]

Should we use -ansi (C90 aka C89 standard) option, too? Python core
compiles fine with -ansi but together with -Werror it breaks several
extensions:

_bsddb _codecs_iso2022 _ctypes
_socket _ssl linuxaudiodev

[tiran]

Socket and SSL are using bluetooth.h which defines some functionas as
inline. Inline isn't part of C89. Linuxaudiodev depends on the 'linux'
macro which is not defined in C89.

The Python core can be compiled with -ansi but the extension modules
require -std=gnu89.

[loewis]

Using ansi is out of scope of this issue, and should not be mixed with
it. -ansi is about disabling certain GCC extensions. This report is
about C code in Python which has undefined behavior.

I think there is disagreement on whether Python should stop relying on
this particular undefined behavior (namely, whether the sum of two large
positive numbers is negative). GvR (apparently) believes that the
compiler should guarantee that the twos-complement semantic is available
throughout the C language.

[malemburg]

Whatever you change regarding the compiler options for Python, please
make sure that this doesn't effect the default settings used by
distutils to compile external modules (it normally takes the options
straight from the Makefile used for compiling Python).

Otherwise, you're likely going to break lots and lots of extensions. Thanks.

[avassalotti]

I compiled Python using gcc 4.3.0 with the -Wstrict-overflow, and that's
the only warning I got:

Objects/doubledigits.c: In function ‘_PyFloat_Digits’:
Objects/doubledigits.c:313: error: assuming signed overflow does not
occur when assuming that (X + c) < X is always false

I am sure yet how to interpret it, though. It says that the overflow
check is in _PyFloat_Digits(), line 313 is in the function add_big(). It
probably means that add_big() gets inlined. I tried to set
-finline-limit=0, but strangely the overflow warning disappears...

I will try to investigate this further, when I will have a bit more time
in my hands.

[gpshead]

heh if thats the only warning gcc -Wstrict-overflow gives then I've
mistitled the bug. Fixed. It'll take some manual code review.

Anyone know if the commercial analysis tools we've run the code base
through in the past can find these for us?

[gvanrossum]

Alexandre, which Python version did you compile with -Wstrict-overflow?
It would behoove us to check 2.5.2 thoroughly before it goes out the door.

I will contact Coverity to ask if they check for this kind of thing.
(They just upgraded us to "Rung 2", whatever that may mean. :-)

MvL: I don't want 2s complement throughout the language, I just want the
overflow checks to be reliable. Since I'd forgotten about the
difference between unsigned and signed overflow, I have no idea how many
overflow checks have been submitted that are relying on signed overflow;
though apparently (if the -Wstrict-overflow results can be trusted)
we're okay.

FWIW, I've heard that some commercial compilers (e.g. XLC) assume that
even *unsigned* overflow is undefined, violating the C standard. This
would suggest that buffer overflow checks should be coded without
relying on arithmetic overflow at all. This is possible, just a bit hairy.

[gvanrossum]

Marc-Andre: what do you mean by breaking lots and lots of extensions?
Extensions also contain buffer overflow checks (at least I hope they do
:-) and those should also be guaranteed safe by using -fwrapv or
-fno-strict-overflow (GCC 4.2 and higher) until we're sure there aren't any.

[donmez]

-Wstrict-overflow=3 with gcc 4.3 trunk here shows :

Modules/cPickle.c: In function 'Unpickler_noload':
Modules/cPickle.c:4232: warning: assuming signed overflow does not occur
when assuming that (X - c) > X is always false

Modules/cPickle.c:194: warning: assuming signed overflow does not occur
when assuming that (X - c) > X is always false
Modules/cPickle.c: In function 'load':
Modules/cPickle.c:4232: warning: assuming signed overflow does not occur
when assuming that (X - c) > X is always false

But also note that -fno-strict-aliasing is also just another workaround
and its more serious than -fwrapv.

[loewis]

But also note that -fno-strict-aliasing is also just another workaround
and its more serious than -fwrapv.

Sure - however, that is fixed in Python 3 (and unrelated to this issue)

[avassalotti]

Hm. I don't get any warning, related to the overflow issue, neither with
-Wstrict-overflow=3, nor -Wstrict-overflow=5. Are the cPickle warnings
already fixed?