C++ Integer Overflow

C integer overflow

Integer overflows are undefined behavior in C.

C says an expression involving integers overflows, if its result after the usual arithmetic conversions is of a signed typed and cannot be represented in the type of the result. Assignment and cast expressions are an exception as they are ruled by the integer conversions.

Expressions of unsigned type cannot overflow, they wrap, e. g., 0U - 1 is UINT_MAX.

Examples:

INT_MAX + 1    // integer overflow
UINT_MAX + 1   // no overflow, the resulting type is unsigned
(unsigned char) INT_MAX // no overflow, integer conversion occurs 

Never let any integer expression overflows, modern compilers (like gcc) take advantage of integer overflows being undefined behavior to perform various types of optimizations.

For example:

a - 10 < 20

when a is of type int after promotion, the expression is reduced in gcc (when optimization are enabled) to:

a < 30

It takes advantage of the expression being undefined behavior when a is in the range INT_MIN + 10 - 1 to INT_MIN.

This optimization could not be done when a is unsigned int because if a is 0, then a - 10 has to be evaluated as UINT_MAX - 9 (no undefined behavior). Optimizing a - 10 < 20 to a < 30 would then lead to a different result than the required one when a is 0 to 9.

Generally, How do I prevent integer overflow from happening in C language?

Whenever you declare an integer variable:

1. Actually consider how large/small a number it will ever contain.
2. Actually consider if it needs to be signed or unsigned. Unsigned is usually less problematic.
3. Pick the smallest type of intn_t or uintn_t types from stdint.h that will satisfy the above (or the ...fast_t etc flavours if you wish).
4. If needed, come up with integer constants that contain the maximum and/or minimum value the variable will hold and check against those whenever you do arithmetic.

That is, don't just aimlessly spam int all over your code without a thought.

Signed types can be problematic for other reasons than overflow too, namely whenever you need to do bitwise arithmetic. To avoid over/underflow and accidental signed bitwise arithmetic, you also need to know of the various implicit integer type promotion rules.

---

Is integer overflow going to get me hacked like buffer overflow or etc?

Not really, but any bug can of course be exploited if someone is aware of it - as you can see in almost every single computer game.

How to detect integer overflow in C

You can predict signed int overflow but attempting to detect it after the summation is too late. You have to test for possible overflow before you do a signed addition.

It's not possible to avoid undefined behaviour by testing for it after the summation. If the addition overflows then there is already undefined behaviour.

If it were me, I'd do something like this:

#include <limits.h>

int safe_add(int a, int b) 
{
    if (a >= 0) {
        if (b > (INT_MAX - a)) {
            /* handle overflow */
        }
    } else {
        if (b < (INT_MIN - a)) {
            /* handle underflow */
        }
    }
    return a + b;
}

Refer this paper for more information. You can also find why unsigned integer overflow is not undefined behaviour and what could be portability issues in the same paper.

EDIT:

GCC and other compilers have some provisions to detect the overflow. For example, GCC has following built-in functions allow performing simple arithmetic operations together with checking whether the operations overflowed.

bool __builtin_add_overflow (type1 a, type2 b, type3 *res)
bool __builtin_sadd_overflow (int a, int b, int *res)
bool __builtin_saddl_overflow (long int a, long int b, long int *res)
bool __builtin_saddll_overflow (long long int a, long long int b, long long int *res)
bool __builtin_uadd_overflow (unsigned int a, unsigned int b, unsigned int *res)
bool __builtin_uaddl_overflow (unsigned long int a, unsigned long int b, unsigned long int *res)
bool __builtin_uaddll_overflow (unsigned long long int a, unsigned long long int b, unsigned long long int *res)

Visit this link.

EDIT:

Regarding the question asked by someone

I think, it would be nice and informative to explain why signed int overflow undefined, whereas unsigned apperantly isn't..

The answer depends upon the implementation of the compiler. Most C implementations (compilers) just used whatever overflow behaviour was easiest to implement with the integer representation it used.

In practice, the representations for signed values may differ (according to the implementation): one's complement, two's complement, sign-magnitude. For an unsigned type there is no reason for the standard to allow variation because there is only one obvious binary representation (the standard only allows binary representation).

Signed integer overflow

        if(nums[i] < target){
            count_elem += 1;
            working_array[count_elem] = nums[i];     
        }

Off-by-one error. This initializes working_array[1], working_array[2], ... potentially up to working_array[numsSize] which would be out of bounds. Meanwhile, working_array[0] is never initialized and contains garbage, which is probably the garbage value that provokes your overflow.

Make it:

        if(nums[i] < target){
            working_array[count_elem] = nums[i];     
            count_elem += 1;
        }

or perhaps

        if(nums[i] < target){
            working_array[count_elem++] = nums[i];     
        }

---

Also, as noted above,

    returnSize = sizeof(int)*2;
    int *result_array = (int*)malloc(returnSize);

is wrong because returnSize is a pointer. If the idea is to return the size by reference, then you want

    *returnSize = sizeof(int)*2;
    int *result_array = (int*)malloc(*returnSize);

c++ Integer overflow in spite of using unsigned int and modulo operations

Basically problem is you have integer overflow just after multiplication.

To overcome this problem you have to approach topic using one of two solutions.

• use integer type which can hold a result of such magnitude, for example: unsigned long long int
• use algorithm which is able to do that calculation without integer overflow
  (for that I can't find good and simple document in English)

Using second approach:

constexpr unsigned mutiplyModulo(unsigned a, unsigned b, unsigned n)
{
    unsigned m = 1, w = 1;

    while (m) {
        if (b & m)
            w = (w + a) % n;
        a = (a << 1) % n;
        m <<= 1;
    }
    return w;
}

constexpr unsigned int intpow(unsigned int x, unsigned int n)
{
    unsigned int r = 1;
    while (n) {
        if (n & 1)
            r *= x;
        x *= x;
        n /= 2;
    }
    return r;
}

unsigned int foo(unsigned int orders)
{
    constexpr auto mod = intpow(10u, 9u) + 7u;
    unsigned int total = mutiplyModulo(orders, orders + 1, mod);
    total /= 2;
    return total;
}

https://godbolt.org/z/ePW7WxcTe

Integer overflow not overflowing?

As has been noted in the comments, signed integer overflow is undefined behavior in C.

The game's version of the program was apparently built with a compiler that handles it naively: by actually adding 1 to impossible_number (using ordinary two's-complement addition), then comparing the result with impossible_number and executing the fopen if it's less. In that case inputting 2147483647 works, as you saw. In my tests, clang without optimizations behaves like this.

But there are other possibilities. For instance, recent versions of GCC, even with -O0, notice that the test can't be true in any case when overflow doesn't occur. And if overflow does occur, the behavior is undefined, and so the compiler is at perfect liberty to do whatever it likes in that case. So it is allowed to assume that the test can't ever be true, and that's what it does: it optimizes away the entire if block, including the test itself which is now redundant. Try on godbolt; note that the generated assembly contains no call to fopen at all. So this program compiled with GCC is not vulnerable. The same is true for clang if optimizations are enabled (-O1 or higher).

(You can force the "naive" behavior in either compiler by compiling with -fwrapv. There is also -ftrapv which forces the program to abort if signed integer overflow ever occurs; it has a substantial runtime performance cost, but might be desirable when security is critical.)

Thus for an attack like this, you have to not only read the source code of the vulnerable program, but also be able to discover or guess what is in the compiled code that the victim is actually using.

Still unsure about signed integer overflow in C++

[expr.pre.incr]/1

The expression ++x is equivalent to x+=1.

[expr.ass]/6

The behavior of an expression of the form E1 op= E2 is equivalent to E1 = E1 op E2 except that E1 is evaluated only once.

But x = x + 1 is not UB (integer promotion and narrowing integer conversion), so the original is well-formed. Therefore, GCC is wrong.

---

Related Topics