July 26, 2016 at 16:51

Myths and legends about integer overflow in Rust

Original author: Huon Wilson
  • Transfer

The primitive integer types supported by processors are a limited approximation to the infinite set of integers that we are used to operating in real life. This limited representation does not always coincide with "real" numbers, for example 255_u8 + 1 == 0. Often, the programmer forgets about this difference, which can easily lead to bugs.

Rust is a programming language whose purpose is to protect against bugs, it focuses on preventing the most insidious of them - memory errors, but also tries to help the programmer avoid other problems: memory leaks , ignoring errors and, as we will see, integer overflows .



Overflow in Rust


The Rust Overflow Detection and Prevention Policy has changed several times on the way to the 1.0.0 release last year. As a result, there is a misunderstanding of how overflow is handled and what consequences it causes.

Prior to version 1.0.0-alpha, the overflow was cyclical and the result corresponded to using the addition of up to two(as most modern processors do). However, such a solution is not optimal: unexpected and unnoticed overflow often leads to errors. This is especially bad in C and C ++ due to the fact that overflowing signed integers is an undefined behavior, which, together with insufficient protection against security breaches in working with memory, can easily lead to its damage. However, in more security-conscious languages ​​such as Rust, this still causes problems: there are many examples of overflows that are found in video games ( economics , health indicators , etc.), binary search implementations , and even aviation software . Simply put, a code likemax(x - y, z)Occurs periodically and may produce incorrect results if the numbers are unsigned and x - ycause overflow. As a result, there was a desire to make Rust safer with respect to integer overflows.

The current status is defined in RFC 560 :


  • In the debug assembly, arithmetic operations ( +, -etc.) are checked for overflow and, if present, cause panic.
  • In the release, there are no checks for the result of overflow, and the result guarantees cyclicality.

Overflow checks can be manually turned on or off regardless of the type of assembly, both globally and at the level of individual operations.
However, you cannot influence some checks: х / 0and MIN / -1(for signed integers) and similarly for %. These calculations are undefined behavior in C and LLVM, which was the reason for the behavior of rustc, although it seems to me that Rust could theoretically be considered MIN / -1as a normal overflow and return MINwhen checks are disabled.

We hope that thanks to checks in debug mode, errors related to overflow in the Rust code will be detected earlier. Moreover, if you really count on overflow, you will have to indicate this explicitly in the code, which reduces the number of false positives for future static analyzers, as well as for code that includes overflow checking in all modes.


Myth: overflow result is undefined (undefined)


Overflow could result in undefined behavior, however, one of the key goals of Rust is to ensure memory security, and such uncertainty (similar to undefined behavior in C) clearly contradicts this goal. A variable containing an undefined value is not required to maintain the same value between uses:


// Псевдо-Rust
let x = undefined;
let y = x;
let z = x;
assert_eq!(y, z); // потенциальная проблема

This will lead to disastrous consequences if security depends on such a value. For example, when checking out of bounds of an array foo[x]:


let x = undefined;
// let y = foo[x]; // что эквивалентно следующему:
let y = if x < foo.len() {
    unsafe { *foo.get_unchecked(x) }
} else {
    panic!("index out of bounds")
};

If the value of a variable хdiffers when comparing x < foo.len()and with direct access to the array, then guarantees may be violated: it may turn 0 < foo.len()out to be a comparison , but it will succeed when accessed by index foo.get_unchecked(123456789). Mess!

Thus, unlike signed integers in C, in Rust, overflow cannot be undefined. In other words, the compiler must assume that overflow can occur, unless it can prove otherwise. This entails non-obvious consequences: it is x + 1 > xnot always true, while C compilers assume that this condition is always fulfilled if it хis a signed integer.

"But what about performance?" I already anticipate this question. Indeed, undefined behavior simplifies optimizations by allowing the compiler to make assumptions. Therefore, rejection of such behavior can affect speed. Uncertainty overflow of integers is especially useful in C because such numbers are often used as inductive variables in loops, therefore, the ability to make assumptions allows a more accurate analysis of the number of iterations of the loop: it for (int i = 0; i < n; i++)will be performed nonce since it can be assumed that it ndoes not contain a negative value. Rust circumvents most of these problems by using positive numbers as indices ( 0..nit will always give nsteps) and allowing lightweight iterators to directly traverse data structures, for examplefor x in some_array { ... }. These iterators can use knowledge about the internal structure of data structures without forcing the user to deal with undefined behavior.

Also, Rust, unlike C, cannot x * 2 / 2simply be reduced to xif it xis a signed integer. This optimization is not applied (unless you manually write xinstead of a complex arithmetic expression), however, in my practice, such expressions are most often found when it xis known at compile time, which means that the whole expression will be replaced by a constant.


Myth: The result of an overflow is unspecified.


The result of an overflow could be unspecified, in which case the compiler would have to assume that it could happen, but would have the right to return any value as a result (or not return it at all). In fact, the first version of RFC 560 to check for integer overflows suggested:


Change the behavior to return an unspecified value or cause a panic, depending on whether the overflow is checked.
[...]
  • Theoretically, an implementation returns an unspecified value. In practice, however, the result will be similar to cyclic overflow. Implementations should avoid excessive unpredictability and unexpected behavior so as not to provoke errors.
  • And the most important: this is not an indefinite behavior in the understanding of C. The result of the operation will be unspecified exclusively, and not the behavior of the entire program as in C. The programmer cannot rely on any specific value during overflow, but the compiler does not have the right to use the assumption about that overflow will not occur, for optimization.


The RFC and the “unspecified” overflow result (that is, it 127_i8 + 1can return -128either or 0or 127or any other value) became the subject of lively discussions that led to its change.

Thanks to the efforts of individuals, the RFC has taken on a modern look: as a result of an overflow, the value will either not be returned at all (for example, panic will occur), or a cyclic result corresponding to the use of the addition to two will be returned. Now the wording looks like this:


The operations +, -, * can lead to overflow or to the disappearance of order (underflow). If the checks are turned on, then a panic will occur. Otherwise, the result will be a cyclic overflow.

The recorded overflow result is a protective measure: errors can have no consequences, even if no overflow is detected. The expression is x - y + zcalculated as (x - y) + zwell and, therefore, the subtraction can lead to overflow (for example, x = 0and y = 1both are unsigned), but if zlarge enough (in our example z >= 1), the result will be similar to using "numbers from the real world".

The change came towards the end of a discussion of 160 comments, so it was easy to skip, because of which people can continue to think that the result of the overflow is unspecified.


Myth: programmer cannot control overflow handling


One of the arguments against introducing overflow checking was the existence of programs and algorithms that rely on cyclical overflows, such as hash calculation algorithms, some data structures (for example, a ring buffer), and even codecs. For these algorithms, use +in debug mode will be incorrect: panic will occur, although such use of overflow was conscious. In addition, in some cases, you may want to include checks not only for debug builds.

The RFC and the standard library provide four sets of methods besides the usual operators:



This should cover all "special cases":


  • wrapping_... return the result of an addition to two.
  • saturating_... return the largest / smallest value when an overflow occurs.
  • overflowing_... return the result of padding to two along with a boolean value indicating an overflow has occurred.
  • checked_...return Option, which takes a value Nonein case of overflow.

All these operations could be implemented in terms overflowing_..., but the standard library tries to simplify the solution of the most frequently occurring problems.

If you really want to use circular overflow then you can write something like x.wrapping_sub(y).wrapping_add(z). This will give the expected result, and verbosity can be reduced by using a type from the standard library Wrapping.

This may not be the final state: the RFC also mentions potential improvements . In the future, operators like cyclic can be added to Rust.&+from Swift. This was not done immediately, since Rust is trying to be conservative and, to a reasonable extent, minimalistic, and also because of the potential to disable overflow checks (for example, a separate function may be explicitly marked and there will be no checks in its code in all modes) . In particular, the most active (potential) users of Servo and Gecko are interested in the latter .

If you want to have overflow checks in all code, you are forced to either use it everywhere checked_add(not too convenient!) Or explicitly enable them. Although they only work in debug mode by default, overflow checks can be enabled by passing -C debug-assertions=onrustc (to the Rust compiler) or by setting a field debug-assertionsin the cargo profile. Also, work is underway to enable them, if possible, independently of other debugging checks (currently rustc supports an unstable option -Z force-overflow-checks flag).


Myth: The chosen approach to overflow checks slows down the code.


Rust aims to be as fast as possible, and when designing overflow checks, performance issues were taken very seriously. Performance is one of the main reasons why checks were disabled for release builds by default. Of course, this means that speed was not sacrificed to the convenience of detecting errors during development.

Unfortunately, overflow checks require more code and instructions:


[no_mangle]
pub fn unchecked(x: i32, y: i32) -> i32 {
    x.wrapping_add(y)
}
#[no_mangle]
pub fn checked(x: i32, y: i32) -> i32 {
    x + y
}

From -O -Z force-overflow-checkson x86 (on 32-bit ARM LLVM currently generates redundant comparisons and register manipulations, so the performance loss is even greater!) This compiles into the following (with some changes for clarity):


unchecked:
    leal (%rdi,%rsi), %eax
    retq
checked:
    pushq   %rax
    addl    %esi, %edi
    jo  .overflow_occurred
    movl    %edi, %eax
    popq    %rcx
    retq
.overflow_occurred:
    leaq    panic_loc2994(%rip), %rdi
    callq   _ZN9panicking5panic20h4265c0105caa1121SaME@PLT

There are more instructions than should be provided that it is checkedembedded (which should happen): in this case, working with registers using pushq/ pop/ is movlnot necessary. I suppose that even without embedding, stack management with pushq/ is popqnot required, but unfortunately, Rust is currently using the LLVM version, which contains an error . Of course, all of these additional instructions are annoying, as is the need to use addinstead lea.


On x86, using lea(load effective address) for arithmetic can be very useful: it allows you to perform relatively complex calculations and, as a rule, is calculated in a separate part of the CPU and its pipeline, unlike add, which contributes to higher concurrency at the instruction level. x86 ISA allows dereferencing the result of complex calculations with pointers: the general form A(r1, r2, B)(in AT&T syntax), which is equivalent r1 + B * r2 + Awhere r1and r2are registers and Aand Bare constants. As a rule, this is used directly in instructions for working with memory, such as mov(for example, it let y = array_of_u32[x];can be compiled into something other than mov (array_of_u32.as_ptr(), x, 4), y, since each element has a size of 4), butleaallows you to perform arithmetic without affecting memory. In general, the ability to use leafor arithmetic is quite useful. The disadvantage is that it leadoes not integrate directly with overflow checks: it does not set a processor status flag indicating this.


However, an even bigger blow to performance is that overflow checks prevent other optimizations. First, the checks themselves sort the code (preventing things like deploying, reordering, and loop vectoring). Secondly, panic and unwinding the stack makes the compiler behave more conservatively .

All of these considerations explain why overflow checks are not included in the release build, where the highest possible performance is usually important.

In this case, even if overflow checks are enabled in release mode, performance losses can be reduced, as is the case with checks for out-of-bounds array. On the one hand, compilers can perform range analysis and prove that individual operations will never lead to overflow. And really , this subject is given a lot of attention . On the other hand, the problems caused by the use of panic can be partially solved by replacing the panic with an abnormal termination of the program , if the subject area allows.

The RFC overflow provides the possibility of additional optimizations: " delayed panic " is allowed , that is, implementations can perform a sequence of operationsa + b + c + dand panic once at the very end, if any of the calculations led to overflow, instead of checking every single operation tmp = a + b, then tmp + cetc. Although at the moment this is not implemented, there is such an opportunity.


Myth: checks do not detect errors


All efforts to develop, discuss, and implement this scheme for handling integer overflows would be in vain if they did not help to detect errors in practice. Personally, I found several problems in my code with expressions like cmp::max(x - y, z)(they didn’t hit the Internet, so there will be no links) almost immediately after writing, especially in combination with a testing infrastructure such as quickcheck .

Overflow checks have detected errors in our ecosystem, for example, such (the list is not complete!):



Outside of Rust, there are many other examples of the danger of overflow errors. In 2011, they made the list of the 25 most common CWE / SANS errors . Some languages, such as Swift, always perform overflow checks, while others, such as Python 3 and Haskell, avoid overflows by default using arbitrary precision numbers. Moreover, some C compilers support options that replace undefined behavior with circular overflow ( -fwrapv) and help detect overflow ( -fsanitize=signed-integer-overflow).

Tags:

Also popular now: