Foundations — Undefined Behavior Sanitizer (UBSan)

Before you can understand the parent note, you need to own every symbol it throws at you. We build each one from nothing — plain words first, then a picture, then why the topic needs it.

1. A bit, and a fixed-width box

An int is not an infinite number line. It is a fixed row of 32 bits — a box with exactly 32 slots. Because the box has a fixed size, there is a largest number it can hold and a smallest one. This single fact — the box is finite — is the root of almost every bug UBSan catches.

Figure 1 below draws that box: 32 numbered slots, with the leftmost slot (bit 31) picked out in red because — as Section 3 shows — it behaves specially.

Why the topic needs this: every "overflow" the parent note talks about is just "the answer needed more slots than the box has." If you don't picture the box in Figure 1, overflow sounds mystical. It isn't.

2. Reading the switches: powers of two

To turn a row of bits into a number, each slot has a weight. The rightmost slot is worth $1$, the next $2$, then $4$, $8$, and so on — each slot doubles the one to its right. We write these weights as $2^0,2^1,2^2,\dots$

To read a number, add up the weights of every slot that is on (1).

Why the topic needs this: the parent writes $2^{31}$ and $2^{31}-1$ everywhere. Those aren't scary — they're just "the biggest thing a 31-slot pile of weights can add up to."

3. The largest and smallest int: INT_MAX and INT_MIN

Here is the twist that makes signed numbers work. In a 32-bit int, the top (leftmost) bit does not add — it subtracts. Its weight is $-2^{31}$ instead of $+2^{31}$. This is called Two's Complement Representation, and it is why one bit can encode negative numbers.

Figure 2 shows all the weights in a row so you can see that only the top box is negative while every other box adds.

• If the top bit is 0: the number is built only from positive weights, up to $\text{INT\_MAX}=2^{30}+2^{29}+\cdots +2^0=2^{31}-1.$
• If the top bit is 1: you start at $-2^{31}$ and add positive weights back, so the smallest possible is $\text{INT\_MIN}=-2^{31}.$

The comparison and membership symbols <, >, ≤, ≥, ∈: these compare numbers or ask "is it inside a range?".

• $a<b$ means "$a$ is to the left of $b$ on the number line" (a is less than b).
• $a>b$ means "$a$ is to the right of $b$" (a is greater than b) — the mirror image of $<$.
• $a\le b$ means "$a$ is left of, or equal to, $b$" (less than or equal).
• $a\ge b$ means "$a$ is right of, or equal to, $b$" (greater than or equal) — the mirror image of $\le$.
• $x\in [0,32)$ means "$x$ is a member of that range" — the square bracket $[$ includes its endpoint, the round bracket $)$ excludes it. So $[0,32)$ is $0$ up to $31$, not $32$.

4. The shift operator <<, and why n << 32 is out of range

The standard demands the shift amount k be $\in [0,32)$ — that is, $0\le k\le 31$. There are only 32 slots, so shifting by 32 would push the bit clean out of the box, which has no defined meaning. That round bracket $)$ in $[0,32)$ excluding 32 is exactly why n << 32 in the parent is illegal — it asks for a slide the box cannot represent.

5. What "wraparound" looks like — the odometer

Add $1$ to the biggest number and the box has no slot for the answer, so all the on-bits roll to $0$ and the top bit flips on — turning a huge positive into a huge negative. Just like a car odometer rolling from 99999 back to 00000.

Figure 3 draws this as a curved red arrow leaping from just past INT_MAX all the way back to INT_MIN on the number line — the visual of "one step past the edge becomes the far negative side."

For unsigned integers this rollover is defined by the standard — see Integer Overflow & Wraparound — it simply counts modulo $2^{32}$. For signed integers the standard refuses to define it: that is the UB the whole topic is about.

6. The sign bit and the symbol $\mathrm{sgnbit}$

The parent uses $\mathrm{sgnbit}(x)$. It just means "the top bit of $x$" — $0$ for non-negative, $1$ for negative. Reading the top bit tells you a number's sign in one glance.

The symbols $\wedge$ (and) and $\vee$ (or) and $\ne$ (not equal) are plain logic words:

• $P\wedge Q$ — both true.
• $P\vee Q$ — at least one true.
• $a\ne b$ — $a$ is different from $b$.

So the parent's overflow rule $\text{overflow}=(\mathrm{sgnbit}(a)=\mathrm{sgnbit}(b))\wedge (\mathrm{sgnbit}(a+b)\ne \mathrm{sgnbit}(a))$ reads in English: "if a and b had the same sign, but the answer's sign came out different, we wrapped." No calculus needed — just watching one bit.

Why the topic needs this: this single-bit test is the cheap check UBSan inserts. Understanding "top bit = sign" is the entire trick.

7. Alignment, the alignof operator, and the % symbol

Example 3 of the parent uses addr % alignof(int) == 0. The symbol % is remainder after division: $13\%4=1$ because $13=3\times 4+1$. If the remainder is $0$, the address sits exactly on a $4$-slot boundary — that is what "aligned" means. So addr % alignof(int) == 0 reads "is the address a clean multiple of 4?" The odd address 1 fails because $1\%4=1\ne 0$.

8. Compile time vs run time

• Compile time = when the compiler builds your program (before it runs). Here UBSan inserts its checks. This is why UBSan is a form of instrumentation added at compile time.
• Run time = when the finished program actually executes on data. Here the inserted check fires and calls libubsan.

This split is the difference between a static analyzer (reasons about code without running it) and UBSan (a dynamic tool that only sees the paths you actually run). It also connects to Compiler Optimization Levels (-O0 vs -O2 change how much the compiler assumes UB never happens) and to Debugging with -g and Debug Info (-g is what lets the whistle point at a line number).

How the foundations feed the topic

Related tooling you will meet later: AddressSanitizer (ASan) for memory bugs, and the GCC and Clang Toolchains that host -fsanitize=undefined.

Equipment checklist

Cover the right side and answer each. If you can, you're ready for the parent note.