Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

ubsan undefined behavior sanitizer flags struct _dictkeysobject (PyDictKeysObj) #77493

Closed
gpshead opened this issue Apr 18, 2018 · 23 comments
Closed

ubsan undefined behavior sanitizer flags struct _dictkeysobject (PyDictKeysObj) #77493

gpshead opened this issue Apr 18, 2018 · 23 comments
Assignees
@gpshead
Labels
build The build process and cross-build

Comments

@gpshead
Copy link
Member

gpshead commented Apr 18, 2018

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
    Copy link
    Member Author

    gpshead commented Apr 18, 2018

    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 gpshead added 3.7 (EOL) end of life 3.8 only security fixes build The build process and cross-build labels Apr 18, 2018
    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 18, 2018

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

    @benjaminp
    Copy link
    Contributor

    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
    Copy link
    Member Author

    gpshead commented Apr 19, 2018

    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
    Copy link
    Member Author

    gpshead commented Apr 19, 2018

    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
    Copy link
    Contributor

    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
    Copy link
    Member Author

    gpshead commented Apr 19, 2018

    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
    Copy link
    Member Author

    gpshead commented Apr 19, 2018

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

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 19, 2018

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

    @benjaminp
    Copy link
    Contributor

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

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    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
    Copy link
    Mannequin

    fweimer mannequin commented Apr 20, 2018

    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).

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    If you think this should be written differently, please propose it in a PR so we can see what you are suggesting.

    An unbounded member at the end of a struct is quite a common practice in C.
    ex: PyBytesObject

    @ned-deily
    Copy link
    Member

    Greg, this change has broken some buildbots:

    http://buildbot.python.org/all/#/builders/85/builds/934

    http://buildbot.python.org/all/#/builders/21/builds/951

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    New changeset 392520b by Gregory P. Smith (Miss Islington (bot)) in branch '3.7':
    bpo-33312: Fix clang ubsan out of bounds warnings in dict. (GH-6537) (GH-6543)
    392520b

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    ned: yes, it supposedly has. test_gdb. in a manner i cannot reproduce or debug without error output that indicates anything about the problem.

    test_gdb passes on my systems.

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    I see one line in Tools/gdb/libpython.py that may be related. i'll try changing that. the only way i have to _test_ it is to merge it into master.

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    New changeset 53f67d4 by Gregory P. Smith in branch 'master':
    bpo-33312: update Tools/gdb/libpython.py to match. (GH-6548)
    53f67d4

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    New changeset 11659d0 by Gregory P. Smith (Miss Islington (bot)) in branch '3.7':
    bpo-33312: update Tools/gdb/libpython.py to match. (GH-6549)
    11659d0

    @ned-deily
    Copy link
    Member

    Thanks, Greg, looking better!

    @gpshead
    Copy link
    Member Author

    gpshead commented Apr 20, 2018

    Sorry for the breakage. I'm glad the fix was that greppable and easy given I had no idea where to start otherwise. :)

    This is in for 3.7. The PR for 3.6 is pending, i want to let it out in the next 3.7 builds for a while before i merge it into 3.6 even though I've got pretty high confidence at this point.

    bpo-33321 filed to track getting an ubsan buildbot setup.

    Also, thank you Benjamin for your patch and pointing out the strict aliasing issue. so many undefined behaviors. it's a wonder the language even works. :)

    @gpshead gpshead self-assigned this Apr 20, 2018
    @gpshead
    Copy link
    Member Author

    gpshead commented Sep 12, 2019

    automated backport of the gdb/libpython change fails on 3.6, if this is needed there (I haven't looked into the code on that branch), it's a tiny change to apply. i'll leave that to the 3.6 RM to decide if at all.

    @gpshead gpshead removed 3.7 (EOL) end of life 3.8 only security fixes labels Sep 12, 2019
    @gpshead gpshead closed this as completed Sep 12, 2019
    @ned-deily
    Copy link
    Member

    This issue does not seem to me to be a security issue so would not meet the criteria for backporting to 3.6.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees

    @gpshead gpshead

    Labels
    build The build process and cross-build
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    3 participants
    @gpshead @benjaminp @ned-deily