Best way to detect integer overflow in C/C++

末蓝、 2022-05-25 11:08 178阅读 0赞

**原帖: **[http://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflow-in-c-c][http_stackoverflow.com_questions_199333_best-way-to-detect-integer-overflow-in-c-c]

\-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

I was writing a program in C++ to find all solutions of ab = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and ran a digit-counting routine each time on a, b andab to check if the digits condition was satisfied.

However, spurious solutions can be generated when ab overflows the integer limit. I ended up checking for this using code like:

unsigned long b, c, c_test; ... c_test=c*b;         // Possible overflow if (c_test/b != c) { /* There has been an overflow*/} else c=c_test;      // No overflow

Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.

=================================================================================================================

Information which may be useful on this subject:

Chapter 5 of "Secure Coding in C and C++" by Seacord

*  [http://www.informit.com/content/images/0321335724/samplechapter/seacord\_ch05.pdf][http_www.informit.com_content_images_0321335724_samplechapter_seacord_ch05.pdf]

SafeInt classes for C++

*  [http://blogs.msdn.com/david\_leblanc/archive/2008/09/30/safeint-3-on-codeplex.aspx][http_blogs.msdn.com_david_leblanc_archive_2008_09_30_safeint-3-on-codeplex.aspx]
 *  [http://www.codeplex.com/SafeInt][http_www.codeplex.com_SafeInt]

IntSafe library for C:

*  [http://blogs.msdn.com/michael\_howard/archive/2006/02/02/523392.aspx][http_blogs.msdn.com_michael_howard_archive_2006_02_02_523392.aspx]

=================================================================================================================

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

bool addition_is_safe(uint32_t a, uint32_t b) {     size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);     return (a_bits<32 && b_bits<32); }

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

bool multiplication_is_safe(uint32_t a, uint32_t b) {     size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);     return (a_bits+b_bits<=32); }

Similarly, you can estimate the maximum size of the result of `a` to the power of `b` like this:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {     size_t a_bits=highestOneBitPosition(a);     return (a_bits*b<=32); }

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

size_t highestOneBitPosition(uint32_t a) {     size_t bits=0;     while (a!=0) {         ++bits;         a>>=1;     };     return bits; }

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the `highestOneBitPosition` function, but it might (especially if you knew how many bits were in the operands beforehand).

=================================================================================================================

I see you're using unsigned integers. By definition, in C (don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)

With signed integers, once there has been overflow, [Undefined Behaviour][] has occurred and your program can do anything (for example: render tests inconclusive).

#include <limits.h> int a = <something>; int x = <something>; a += x;              /* UB */ if (a < 0) {         /* unreliable test */   /* ... */ }

To create a conforming program you need to test for overflow before generating said overflow. The method can be used with unsigned integers too

#include <limits.h> int a = <something>; int x = <something>; if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */; if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */; /* ... same thing for subtraction, multiplication, and division */

=================================================================================================================

The simplest way is to convert your `unsigned long`s into `unsigned long long`s, do your multiplication, and compare the result to 0x100000000LL.

You'll probably find that this is more efficient than doing the division as you've done in your example.

Oh, and it'll work in both C and C++ (as you've tagged the question with both).

--------------------

Just been taking a look at the [glibc manual][]. There's a mention of an integer overflow trap (`FPE_INTOVF_TRAP`) as part of `SIGFPE`. That would be ideal, apart from the nasty bits in the manual:

> `FPE_INTOVF_TRAP` Integer overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).

A bit of a shame really.

=================================================================================================================

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.

You could also test for the possibility of overflow before you perform the multiplication:

if ( b > ULONG_MAX / a ) // a * b would overflow

=================================================================================================================

Warning: GCC can optimize away an overflow check when compiling with `-O2`. The option `-Wall` will give you a warning in some cases like

if (a + b < a) { /* deal with overflow */ }

but not in this example:

b = abs(a); if (b < 0) { /* deal with overflow */ }

The only safe way is to check for overflow before it occurs, as described in the [CERT paper][], and this would be incredibly tedious to use systematically.

Compiling with `-fwrapv` solves the problem but disables some optimizations.

We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.

=================================================================================================================

If you have a datatype which is bigger than the one you want to test (say a you do a 32-bit add and you have a 64-bit type). Then this will detect if an overflow occured. My example is for an 8-bit add. But can be scaled up.

uint8_t x, y;   /* give these values */ const uint16_t data16   = x + y; const bool carry        = (data16 > 0xff); const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

It is based on the concepts explained on this page:[http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html][http_www.cs.umd.edu_class_spring2003_cmsc311_Notes_Comb_overflow.html]

For a 32-bit example, `0xff` becomes `0xffffffff` and `0x80` becomes `0x80000000` and finally `uint16_t`becomes a `uint64_t`.

NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves powers. In which case, division is likely the best approach. This is commonly a way that `calloc` implementations make sure that the params don't overflow as they are multiplied to get the final size.

=================================================================================================================

[http_stackoverflow.com_questions_199333_best-way-to-detect-integer-overflow-in-c-c]: http://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflow-in-c-c
[http_www.informit.com_content_images_0321335724_samplechapter_seacord_ch05.pdf]: http://www.informit.com/content/images/0321335724/samplechapter/seacord_ch05.pdf
[http_blogs.msdn.com_david_leblanc_archive_2008_09_30_safeint-3-on-codeplex.aspx]: http://blogs.msdn.com/david_leblanc/archive/2008/09/30/safeint-3-on-codeplex.aspx
[http_www.codeplex.com_SafeInt]: http://www.codeplex.com/SafeInt
[http_blogs.msdn.com_michael_howard_archive_2006_02_02_523392.aspx]: http://blogs.msdn.com/michael_howard/archive/2006/02/02/523392.aspx
[Undefined Behaviour]: http://en.wikipedia.org/wiki/Undefined_behavior
[glibc manual]: http://www.gnu.org/software/libc/manual/html_node/Program-Error-Signals.html#Program%20Error%20Signals
[CERT paper]: https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false
[http_www.cs.umd.edu_class_spring2003_cmsc311_Notes_Comb_overflow.html]: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html