AddressSanitizer Shadow Memory and the Cost of Byte-Granular Checks

A heap buffer overflow one byte past an allocation is invisible to the hardware. The byte lies in a page that is mapped, writable, and part of some other object, so no fault occurs, no signal is raised, and the corruption may not surface until much later. Detecting it requires a check on the access itself, and a check on every access requires a cheap way to answer “is this byte valid” without consulting a data structure with a lookup per load.

AddressSanitizer’s answer is a shadow memory: a parallel mapping in which each byte summarises the validity of a fixed group of application bytes. The compiler inserts a check before each memory access, the runtime maintains the shadow as allocations and frees happen, and the check is a load, a shift, and a compare.

Eight bytes of program per byte of shadow

The scale is 1:8. Every eight bytes of application address space correspond to one byte of shadow, and the shadow byte’s value encodes how many of those eight bytes are addressable from the start of the group. A value of 0 means all eight are valid; a value of k between 1 and 7 means the first k are valid and the rest are poisoned; a negative value marks the whole group as poisoned, with distinct constants for heap redzones, stack redzones, global redzones, and freed memory.

The mapping is a shift and an add. On x86-64, the shadow address for an application address is that address shifted right by three plus a fixed offset. Because the offset and the shift are constants, the compiler can emit them inline, and the check becomes:

#define SHADOW_OFFSET 0x7fff8000UL   /* fixed by the runtime's layout */

static unsigned char *shadow_for(const void *p)
{
    return (unsigned char *)(((unsigned long)p >> 3) + SHADOW_OFFSET);
}

/* One-byte access at p: any nonzero shadow value poisons this byte. */
int byte_is_addressable(const void *p)
{
    return *shadow_for(p) == 0;
}

For an access of n bytes at address p, the check compares the shadow byte at p >> 3 against p & 7, and if the access extends beyond the group boundary, also checks the next shadow byte. The compiler emits a fast path that falls through when both conditions hold and a call to the runtime otherwise, so the common case is a few instructions with no branch misprediction when the access is valid.

The choice of eight is the design’s central compromise. A finer scale — one shadow byte per program byte — would cost an eighth of the address space per byte of shadow, which is unaffordable, and would still not distinguish sub-byte validity, which is meaningless. A coarser scale — one per thirty-two bytes — would lose the ability to describe a partial group, and every allocation would have to be rounded up to the group size, so an overflow past the end of a 20-byte allocation would land in valid shadow. Eight is the granularity of the alignment that matters in practice: the smallest natural alignment is one byte, but partial groups arise only at allocation boundaries and at the end of stack objects, both of which the runtime can describe exactly.

Redzones turn overflow into a poisoned read

The shadow only helps if the bytes around an object are poisoned. The instrumentation therefore pads every allocation: a redzone before the object and a redzone after it, both poisoned, with the object’s own bytes left addressable. An access into the redzone reads a poisoned shadow byte and is reported at the moment of the access, with the address of the access, the address of the allocation, and the size of the allocation all available to the report.

The heap path is the runtime’s responsibility. The allocator behind malloc returns an address such that the bytes immediately after the requested size are poisoned, and the alignment of the returned pointer is preserved by choosing where the object sits inside a larger region. Freeing poisons the whole object rather than unpoisoning it, so a use-after-free reads a poisoned shadow byte and is reported.

Freed memory is not returned to the allocator immediately. It goes into a quarantine — a bounded queue of freed regions that are kept mapped and poisoned for a while. Quarantine is what makes use-after-free detectable at all: if the memory were reused at once, the next allocation would unpoison it and the stale pointer would read valid-looking data. The queue is bounded, so a program that frees more than the quarantine capacity eventually reuses memory, and a use-after-free of an old allocation may go undetected. That is a deliberate trade: the alternative is unbounded memory growth in a tool meant to run alongside the program it checks.

Stack and global objects are handled by the compiler rather than the runtime. For a stack frame, the compiler lays out the local variables with poisoned gaps between them and calls the runtime to poison and unpoison the frame at function entry and exit. The frame is unpoisoned on return, so a pointer to a dead frame is not detected by shadow alone; detecting it requires the fake-stack mechanism that keeps a shadow copy of returned frames for a bounded period. Global variables get redzones inserted at link time, with the runtime poisoning them during initialisation.

What the checks cannot see

The instrumented checks are inserted by the compiler, so anything the compiler does not instrument is unobserved. Hand-written assembly, code in a library built without instrumentation, and code reached through a function pointer into a prebuilt object are all unchecked. Calls from instrumented code into uninstrumented code are fine; the reverse is where errors escape, and the common case is a system library writing into a buffer the program passed it, which the library’s own instructions do unchecked.

The second blind spot is the interior of an object. Overwriting the second field of a struct with a value meant for the first is not a memory error at the shadow level: both bytes are addressable. The shadow answers “is this address part of a live object”, not “is this the right object for this pointer”. Distinguishing the two requires type information at every access, which C does not carry.

The third is arithmetic that stays inside a poisoned-but-mapped region. An access to a redzone is caught because the shadow byte is poisoned; an access to an address that was never mapped at all produces a genuine fault, which is also reported, but by a different path. And an access that is out of bounds by a large amount may land in another live allocation, where the shadow is unpoisoned. The report then comes from a check that sees a valid byte, and nothing happens. Large overflows are caught by chance, not by design.

The fourth is that the shadow map itself occupies address space. On x86-64 the offset is chosen so the shadow of the entire user address space is reserved in a region the kernel will not otherwise hand out, and the reservation is made at startup. That reservation is virtual, not resident: only pages whose corresponding program memory has been touched are committed. On a 32-bit target the arithmetic is much tighter, and the scale and offset were chosen to fit a 4 GB address space, which is why 32-bit sanitized builds have less room for the program itself.

Why this shape won over the alternatives

The competing approach at the time was dynamic binary instrumentation, as in Valgrind’s Memcheck: run the program on a synthetic CPU, track definedness per bit, and report errors without recompilation. That approach catches reads of uninitialised memory, which shadow-based ASan does not, and it requires no rebuild. Its cost is an order of magnitude in run time, and it cannot be combined with a normal debugger session without the debugger seeing the synthetic CPU’s state rather than the real one. The trade is described further in what dynamic instrumentation tracks that compiler instrumentation cannot.

Compile-time instrumentation wins on speed because the checks are inline and predictable, and it wins on debuggability because the program runs on the real CPU with real addresses. It loses on coverage of uninstrumented code and on detection of uninitialised reads, which is why MemorySanitizer exists as a separate build with a separate shadow scheme for definedness. Mixing sanitizers in one binary is possible for some pairs and not others, because each wants to own the shadow layout.

The instrumentation also changes the program’s memory behaviour in ways that matter when a bug is timing-dependent. Allocations are larger, addresses differ, and a race that manifested under one layout may vanish under another. A sanitized build is evidence about memory errors, not a faithful reproduction of the original timing.

Reading a report

A report names the access type, the address, whether the address is inside a heap, stack, or global region, and the allocation or free site with a stack trace. The trace is produced by the same unwinder machinery that a debugger uses, and its quality depends on frame information being present — the subject of stack unwinding with call frame information. The addresses in the trace are resolved to source lines through the line tables described in DWARF line tables, which is why a sanitized build should keep its debug information even when the shipping build does not.

The most misread part of a report is the distinction between the access and the allocation. A use-after-free report shows where the memory was allocated, where it was freed, and where it was accessed, in that order of recency reversed. The bug is at the access; the allocation and free traces explain why the memory was in the state it was. Treating the free site as the bug leads to fixes in the wrong function.

Two other report classes are worth recognising. A container overflow is reported when a standard library container’s internal buffer is accessed beyond its logical size but within its capacity; that check requires the library itself to be built with instrumentation, so it appears only with a fully instrumented standard library. A stack-buffer-overflow report includes the frame layout, with each variable’s offset and size, which is often the clearest evidence of which array index went wrong.