Mailing List Archive: Python: Bugs

[issue14700] Integer overflow in classic string formatting

Index | Next | Previous | View Threaded

report at bugs

Apr 30, 2012, 9:55 AM

Post #1 of 19 (141 views)
Permalink

[issue14700] Integer overflow in classic string formatting

New submission from Serhiy Storchaka <storchaka [at] gmail>:

Check for integer overflow for width and precision is buggy.

Just a few examples (on platform with 32-bit int):

>>> '%.21d' % 123
'000000000000000000123'
>>> '%.2147483648d' % 123
'123'
>>> '%.2147483650d' % 123
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: prec too big

>>> '%.21f' % (1./7)
'0.142857142857142849213'
>>> '%.2147483648f' % (1./7)
'0.142857'
>>> '%.2147483650f' % (1./7)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: prec too big

----------
components: Interpreter Core
messages: 159707
nosy: storchaka
priority: normal
severity: normal
status: open
title: Integer overflow in classic string formatting
type: behavior
versions: Python 2.6, Python 2.7, Python 3.1, Python 3.2, Python 3.3

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 10:05 AM

Post #2 of 19 (136 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

R. David Murray <rdmurray [at] bitdance> added the comment:

Serhiy: FYI we use the versions field to indicate which versions the fix will be made in, not which versions the bug occurs in. Since only 2.7, 3.2, and 3.3 get bug fixes, I've changed the versions field to be just those three. (3.1 and 2.6 are still in the list because they get *security* fixes, but those are rare.)

----------
nosy: +eric.smith, mark.dickinson, r.david.murray
versions: -Python 2.6, Python 3.1

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 10:16 AM

Post #3 of 19 (136 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Mark Dickinson <dickinsm [at] gmail> added the comment:

Indeed, Objects/unicodeobject.c (default branch) has this, at around line 13839:

if ((prec*10) / 10 != prec) {
PyErr_SetString(PyExc_ValueError,
"prec too big");
goto onError;
}

... which since 'prec' has type int, will invoke undefined behaviour. There are probably many other cases like this one.

Serhiy, what platform are you on? And are you applying any special compile-time flags? For gcc, we should be using -fwrapv, which in this case should make the above code work as intended.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 10:29 AM

Post #4 of 19 (131 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Mark Dickinson <dickinsm [at] gmail> added the comment:

See get_integer in Objects/stringlib/unicode_format.h for a better way to do this sort of thing.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 10:43 AM

Post #5 of 19 (131 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

> Serhiy: FYI we use the versions field to indicate which versions the fix will be made in, not which versions the bug occurs in. Since only 2.7, 3.2, and 3.3 get bug fixes, I've changed the versions field to be just those three. (3.1 and 2.6 are still in the list because they get *security* fixes, but those are rare.)

Well, David, I understand. This ridiculous bug is unlikely security
issue.

Here is a patch that fixes this bug.

----------
keywords: +patch
Added file: http://bugs.python.org/file25426/pyunicode_format_integer_overflow.patch

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________

Attachments:

pyunicode_format_integer_overflow.patch (1.03 KB)

report at bugs

Apr 30, 2012, 10:56 AM

Post #6 of 19 (134 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

> Serhiy, what platform are you on?

32-bit Linux (Ubuntu), gcc 4.6. But it has to happen on any platform
with a 32-bit integer (for 64-bit use 9223372036854775808).

214748364*10/10 == 214748364 -- test passed
214748364*10 + ('8'-'0') == -2147483648 -- oops!

See also how is this problem solved in _struct.c.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 11:04 AM

Post #7 of 19 (133 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Mark Dickinson <dickinsm [at] gmail> added the comment:

> But it has to happen on any platform
> with a 32-bit integer

Not necessarily: it's undefined behaviour, so the compiler can do as it wishes.

Your patch should also address possible overflow of the addition.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 11:13 AM

Post #8 of 19 (131 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

> Your patch should also address possible overflow of the addition.

Here there is no overflow. The patch limits prec of a little stronger
(instead of 2147483647 to 2147483639 on a 32-bit platform).

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 11:14 AM

Post #9 of 19 (132 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Mark Dickinson <dickinsm [at] gmail> added the comment:

Ah yes, true.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 11:17 AM

Post #10 of 19 (132 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Mark Dickinson <dickinsm [at] gmail> added the comment:

Any chance of some tests? :-)

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 12:07 PM

Post #11 of 19 (133 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

> Any chance of some tests? :-)

Even a test for struct tests only struct.calcsize on this specific case.
For string formatting has no such function, on most platforms testing
would be a memory overflow.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 12:21 PM

Post #12 of 19 (132 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

> 32-bit Linux (Ubuntu), gcc 4.6.

Sorry, gcc 4.4.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 12:33 PM

Post #13 of 19 (131 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Mark Dickinson <dickinsm [at] gmail> added the comment:

Still, I think it would be useful to have some tests that exercise the overflow branches. (If those tests had existed before, then this issue would probably already have been found and fixed, since clang could have detected the undefined behaviour resulting from signed overflow.)

I'll add tests and apply this later.

----------
assignee: -> mark.dickinson

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

Apr 30, 2012, 12:56 PM

Post #14 of 19 (133 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

> I'll add tests and apply this later.

Well, look at test_crasher in Lib/test/test_struct.py.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

May 7, 2012, 3:21 AM

Post #15 of 19 (115 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Roundup Robot <devnull [at] psf> added the comment:

New changeset 064c2d0483f8 by Mark Dickinson in branch 'default':
Issue #14700: Fix two broken and undefined-behaviour-inducing overflow checks in old-style string formatting. Thanks Serhiy Storchaka for report and original patch.
http://hg.python.org/cpython/rev/064c2d0483f8

----------
nosy: +python-dev

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

May 7, 2012, 3:22 AM

Post #16 of 19 (115 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Changes by Mark Dickinson <dickinsm [at] gmail>:

----------
resolution: -> fixed
status: open -> closed

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

May 7, 2012, 5:14 AM

Post #17 of 19 (115 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

Mark, I deliberately have not used the exact formula for the overflow. Comparison with the constant is much cheaper than division or multiplication.

Microbencmark:

./python -m timeit -s 'f="%.1234567890s"*100;x=("",)*100' 'f%x'

Before changeset 064c2d0483f8: 10000 loops, best of 3: 27.1 usec per loop
Changeset 064c2d0483f8: 10000 loops, best of 3: 25.7 usec per loop
Original patch: 100000 loops, best of 3: 18.2 usec per loop

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

May 7, 2012, 5:21 AM

Post #18 of 19 (115 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Mark Dickinson <dickinsm [at] gmail> added the comment:

Sure, I realize that, but I prefer not to be sloppy in the overflow check, and to use the same formula that's already used in stringlib. I somehow doubt that this micro-optimization is going to have any noticeable effect in real code.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

report at bugs

May 7, 2012, 8:54 AM

Post #19 of 19 (114 views)
Permalink

[issue14700] Integer overflow in classic string formatting [In reply to]

Serhiy Storchaka <storchaka [at] gmail> added the comment:

> I somehow doubt that this micro-optimization is going to have any noticeable effect in real code.

Agree. I just found this bug, trying to optimize the code.

----------

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue14700>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads