Foundations — Address Sanitizer (ASan) — detecting buffer overflows at runtime

Before you can understand the parent note, you need to see what each symbol means. This page builds every one of them from nothing. We go slowly, one brick at a time, and each brick sits on the one before it. Never worry about the fancy word — worry about the picture.

0. What is memory, really? (the ruler picture)

Everything else rests on this. So let's define it with zero assumptions.

Think of a very long ruler. Every millimetre mark is a box. The mark number is the address; whatever you scribble at that mark is the byte stored there.

Why does the topic need this? Because ASan's whole job is to notice when your "walk to box number X" lands on a box you were never allowed to open.

1. The address symbol A

Throughout the parent note you see the letter $A$.

That's it. When the note writes *A = x, read it as: "go to box number $A$ and write the value $x$ into it." The little star * means "the box at this address", not the sticky note itself.

2. Grouping boxes into 8s — the "granule"

ASan does not track boxes one at a time (that would need one note per box — doubling memory). Instead it clumps the ruler into groups of 8.

Why 8 and not 4 or 16? Because on 64-bit machines the CPU naturally hands out memory in 8-byte chunks anyway, so most buffers already line up with these pens — a clean fit.

3. Two tools for splitting an address: >> 3 and & 7

The formula $\text{Shadow}(A)=(A\gg 3)+\text{Offset}$ uses >> 3, and the check uses A & 7. These two symbols look scary but they answer two very ordinary questions:

• A >> 3 asks: "Which pen is box $A$ in?"
• A & 7 asks: "How far along inside that pen is box $A$?"

3a. Why >> 3 means "divide by 8"

WHY this tool and not plain division / 8? Same result, but a shift is a single ultra-cheap CPU instruction. ASan runs this on every memory access ever, so cheapness matters enormously.

$\text{pen number of }A=A\gg 3=\lfloor \frac{A}{8}\rfloor$

(The $\lfloor \rfloor$ means "round down", because we drop the remainder.)

3b. Why & 7 means "the leftover within the pen"

So together: $A=\underset{\text{which pen}}{\underbrace{(A\gg 3)}}\times 8+\underset{\text{offset in pen, }0\text{–}7}{\underbrace{(A\&7)}}$

4. The Offset and the Shadow(A) formula

Now the full mapping makes sense.

5. The shadow byte value s — the colour code

Each pen's note holds a single small number, the shadow byte $s$. It is a compact colour code for the 8 boxes in that pen.

Why can one number capture a whole pen? Because in real programs a buffer's end falls somewhere inside a pen: the boxes before the end are valid, the boxes after are padding. So "first $k$ valid" covers the common case. A completely poisoned pen (a redzone, or freed memory) gets a negative $s$ — an impossible "count", used as a flag for "all red".

6. The trigger condition — putting the symbols together

The parent's check is: $s\ne 0\text{AND}(A\&7)+N-1\ge s\Rightarrow \text{REPORT}$

Now every symbol is defined, so read it as one plain sentence:

• $N$ = how many bytes this access touches (1 for a char, 4 for an int, …).
• $(A\&7)$ = offset of the first box you touch inside its pen (Section 3b).
• $(A\&7)+N-1$ = offset of the last box you touch.

7. Stack vs heap vs global — where the buffers live

The parent mentions heap, stack, and global buffers. You need the picture of where your boxes come from, covered in Stack vs Heap Memory Layout.

• Heap: memory you request at runtime with malloc(n); ASan's runtime secretly grabs extra boxes for redzones.
• Stack: local arrays like int a[4]; the compiler inserts redzones around them.
• Globals: file-level arrays; redzones baked in at compile time.

All three then rely on the same shadow-check machinery — only who inserts the redzone differs. This is why the tool must be applied consistently via Compiler Instrumentation and -fsanitize flags.

Prerequisite map

Read it bottom-up: boxes give you addresses; addresses split into pen + offset; the pen leads to a shadow note $s$; offset + $N$ + $s$ decide the trigger; layout tells you where the buffers (and their redzones) sit.

Equipment checklist

Test yourself — you're ready for the parent note when you can answer each without peeking.