ubsan undefined behavior sanitizer flags struct _dictkeysobject (PyDictKeysObj)

[gpshead]

BPO	33312
Nosy	@Yhg1s, @gpshead, @benjaminp, @ned-deily, @methane
PRs	bpo-33312: Fix clang ubsan out of bounds warnings in dict. #6537 [3.7] bpo-33312: Fix clang ubsan out of bounds warnings in dict. (GH-6537) #6543 [3.6] bpo-33312: Fix clang ubsan out of bounds warnings in dict. (GH-6537) #6544 bpo-33312: update Tools/gdb/libpython.py to match. #6548 [3.7] bpo-33312: update Tools/gdb/libpython.py to match. (GH-6548) #6549
Files	horrible.patch maybe-less-horrible-gps01.patch maybe-less-horrible-no-vla-gps02.patch

^{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 = 'https://github.com/gpshead'
closed_at = <Date 2019-09-12.14:13:18.032>
created_at = <Date 2018-04-18.21:59:39.232>
labels = ['build']
title = 'ubsan undefined behavior sanitizer flags struct _dictkeysobject (PyDictKeysObj)'
updated_at = <Date 2019-09-12.14:54:59.916>
user = 'https://github.com/gpshead'

bugs.python.org fields:

activity = <Date 2019-09-12.14:54:59.916>
actor = 'ned.deily'
assignee = 'gregory.p.smith'
closed = True
closed_date = <Date 2019-09-12.14:13:18.032>
closer = 'gregory.p.smith'
components = []
creation = <Date 2018-04-18.21:59:39.232>
creator = 'gregory.p.smith'
dependencies = []
files = ['47541', '47542', '47543']
hgrepos = []
issue_num = 33312
keywords = ['patch']
message_count = 23.0
messages = ['315464', '315466', '315473', '315479', '315489', '315491', '315492', '315493', '315494', '315495', '315501', '315503', '315520', '315522', '315523', '315524', '315525', '315528', '315531', '315535', '315543', '352171', '352188']
nosy_count = 6.0
nosy_names = ['twouters', 'gregory.p.smith', 'benjamin.peterson', 'ned.deily', 'methane', 'fweimer']
pr_nums = ['6537', '6543', '6544', '6548', '6549']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'compile error'
url = 'https://bugs.python.org/issue33312'
versions = ['Python 3.6']

[gpshead]

Build CPython (master in this case - though I originally noticed the problem when building a 3.6 tree) as follows with clang installed:

build$ LD=clang-5.0 LDFLAGS=-fsanitize=undefined CC=clang-5.0 CXX=clang-5.0 CFLAGS=-fsanitize=undefined CXXFLAGS=-fsanitize=undefined ../gpshead/configure
build$ make -j12

...

notice many of the warnings scroll by during the build itself as it executes the interpreter

then execute it yourself at the end and you'll get a bunch of these:

../gpshead/Objects/dictobject.c:547:12: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:1145:18: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:2817:15: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:831:27: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:1144:18: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:1034:15: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:728:11: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:1064:9: runtime error: index 64 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:2960:31: runtime error: index 64 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:1489:11: runtime error: index 32 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:637:27: runtime error: index 128 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:788:27: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:1671:22: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:554:31: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:1223:15: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:876:27: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:2396:15: runtime error: index 32 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:2078:10: runtime error: index 128 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:3584:38: runtime error: index 16 out of bounds for type 'int8_t [8]'
../gpshead/Objects/dictobject.c:3502:38: runtime error: index 64 out of bounds for type 'int8_t [8]'

At issue is the hash table here: https://github.com/python/cpython/blob/3.7/Objects/dict-common.h

which is intentionally meant to be indexed "out of bounds" off the end of the struct.

I'm not a strict C language definition so I don't know if that is _supposed_ to be defined behavior as we all tend to assume it is in C or not. If it is supposed to be okay, we should be able to annotate it as such to avoid the warning under ubsan builds.

If it is not, we need to change the way this is written.

[gpshead]

related: https://ssl.icu-project.org/trac/ticket/13503

[benjaminp]

Yeah, I've run into this before. The "correct" thing to do is use C99 VLAs. Unfortunately, that doesn't work for PyDictKeysObject because it really wants a union of VLAs but that isn't supported. The best I could do is making a struct for every possible member of the union. See the attached patch. I didn't land it because it's gross. OTOH, undefined behavior is bad, so I'm okay landing this if you don't find it too revolting.

[gpshead]

I think it is worth getting such a change in.

its arguable that the compiler should be able to see through the union for this use case but I assume such a fix would only land in a recent clang version.

i'm attaching a variant on your patch that doesn't cast entire structs but just casts the VLA.

thoughts?

[gpshead]

notably, C99 variable length arrays syntax is not mentioned as allowed in https://www.python.org/dev/peps/pep-0007/. If we want to use VLAs, that should be clarified. But both our solutions should work with [1] instead of [] which is allowed by the ubsan checker.

it means keeping the annoying "- Py_MEMBER_SIZE(...)" of the array on all size calculations (but because of that the patch is smaller).

[benjaminp]

Your PR is basically what we did prior to 186122e. The problem is that may run afoul of different UB, namely strict aliasing. (Though, I suppose we could probably also avoid that by making dk_indices char[].)

If VLAs work with whatever MSVC we're using, it seems fine to add it to PEP-7. At worst, we can #ifdef sanitizer it.

[gpshead]

By my reading on how strict aliasing works, I think just changing the int64_t[1] or int32_t[1] in my PR to char[1] will work as char is always assumed to alias?

the clang ubsan i was testing my PR against wasn't warning me about strict aliasing. :/

[gpshead]

I'm going to see what appveyor says with the VLA code on the PR. I've updated it to use char[].

[gpshead]

My PR is almost a revert of 186122e so I'm curious what your motivation behind that change to use the union was?

[benjaminp]

I was fixing strict aliasing problems in the code and I thought the union was cleaner than a bunch of casts.

[gpshead]

New changeset 397f1b2 by Gregory P. Smith in branch 'master':
bpo-33312: Fix clang ubsan out of bounds warnings in dict. (GH-6537)
397f1b2

[fweimer]

Why does the code even need the flexible struct member? If you use the surrounding backing store directly, the aliasing issue disappears if the backing store is untyped memory (if not, you have the aliasing problem with the rest of the struct anyway).