Thread: Definitive Guide To Integer Overflow.

  1. #1
    Registered User
    Join Date
    May 2016
    Posts
    104

    Definitive Guide To Integer Overflow.

    Hey guys,
    I’ve been struggling to find accurate, complete and reliable information on this topic. At best, I’ve gotten partial truths, but mostly, conflicting advice. My go-to for answers, the complang.c.faq compilation in pdf form, surprisingly doesn’t have anything on this, perhaps an indicator of how little understood the topic is; while The Standard is simultaneously a little too vague and rather too broad in the matter.

    This is what I understand as true:

    Unsigned integers never overflow. Their wrap around behavior is well specified and defined.
    Signed integers can overflow. Depending on the conditions, the overflow can invoke implementation defined or unspecified behavior.

    When does overflow occur?
    *When performing arithmetic operations in which both left and right operands are signed integers -either by nature or promotion- and the result is bigger than the maximum representable value for their size.
    -[+, -, *, /, %, ++, –, <<] and their compound assignment counterparts can overflow.
    -Comparison, bitwise and boolean expressions and their compound assignement counterparts will not result in overflow.

    But what about these cases.

    *Right shifting a signed integer.
    *Right shifting using a negative value as the right hand operand.
    *Assigning a signed int of bigger precision to a lower precision int and assigning an unsigned int greater than INT_MAX to a signed int. In my experience these result in truncation, but is this the “implementation defined” result of an overflow. Or is this specified behavior?

    *The same with casting. I though for a long time that casting an unsigned int to a signed int of the same precision would be a mere reinterpretation of the same underlying bit pattern -at least on a two’s complement machine- and thus completely valid. I’ve faithfully relied on this to do things like: (int32_t)(uint32_t)(int64_t) But after reading conflicting reports, I’m not sure if I’ve been relying on implementation defined behavior and my code might break with the next gcc version.

    *Trap values.

    If you’re confident in your knowledge, I will be eternally grateful if you could shed some light in the matter, or point me to a good source of information.

    Thank you.
    printf("I'm a %s.\n", strrev("Dren"));

  2. #2
    Registered User
    Join Date
    May 2016
    Posts
    104
    If we were to look at overflow as a mere pathway to security issues or other errors like using a negative number as an array index or reading/writing outside a buffer, I would not have any concerns. That is because I explicitly use unsigned for absolutely everything that doesn’t require to be signed and always check for boundaries.

    My concern comes from the undefined behavior of the overflow itself, not of what I might do with the overflowed value later. Will the overflow corrupt the stack, will it overwrite heap memory, will it overwrite another process memory? Will it burn my house and kill my cat?

    Yes, major compilers give well defined, consistent behavior for integer overlow, but not all, and not all document it even when they behave differently under different circumstances, when they can either wrap, act as if overflow never occurs (specially when optimizing) or trap.


    Quick examples of conflicting information I’ve found:

    This is from a very popular and frequented site: “Division and modulo can never generate an overflow”
    Uhm, what about?
    LLONG_MIN / -1
    LLONG_MIN % -1
    Integer overflow - C++ Articles

    Casting an unsigned int with a value bigger than it’s signed counterpart can hold “will result in erroneous behavior” Top answer.
    casting - How to cast or convert an unsigned int to int in C? - Stack Overflow

    Casting and assignment do not result in overflow behavior:
    “Assignment and cast expressions are an exception as they are ruled by the integer conversions” Top answer.
    C integer overflow - Stack Overflow.


    Please, do not take my “If you’re confident in your knowledge” to heart. I am the one without any confidence and full of doubt, that is why I’m asking. And the reason I ask here is because I believe
    there are plenty of people here with vast knowledge and expertise, a couple of whom I admire and appreciate.
    Last edited by Dren; 4 Weeks Ago at 06:45 PM.
    printf("I'm a %s.\n", strrev("Dren"));

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,235
    Quote Originally Posted by Dren
    *Right shifting a signed integer.
    *Right shifting using a negative value as the right hand operand.
    Both of these are directly addressed by the C++ standard:
    Quote Originally Posted by C++11 Clause 5.8 Paragraphs 1 (part), 3
    The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

    The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/(2 raised to the power of E2). If E1 has a signed type and a negative value, the resulting value is implementation-defined.
    So, 2 >> -1 results in undefined behaviour, 2 >> 5 results in zero, and -2 >> 1 has an implementation-defined result.

    Quote Originally Posted by Dren
    *Assigning a signed int of bigger precision to a lower precision int and assigning an unsigned int greater than INT_MAX to a signed int. In my experience these result in truncation, but is this the “implementation defined” result of an overflow. Or is this specified behavior?
    Both of these are also directly addressed by the C++ standard:
    Quote Originally Posted by C++11 Clause 4.7 Paragraph 3
    If the destination type is signed, the value is unchanged if it can be represented in the destination type (and bit-field width); otherwise, the value is implementation-defined.
    So, in your first scenario, it depends on what exactly is the source signed int value: if it can fit in the lower precision int type, then its value remains as-is, but otherwise the value is implementation defined. In your second scenario, the value is implementation defined.

    Quote Originally Posted by Dren
    *The same with casting. I though for a long time that casting an unsigned int to a signed int of the same precision would be a mere reinterpretation of the same underlying bit pattern -at least on a two’s complement machine- and thus completely valid. I’ve faithfully relied on this to do things like: (int32_t)(uint32_t)(int64_t) But after reading conflicting reports, I’m not sure if I’ve been relying on implementation defined behavior and my code might break with the next gcc version.
    A cast basically specifies a type conversion, so the same rule applies: the value is unchanged if it can be represented in the destination signed integer type, otherwise the value is implementation defined.

    To refresh your memory on what the terms mean:
    Quote Originally Posted by C++11 Clause 1.3 (extracted)
    implementation-defined behavior
    behavior, for a well-formed program construct and correct data, that depends on the implementation and that each implementation documents

    undefined behavior
    behavior for which this International Standard imposes no requirements

    unspecified behavior
    behavior, for a well-formed program construct and correct data, that depends on the implementation
    [ Note: The implementation is not required to document which behavior occurs. The range of possible behaviors is usually delineated by this International Standard. — end note ]
    Quote Originally Posted by Dren
    My concern comes from the undefined behavior of the overflow itself, not of what I might do with the overflowed value later. Will the overflow corrupt the stack, will it overwrite heap memory, will it overwrite another process memory? Will it burn my house and kill my cat?
    The overflow from assignment is implementation defined behaviour resulting in an implementation defined value, i.e., it will do none of what you described (or else we have a showstopper compiler bug). What could happen is disaster arising from not accounting for overflow, e.g., assuming that an assignment always preserves the value... but then such mistakes could happen with unsigned integer types too, just that they tend to be easier to predict since the behaviour is specified.

    Note that in the case of mathematical operations, a different rule (i.e., not conversions) applies when we're talking about the final result:
    Quote Originally Posted by C++11 Clause 5 Paragraph 4 (part)
    If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.
    But also keep in mind that integer promotions may apply.
    Last edited by laserlight; 4 Weeks Ago at 04:18 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    May 2016
    Posts
    104
    Thank you dear, you’re an angel.
    You’ve answered my concerns and set me straight on a few misconceptions.

    Although, C++ and C are very different languages and this has been the case for awhile, they still share many similarities at a low level; with the standards even borrowing a few things from the opposite camp on occasion. I don’t doubt most if not all of what you graciously explained pertains to C as much as to C++; I even found the same right-shift section in the C standard almost verbatim, after going back to it, inspired by your post.

    Although there are ways to minimize it, I guess for the time being it is hard to completely avoid implementation-defined behavior in certain scenarios. The best one can do is be aware of the circumstances, and plan accordingly; knowing there are options at our disposal such as -fwrapv and -ftrapv flags which can help control the outcome, at least on gcc.

    I hope this thread, thanks to laserlight's detailed explanations, can help others with the same questions I had. Here are a couple of links which might be of use to you.

    Using the GNU Compiler Collection (GCC): Code Gen Options
    https://www.cs.utah.edu/~regehr/papers/overflow12.pdf
    Last edited by Dren; 4 Weeks Ago at 08:17 AM.
    printf("I'm a %s.\n", strrev("Dren"));

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,235
    Oh dear, my apologies, my turn to not see that this was posted in the C programming forum. The C++11 rules are likely to be consistent with C99 though as that's the C++11 reference for constructs inherited from C.

    If you want the latest and greatest you'll have to check C18, but from what I understand C18 is a minor update to C11, so if you've checked C11 and found it to be consistent with what I mentioned, then you should be good to go. It's very likely that this kind of behaviour hasn't changed between C99 and C11.
    Last edited by laserlight; 4 Weeks Ago at 02:00 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Signed integer overflow - undefined behaviour
    By MartinR in forum C Programming
    Replies: 3
    Last Post: 01-21-2019, 02:39 PM
  2. Replies: 5
    Last Post: 04-14-2009, 09:09 PM
  3. integer overflow
    By John Connor in forum C Programming
    Replies: 11
    Last Post: 02-11-2008, 05:30 PM
  4. how to handle integer overflow in C
    By kate1234 in forum C Programming
    Replies: 8
    Last Post: 04-23-2003, 12:20 PM
  5. the definitive guide to code commenting
    By Aran in forum C++ Programming
    Replies: 5
    Last Post: 09-16-2002, 01:43 PM

Tags for this Thread