Undefined behavior in dtoa.c (rshift 32 of 32bit data type)

[tiran]

BPO	23999
Nosy	@doko42, @mdickinson, @ericvsmith, @tiran, @serhiy-storchaka

^{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 = None
created_at = <Date 2015-04-18.22:52:13.789>
labels = ['type-bug']
title = 'Undefined behavior in dtoa.c (rshift 32 of 32bit data type)'
updated_at = <Date 2015-04-19.13:03:53.726>
user = 'https://github.com/tiran'

bugs.python.org fields:

activity = <Date 2015-04-19.13:03:53.726>
actor = 'christian.heimes'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = []
creation = <Date 2015-04-18.22:52:13.789>
creator = 'christian.heimes'
dependencies = []
files = []
hgrepos = []
issue_num = 23999
keywords = []
message_count = 7.0
messages = ['241464', '241492', '241495', '241496', '241497', '241498', '241515']
nosy_count = 5.0
nosy_names = ['doko', 'mark.dickinson', 'eric.smith', 'christian.heimes', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = None
stage = 'needs patch'
status = 'open'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue23999'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4', 'Python 3.5']

[tiran]

Coverity has found undefined behavior in dtoa.c:d2b(). lo0bits() can return 32 which z >>= 32, where z is an uint32. I've talked to doku at PyCon. He suggested to update dtoa.c to a more recent version. Our copy is based on a version from 2001. There are more modern versions available, e.g. https://searchcode.com/codesearch/view/52748288/ from 2006.

CID 1202735 (#1 of 1): Bad bit shift operation (BAD_SHIFT)
large_shift: In expression z >>= k, right shifting by more than 31 bits has undefined behavior. The shift amount, k, is 32.

[mdickinson]

I'm pretty sure that our code was based on something rather more recent than 2001: it was the most recent version available at the time (around 2008?), and it incorporates subsequent fixes from David Gay.

Please don't replace our dtoa.c with a current version: ours has diverged from the original, and includes fixes that aren't available upstream.

[mdickinson]

Looking more closely, the report doesn't make sense to me: k is the return value from a call to lo0bits. From the source of lo0bits, I don't see any way that k can be 32: it's always going to be in the range [0, 31]. Christian: do you have any more information from Coverity? This looks like a false positive to me.

[mdickinson]

Ah, sorry; I see it. Fix on the way.

[mdickinson]

Okay, so after looking more closely, this still looks like a false positive: lo0bits can return 32, but only for an input of zero. In the code in question, we're doing k = lo0bits(&y), so the only way we can get a k of 32 is if y = 0. But the whole thing is inside an "if" block that looks like if ((y = word1(d))) { ... } (yep, completely with the extra parentheses and the misleading equality-test-lookalike assignment), so that if block won't be executed if y is zero.

I edited the code to print out debugging information if k is ever 32 at that point, and saw no output. So I don't think that line ever gets executed with k = 32.

[mdickinson]

saw no output

Bah; missed a bit. I saw no output when running the Python test suite, that is. That's not definitive, of course.

[tiran]

You could be right. I didn't track all paths manually. All this bit shifting is making my head dizzy... :)

Anyways I have sent you an invite for Coverity, so you can check the result yourself. The Python test suite passes with assert(k < 32); inside the problematic block, too.