classification
Title: integer undefined behaviors
Type: behavior Stage:
Components: Versions: Python 3.3
process
Status: closed Resolution: fixed
Dependencies: 14700 Superseder:
Assigned To: mark.dickinson Nosy List: amaury.forgeotdarc, cvrebert, eric.smith, jcea, mark.dickinson, meador.inge, python-dev, regehr, skrah
Priority: normal Keywords: patch

Created on 2010-08-06 06:16 by regehr, last changed 2012-10-28 11:50 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
python-errors.txt regehr, 2010-08-06 06:16
issue9530_1.patch mark.dickinson, 2010-08-06 12:04 review
Messages (24)
msg113079 - (view) Author: John Regehr (regehr) Date: 2010-08-06 06:16
I ran "make test" for today's Python3k snapshot under a tool which detects math operations that the C language considers to have undefined behavior.  This was on x86 Linux.  The list of undefined behaviors is attached.  Hopefully they are self-explanatory, but please let me know if more details are needed.
msg113091 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-08-06 10:07
This is good stuff!  Thank you!  I'll look through these.

Is the tool you used publicly available?
msg113098 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-08-06 12:04
Here are some fixes for Objects/bytesobject.c and Objects/bytearrayobject.c.  More to come.
msg113099 - (view) Author: John Regehr (regehr) Date: 2010-08-06 13:09
Hi Mark-- Glad it's useful! We plan to release this tool but haven't done so yet, it still has rough edges.  It's LLVM-based and it seems likely they will take our patches.
msg113138 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-08-06 21:34
Fixed two more bytearray problems in r83768.
msg113555 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-08-10 18:35
Applied issue9530_1.patch in r83936.
msg147954 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-11-19 16:58
Status update:  all the reported errors from the Objects/ directory have been fixed in the default branch (many of these were fixed recently as part of making sure that the test-suite runs under Clang's -ftrapv option), or are out of date.  I haven't checked the reports for the extension Modules.
msg147955 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-11-19 17:00
See also issue #1621.
msg147957 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-11-19 17:08
The issues reported for the datetime, array, itertools and math modules are also already fixed.  That just leaves the following two of the reported issues outstanding:

</home/regehr/z/python/Modules/_ctypes/cfield.c, (590:5)> : Op: <<=, Reason : Signed Left Shift Error: Right operand is negative or is greater than or equal to the width of the promoted left operand, BINARY OPERATION: left (int32): 0 right (int32): -2 

and

</home/regehr/z/python/Modules/testcapi_long.h, (37:47)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int32): 0 right (int32): -2147483648

I'm using r63764 as the revision that the line numbers relate to; not sure whether this exactly right, but it seems to be close enough.
msg147961 - (view) Author: John Regehr (regehr) Date: 2011-11-19 17:28
This is great.  I'd be happy to re-run the tests sometime, and also we're talking with the LLVM folks about getting our patches into the main LLMM tree.  Basically it'll act as a more powerful -ftrapv, and the error message will be much better than "aborted".
msg147964 - (view) Author: Roundup Robot (python-dev) Date: 2011-11-19 17:58
New changeset 71100ef4f7a2 by Mark Dickinson in branch 'default':
Issue #9530: Fix undefined behaviour due to signed overflow in testcapi_long.h.
http://hg.python.org/cpython/rev/71100ef4f7a2
msg148035 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-11-21 12:39
> I'd be happy to re-run the tests sometime.

Yes, please!  Alternatively, if there are easy instructions for us to re-run these tests, that would be valuable, too.  Do I understand correctly that you have a publicly available extension to LLVM for this?

> Basically it'll act as a more powerful -ftrapv, and the error message will be much better than "aborted".

Indeed---there were a number of places where tracking down the exact cause of the error using a combination of -ftrapv and gdb was painful. :-)

I'm aware of two current issues: one in Python/formatter_unicode.c, and one in Modules/timemodule.c.  I'll try to fix these shortly.
msg148068 - (view) Author: John Regehr (regehr) Date: 2011-11-21 18:17
Hi Mark, yes you can run the overflow checker but "easy instructions" depends on whether you feel like building your own LLVM.  It is not at all difficult, but it's certainly not as easy as "apt-get install ...".

Patch and instructions are here:

  http://embed.cs.utah.edu/ioc/

If/when we get this into LLVM (the earliest possible release containing IOC will be 3.1), I'll let you know.  Thanks again.
msg148726 - (view) Author: Roundup Robot (python-dev) Date: 2011-12-01 15:27
New changeset 7e37598a25a6 by Mark Dickinson in branch 'default':
Issue #9530: Fix undefined behaviour due to signed overflow in Python/formatter_unicode.c.
http://hg.python.org/cpython/rev/7e37598a25a6
msg148758 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-12-02 16:28
See also issue #13496.
msg159711 - (view) Author: John Regehr (regehr) Date: 2012-04-30 17:35
Hi folks,

I realize it was a long time ago that I reported this issue!  Since then our tool has been made available:

  http://embed.cs.utah.edu/ioc/

In particular, that web page contains a pre-compiled version of the tool for recent Ubuntu on x86-64, that should be pretty easy to use.

Alternatively, I can re-run the Python test suite on a Python compiled using our tool.  Let me know if this would be helpful.
msg159812 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-05-02 18:36
> Alternatively, I can re-run the Python test suite on a Python compiled
> using our tool.  Let me know if this would be helpful.

Definitely helpful if you have the time!  Yes, please.  Though I do intend to try out the tool for myself at some point.
msg160126 - (view) Author: Roundup Robot (python-dev) Date: 2012-05-07 09:37
New changeset c9c2031cf16d by Mark Dickinson in branch 'default':
Add John Regehr to Misc/ACKS for his help with finding integer overflows (issue #9530).
http://hg.python.org/cpython/rev/c9c2031cf16d
msg163303 - (view) Author: John Regehr (regehr) Date: 2012-06-21 04:07
I the tests for today's cpython using IOC and got only the issues below.

The on-purpose divide by zero should be OK but the shift by -2 probably wants to be fixed.

ARITHMETIC UNDEFINED at </home/regehr/tmp/cpython/Modules/_ctypes/cfield.c, (589:5)> : Op: <<=, Reason : Signed Left Shift: Right operand is negative or is greater than or equal to the width of the promoted left operand, BINARY OPERATION: left (int32): 0 right (int32): -2 

ARITHMETIC UNDEFINED at <./Modules/faulthandler.c, (844:11)> : Op: /, Reason : Signed Division: Divisor is 0 || divident is INT_MIN, divisor is -1, BINARY OPERATION: left (int32): 1 right (int32): 0 


version info:

regehr@home:~/tmp/cpython$ ./python 
Python 3.3.0a4+ (default:24369f6c4a22+, Jun 20 2012, 16:41:04) 
[GCC 4.2.1 Compatible Clang 3.1 ((branches/release_31))] on linux
Type "help", "copyright", "credits" or "license" for more information.
msg163309 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-06-21 08:01
Thanks.  It looks like that <<= report has uncovered a bug in the way that ctypes lays out bitfields:  in the following, BITS.M should (I believe) look like: <Field type=c_short, ofs=4:0, bits=1>.  Instead, ctypes is trying to store a bitfield starting at bit position 17 of a short, which doesn't make much sense.

iwasawa:cpython mdickinson$ ./python.exe
Python 3.3.0a4+ (default:2035c5ad4239+, Jun 21 2012, 08:30:36) 
[GCC 4.2.1 (Apple Inc. build 5664)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from ctypes import Structure, c_int, c_short
>>> class BITS(Structure):
...     _fields_ = [("A", c_int, 17), ("M", c_short, 1)]
... 
>>> BITS.M
<Field type=c_short, ofs=2:17, bits=1>
msg163310 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-06-21 08:13
Meador:  I see that you've been working on some ctypes issues; does the ctypes bitfield problem above fall under any of the existing issues, or should I open a new one?
msg163312 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2012-06-21 08:23
Issue3547 looks similar.
msg163316 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-06-21 09:14
Thanks, Amaury.  I see a whole bunch of related issues, but none of them quite seems to capture this exact issue.  So I've opened a new bug report: see issue 15119.
msg174031 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-10-28 11:50
It looks as though all the issues found by John's tool have now been fixed, with the exception of the ctypes issue.  There's a separate issue open for that, so I'm closing this issue as fixed.
History
Date User Action Args
2012-10-28 11:50:12mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg174031
2012-06-21 09:14:46mark.dickinsonsetmessages: + msg163316
2012-06-21 08:23:45amaury.forgeotdarcsetnosy: + amaury.forgeotdarc
messages: + msg163312
2012-06-21 08:13:36mark.dickinsonsetnosy: + meador.inge
messages: + msg163310
2012-06-21 08:01:07mark.dickinsonsetmessages: + msg163309
2012-06-21 04:07:52regehrsetmessages: + msg163303
2012-05-07 09:37:45python-devsetmessages: + msg160126
2012-05-02 18:36:33mark.dickinsonsetmessages: + msg159812
2012-05-02 17:52:17cvrebertsetnosy: + cvrebert
2012-04-30 21:45:48skrahsetnosy: + skrah
2012-04-30 17:35:36regehrsetmessages: + msg159711
2012-04-30 17:31:39mark.dickinsonsetdependencies: + Integer overflow in classic string formatting
2011-12-02 16:28:24mark.dickinsonsetmessages: + msg148758
2011-12-01 15:27:10python-devsetmessages: + msg148726
2011-11-21 18:17:02regehrsetmessages: + msg148068
2011-11-21 12:39:28mark.dickinsonsetmessages: + msg148035
2011-11-20 03:43:34jceasetnosy: + jcea
2011-11-19 17:58:59python-devsetnosy: + python-dev
messages: + msg147964
2011-11-19 17:28:26regehrsetmessages: + msg147961
2011-11-19 17:08:34mark.dickinsonsetmessages: + msg147957
2011-11-19 17:00:09mark.dickinsonsetmessages: + msg147955
2011-11-19 16:58:35mark.dickinsonsetmessages: + msg147954
versions: + Python 3.3, - Python 3.2
2010-08-10 18:35:57mark.dickinsonsetmessages: + msg113555
2010-08-06 21:34:32mark.dickinsonsetmessages: + msg113138
2010-08-06 13:09:33regehrsetmessages: + msg113099
2010-08-06 12:04:45mark.dickinsonsetfiles: + issue9530_1.patch
keywords: + patch
messages: + msg113098

versions: + Python 3.2, - Python 3.3
2010-08-06 11:52:48eric.smithsetnosy: + eric.smith
2010-08-06 10:07:03mark.dickinsonsetassignee: mark.dickinson

messages: + msg113091
nosy: + mark.dickinson
2010-08-06 06:16:24regehrcreate