[rust-dev] Integer overflow checking

[Patrick Walton]

Hi everyone,

I've been wondering for a while whether it's feasible from a performance 
standpoint for a systems language to detect and abort on 
potentially-dangerous integer overflows by default. Overflow is an 
insidious problem for several reasons:

(1) It can happen practically anywhere; anytime the basic arithmetic 
operators are used, an overflow or underflow could occur.

(2) To reason about overflow, the programmer has to solve a global data 
flow problem. An expression as simple as "a + b" necessitates an answer 
to the question "could the program input have influenced a or b such 
that the operation could overflow?"

(3) Overflow checking is rarely used in practice due to the performance 
costs associated with it. ISAs aren't that well-suited for overflow 
checking. For example, on the x86 one has to test for the overflow 
and/or carry flag after every integer operation that could possibly set 
it. Contrast this with the floating-point situation, in which a SIGFPE 
is raised on overflow without having to explicitly test after each 
instruction.

(4) It can be catastrophic from a memory safety and security standpoint 
when overflow errors creep in, especially when unsafe operations such as 
memory allocation and unchecked array copying are performed. We do 
permit unsafe operations in Rust (although we certainly hope they're 
going to be rare!)

I did a quick survey of the available literature and there isn't too 
much out there*, but there is a recent gem of a paper from CERT:

http://www.cert.org/archive/pdf/09tn023.pdf

They managed to get quite impressive numbers: under 6% slowdown using 
their As-If-Infinitely-Ranged model on GCC -O3. The trick is to delay 
overflow checking to "observation points", which roughly correspond to 
state being updated or I/O being performed (there's an interesting 
connection between this and the operations that made a function "impure" 
in the previous effect system).

This area seems promising enough that I was wondering if there was 
interest in something like this for Rust. There's no harm in having the 
programmer explicitly be able to turn off the checking at the block or 
item level; some algorithms, such as hashing algorithms, rely on the 
overflow semantics, after all. But it seems in the spirit of Rust (at 
the risk of relying on a nebulous term) to be as safe as possible by 
default, and so I'd like to propose exploring opt-out overflow checking 
for integers at some point in the future.

Thoughts?

Patrick

* That said, Microsoft seems to have put more effort than most into 
detecting integer overflows in its huge C++ codebases, both through 
fairly sophisticated static analysis [1] and through dynamic checks with 
the SafeInt library [2]. Choice quote: "SafeInt is currently used 
extensively throughout Microsoft, with substantial adoption within 
Office and Windows."

[1]: http://research.microsoft.com/pubs/80722/z3prefix.pdf
[2]: http://safeint.codeplex.com/