Don't shoot your foot: signed overflow edition

Recently myself and my colleague Johan Moraal discussed a critical vulnerability in FreeRTOS kernel and the patch which mitigated it (CVE-2021-31571 for those who might be interested). How can one exploit this vulnerability, this is actually a very interesting topic and I'll probably cover it someday, but today I want to focus on way the patch has been implemented, because sometimes this way of patching is useless and harmful, because it gives you a false sense of safety.

So, what's the problem?

Author of the patch wanted to use the fact that unsigned arithmetic in C (and C++ as well) is actually arithmetic in a ring: once you reach the maximum value, you go back to 0, so e.g. in case of a 8-bit unsigned char you have numbers like these: 253, 254, 255, 0, 1, 2, ... So from this perspective the patch is OK:

/* Check for addition overflow. */ 
configASSERT( ( sizeof( Queue_t ) + xQueueSizeInBytes ) > xQueueSizeInBytes );        

Actually, we have an expression like a + b > a, where a and b are positive numbers. This is totally fine, if operands are unsigned; If not, things get ugly. In C and C++ signed integer overflow is Undefined Behaviour, therefore compiler suggests that such an overflow can never happen, so it happily throws away the overflow checks.

This example can demonstrate what's wrong with these checks: https://godbolt.org/z/P6e6jMfon

Here we have a generic function which either adds 10 to the given number, or returns the saturated (maximum possible) value for the given argument type:

auto __attribute__ ((noinline)) saturate_add(std::integral auto num) {
    if (num + 10 < num) {
        return std::numeric_limits<decltype(num)>::max();
    } else {
        return num + 10;
    }
}        

Here, attribute noinline was used to make the generated assembly clearly visible.

The problem is, that the template instantiation for unsigned types contains the check:

auto saturate_add<unsigned int>(unsigned int):   # @auto saturate_add<unsigned int>(unsigned int)
        add     edi, 10
        mov     eax, -1
        cmovae  eax, edi
        ret        

Here we check some flags and use either the sum, or -1 which is the same as 0xFFFFFFFF - maximum value of a 32-bit unsigned integer. But for signed types, we assume that an overflow never happens (our programs are UB-free!), and the check is omitted:

auto saturate_add<int>(int):   # @auto saturate_add<int>(int)
        lea     eax, [rdi + 10]
        ret        

No flag checks, no comparisons, just perform the operation and call it done. So, if we print the results, they will look like:

Orig unsigned num = 4294967294, function result: 4294967295, expected result: 4294967295 Orig signed num = 2147483646, function result: -2147483640, expected result: 2147483647

So, what can we do? If we want to be defensive, we don't need to rely on overflows; instead, we can check if the number exceeds the difference between the maximum possible value and the number which we want to add:

auto __attribute__ ((noinline)) safe_saturate_add(std::integral auto num) {
    if (std::numeric_limits<decltype(num)>::max() - 10 < num) {
        return std::numeric_limits<decltype(num)>::max();
    } else {
        return num + 10;
    }
}        

This way we don't rely on the overflows, therefore the generated assembly code for signed and unsigned integers contains the saturation check:

auto safe_saturate_add<unsigned int>(unsigned int): # @auto safe_saturate_add<unsigned int>(unsigned int)
        add     edi, 10
        mov     eax, -1
        cmovae  eax, edi
        ret
auto safe_saturate_add<int>(int): # @auto safe_saturate_add<int>(int)
        lea     ecx, [rdi + 10]
        cmp     edi, 2147483638
        mov     eax, 2147483647
        cmovl   eax, ecx
        ret        

So, my advices are:

• Always check if your operands are signed or unsigned
• Even if today your operands are unsigned, but their type is a subject of change (e.g. it's set by a macro definition which might be platform-dependent), add static assertions or prefer defensive programming style.
• When writing generic code, be extremely cautious, and don't forget to fuzz-test your code: some corner cases are easy to forget.

Happy safe and secure coding!