Solutions to Integer Overflow

http://blog.regehr.org/archives/1401

by deafcalculus • 10 years ago

86 49 10 years ago

blog.regehr.org

morecoffee• 10 years ago

The Rust developers have adopted a hybrid solution where integer overflows trap in debug builds and wrap in optimized builds.

This is not a solution. The production binaries and the test binaries run on different data. We try as programmers and release engineers to try to get the test environment to match production, but it's hard to do right, and takes constant upkeep.

Trapping should be the default, and disabled only by special user intent, which optimization flags are not.

dbaupp2• 10 years ago

Many (maybe most) languages are OK with changing behaviour/code between debug and release builds, e.g. disabling `assert`s and even the optimisations themselves. Of course, this is suboptimal in some cases, and thus providing a way to disable it is good and thus rustc has -C debug-assertions=on, and a currently-unstable flag to control just the overflow checks themselves. Seguing from that first flag, Rust makes it explicit when an assertion is OK to omit by providing both debug_assert! (removed in release) and assert! (never removed), so I guess Rust is in a middle ground that's the reverse of the middle ground of a language like, say, Swift, which removes assertions but not overflow checks in its default optimised build.

SamReidHughes5• 10 years ago

Swift has release-mode assertions, they're done with precondition().

pcwalton2• 10 years ago

Trapping should be the default, and disabled only by special user intent, which optimization flags are not.

At the cost of making programs slower. For every comment like this we would have 5 comments asking why Rust is slower than C++.

Besides, the real solution is memory safety, which Rust does not compromise. Memory safety stops the vast majority of overflow issues from becoming security problems.

justinlardinois3• 10 years ago

[Bignum] isn’t yet implemented widely enough, but happily there are plenty of languages such as Python that give bignums by default.

This was news to me, and when I looked it up I found out why: that's only the case in Python 3. Python 2 has a type called int that's implemented as a C long and a type called long that's a bignum [0]; Python 3 just has the latter and it's called int [1].

[0] https://docs.python.org/2/library/stdtypes.html#numeric-type...

[1] https://docs.python.org/3/library/stdtypes.html#numeric-type...

Dylan168074• 10 years ago

They both give you bignums by default. They only differ slightly in implementation.

  Python 2.7.6 (default, Jun 22 2015, 17:58:13)
  [GCC 4.8.2] on linux2
  Type "help", "copyright", "credits" or "license" for more information.
  >>> type(10)
  <type 'int'>
  >>> type(10 ** 100)
  <type 'long'>

justinlardinois3• 10 years ago

Well, not quite. The documentation summarizes what your experiment showed.

Unadorned integer literals (including binary, hex, and octal numbers) yield plain integers unless the value they denote is too large to be represented as a plain integer, in which case they yield a long integer.

0xmohit• 10 years ago

One of the numeric types `Integer` in Haskell prelude is an integer with unlimited precision.

https://wiki.haskell.org/Learn_Haskell_in_10_minutes#Simple_...

SamReidHughes5• 10 years ago

Using bignums means that arithmetic operations would have to check their arguments for whether they're bignums and also check the result for overflow, and that's going to be a lot worse than some branch-on-OF, which I'd think any sane CPU should statically predict not to be taken. The needs for things like array indexes, sizes of things, and other stuff that isn't in-band user data, these janitorial integer values, are such that you don't need (or want) bignums for them.

If I ruled the universe, I would declare overflow-checked signed and unsigned types to be the ordinary numeric types, and then in-band user values -- the data the program's written to work with, like coordinates of stuff in video games, values in spreadsheets, data in strings that is going through a crypto algorithm -- are the sort of thing that would deviate from the ordinary. They might use bignums, or floats or doubles or float128's, or unchecked 2's complement integer types, depending on the needs of correctness and performance.

Most of the operations on janitorial integers can have the overflow checks be optimized away, anyway. On one 20k line C program I counted, and I forget the exact number of arithmetic operations where (1) the overflow check would be gratuitous and (2) where omitting the overflow check wasn't a trivial optimization, was less than 10.

(Edited to make clear I was talking about gratuitous checks, by which I mean the overflow check would provably never catch overflow, and where a human programmer might feel bad about doing the wasteful check. There were less than 10 provably unnecessary overflow checks that were not "trivially" provable. One example of an overflow check I would not consider gratuitous is a doubling in capacity of a std::vector<T> when adding an element, or multiplying by a sizeof before a malloc. It could be theoretically provable if you bound other integers globally that such an overflow could never happen, but a human editing the code would be OK with the check and its performance implications.)

junke• 10 years ago

That's the case in practice (both the internal limits and the optimizations). For example Common Lisp's ARRAY-TOTAL-SIZE-LIMIT is a fixnum. The default numeric type is not bignum, however, the numeric tower is here to use them only when needed.

SamReidHughes5• 10 years ago

That distinction is a common lisp-ism. A "bignum" implementation in the context of this article won't allocate for the small values.

Dylan168074• 10 years ago

Why is having two never-taken branches worse than one never-taken branch?

SamReidHughes5• 10 years ago

Three, not two.

And it will be worse because the two extra are checks that'll require a test instruction too, instruction cache overhead, sometimes a shift to line up the bits right.

SamReidHughes5• 10 years ago

Using bignums means that arithmetic operations would have to check their arguments for whether they're bignums and also check the result for overflow,

This is a bit thoughtless because you could code generate two parallel sides of a function -- one where everything is a small-value and you only need to check for overflow after the fact, and one where some values are big-values. The small-value side of the function then jumps to the big-value side once an overflow happens. The only overhead on the small-value side is that after calling a function that returns a bignum, the return value has to be tested to confirm that it's a small-value. Functions can also have separate entry points for when all parameters are known to be a small-value, versus when they're not.

ScottBurson• 10 years ago

Surprised no one has mentioned the TADDCC instruction that Sun put in the 32-bit SPARC ISA for Franz Lisp, short for "Tagged ADD and set Condition Codes". This instruction, along with performing a normal add, would also set the overflow bit if the two low-order bits of either operand were nonzero. Thus it had baked in the assumption that the fixnum tag was 00. A subsequent instruction could branch on the overflow bit to the bignum/overflow handler, or if the implementor wanted to use a trap instead, there was the TADDCCTV variant that also trapped on overflow.

The 64-bit SPARC ISA has no such instruction. I guess it was concluded that a superscalar CPU could do well enough with a short sequence of general-purpose instructions, and it was better not to build in assumptions as to how a Lisp implementation would want to represent numbers, and Lisp was no longer very commercially important anyhow at that point in Sun's existence.

Anyway, if I ruled the universe, I would declare arbitrary-precision integers to be the default, but provide ways for the programmer to turn off the overflow check for specific operations as needed. This is exactly what Common Lisp does, though its notation for suppressing the check is rather verbose.

legulere3• 10 years ago

worse than C and C++’s UB-on-overflow which at least permits an implementation to trap.

That's only true for signed integers, overflow is defined as wrapping for unsigned integers.

And even with signed integers the compilers handle it way worse than wrapping: When LLVM finds a overflow that will always happen, it won't report it (Only Clang will do that, but that's before any optimisations and thus can see far less) and optimize it to a `undef` value. The backend subsequently will treat the `undef` value like it's in all registers. If you make a function call with an `undef` value you will pass what's in the register used according to the calling convention before. This can be a pointer that will be leaking info about ASLR or a register that can contain user controlled information.

As an example compile this with optimisations (should work the same with signed integer overflow):

    #include <stdio.h>
    
    int main(int argc, char ** argv) {
      int a = 1;
      int b = 0;
      printf("%d", a/b);
    }

This prints some ASLR-protected pointer which you can use to calculate the offset, which allows you to break ASLR. I haven't seen this attack mentioned before and it's probably extremely unlikely to happen in the wild, but it's possible.

I also found the article lacking because it doesn't talk about saturation arithmetics: https://en.wikipedia.org/wiki/Saturation_arithmetic Rust offers some functions for it and it can often be less problematic than wrapping, for instance when dealing with the length of things.

kzrdude• 10 years ago

That's only true for signed integers, overflow is defined as wrapping for unsigned integers.

Overflow is an error condition. Unsigned integer addition is defined to wrap around, and does not have this error.

C11 standard says this like:

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned integer type is
reduced modulo the number that is one greater than the largest value that can be
represented by the resulting type.

couchand• 10 years ago

The article argues that wrapping by default is the wrong choice, and that C and C++ got it right with UB-on-overflow. GP points out that for unsigned integers, C and C++ got it wrong, too.

The C11 standard agrees that when an integer would overflow, instead it wraps, while carefully avoiding saying that it's overflowing simply to preserve the defined term "Overflow" for the error code. In contexts other than the C11 standard it's fair to say that the integer overflowed, even if the language specifies that it wraps and "can never overflow".

mdadm• 10 years ago

As an example compile this with optimisations (should work the same with signed integer overflow):

Interesting. Clang and GCC both produce a binary that gets terminated by SIGFPE under normal compilation, but using -O3, Clang's output will run correctly while GCC's output will still SIGFPE.

legulere3• 10 years ago

Not that surprising for the unoptimized binary, the expression simply doesn't get folded and the division is executed on the processor. x86 processors trap when they do a division by zero. This is a totally correct execution with C, as division by zero is undefined behaviour. You would probably even expect that to happen.

I can't tell you though why the GCC binary even with optimisations outputs SIGFPE though, they probably don't optimize as much with undefined values.

nkurz2• 10 years ago

As an example compile this with optimisations

Could you be more specific? I'm not sure I'm following your example. Referring to the assembly output here might help me:

https://godbolt.org/g/RN1Ngm

legulere3• 10 years ago

Check the difference when you change `b` to 1. Then `a/b` is optimized to 1 and not undef. Thus there's an additional `movl $1, %esi`. This is lacking in the example where `a/b` is undef. So `printf` gets passed whatever value is in `%esi`. There is some code that calls main in the binary which is lacking in your disassembly so I can't exactly tell you where `%esi` is from.

https://godbolt.org/g/cEaAVR

mzs• 10 years ago

It's worse than you might expect, try it with unsigned int ;)

    $ cc -O3 foo.c
    $ ./a.out 
    5e574b68
    $ cat foo.c 
    #include <stdio.h>
    
    int main(int argc, char ** argv) {
      unsigned int a = 1;
      unsigned int b = 0;
      printf("%x\n", a/b);
    }

Yes overflow wraps on unsigned as defined, but that example is divide-by-zero which is UB for unsigned too and the compiler is free to optimize there, which LLVM does.

js8• 10 years ago

I have to ask again: Why isn't there a better hardware support for overflows on x86? Mainframe CPUs do have an option to raise an exception condition on arithmetic overflow.

hyperpape• 10 years ago

I can't comment on his assessment, but here is what Dan Luu says: http://danluu.com/integer-overflow/#fnref:H

jerf2• 10 years ago

Based on discussions I've had here, I do agree that step one is just for more people to care. If more people care, it will eventually get the attention of hardware people.

I mostly care about this issue because of the security issues that arise (overflow is somewhere around #4 or #5 on the list of top root causes of security issues), and for all that a lot of programmers think they care about security, there's still a lot of programmers that are quite cavalier about fixing the root causes of these issues rather than occasionally fixing symptoms when you think of it.

catnaroek2• 10 years ago

Wrapping arithmetic makes perfect sense in many ways:

(0) It is still a commutative ring, so it has the most important nice algebraic properties of number arithmetic: addition and multiplication are associative and commutative, multiplication distributes over addition, etc.

(1) It is the ideal building block for implementing the very big integers that high-level languages need.

Trapping on overflow is a relatively minor concession in elegance: You are admitting that you want all integers, but, for efficiency reasons, constrain yourself to those that fit into some fixed amount of space. The worst that can happen is that you can't compute the result you want. You never compute a nonsensical result.

Saturating arithmetic is an abomination and simply shouldn't exist.

grandinj• 10 years ago

Saturating math is mainly a DSP thing, where it can be very useful in mimicking the behavior of some analog circuits. And it makes some algorithms have much nicer boundary behavior.

catnaroek2• 10 years ago

I confess my ignorance. Maybe in a DSP context saturating arithmetic makes sense.

mamcx• 10 years ago

So, it will make sense to make Int64 the default even in 32 bits?

beached_whale• 10 years ago

SafeInt also does wonders and stops you from doing things you shouldn't without going to extremes, at least the last time I used it. https://safeint.codeplex.com/

thewisenerd• 10 years ago

Before going to solutions, people need to be made aware of it first.

Take any "introduction to programming" course, and it is likely to include a question on: "swap two variables without using a third variable". When basic algebra is the simplest way to solve it, you also need to point out of the obvious case of integer overflow.

When I asked my professor why I wasn't graded for using the XOR-swap for solving that question, his reply was "we do not expect students to know this".

douchescript2• 10 years ago

There's always the overflow flag in the cpu, I don't get why it's not readily available in C when needed.

effie• 10 years ago

Indeed, strange. There are also other flags for floating point exceptions, but I have never heard about anyone actually using them. I'd like to have a look at language that supports these flags - do you know any?

douchescript2• 10 years ago

The compilers have it, google __builtin_add_overflow as an example.

runeks• 10 years ago

Haskell's Integer type transforms an exception into a decrease in performance by, behind the scenes, using the native (32/64 bit) integer type for values in that range, and a custom bignum implementation for when the native type would overflow.

ramshorns• 10 years ago

The article mentions that undefined behavior permits wrapping and trapping implementations. What about bignums? Would a C or C++ implementation be allowed to allocate more space to deal with integer overflow?

On the one hand, C data types are supposed to be fixed sizes, but on the other, "integer overflow = undefined behavior = anything can happen" seems to permit extending the size of the type when it overflows.

TorKlingberg• 10 years ago

I may be late to answer here, but no you couldn't reasonably make int a bignum in C. Unsigned integers are defined to wrap around, so certainly not there.

Signed overflow is undefined behaviour so the compiler and runtime can do anything. But, where would it store the extra bits? It could call malloc, but it wouldn't know when to free. It would violate the expectation that memory is managed manually in C. Not all C code even uses malloc. Or, what if the int is in a struct? Should the implementation go allocate extra overflow space elsewhere, and then what happens when you memcpy the struct?

I think there is a strong impedance mismatch between bignums and languages that aren't garbage collected.

Animats• 10 years ago

Explicitly ranged integers as seen in Ada are also very nice, there’s no reason that traps should only occur at the 32-bit or 64-bit boundaries.

Pascal had that. Somehow it got lost.

The formal verification community ignored integer overflow for far too long

Well, we didn't, back in the early 1980s.[1] But I had that argument with other people in the formal verification community.

I once wrote a paper called "Type Integer Considered Harmful". (Unfortunately, I've lost this.) This was back in the era when there were mixed 16-bit and 32-bit integers as machines transitioned to 32 bit. My position was that it was the compiler's job to size intermediate expressions so that overflow couldn't occur there if it wasn't going to occur in the final result. Overflow in the final result should be detected at run time or proved impossible.

Here's what that means. Consider

   uint_32 a,b,c;
   a = b + c;

Overflow of "b + c" implies overflow in a, so we just have to check for overflow.

   uint_32 a,b,c,d;
   a = b + c - d; // ordered as (b + c) - d

Overflow of "b + c" does not imply overflow in a. So the "b + c" sum has to be done in 64 bit.

   uint_32 a,b,c;
   a = b * c;

Again, overflow in "b + c" implies overflow in a, so we don't need a bigger intermediate value.

   uint_32 a,b,c,d;
   a = (b * c) / d;

The "b * c" term needs to be 64-bit.

   uint_32 a,b,c,d,e;
   a = (b * c * d) / e;

Either we need 128 bit arithmetic, or refuse to compile this. Some expressions you just can't do right with the machine hardware. The user could write

   uint_32 a,b,c,d,e;
   a = (uint_32(b * c) * d) / e;

which means trapping on overflow if "b * c" is bigger than an uint_32, and the compiler must generate a 64-bit product for "uint_32(b * c) * d)".

Languages tend to view numeric type conversion as a named type problem, rather than a numeric range problem. That leads to wrong answers in some cases. The goal is to get the right answer or trap.

If you want unsigned arithmetic that wraps, you would write

   uint_32 a,b;
   a = (a + b) % (2^32);

The compiler should recognize this as an optimization and do 32-bit unsigned wrapped arithmetic without trapping. The programmer says what they mean, rather than relying on the semantics of the hardware, which might change. (This used to be a bigger issue when we had to support 36 bit and 48 bit CPUs. There are still some odd-size DSP chips.)

[1] http://www.animats.com/papers/verifier/verifiermanual.pdf

zde• 10 years ago

Uhm, why use integers when you have floats that don't overflow but saturate nicely. lua/perl/js did just that.

ajuc• 10 years ago

Floats cause even more problems.

Solutions to Integer Overflow

Related Stories