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	python/cpython#9059 python/cpython#9198 python/cpython#9199 python/cpython#9261 python/cpython#9261
Dependencies	bpo-13312: test_time fails: strftime('%Y', y) for negative year bpo-27473: bytesconcat 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: ```python assignee = None closed_at = created_at = labels = ['type-security', '3.7', '3.8'] title = 'Do not assume signed integer overflow behavior' updated_at = user = 'https://github.com/gpshead' ``` bugs.python.org fields: ```python activity = actor = 'vstinner' assignee = 'none' closed = True closed_date = closer = 'vstinner' components = [] creation = 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'] ```

[gvanrossum]

Don't create new bug reports!

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

Neal,

I'll try to answer your questions one by one, first with _csv.c compiler issues :

Modules/_csv.c:969: warning: assuming signed overflow does not occur when simplifying conditional to constant

There is a check inside loop like this:

           if (c == '\0')
                   break;

Instead of this if we do the check in the for :

+ for (i = 0; i \< strlen(field) ; i++) {

and remove the if check compiler no longer issues a warning also csv test passes with this. Attached patch implements this optimization.

Guido, you don't have to shout, you know noone pays me per python bugreport I create :)

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

_sre.c case is the most interesting one , compiler says :

./Modules/_sre.c:1002: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1069: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1086: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1143: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1185: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1214: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1238: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1251: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1277: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1291: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1308: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1395: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1408: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c: In function 'sre_umatch': ./Modules/_sre.c:1002: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1069: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1086: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1143: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1185: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1214: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1238: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1251: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1277: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1291: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1308: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1395: warning: assuming signed overflow does not occur when simplifying conditional to constant ./Modules/_sre.c:1408: warning: assuming signed overflow does not occur when simplifying conditional to constant

all lines refer to : RETURN_ON_ERROR(ret);

My investigation :

On line 1002 we got RETURN_ON_ERROR(ret); but ret is already 0 and not set to anything this if will always be false.

Same for line 1069, ret is still zero there. Maybe I am missing something here?

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

For xmlparse.c compiler says :

Modules/expat/xmlparse.c:5337: warning: assuming signed overflow does not occur when simplifying conditional to constant

Its impossible for j to overflow here due to name[i] check but I am not sure what gcc is optimizing here.

[gvanrossum]

for (i = 0; i \< strlen(field) ; i++) {

This looks inefficient. Why not

 for (i = 0; field[i] != '\0'; i++) {

???

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

Hah strlen in a loop, a nice beginner mistake but its 5.30 AM here so please excuse me, Guido your version of course is way better. But with that version compiler issues

Modules/_csv.c:969: warning: assuming signed overflow does not occur when simplifying conditional to constant

again, strlen() just fooled that optimization it seems. So there should be another way to optimize this loop.

[61337411-43fc-4a9c-b8d5-4060aede66d0]

With Neal, I don't see what the warning in _csv is about. What condition is being turned into a constant? Is the compiler perhaps rearranging the code so as to insert "if (field[0] == '\0') goto XXX;" in front of the for-loop where XXX jumps into the middle of the condition in the if-statement immediately following the for-loop, and skipping that if-block when breaking of the loop later?

Indeed that's what happens. In the case of breaking the loop later, the compiler can skip the if-block only if signed ints never overflow, hence the warning.

Another way of silencing the warning is to test field[0]=='\0' in the if-statement. This might also somewhat pessimize the code, but allows the compiler to eliminate i altogether.

[gvanrossum]

I wonder if it would help making i a Py_ssize_t instead of an int?

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

Neal,

You could btw check http://repo.or.cz/w/pytest.git?a=shortlog;h=overflow-fix which have each fix seperate so that reviewing is easy. Just ignore configure changes thats for later.

Thanks, ismail

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

Guido van Rossum added the comment:

I wonder if it would help making i a Py_ssize_t instead of an int?

gcc still issues the same warning with that.

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

gcc is optimizing the second if check , for specifically i == 0 seems to redundant according to gcc.

        if (i == 0 && quote_empty) {
                if (dialect->quoting == QUOTE_NONE) {
                        PyErr_Format(error_obj,
                                     "single empty field record must be
quoted");
                        return -1;
                }
                else
                        *quoted = 1;
        }

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

Moving the empty check before the loop will fix this and possibly optimize empty string handling.

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

Any news on this? Also gcc 4.3 & gcc 4.2.3 fixed the -Wall clobbering - Wstrict-overflow problem, which is good news.

[mdickinson]

A few comments:

(1) I agree that signed overflows should be avoided where possible.

(2) I think some of the changes in the latest patch (fix-overflows-final.patch) are unnecessary, and decrease readability a bit. An example is the following chunk for the x_divrem function in Objects/longobject.c.

@@ -1799,7 +1799,7 @@ x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
    k = size_v - size_w;
    a = _PyLong_New(k + 1);

-   for (j = size_v; a != NULL && k >= 0; --j, --k) {
+   for (j = size_v; a != NULL && k >= 0; j = (unsigned)j - 1 , k = (unsigned)k - 1) {
        digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
        twodigits q;
        stwodigits carry = 0;

In this case it's easy to see from the code that j and k will always be nonnegative, so replacing --j with j = (unsigned)j - 1 is unnecessary. (This chunk no longer applies for 2.7 and 3.1, btw, since x_divrem got rewritten recently.) Similar comments apply to the change:

• min_gallop -= min_gallop > 1; + if (min_gallop > 1) min_gallop = (unsigned)min_gallop - 1;

in Objects/listobject.c. Here it's even clearer that the cast is unnecessary.

I assume these changes were made to silence warnings from -Wstrict-overflow, but I don't think that should be a goal: I'd suggest only making changes where there's a genuine possibility of overflow (even if it's a remote one), and leaving the code unchanged if it's reasonably easy to see that overflow is impossible.

(3) unicode_hash also needs fixing, as do the lookup algorithms for set and dict. Both use overflowing arithmetic on signed types as a matter of course. Probably a good few of the hash algorithms for the various object types in Objects/ are suspect.

[gpshead]

"""I assume these changes were made to silence warnings from -Wstrict-overflow, but I don't think that should be a goal: I'd suggest only making changes where there's a genuine possibility of overflow (even if it's a remote one), and leaving the code unchanged if it's reasonably easy to see that overflow is impossible."""

There is a lot of value in being able to compile with -Wstrict-overflow and know that every warning omitted is something to be looked at. I think it is advantageous to make all code pass this. Having any "expected" warnings during compilation tends to lead people to ignore all warnings.

That said, I agree those particular examples of unnecessary casts are ugly and should be written differently if they are actually done to prevent a warning.

[mdickinson]

There is a lot of value in being able to compile with -Wstrict-overflow and know that every warning omitted is something to be looked at.

I agree in principle; this certainly applies to -Wall. But -Wstrict- overflow doesn't do a particularly good job of finding signed overflow cases: there are a good few false positives, and it doesn't pick up the many cases of actual everyday signed overflow e.g., in unicode_hash, byteshash, set_lookkey, etc.), so it doesn't seem a particular good basis for code rewriting.

[aa2c5943-8264-4a78-97ed-7013d2cb52f6]

You should be using gcc 4.4 to get the best warning behaviour.

[mdickinson]

Thanks Ismail. I'm currently using gcc-4.4 with the -ftrapv (not -fwrapv!) option to see how much breaks. (Answer: quite a lot. :-[ )

I'm finding many overflow checks that look like:

    size = Py_SIZE(a) * n;
    if (n && size / n != Py_SIZE(a)) {
        PyErr_SetString(PyExc_OverflowError,
            "repeated bytes are too long");
        return NULL;
    }

where size and n have type Py_ssize_t. That particular one comes from bytesobject.c (in py3k), but this style of check occurs frequently throughout the source.

Do people think that all these should be fixed?

The fix itself s reasonably straightforward: instead of multiplying and then checking for an overflow that's already happened (and hence has already invoked undefined behaviour according to the standards), get an upper bound for n *first by dividing PY_SSIZE_T_MAX by Py_SIZE(a) and use that to do the overflow check *before the multiplication. It shouldn't be less efficient: either way involves an integer division, a comparison, and a multiplication.

The hard part is finding all the places that need to be fixed.

[61337411-43fc-4a9c-b8d5-4060aede66d0]

I'm finding many overflow checks that look like:

size = Py_SIZE(a) * n; if (n && size / n != Py_SIZE(a)) { PyErr_SetString(PyExc_OverflowError, "repeated bytes are too long"); return NULL; }

where size and n have type Py_ssize_t. That particular one comes from bytesobject.c (in py3k), but this style of check occurs frequently throughout the source.

Do people think that all these should be fixed?

If this really invokes undefined behavior already (i.e. a compiler could set "size" to -1, and have the test fail - ie. not give an exception, and still be conforming) - then absolutely yes.

The fix itself s reasonably straightforward: instead of multiplying and then checking for an overflow that's already happened (and hence has already invoked undefined behaviour according to the standards), get an upper bound for n *first by dividing PY_SSIZE_T_MAX by Py_SIZE(a) and use that to do the overflow check *before\ the multiplication. It shouldn't be less efficient: either way involves an integer division, a comparison, and a multiplication.

[and then perform the multiplication unsigned, to silence the warning - right?]

I think there is a second solution: perform the multiplication unsigned in the first place. For unsigned multiplication, IIUC, overflow behavior is guaranteed in standard C (i.e. it's modulo 2**N, where N is the number of value bits for the unsigned value).

So the code would change to

nbytes = (size_t)Py_SIZE(a)*n;
if (n && (nbytes > Py_SSIZE_T_MAX || nbytes/n != Py_SIZE(a))...
size = (Py_ssize_t)nbytes;

[mdickinson]

[and then perform the multiplication unsigned, to silence the warning - right?]

That wasn't actually what I was thinking: I was proposing to rewrite it as:

    if (Py_SIZE(a) > 0 && n > PY_SSIZE_T_MAX/Py_SIZE(a)) {
        PyErr_SetString(PyExc_OverflowError,
            "repeated bytes are too long");
        return NULL;
    }
    size = Py_SIZE(a) * n;

The multiplication should be safe from overflow, and I don't get any warning at all either with this rewrite (using -O3 -Wall -Wextra - Wsigned-overflow=5) or from the original code, so there's nothing to silence.

I think there is a second solution: perform the multiplication unsigned in the first place.

That would work too. I find the above code clearer, though. It's not immediately obvious to me that the current overflow condition actually works, even assuming wraparound on overflow; I find myself having to think about the mathematics every time.

In general, it seems to me that the set of places reported by -Wsigned- overflow is a poor match for the set of places that need to be fixed. - Wsigned-overflow only gives a warning when that particular version of gcc, with those particular flags, happens to make use of the no-overflow assumption for some particular optimization. Certainly each of the places reported by -Wsigned-overflow should be investigated, but I don't believe it's worth 'fixing' correct code just to get rid of warnings from this particular warning option.

[61337411-43fc-4a9c-b8d5-4060aede66d0]

size = Py_SIZE(a) * n;

The multiplication should be safe from overflow, and I don't get any warning at all either with this rewrite (using -O3 -Wall -Wextra - Wsigned-overflow=5) or from the original code, so there's nothing to silence.

This is puzzling, isn't it? It *could* overflow, could it not?

> I think there is a second solution: perform the multiplication > unsigned in the first place.

That would work too. I find the above code clearer, though.

I agree in this case. In general, I'm not convinced that it is always possible to rewrite the code in that way conveniently.

[mdickinson]

This is puzzling, isn't it?

I don't see why. There's nothing in -Wall -Wextra -Wsigned-overflow that asks for warnings for code that might overflow. Indeed, I don't see how any compiler could reasonably provide such warnings without flagging (almost) every occurrence of arithmetic on signed integers as suspect.[*]

The -ftrapv option is useful for catching genuine signed-integer overflows at runtime, but it can still only catch those cases that actually get exercised (e.g., by the Python test suite).

[] Even some operations on unsigned integers would have to be flagged: the C expression "(unsigned short)x (unsigned short)y" also has the potential to invoke undefined behaviour, thanks to C's integer promotion rules.

[mdickinson]

Aargh!

s/Wsigned-overflow/Wstrict-overflow/g

Sorry.

[61337411-43fc-4a9c-b8d5-4060aede66d0]

I don't see why. There's nothing in -Wall -Wextra -Wsigned-overflow that asks for warnings for code that might overflow.

Ah, right. I misunderstood (rather, didn't bother checking) what -Wsigned-overflow really does.

[86deb77b-abfb-4247-ac01-c8ec70fba690]

Since this is still dribbling along I'll point out intobject.c:int_pow() and:

        prev = ix;              /* Save value for overflow check */
        if (iw & 1) {
            ix = ix*temp;
            if (temp == 0)
                break; /* Avoid ix / 0 */
            if (ix / temp != prev) {
                return PyLong_Type.tp_as_number->nb_power(
                    (PyObject *)v,
                    (PyObject *)w,
                    (PyObject *)z);
            }
        }

which I misclassified in http://bugs.python.org/issue12701

[mdickinson]

Resetting versions.

[mdickinson]

Clang has an -ftrapv option that seems to be less buggy and more complete than gcc's. Compiling and running the test suite with that option enabled looks like a good way to catch a lot of these signed overflows.

[61337411-43fc-4a9c-b8d5-4060aede66d0]

Do we consider these overflows as bugs in Python, or do we declare that we expect compilers to "do the right thing" for the bug fix releases (i.e. care only about the default branch). I'd personally vote for the latter - i.e. don't apply any of the resulting changes to the maintenance releases, and target the issue only for 3.3.

Realistically, a compiler that invokes truly undefined behavior for signed overflow has no chance of getting 3.2 compiled correctly, and we have no chance of finding all these issues within the lifetime of 3.2.

If that is agreed, I would start committing changes that fix the issues Mark already discussed in 2009 (unless he wants to commit them himself).

[mdickinson]

don't apply any of the resulting changes to the maintenance releases, and target the issue only for 3.3.

That sounds fine to me, though if we find more instances of signed overflow that actually trigger test failures in the maintenance branches (like the int_pow one) on mainstream compilers, we might want to fix those there too, on a case-by-case basis.

To get started, here's a patch that fixes occurrences of signed overflow in the bytes, str and tuple hash methods, and also in set lookups. It also fixes a related and minor casting inconsistency in dictobject.c (which was using (size_t)hash & mask in some places, and just 'hash & mask' in others). These are the minimal changes required to get Python to build completely using Clang with '-ftrapv' turned on and --with-pydebug enabled.

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

New changeset 698fa089ce70 by Mark Dickinson in branch 'default': Issue bpo-1621: Fix undefined behaviour in bytes.__hash, str.__hash, tuple.__hash, frozenset.__hash and set indexing operations. http://hg.python.org/cpython/rev/698fa089ce70

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

New changeset 5e456e1a9e8c by Mark Dickinson in branch 'default': Issue bpo-1621: Fix undefined behaviour from signed overflow in get_integer (stringlib/formatter.h) http://hg.python.org/cpython/rev/5e456e1a9e8c

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

New changeset 3fb9464f9b02 by Mark Dickinson in branch 'default': Issue bpo-1621: Fix undefined behaviour from signed overflow in datetime module hashes, array and list iterations, and get_integer (stringlib/string_format.h) http://hg.python.org/cpython/rev/3fb9464f9b02

[mdickinson]

See also issue bpo-9530.

[873bc774-1538-46b2-932f-97fc1aaed8c5]

Also see http://bugs.python.org/issue20944 for suggestions to identify the offending code.

[ff59cd45-ebe3-4b3e-9696-65dc59a38b8c]

One common case where signed integer overflow has been assumed has been the wraparound/overflow checks like in http://bugs.python.org/issue27473

I propose that such commonly erroneous tasks such as overflow checks be implemented as common macros in CPython as getting them right is not quite easy (http://c-faq.com/misc/sd26.html); it would also make the C code more self-documenting.

Thus instead of writing

     if (va.len > PY_SSIZE_T_MAX - vb.len) {

one would write something like

    if (PY_SSIZE_T_SUM_OVERFLOWS(va.len, vb.len)) {

and the mere fact that such a macro *wasn't* used there would signal about possible problems with the comparison.

[vadmium]

Inspired by bpo-27473, I did a quick and dirty scan for obvious places that expect overflow to wrap, and found the following, which I think should be fixed:

Modules/_ctypes/_ctypes.c:1388, in PyCArrayType_new() Objects/listobject.c:492, in list_concat() Objects/tupleobject.c:457, in tupleconcat() Objects/listobject.c:845, in listextend()

Also I played with enabling GCC’s -ftrapv option. Attached is a patch with three changes:

1. configure --with-pydebug enables -ftrapv (experimental, not sure everyone would want this)

2. Easy fix for negation overflow in audioop (I am happy to apply this part)

3. Avoid dumb overflows at end of for loop in Element Tree code when handling slices with step=sys.maxsize. Technically the overflow is undefined behaviour, but the change is annoying, because ignoring the overflow at the end of the loop is much simpler than adding special cases. Not sure what I think about this part.

[vadmium]

I added bpo-13312 as a dependency, there is currently a test for a negative year that relies on overflow handling.

Here is a patch where I tried to fix overflow detection for huge set objects.

[serhiy-storchaka]

The audioop part LGTM. If this case was found with the help of -ftrapv, I'm for adding this option in a debug build.

[vadmium]

I tried the newer -fsanitize=undefined mode, and it is better than -ftrapv. It adds instrumentation that by default nicely reports the errors and continues running.

My problem with the large slice step is not restricted to Element Tree; it affects list objects too:

>>> "abcdef"[3::sys.maxsize]
Objects/unicodeobject.c:13794:55: runtime error: signed integer overflow: 3 + 9223372036854775807 cannot be represented in type 'long int'
'd'

Regarding Antti’s overflow macros, I noticed there is already a macro _PyTime_check_mul_overflow() in Python/pytime.c which does that kind of thing. Maybe it could help, though I am not sure. Has this sort of thing been done in other projects? We might need to be careful about the sign, e.g. clarify the macro is only for positive values, add an assertion, or handle both positive and negative.

[873bc774-1538-46b2-932f-97fc1aaed8c5]

Has this sort of thing been done in other projects?

Yes.

If you are using C, you can use safe_iop. Android uses it for safer integer operations. If you are using C++, you can use David LeBlanc's SafeInt class. Microsoft uses it for safer inter operations.

Jeff

[ff59cd45-ebe3-4b3e-9696-65dc59a38b8c]

Gnulib portability library has https://www.gnu.org/software/gnulib/manual/html_node/Integer-Range-Overflow.html and https://www.gnu.org/softwarhe/gnulib/manual/html_node/Integer-Type-Overflow.html and even macros for producing well-defined integer wraparound for signed integers: https://www.gnu.org/software/gnulib/manual/html_node/Wraparound-Arithmetic.html

That code is under GPL but I believe there is no problem if someone just looks into that for ideas on how to write similar macros.

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

New changeset d6a86018ab33 by Martin Panter in branch 'default': Issue bpo-1621: Avoid signed int negation overflow in audioop https://hg.python.org/cpython/rev/d6a86018ab33

[vadmium]

I committed the fix for negation in audioop.

slice-step.patch includes a better fix for the remaining part of trapv.patch, with Element Tree slicing. I think this fix is much less intrusive, and I have copied it to other places that handle slicing, and added corresponding test cases.

The undefined behaviour sanitizer produces lots of errors about bit shifting signed integers in low-level modules like ctypes, struct, audioop. Typically this is for code converting signed integers to and from bytes, and big/little-endian conversions. This is technically undefined behaviour, but I think it may be less serious than the other overflows with traditional arithmetic like addition and multiplication. E.g. GCC explicitly documents \https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html\ that this is handled as expected with twos-complement, so with GCC there should be no nasty surprises with optimizing out undefined behaviour. My set-overflow.patch would also be in this boat.

[serhiy-storchaka]

Does this work with negative steps?

[ff59cd45-ebe3-4b3e-9696-65dc59a38b8c]

About shifts, according to C standard, right shifts >> of negative numbers are implementation-defined:

"[in E1 >> E2], If E1 has a signed type and a negative value, the resulting value is implementation-defined."

In K&R this meant that the number can be either zero-extended or sign-extended. In any case it cannot lead to undefined behaviour, but the implementation must document what is happening there. Now, GCC says that >> is always arithmetic/sign-extended. This is the implementation-defined behaviour, now GCC has defined what its implementation will do, but some implementation can choose zero-extension. (unlikely)

As for the other part as it says "GCC does not use the latitude given in C99 only to treat certain aspects of signed ‘\<\<’ as undefined". But GCC6 will diagnose that now with -Wextra, and thus it changed already, as with -Werror -Wextra the code doesn't necessarily compile any longer, which is fine. Note that this "certain -- only" refers to that section where the C99 and C11 explicitly say that the behaviour is undefined and C89 doesn't say anything. It could as well be argued that in C89 it is undefined by omission.

Additionally all shifts that shift by more than or equal to the width *still* have undefined behaviour (as do shifts by negative amount). IIRC they work differently on ARM vs x86: in x86 the shift can be mod 32 on 386, and in ARM, mod 256.

[vadmium]

Serhiy: slice-step.patch seems to be fine with negative slice steps. The actual indexes are still positive, and “unsigned” arithmetic is really modular arithmetic, so when you add the negative “unsigned” step value, it decrements the index properly.

Antti: if you use the sanitizer, (almost?) all the shift errors are for left shifts, either of a positive signed overflow, or a negative value. There is a bit more discussion of bit shift errors in bpo-20932. Examples:

Modules/audioop.c:1527:43: runtime error: left shift of negative value -24 Objects/unicodeobject.c:5152:29: runtime error: left shift of 255 by 24 places cannot be represented in type 'int'

I didn’t see any sanitizer reports about right shifts; perhaps it doesn’t report those (being implemenation-defined, rather than undefined, behaviour). And the only report about an excessive shift size is due to a known bug in ctypes, bpo-15119.

[zhangyangyu]

@Martin, attach a patch to fix the overflow check you mentioned in tuple and list objects.

[vadmium]

Apart from the empty “if” statement style (see review), tuple_and_list.patch looks good to me.

I understand the patches from 2011 and earlier have all been committed (correct me if I missed something).

Here is another patch fixing a 64-bit overflow in _thread, detected by the test_timeout() method in test_threading: Modules/_threadmodule.c:59:17: runtime error: signed integer overflow: 6236628528058 + 9223372036000000000 cannot be represented in type 'long int'

[vadmium]

Perhaps we should add a test for the __length_hint__() overflow to tuple_and_list.patch:

>>> a = [1,2,3,4]
>>> import sys
>>> class B:
...  def __iter__(s): return s
...  def __next__(s): raise StopIteration()
...  def __length_hint__(s): return sys.maxsize
... 
>>> a.extend(B())
Objects/listobject.c:844:8: runtime error: signed integer overflow: 4 + 2147483647 cannot be represented in type 'int'

array-size.patch fixes the ctypes array size overflow (including a test).

[zhangyangyu]

Change tuple_andlist.patch with empty curly braces. I don't add the test for \_length_hint__. According to the comment, when overflow happens, it is either ignored or a MemoryError will finally be raised. I am not willing to test a MemoryError in this case.

BTW, how do you get the error?