Integer Underflow & Overflow

Integer Underflow and Integer Overflow are bugs that occur when operations on integers unintentionally result in values that exceed the maximum size that their representation can store and end up with different values. This is different from Integer Wraparound where, in this case, the aim is to deliberately exceed the maximum size that the representation of an integer can store so that the value can wrap around the possible integer values in algorithms that require this behaviour. Integer Underflow or Integer Overflow can result in risks to confidentiality, integrity or availability depending on whether these bugs corrupt valid data, cause the program to crash or trigger buffer overflows which can be used to execute arbitrary code (CWE-190,CWE-191).

A simple example is the code below:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    short car_price = 32000;
    short heated_seats_price = 1500;

    short total_price = car_price + heated_seats_price;

    printf("Total price: %d\n", total_price); // Prints "Total price: -32036".

    return EXIT_SUCCESS;
}

The size of a signed short integer in C is usually 2 bytes (16 bits) so it can represent numbers between -32768 (\(-2^{15})\) and 32767 (\(2^{15}-1)\).

The operation 32000 + 1500 is equal to 33500 which is greater than 32767 so it wraps around. It is the same as if we subtract 65536 (\(2^{16})\) from 33500 which gives 33500 - 65536 and it is equal to -32036.

Detection and Debugging Tools

To detect these bugs, it is possible to use static code analysis tools such as Clang Static Analyzer or Cppcheck (for the C language) or fuzzers such as AFL++ (for the C language), although these tools do not detect all occurrences of the problem.

In the event of a failure, it is therefore also necessary to have debugging tools such as GDB or Valgrind (for the C language), that can identify the instruction causing the problem.

These are fairly complicated bugs to manage, as adding an automatic underflow/overflow check at runtime can result in severe performance penalties if the program performs a lot of operations on integers. This is why one approach that is often used is to add functions that allow integer operations to be performed while providing the developer with the option of how to manage underflows/overflows, with these functions being primarily intended for use in critical areas where it is not possible to be sure that there won’t be an underflow/overflow.

Exercise

The exercise program contains the implementation of some functions and, unfortunately, it doesn’t work. Your goal is:

1. to find the bug using debugging tools;
2. and to fix it.

Your other goal is to think about how you can prevent this from happening in other projects.

The Case of Rust

In Rust, these bugs are partially managed by several mechanisms, although for performance reasons, it is still possible to have Integer Underflow and Integer Overflow at runtime if these mechanisms have not been able to find the underflow/overflow before release.

The first mechanism comes from the fact that the Rust documentation requires to be explicit about whether an operation can cause an underflow/overflow or not, with the default being that usual integer operators must not cause an underflow/overflow.

This first mechanism is enforced by a second mechanism which ensures that underflows/overflows on usual integer operators are checked at runtime in debug mode to find bugs during the development stage, even though this does not exist in release mode for performance reasons, and that a static analysis is performed to find underflows/overflows bugs at compilation time.

As a final mechanism, Rust offers functions with well-defined semantics on how they should handle underflow/overflow when needed, such as the checked_* function to return the value or None in the event of underflow/overflow, or wrapping_* to have an explicit wraparound.

Here is an example of Rust code that shows this feature:

fn main() {
    let car_price: i16 = 32000;
    let heated_seats_price: i16 = 1500;

    // Does not compile because the compiler found an overflow
    // using a static analysis.
    let total_price: i16 = car_price + heated_seats_price;

    println!("Total price: {}", total_price);
}

It is the equivalent of the C code showed in the intro.