2
Vote

integer overflows

description

I've been tracking down some integer overflows in Firefox and seem to have narrowed some of them down to the SafeInt library.
 
As an example, the "a = -a;" assignment at SafeInt3.hpp:2102 is sometimes invoked while a has value INT_MIN. Of course, negating INT_MIN is undefined behavior in C++98 and C++11.
 
To reproduce, change the code like this:
 
   if( a < 0 )
    {
  if (a==INT_MIN) printf ("oops!\n");
       a = -a;
       fIsNegative = true;
    }
 
Then run MultVerify(). Here is what I get:
 
[regehr@gamow safeint]$ g++ -O -w TestMain.cpp MultVerify.cpp -o TestMain
[regehr@gamow safeint]$ ./TestMain
oops!
oops!
oops!
oops!
oops!
oops!
 
This is 3.0.16p. There are some other overflows in SafeInt, please let me know if you are interested in bug reports about them.

comments

regehr wrote Sep 22, 2011 at 3:21 AM

I got SafeInt to malfunction due to this undefined behavior by writing this test code:

void test (__int32 a, __int64 b) {
__int32 ret;
bool res = SafeMultiply (a, b, ret);
if (res) {
printf ("%d * %lld = %d\n", a, b, ret);
} else {
printf ("%d * %lld = INVALID\n", a, b);
}
}

int main (void)
{
test (INT_MIN, -2);
test (INT_MIN, -1);
test (INT_MIN, 0);
test (INT_MIN, 1);
test (INT_MIN, 2);
return 0;
}

Now, watch the answer change as the optimization options are changed:

regehr@home:~/embedded_papers/john/overflow12/safeint$ current-g++ -O1 john_test.cpp ; ./a.out
-2147483648 * -2 = INVALID
-2147483648 * -1 = INVALID
-2147483648 * 0 = 0
-2147483648 * 1 = -2147483648
-2147483648 * 2 = INVALID
regehr@home:~/embedded_papers/john/overflow12/safeint$ current-g++ -O2 john_test.cpp ; ./a.out
-2147483648 * -2 = INVALID
-2147483648 * -1 = INVALID
-2147483648 * 0 = 0
-2147483648 * 1 = INVALID
-2147483648 * 2 = INVALID

This is using today's pre-4.7 G++ snapshot on Ubuntu Linux. Behavior is consistent across x86 and x64.

Basically the current version of SafeInt needs to be compiled with -fwrapv or equivalent in order to function correctly. Of course, not all compilers support such an option.

regehr wrote Sep 22, 2011 at 3:03 PM

Below, the full list of integer undefined behaviors seen while running *Verify.cpp.

UNDEFINED at <./SafeInt3.hpp, (2102:16)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2120:25)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2148:16)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2166:25)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2252:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2258:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2269:29)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2305:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2311:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2322:25)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2356:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2367:29)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2400:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2411:25)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2448:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2465:29)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2499:17)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2505:17)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2516:25)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2565:17)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2571:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2582:29)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2629:17)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2635:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2646:25)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2679:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2690:29)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2718:18)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (2729:29)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (3798:44)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (3826:44)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (3855:36)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <./SafeInt3.hpp, (3878:36)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <./SafeInt3.hpp, (4539:62)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (4570:62)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (4652:27)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (4678:27)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (4782:36)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (4842:36)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (6519:43)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (6521:25)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (868:34)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <./SafeInt3.hpp, (878:34)> : Op: -, Reason : Signed Subtraction Overflow

dcleblanc wrote Sep 22, 2011 at 11:36 PM

Thanks for looking into this. I hadn't previously considered -MIN_INT to be something that a compiler would get overly ambitious about optimizing.

At the moment, I think the scope of the problem is largely when MIN_INT is passed as a compile-time constant to SafeInt. We're working on an update that will resolve the problem.

dcleblanc wrote Sep 23, 2011 at 7:14 AM

This issue should be addressed by the 3.0.17 release. Note to consumers - 3.0.17 is still considered a beta. It is strongly recommended that if you are using a compiler which aggressively optimizes that you also enable (and pay attention to) the warnings that it is removing code.

Sign in to add a comment or to set email notifications