Visual walkthrough — Address Sanitizer (ASan) — detecting buffer overflows at runtime

Prerequisites we lean on: Stack vs Heap Memory Layout (where buffers live), Undefined Behaviour in C and C++ (why overflows are legal-to-compile but wrong), and Compiler Instrumentation and -fsanitize flags (how the check gets injected).

Step 1 — What "memory" even is: a row of numbered boxes

WHAT. Before any formula, picture memory as a long row of 1-byte boxes. Each box has a number called its address — just its position in the row, like house numbers on a street. A pointer (say p) is nothing but "the address of the first box of your thing."

WHY. Every later idea (shadow, redzone, the shift-by-3) is an operation on these addresses. If we don't see addresses as plain positions on a number line, none of the arithmetic will feel like anything.

PICTURE. Look at the row below. The blue boxes are the 8 bytes a program asked for with malloc(8). p points at the first one. The number under each box is its address.

Step 2 — The problem, drawn: the access that walks off the end

WHAT. With char a[4] you legally own 4 boxes (indices 0,1,2,3). Writing a[4] touches the fifth box — one past the end. C compiles this happily; it just scribbles on whatever byte sits there.

WHY. We must see that the bad byte is a real, addressable box that belongs to something else (or to nothing in particular). Plain hardware has no way to know it's "not yours." That absence of a check is the whole gap ASan fills.

PICTURE. Green = the 4 boxes you own. The orange box is a[4] — one step too far. Notice it looks identical to your boxes; nothing physically stops the write.

Step 3 — The idea: paint a "do-not-touch" strip, and keep a cheat-sheet

WHAT. Two new objects enter here.

1. A redzone: extra bytes ASan sneaks in just after (and before) your buffer, marked forbidden.
2. A shadow map: a separate tiny notebook that records, for each region, "safe" or "forbidden."

WHY. We can't ask the hardware "is this byte mine?" — so we build our own record. The redzone guarantees that a one-past-the-end write lands on a byte we've marked forbidden, and the shadow map lets a check read that mark fast.

PICTURE. Same buffer as Step 2, now with an orange redzone appended, and above it a small notebook (the shadow) with one entry per chunk. Green entry = "all safe," red entry = "forbidden."

Step 4 — Why one shadow byte covers exactly 8 real bytes

WHAT. If we stored one shadow byte per real byte, memory would double — unacceptable. Instead ASan groups real memory into 8-byte granules and uses one shadow byte per granule. So 8 real bytes → 1 note. That's a 1/8 overhead, not 1/1.

WHY 8? Allocations on modern CPUs are 8-byte aligned anyway (see Stack vs Heap Memory Layout), so a granule boundary lines up with allocation boundaries. And within a granule the valid bytes are always a prefix: the first $k$ bytes safe, the rest poisoned. A single small number $k$ captures that.

PICTURE. Eight real boxes bracket-grouped into one granule, an arrow pointing up to a single shadow box. The shadow box shows the number $k$ = "how many of these 8 are safe."

Step 5 — Finding the shadow byte: the shift-by-3 and the offset

WHAT. Given an address $A$, where is its shadow byte? Two operations: $\text{Shadow}(A)=\underset{\text{which granule}}{\underbrace{(A\gg 3)}}+\underset{\text{where the notebook lives}}{\underbrace{\text{Offset}}}$

WHY $\gg 3$? The symbol $\gg 3$ means "shift the binary number right by 3 places," which is exactly integer division by $2^3=8$. We chose 8-byte granules in Step 4, so dividing the address by 8 turns "byte number $A$" into "granule number $A/8$" — the index of its notebook entry. We use a shift instead of / 8 because it's a single, blazing-fast CPU instruction, and this runs on every memory access.

WHY + Offset? The granule number by itself is small and would collide with real program data. Adding a big fixed constant Offset (e.g. 0x7fff8000 on 64-bit Linux) slides the whole notebook to a reserved corner of the address space where nothing else lives.

PICTURE. Address $A$ on the left; a "$÷8$" box (labelled $\gg 3$) shrinks it to a granule index; a "$+\text{Offset}$" box slides it into the shadow region on the right. Follow the arrow.

Step 6 — The in-granule question: A & 7 and the compare

WHAT. We now have the shadow value $s$ for $A$'s granule. But $s=5$ means "bytes 0–4 of this granule are safe." Which byte within the granule are we touching? That's the remainder of $A$ divided by 8, written $A\&7$.

WHY $\&7$? The symbol $\&$ is bitwise AND. AND-ing with $7$ (binary 111) keeps only the lowest 3 bits of $A$ — precisely the remainder $A\mathrm{mod}8$, i.e. the offset inside the granule (0 to 7). It's the fast twin of the $\gg 3$ from Step 5: shift gives the quotient, AND-7 gives the remainder.

WHAT the check does. For an $N$-byte write, the last byte we touch is at in-granule index $(A\&7)+N-1$. The write is illegal exactly when that reaches into the poisoned part, i.e. is $\ge s$ (and $s\ne 0$).

• $s\ne 0$ — "granule not fully green, so bother checking."
• $A\&7$ — first byte offset touched.
• $+N-1$ — reach forward to the last byte of an $N$-byte access.
• $\ge s$ — that last byte is at or past the first poisoned byte.

PICTURE. One granule of 8 cells: green cells $\mathrm{0..}s-1$, red cells $s..7$. A bracket marks the access span from $A\&7$ to $(A\&7)+N-1$. When the bracket's right edge crosses the green/red line, the alarm rings.

Step 7 — Walk every case (so no scenario surprises you)

WHAT. We now run the Step-6 rule through all the shapes it can meet, so nothing is untested.

PICTURE. Four mini-granules stacked, each showing the access bracket and the verdict.

Case A — fully green ($s=0$). The first clause $s\ne 0$ is false, so we skip the comparison entirely. Any 1-byte access inside a fully-owned granule is instant-pass. This is the common, fast case.

Case B — partial granule, still inside ($s=5$, access byte 4, $N=1$). $(A\&7)+N-1=4+1-1=4$. Is $4\ge 5$? No → allowed. Byte 4 is the last safe byte.

Case C — partial granule, one step too far ($s=5$, access byte 5, $N=1$). $5+1-1=5$. Is $5\ge 5$? Yes → reported. Byte 5 is the first poisoned byte of the same granule — the subtle case only per-granule tracking can catch.

Case D — full redzone ($s$ negative). A negative $s$ is treated as "all 8 poisoned." Since any real in-granule index $\mathrm{0..7}$ is $\ge$ a negative number, every access reports. This is what a pure redzone, a freed block, or a use-after-return looks like.

Step 8 — Degenerate & edge inputs (the corners people forget)

WHAT. Three corner cases that the rule must still handle sanely.

PICTURE. Three panels: a zero-size chunk, an unaligned access straddling two granules, and a freed-then-quarantined block.

1. malloc(0). ASan returns a valid, unique pointer to a zero-byte region wrapped entirely in redzones. Its own granule is poisoned, so any dereference reports — reading/writing a 0-size allocation is a bug, and this makes it visible.

2. Unaligned / multi-granule access. An 8-byte read at an address that isn't a multiple of 8 spans two granules. ASan checks the shadow of both the first and last touched byte. The single-granule formula of Step 6 is the aligned fast path; the slow path repeats the check per granule so a straddling access can't sneak through a green/red seam.

3. Use-after-free. On free(p), ASan sets the block's shadow to a negative "freed" marker (Case D) and drops the block into a quarantine so its address isn't recycled immediately. A later p[0] reads that negative shadow → reported, and ASan can still name where it was freed. Contrast with Valgrind Memcheck, which achieves similar detection by emulation instead of instrumentation, and with MemorySanitizer (MSan) / UndefinedBehaviorSanitizer (UBSan), which watch uninitialised reads and UB respectively rather than out-of-bounds.

The one-picture summary

PICTURE. The whole pipeline on one canvas: real memory (green + orange redzone) at the bottom, the $\gg 3$ + Offset arrow lifting an address up to its shadow byte, and the two-clause if verdict on the right — green flows through, red aborts with a report.