Detect signed integer wrap-around (overflow and underflow)

[kees]

Much like the array bounds checking (issue #25), the kernel should be detecting signed integer overflows using the Undefined Behavior Sanitizer (UBSan) compiler feature. There are some false positives that need to be fixed (e.g. commit a318f12), and there are some true positives that are expected (e.g. refcount_t overflow), and need to be marked.

There is, however, a complication with the kernel's use of -fno-strict-overflow which implies -fwrapv-pointer and -fwrapv (which is needed to keep the compiler from optimizing things away that are considered "undefined", when what is wanted is "expected" 2s-complement wrap-around on overflow). The former is for wrapped unsigned integer overflow (i.e. unsigned long pointer values), and the latter is needed for true positive signed overflow (i.e. refcount_t). However, this makes integer overflow no longer undefined behavior, making UBSan not catch overflows any more. :( To fix this, we need the "intentional overflow/wrap" helpers to DTRT in the face of -fno-wrapv so that UBSan will work correctly.

Language clarification:

• "overflow" has a specific meaning related to undefined behavior
• "wrap (around)" has a specific meaning related to the handling of signed overflow through wrap-around (i.e. defined behavior).

To avoid Undefined Behavior, the kernel must keep -fno-strict-overflow.

So, things to do:

• make signed integer sanitizer work even with -fwrapv (and -fno-strict-overflow). done
• create "expected signed overflow" helper inline functions marked with __attribute__((no_sanitize("signed-integer-overflow"))). done
• add back signed integer overflow as a UBSan Kconfig done
• add note to "deprecated.rst" with something like "open coded signed integer wrap around without a helper".
• investigate need for -fsanitize=signed-integer-truncation and create new issue if needed
• annote enough false positives that production workloads can run (e.g. Android, Ubuntu, etc).

[kees]

To illustrate the issue:

#include <stdio.h>
#include <limits.h>

/* volatile to avoid optimization */
volatile int val;

int main(void)
{   
    val = INT_MAX; 
    val += 1;
    printf("%d\n", val);
    return 0;
}

Normally, the expected warning is generated:

$ gcc -Wall -O2 -fsanitize=signed-integer-overflow -o wrap wrap.c
$ ./wrap
wrap.c:10:9: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
-2147483648

But with -fno-strict-overflow the condition goes unnoticed:

$ gcc -Wall -O2 -fsanitize=signed-integer-overflow -fno-strict-overflow -o wrap wrap.c
$ ./wrap
-2147483648

[kees]

See also commit 6aaa31a

[kees]

Interaction with -fno-wrapv: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102317

[kees]

A nice test for the UB (thank you to Miguel Ojeda) here is:

bool f(const int x) {
    return x + 1 > x;
}

UB will show this as always returning true.

[kees]

More notes/background: https://danluu.com/integer-overflow/

[kees]

Would have caught:
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=722d94847de2

[bwendling]

Copying this GCC documentation here for my benefit:

-fstrict-overflow

Allow the compiler to assume strict signed overflow rules, depending on the language being compiled. For C (and C++) this means that overflow when doing arithmetic with signed numbers is undefined, which means that the compiler may assume that it does not happen. This permits various optimizations. For example, the compiler assumes that an expression like i + 10 > i is always true for signed i. This assumption is only valid if signed overflow is undefined, as the expression is false if i + 10 overflows when using twos complement arithmetic. When this option is in effect any attempt to determine whether an operation on signed numbers overflows must be written carefully to not actually involve overflow.

This option also allows the compiler to assume strict pointer semantics: given a pointer to an object, if adding an offset to that pointer does not produce a pointer to the same object, the addition is undefined. This permits the compiler to conclude that p + u > p is always true for a pointer p and unsigned integer u. This assumption is only valid because pointer wraparound is undefined, as the expression is false if p + u overflows using twos complement arithmetic.

See also the -fwrapv option. Using -fwrapv means that integer signed overflow is fully defined: it wraps. When -fwrapv is used, there is no difference between -fstrict-overflow and -fno-strict-overflow for integers. With -fwrapv certain types of overflow are permitted. For example, if the compiler gets an overflow when doing arithmetic on constants, the overflowed value can still be used with -fwrapv, but not otherwise.

The -fstrict-overflow option is enabled at levels -O2, -O3, -Os.

-fwrapv

This option instructs the compiler to assume that signed arithmetic overflow of addition, subtraction and multiplication wraps around using twos-complement representation. This flag enables some optimizations and disables others. This option is enabled by default for the Java front-end, as required by the Java language specification.

[kees]

Also:

-fwrapv-pointer

This option instructs the compiler to assume that pointer arithmetic overflow on addition and subtraction
wraps around using twos-complement representation. This flag disables some optimizations which assume pointer
overflow is invalid.

[JustinStitt]

Does anyone know why this sanitizer only works for some integer types and not all? Is this intentional?

See: https://godbolt.org/z/ET1Kz6YYn

Here it works fine with int but not with int8_t.

edit (01/30/2024): This is likely due to promotion rules (well-defined by the spec)

[kees]

Yet another bug! Yes, it seems that it is limited only to 32-bit signed overflow. :(

[kees]

Here's a recent thread with GCC folks where we clarified language and I tried to explain the kernel's behavioral needs:
https://gcc.gnu.org/pipermail/gcc-patches/2023-September/630578.html