Step 8 of 8

Challenge: hunt the undefined behavior

Undefined behavior (UB) is code the C standard gives no meaning to. It's the biggest source of security vulnerabilities in C and C++, and the hardest bugs to find, because UB often seems to work: in testing, at one optimization level, with one compiler. Then a new compiler version, a different flag, or an unusual input changes everything.

The usual suspects:

UB	Example
Out-of-bounds access	`a[n]` in an array of n elements
Signed overflow	`INT_MAX + 1`
Reading uninitialized memory	`int x; printf("%d", x);`
Null or dangling pointer use	`*NULL`, use after `free`
Shifting too far	`1 << 32` on a 32-bit int
Modifying twice without sequencing	`i = i++ + 1;`

A classic: the midpoint

Binary search computes the middle of a range as (lo + hi) / 2. When lo and hi are both large, their sum overflows int even though the midpoint itself would fit. This exact bug sat in Java's standard library binary search for about nine years. The fix is to compute the distance first, which can't overflow when lo <= hi:

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

int main(void) {
    int lo = INT_MAX - 10, hi = INT_MAX - 2;
    int mid = lo + (hi - lo) / 2;
    printf("%d\n", mid - lo);
    int a[4] = {1, 2, 3, 4};
    int s = 0;
    for (int i = 0; i < 4; i++) s += a[i];
    printf("%d\n", s);
    return 0;
}

4
10

Finding UB

Read carefully (every array index, every arithmetic step), compile with warnings, and on a real machine use sanitizers: -fsanitize=address,undefined catches most of these the moment they happen. The Pro Track has you do exactly that.

Your turn: these two functions each have undefined behavior. Fix both:

sum reads one element past the end of the array.
midpoint overflows for large inputs. Compute it without overflowing (assume lo <= hi).

Previous: Type punning and strict aliasing