Skip to content

Overflows in SafeInt

Update from Friday 9/23: The SafeInt developers have already uploaded a new version that fixes the problems described in this post. Nice!

I have a minor obsession with undefined behaviors in C and C++. Lately I was tracking down some integer overflows in Firefox — of which there are quite a few — and some of them seemed to originate in the well-known SafeInt library that it uses to avoid performing unsafe integer operations. Next, I poked around in the latest version of SafeInt and found that while executing its (quite good) test suite there are 43 different places in the code where an undefined integer operation is performed. A substantial number of them stem from code like this:

bool negative = false;
if (a<0) {
  a = -a;
  negative = true;
}

... assume a is positive ...

if (negative) {
  return -result;
} else {
  return result;
}

To see a real example of this, take a look at the code starting at line 2100 of SafeInt3.hpp. The problem here, of course, is that for the most common choices of implementation-defined behaviors in C++, negating INT_MIN is an undefined behavior.

Now we have to ask a couple of questions. First, does this code operate properly if the compiler happens to implement -INT_MIN using 2′s complement arithmetic? I’m not sure about all of the overflows in SafeInt, but I believe this function actually does work in that case. The second question is, do compilers (despite not being required to do so) give 2′s complement semantics to -INT_MIN? Every compiler I tried has this behavior when optimizations are disabled. On the other hand, not all compilers have this behavior when optimizations are turned on. A simple test you can do is to compile this function with maximum optimization:

void bar (void);

void foo (int x) {
 if (x<0) x = -x;
 if (x<0) bar();
}

If the resulting assembly code contains no call to bar(), then the compiler has (correctly) observed that every path through this function either does not call bar() or else relies on undefined behavior. Once the compiler sees this, it is free to eliminate the call to bar() as dead code. Most of the compilers I tried — even ones that are known to exploit other kinds of integer undefined behavior — don’t perform this optimization. However, here’s what I get from a recent GCC snapshot:

[regehr@gamow ~]$ current-gcc -c -O2 overflow2.c        
[regehr@gamow ~]$ objdump -d overflow2.o
0000000000000000 <foo>:
 0:    f3 c3                    repz retq 

Now, does this same optimization ever fire when compiling SafeInt code, causing it to return a wrong result? Here’s a bit of test code:

#include <cstdio>
#include <climits>
#include "SafeInt3.hpp"

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;
}

Next we compile it with the recent g++ at a couple of different optimization levels and run the resulting executables:

[regehr@gamow safeint]$ current-g++ -O1 -Wall safeint_test.cpp
[regehr@gamow safeint]$ ./a.out
-2147483648 * -2 = INVALID
-2147483648 * -1 = INVALID
-2147483648 * 0 = 0
-2147483648 * 1 = -2147483648
-2147483648 * 2 = INVALID
[regehr@gamow safeint]$ current-g++ -O2 -Wall safeint_test.cpp
[regehr@gamow safeint]$ ./a.out
-2147483648 * -2 = INVALID
-2147483648 * -1 = INVALID
-2147483648 * 0 = 0
-2147483648 * 1 = INVALID
-2147483648 * 2 = INVALID

The first set of results is correct. The second set is wrong for the INT_MIN * 1 case, which should not overflow. Basically, at -O2 and higher gcc and g++ turn on optimization passes that try to generate better code by taking integer undefined behaviors into account. Let’s be clear: this is not a compiler bug; g++ is simply exploiting a bit of leeway given to it by the C++ standards.

What can we take away from this example?

  • It’s a little ironic that the SafeInt library (a widely used piece of software, and not a new one) is itself performing operations with undefined behavior. This is not the only safe math library I’ve seen that does this — it is simply very hard to avoid running afoul of C/C++’s integer rules, particularly without good tool support.
  • It’s impressive that G++ was able to exploit this undefined behavior. GCC is getting to be a very strongly optimizing compiler and also SafeInt was carefully designed to not get in the way of compiler optimizations.

If you have security-critical code that uses SafeInt to manipulate untrusted data, should you be worried? Hard to say. I was able to get SafeInt to malfunction, but only in a conservative direction (rejecting a valid operation as invalid, instead of the reverse) and only using a recent G++ snapshot (note that I didn’t try a lot of compilers — there could easily be others that do the same thing). Also, there are 42 more integer overflow sites that I didn’t look at in detail. One way to be safe would be to use GCC’s -fwrapv option, which forces 2′s complement semantics for signed integer overflows. Clang also supports this option, but most other compilers don’t have an equivalent one. Also unfortunately, SafeInt is structured as a header file instead of a true library, so it’s not like just this one file can be recompiled separately.

This issue has been reported here.

Update: I checked CERT’s IntegerLib (download here) and it is seriously broken. Its own test suite changes behavior across -O0 … -O3 for each of Clang, GCC, and Intel CC. The undefined behaviors are:

UNDEFINED at <add.c, (24:12)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (24:28)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (29:12)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (43:14)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (43:30)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (47:14)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (61:12)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (61:28)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <add.c, (65:15)> : Op: +, Reason : Signed Addition Overflow
UNDEFINED at <mult.c, (52:13)> : Op: *, Reason : Signed Multiplication Overflow
UNDEFINED at <mult.c, (69:47)> : Op: *, Reason : Signed Multiplication Overflow
UNDEFINED at <sub.c, (24:23)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <sub.c, (28:12)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <sub.c, (42:23)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <sub.c, (46:12)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <sub.c, (60:23)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <sub.c, (64:12)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <unary.c, (28:9)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <unary.c, (37:9)> : Op: -, Reason : Signed Subtraction Overflow
UNDEFINED at <unary.c, (46:9)> : Op: -, Reason : Signed Subtraction Overflow

I cannot imagine this library is suitable for any purpose if you are using an optimizing compiler.

Update from Friday 9/23: I looked into the problems in IntegerLib in more detail. The different output across different compilers and optimization levels isn’t even due to the integer problems — it’s due to the fact that a couple of functions have no “return” statement, and therefore return garbage. Do not use IntegerLib! Use SafeInt.

{ 8 } Comments

  1. Jason Orendorff | September 22, 2011 at 12:44 pm | Permalink

    I appreciate your work on this, but I think the inescapable conclusion is that allowing simple arithmetic on signed integers to trigger undefined behavior is clearly unworkable.

    In practice, it means that nobody can write safe code. Surely nobody is much better at writing careful integer code than the SafeInt authors. Even with stellar tool support, we will not find all the bugs—or even fix all the bugs that could be found.

    I’ve read about the neato ways compilers can take advantage of this rule, but I have yet to see any example where the optimization actually seemed desirable. It usually amounts to taking code that is apparently intended to do one thing, and using the accidental undefined behavior as an excuse to rewrite the code to do something completely different and unexpected (but fast). The more you break the rule, the faster your code can do the wrong thing. Isn’t that something.

    Ideally, in my view, you could direct your obvious talents to more deserving problems. But if the outcome here is that the C++ committee agrees enough is enough and specifies two’s complement, it will have been worth it!

  2. regehr | September 22, 2011 at 12:51 pm | Permalink

    Hi Jason, the examples people have told me about where undefined signed overflow is useful involve loop-intensive numerical codes where, for example, it is highly advantageous to be able to assume that an increasing induction variable never goes negative. Apparently 30%-50% speedups on certain loops are not unheard of.

    But of course you are right: this part of the C standard gives zero benefit to 99.9% of C/C++ developers and causes significant pain for some fraction of them. I don’t see the standards committees changing this — the languages will die first.

  3. Anonymous Cowherd | September 22, 2011 at 9:05 pm | Permalink

    @regehr#2: The committee could usefully mandate “two’s-complement” while still allowing the result of INT_MAX+1 to be undefined. In my opinion, a two’s-complement mandate would include finally giving a definition to at least the following behaviors:

    * Right-shifting a signed value (by 0<=n<width, at least).

    * Performing bitwise operations on signed values.

    They could mandate all that and just decide to leave the "school-arithmetic" operations undefined. Wouldn't really help with the problem at hand, but at least it would be helpful to people such as yourself who care about the semantics of the language.

  4. Anonymous Cowherd | September 22, 2011 at 9:13 pm | Permalink

    And @post: It strikes me as just outrageous that SafeInt and IntegerLib exist at all, if their creators couldn’t be bothered to check for obvious overflow conditions. Jason’s takeaway was “SafeInt authors are experts, therefore it’s impossible to use C++ safely”. My takeaway is the contrapositive of that: “SafeInt seems like an obvious idea, but its authors somehow managed to screw up the implementation, therefore SafeInt’s authors are idiots.”

    I took a quick look at the code, but it seemed way over-templatized. For someone who wanted a solid “safe integer” class, it seems easier to throw it out and start from scratch than to try fixing all the bugs that might exist in there.

    (And yeah, I know about template metaprogramming… but SafeInt isn’t a template-meta- type of class; it’s a traditional class with overloaded operators and stuff. That doesn’t seem like it would actually fold away at compile time without an aggressive inliner, and if you have an aggressive inliner you can dispense with most of that template junk.)

  5. argp | September 23, 2011 at 1:31 am | Permalink

    g++ from gcc 4.6.1 does not exhibit the suggested behavior with -O2 optimization enabled.

  6. maht | September 23, 2011 at 5:06 am | Permalink

    Plan9 prints

    void
    main(void) {
    long x = -2147483648L;
    if(x<0) x = -x;
    if(x<0) print("X %ld\n", x);
    }

  7. regehr | September 23, 2011 at 1:30 pm | Permalink

    AC, I agree that C/C++ would lose little by mandating 2′s complement. I’m guessing there are a few DSPs or similar that are not 2′s complement, but I have no idea if any such architectures are still actively targeted by C compilers.

    Re. the templates, I’m happily ignorant about C++ design. The language fills no niche in my programming life. Efficiency wise, clang++, g++, and Intel C++ seem to see through all the templates.

  8. Jeffrey Walton | September 24, 2011 at 5:34 am | Permalink

    Thanks for the insightful article.

    As a SafeInt user, I tend to feel much like Orendorff (and disagree with Cowherd). I would even take it a bit further: the C++ committee and its abstract machine with unlimited precision which never overflows is a majority of the problem. Its absurd that math is well defined until a result overflows or wraps (after the fact!).

    GCC aggravates the problem by complying with the standard but ignoring the practical issues of wrap and overflow. Ie, GCC does not offer primitives or intrinsics to detect overflow or wrap efficiently via hardware supported mechanisms (ie, FLAGS/EFLAGS in the x86 family, and PSR on ARMs).

    Unlike Linus Torvalds, I don’t feel like “GCC is crap” [1]. But I would like something better to deal with the problem other than -fwrapv and -fno-strict-overflow [2].

    JW, Baltimore, MD, US

    [1] http://linux.derkeiler.com/Mailing-Lists/Kernel/2006-11/msg08325.html
    [2] http://www.airs.com/blog/archives/120