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

1. The map. One shadow byte describes 8 application bytes. Which shadow byte? $\text{Shadow}(A)=(A\gg 3)+\text{Offset}$. The symbol $\gg 3$ means "shift the bits right by 3", which is the same as "divide by $2^3=8$ and throw away the remainder" — that is how 8 app bytes collapse to 1 shadow byte. 2. The shadow value $s$. $s=0$ = all 8 bytes green (legal). $s=k$ with $1\le k\le 7$ = only the first $k$ bytes legal. $s$ negative = whole granule red (redzone / freed). 3. The check for an $N$-byte access at address $A$ (with $N\le 8$, aligned): it reports a bug when $s\ne 0\text{AND}(A\&7)+N-1\ge s.$ Here $A\&7$ is the offset inside the granule (the last 3 bits of the address), and $(A\&7)+N-1$ is the index of the last byte you touch.

-fsanitize=address. You must use it when compiling and linking every object, because the runtime replaces malloc/free process-wide. See Compiler Instrumentation and -fsanitize flags.

Fully legal (green). Zero literally means "all 8 bytes addressable". Look at the leftmost stack of tiles in the figure: the note on it reads 0.

• (a) redzone — poisoned padding placed around each buffer so an adjacent overflow lands in red.
• (b) shadow memory — the compact map, 1 byte per 8 app bytes, storing legality.
• (c) quarantine — after free, the block is held (not reused) so use-after-free stays detectable.
• (d) Offset — the fixed constant added in $\text{Shadow}(A)=(A\gg 3)+\text{Offset}$ so the shadow region sits somewhere that never collides with real data.

$A\gg 3$ divides by 8: $0x70000040/8=0x0E000008$. Add the offset: $0x0E000008+0x7FFF8000=0x8DFF8008$. So the one shadow byte guarding this granule sits at $0x8DFF8008$. In decimal: $A=1879048256$, $A\gg 3=234881032$, shadow $=234881032+2147450880=2382331912$.

$0x1000\gg 3=0x200$ and $0x1007\gg 3=0x200$ (the low 3 bits $000$…$111$ are shifted away), so $A_1$ and $A_2$ share one shadow byte — they are the first and last byte of the same 8-byte granule. $0x1008\gg 3=0x201$, a different shadow byte: $0x1008$ starts the next granule. See the two adjacent tile-stacks in the figure — each stack of 8 tiles gets exactly one note.

Since $s=0$, the first condition $s\ne 0$ is false, so the whole AND is false → no report. The check short-circuits the instant it sees a fully-green granule. That is the fast common case: one shadow load, one compare-to-zero, done.

The condition is $s\ne 0\text{ AND }(A\&7)+N-1\ge s$, i.e. $i+1-1=i\ge 5$.

• p[4]: $4\ge 5$? No → legal. Byte 4 is inside the first $k=5$ green bytes (indices $0,1,2,3,4$).
• p[5]: $5\ge 5$? Yes → reported. Index 5 is the first poisoned byte in the same granule.
• p[6]: $6\ge 5$? Yes → reported. This is exactly the case one shadow byte per 8 was designed to express — a granule that is partly green.

Last byte touched $=(A\&7)+N-1$.

• Offset 2: $2+4-1=5$. Is $5\ge 5$? Yes → reported. The int spans bytes $2,3,4,5$ — and byte 5 is poisoned. This is the classic multi-byte access straddling the boundary: even though its first byte (offset 2) is green, ASan reports because its last byte crosses into red.
• Offset 3: $3+4-1=6\ge 5$ → reported too (spans bytes $3,4,5,6$). Notice a single shadow byte cannot say "bytes 0–4 ok and bytes 6–7 ok but 5 bad" — the model is strictly prefix-green: the first $k$ bytes green, the rest red. That prefix rule is why the check compares against the last byte you touch.

A freed / redzone granule gets a negative shadow value (ASan uses specific negative codes like heap-freed). For the comparison, negatives behave as "the whole granule is red": since $s\ne 0$ is true and $(A\&7)+N-1\ge s$ is always true when $s$ is negative (any offset $\ge$ a negative number), every access into it reports — no matter which byte. That is why use-after-free is caught on the first touch. See Stack vs Heap Memory Layout for why the freed heap block stays mapped long enough to be poisoned rather than unmapped.

• Granule 0 (bytes 0–7): all used → shadow $=0$.
• Granule 1 (bytes 8–15): only bytes 8,9,10,11,12 are user bytes (that is 5 of them, indices $\mathrm{0..4}$ inside this granule) → shadow $=5$.
• p[12]: inside granule 1 at intra-granule offset $12-8=4$. Check: $4\ge 5$? No → legal (it is the 13th and last user byte).
• p[13]: intra-granule offset $13-8=5$. Check: $5\ge 5$? Yes → reported (first redzone byte). See the two-tile picture in the figure: a full green stack next to a "5-green-3-red" stack.

a[4] lands in the redzone immediately after the array — a granule whose shadow is negative. The check's first clause $s\ne 0$ is true and the second is true → reported. This is the adjacent overflow ASan is built for. a[1000000] computes an address far away that may fall inside another live object's green memory. There the shadow byte is $0$, the check short-circuits, and ASan stays silent. Redzones are finite padding; they guard neighbours, not the whole address space. Pair ASan with Fuzzing (libFuzzer / AFL) to reach bugs and with Undefined Behaviour in C and C++ awareness to know its blind spots.

Shadow map: $\frac{1}{8}=0.125=12.5\%$ extra. That alone is small. The large "2–3×" figure comes from redzones (padding around every allocation), the quarantine (freed blocks held un-reused), and per-allocation bookkeeping. So the shadow is cheap; the safety padding and quarantine dominate — which is exactly why ASan is a debug tool, not a production one.

Sizes: malloc(10) → granule 0 = bytes 0–7 (shadow 0), granule 1 = bytes 8–15 but only 8,9 are user → shadow $=10\mathrm{mod}8=2$.

• p[9] = 'a': granule 1, offset $9-8=1$, $N=1$: $1\ge 2$? No → legal.
• p[10] = 'b': granule 1, offset $10-8=2$, $N=1$: $2\ge 2$? Yes → heap-buffer-overflow, WRITE of size 1.
• free(p): poisons both granules (now negative) and quarantines the block.
• char c = p[0]: granule 0 now negative, $s\ne 0$ true and $0\ge (\text{negative})$ true → heap-use-after-free, READ of size 1. ASan also prints where it was freed. (In a real run the process typically aborts at the first error — p[10] — unless halt_on_error=0; conceptually every listed access is a violation.)

ASan's runtime intercepts malloc/free globally. If some code allocates through the intercepted malloc (getting redzones) but other code was built assuming plain allocation — or if you fail to link the ASan runtime at all — you get link errors or false reports (e.g. mismatched allocator/deallocator). Fix: compile and link every translation unit and the final binary with -fsanitize=address, or if you truly cannot rebuild a dependency, isolate it or fall back to Valgrind Memcheck, which needs no recompilation because it instruments by emulation instead. Contrast with siblings MemorySanitizer (MSan) and UndefinedBehaviorSanitizer (UBSan), which have the same "instrument everything consistently" requirement.

For $N=1$ the report condition is $(A\&7)+0\ge s$, i.e. offset $\ge s$. So an offset is legal exactly when offset $<s$, whose largest integer value is $s-1$; it is reported exactly when offset $\ge s$, whose smallest value is $s$. With $s=5$: largest legal offset $=4$ (matches p[4] legal), smallest reported $=5$ (matches p[5] reported). ∎

1. Shadow byte $=0$ means what? ::: All 8 bytes green/legal.
2. Shadow of malloc(13)'s tail granule? ::: $13\mathrm{mod}8=5$.
3. Report condition for an $N$-byte access at $A$? ::: $s\ne 0$ AND $(A\&7)+N-1\ge s$.
4. Why is a[1000000] sometimes missed? ::: It can land in another live object's green memory.
5. Shadow-map memory overhead alone? ::: $12.5\%$ (1 byte per 8).