Skip to content

Do not assume signed integer overflow behavior #45962

Closed

Description

@gpshead
BPO 1621
Nosy @loewis, @jcea, @mdickinson, @pitrou, @vstinner, @avassalotti, @matejcik, @jwilk, @alex, @davidmalcolm, @vadmium, @serhiy-storchaka, @ztane, @zhangyangyu, @sir-sigurd, @miss-islington
PRs
  • bpo-1621: Avoid signed integer overflow in set_table_resize(). #9059
  • [3.7] bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) #9198
  • [3.6] bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) #9199
  • bpo-34656: Avoid relying on signed overflow in _pickle memos. #9261
  • bpo-34656: Avoid relying on signed overflow in _pickle memos. #9261
  • Dependencies
  • bpo-13312: test_time fails: strftime('%Y', y) for negative year
  • bpo-27473: bytes_concat seems to check overflow using undefined behaviour
  • bpo-29145: failing overflow checks in replace_*
  • Files
  • config.patch
  • overflow-error.patch
  • overflow-error2.patch
  • overflow-error3.patch: Fix whitespace change and comment.
  • overflow-error4.patch: Fix -fwrapv check, thanks tiran
  • fix-overflows-try1.patch
  • fix-overflows-try2.patch: Better patch
  • fix-overflows-try3.patch
  • fix-overflows-final.patch
  • csv.patch
  • issue1621_hashes_and_sets.patch
  • trapv.patch: Committed & superseded
  • set-overflow.patch: Superseded
  • slice-step.patch: => python/issues-test-cpython#36946; supersedes trapv.patch
  • tuple_and_list.patch
  • thread.patch: => Issue 33632
  • array-size.patch: Superseded
  • tuple_and_list_v2.patch
  • ctypes_v2.patch: Supersedes array-size.patch
  • unicode.patch: Committed
  • tuple_and_list_v3.patch: Committed
  • overflow_fix_in_listextend.patch: Superseded
  • 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 = <Date 2018-10-19.22:55:35.437>
    created_at = <Date 2007-12-14.00:43:47.318>
    labels = ['type-security', '3.7', '3.8']
    title = 'Do not assume signed integer overflow behavior'
    updated_at = <Date 2018-10-19.22:55:35.436>
    user = 'https://github.com/gpshead'

    bugs.python.org fields:

    activity = <Date 2018-10-19.22:55:35.436>
    actor = 'vstinner'
    assignee = 'none'
    closed = True
    closed_date = <Date 2018-10-19.22:55:35.437>
    closer = 'vstinner'
    components = []
    creation = <Date 2007-12-14.00:43:47.318>
    creator = 'gregory.p.smith'
    dependencies = ['13312', '27473', '29145']
    files = ['8950', '9205', '9207', '9209', '9210', '9211', '9238', '9239', '9242', '9307', '23237', '43728', '43729', '43785', '43827', '43838', '43839', '43842', '43855', '43856', '43862', '43956']
    hgrepos = []
    issue_num = 1621
    keywords = ['patch']
    message_count = 128.0
    messages = ['58602', '58609', '58610', '58611', '58617', '58620', '58684', '58711', '59611', '59612', '59616', '59619', '59692', '59693', '59694', '59696', '59699', '60078', '60079', '60102', '60103', '60105', '60107', '60109', '60110', '60111', '60114', '60115', '60116', '60118', '60120', '60121', '60124', '60125', '60126', '60146', '60246', '60254', '60260', '61272', '61286', '61291', '61319', '61320', '61757', '61758', '61759', '61760', '61761', '61762', '61763', '61765', '61766', '61767', '61768', '61770', '61774', '61784', '61785', '61788', '61791', '61792', '62616', '87689', '87690', '87693', '87694', '87704', '87707', '87708', '87712', '87730', '87731', '87908', '141871', '144490', '144492', '144499', '144501', '144503', '144505', '144524', '147958', '213729', '270084', '270460', '270461', '270463', '270562', '270580', '270582', '270807', '270809', '270823', '270827', '270869', '270977', '271057', '271058', '271084', '271118', '271136', '271143', '271144', '271150', '271223', '271735', '271759', '271763', '271766', '271768', '271769', '271800', '271803', '272077', '272078', '285466', '303330', '317087', '325091', '325105', '325109', '325113', '325128', '325284', '328068', '328069', '328070']
    nosy_count = 22.0
    nosy_names = ['loewis', 'nnorwitz', 'jcea', 'mark.dickinson', 'pitrou', 'vstinner', 'alexandre.vassalotti', 'donmez', 'matejcik', 'jwilk', 'alex', 'dmalcolm', 'python-dev', 'deadshort', 'martin.panter', 'serhiy.storchaka', 'ztane', 'fweimer', 'Jeffrey.Walton', 'xiang.zhang', 'sir-sigurd', 'miss-islington']
    pr_nums = ['9059', '9198', '9199', '9261', '9261']
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'security'
    url = 'https://bugs.python.org/issue1621'
    versions = ['Python 3.6', 'Python 3.7', 'Python 3.8']

    Activity

    1. gpshead commented on Dec 14, 2007

      @gpshead
      MemberAuthor

      The resolution to http://bugs.python.org/issue1608 looks like it'll add
      a -fwrapv gcc flag when building python. This works around the issue
      nicely on one compiler (gcc) but doesn't fix our fundamentally broken code.

      We should fix all dependencies on integer overflow behavior, starting by
      making everything compile properly with gcc's -Wstrict-overflow and
      -Werror flags.

    2. tiran commented on Dec 14, 2007

      @tiran
      Member

      My gcc 4.1 doesn't have the -Wstrict-overflow option.

      gcc-Version 4.1.3 2007092 (prerelease) (Ubuntu 4.1.2-16ubuntu2)

    3. tiran commented on Dec 14, 2007

      @tiran
      Member

      Should we use -ansi (C90 aka C89 standard) option, too? Python core
      compiles fine with -ansi but together with -Werror it breaks several
      extensions:

      _bsddb _codecs_iso2022 _ctypes
      _socket _ssl linuxaudiodev

    4. tiran commented on Dec 14, 2007

      @tiran
      Member

      Socket and SSL are using bluetooth.h which defines some functionas as
      inline. Inline isn't part of C89. Linuxaudiodev depends on the 'linux'
      macro which is not defined in C89.

      The Python core can be compiled with -ansi but the extension modules
      require -std=gnu89.

    5. loewis commented on Dec 14, 2007

      loewismannequin
      Mannequin

      Using ansi is out of scope of this issue, and should not be mixed with
      it. -ansi is about disabling certain GCC extensions. This report is
      about C code in Python which has undefined behavior.

      I think there is disagreement on whether Python should stop relying on
      this particular undefined behavior (namely, whether the sum of two large
      positive numbers is negative). GvR (apparently) believes that the
      compiler should guarantee that the twos-complement semantic is available
      throughout the C language.

    6. malemburg commented on Dec 14, 2007

      @malemburg
      Member

      Whatever you change regarding the compiler options for Python, please
      make sure that this doesn't effect the default settings used by
      distutils to compile external modules (it normally takes the options
      straight from the Makefile used for compiling Python).

      Otherwise, you're likely going to break lots and lots of extensions. Thanks.

    7. avassalotti commented on Dec 17, 2007

      @avassalotti
      Member

      I compiled Python using gcc 4.3.0 with the -Wstrict-overflow, and that's
      the only warning I got:

      Objects/doubledigits.c: In function ‘_PyFloat_Digits’:
      Objects/doubledigits.c:313: error: assuming signed overflow does not
      occur when assuming that (X + c) < X is always false

      I am sure yet how to interpret it, though. It says that the overflow
      check is in _PyFloat_Digits(), line 313 is in the function add_big(). It
      probably means that add_big() gets inlined. I tried to set
      -finline-limit=0, but strangely the overflow warning disappears...

      I will try to investigate this further, when I will have a bit more time
      in my hands.

    8. gpshead commented on Dec 17, 2007

      @gpshead
      MemberAuthor

      heh if thats the only warning gcc -Wstrict-overflow gives then I've
      mistitled the bug. Fixed. It'll take some manual code review.

      Anyone know if the commercial analysis tools we've run the code base
      through in the past can find these for us?

    9. changed the title [-]Python should compile with -Wstrict-overflow when using gcc[/-] [+]Do not assume signed integer overflow behavior[/+] on Dec 17, 2007
    10. gvanrossum commented on Jan 9, 2008

      @gvanrossum
      Member

      Alexandre, which Python version did you compile with -Wstrict-overflow?
      It would behoove us to check 2.5.2 thoroughly before it goes out the door.

      I will contact Coverity to ask if they check for this kind of thing.
      (They just upgraded us to "Rung 2", whatever that may mean. :-)

      MvL: I don't want 2s complement throughout the language, I just want the
      overflow checks to be reliable. Since I'd forgotten about the
      difference between unsigned and signed overflow, I have no idea how many
      overflow checks have been submitted that are relying on signed overflow;
      though apparently (if the -Wstrict-overflow results can be trusted)
      we're okay.

      FWIW, I've heard that some commercial compilers (e.g. XLC) assume that
      even *unsigned* overflow is undefined, violating the C standard. This
      would suggest that buffer overflow checks should be coded without
      relying on arithmetic overflow at all. This is possible, just a bit hairy.

    11. gvanrossum commented on Jan 9, 2008

      @gvanrossum
      Member

      Marc-Andre: what do you mean by breaking lots and lots of extensions?
      Extensions also contain buffer overflow checks (at least I hope they do
      :-) and those should also be guaranteed safe by using -fwrapv or
      -fno-strict-overflow (GCC 4.2 and higher) until we're sure there aren't any.

    12. donmez commented on Jan 9, 2008

      donmezmannequin
      Mannequin

      -Wstrict-overflow=3 with gcc 4.3 trunk here shows :

      Modules/cPickle.c: In function 'Unpickler_noload':
      Modules/cPickle.c:4232: warning: assuming signed overflow does not occur
      when assuming that (X - c) > X is always false

      Modules/cPickle.c:194: warning: assuming signed overflow does not occur
      when assuming that (X - c) > X is always false
      Modules/cPickle.c: In function 'load':
      Modules/cPickle.c:4232: warning: assuming signed overflow does not occur
      when assuming that (X - c) > X is always false

      But also note that -fno-strict-aliasing is also just another workaround
      and its more serious than -fwrapv.

    13. loewis commented on Jan 9, 2008

      loewismannequin
      Mannequin

      But also note that -fno-strict-aliasing is also just another workaround
      and its more serious than -fwrapv.

      Sure - however, that is fixed in Python 3 (and unrelated to this issue)

    14. avassalotti commented on Jan 11, 2008

      @avassalotti
      Member

      Hm. I don't get any warning, related to the overflow issue, neither with
      -Wstrict-overflow=3, nor -Wstrict-overflow=5. Are the cPickle warnings
      already fixed?

    15. 104 remaining items

    16. serhiy-storchaka commented on Sep 29, 2017

      @serhiy-storchaka
      Member

      Martin, do you mind to create a PR for your ctypes_v2.patch?

    17. vadmium commented on May 19, 2018

      @vadmium
      Member

      Sorry I haven’t made a PR for ctypes_v2.patch, but I don’t mind if someone else takes over. I understand the HAVE_LONG_LONG check may no longer necessary for newer Python versions.

    18. miss-islington commented on Sep 11, 2018

      @miss-islington
      Contributor

      New changeset 6c7d67c by Miss Islington (bot) (Sergey Fedoseev) in branch 'master':
      bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059)
      6c7d67c

    19. vstinner commented on Sep 12, 2018

      @vstinner
      Member

      newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.

      Previously, there was a explicitly check for error raising PyErr_NoMemory() on overflow. Now you rely on PyMem_Malloc() to detect the overflow. I'm not sure that it's a good idea.

    20. JeffreyWalton commented on Sep 12, 2018

      JeffreyWaltonmannequin
      Mannequin

      On Tue, Sep 11, 2018 at 8:26 PM, STINNER Victor <report@bugs.python.org> wrote:

      STINNER Victor <vstinner@redhat.com> added the comment:

      > newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.

      Previously, there was a explicitly check for error raising PyErr_NoMemory() on overflow. Now you rely on PyMem_Malloc() to detect the overflow. I'm not sure that it's a good idea.

      +1. It will probably work as expected on Solaris and other OSes that
      don't oversubscribe memory. It will probably fail in unexpected ways
      on Linux when the allocation succeeds but then the OOM killer hits a
      random process.

      Jeff

    21. sir-sigurd commented on Sep 12, 2018

      sir-sigurdmannequin
      Mannequin

      Now you rely on PyMem_Malloc() to detect the overflow.

      Now overflow is not possible or am I missing something?

    22. vstinner commented on Sep 12, 2018

      @vstinner
      Member

      I asked if there is an issue. In fact, all Python memory allocators start by checking if the size is larger than PY_SSIZE_T_MAX. Example:

      void *
      PyMem_RawMalloc(size_t size)
      {
          /*
           * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes.
           * Most python internals blindly use a signed Py_ssize_t to track
           * things without checking for overflows or negatives.
           * As size_t is unsigned, checking for size < 0 is not required.
           */
          if (size > (size_t)PY_SSIZE_T_MAX)
              return NULL;
          return _PyMem_Raw.malloc(_PyMem_Raw.ctx, size);
      }
    23. vstinner commented on Sep 13, 2018

      @vstinner
      Member

      Benjamin: what do you think of adding an explicit check after the "new_size <<= 1;" loop?

          if (new_size > (size_t)PY_SSIZE_T_MAX) {
              PyErr_NoMemory();
              return -1;
          }

      Technically, PyMem_Malloc() already implements the check, so it's not really needed. So I'm not sure if it's needed :-)

    24. vstinner commented on Oct 19, 2018

      @vstinner
      Member

      New changeset a9274f7 by Victor Stinner (Miss Islington (bot)) in branch '3.6':
      bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) (GH-9199)
      a9274f7

    25. vstinner commented on Oct 19, 2018

      @vstinner
      Member

      New changeset 6665802 by Victor Stinner (Miss Islington (bot)) in branch '3.7':
      bpo-1621: Avoid signed integer overflow in set_table_resize() (GH-9059) (GH-9198)
      6665802

    26. vstinner commented on Oct 19, 2018

      @vstinner
      Member

      Thank you very much to the task force who worked on this issues which can be seen as boring and useless, but are very important nowadays with C compilers which are more and more agressive to optimize everything (I'm looking at you clang!).

      This bug is open for 11 years and dozens and dozens of undefined behaviours have been fixed in the meanwhile.

      This bug is a giant beast with many patches and many pull requests. I dislike such bug, it's very hard to follow them. I suggest to open new bugs for undefined behaviour on specific functions, rather than a very vague "let's open a single bug to track everything".

      It's now time to close the issue.

    27. transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    No one assigned

      Projects

      No projects

        Milestone

        No milestone

        Relationships

        None yet

        Development

        No branches or pull requests

        Issue actions