AddressSanitizer and the Arithmetic of Shadow Memory

An out-of-bounds access is undetectable in the machine model because the address it produces is indistinguishable from a valid one. A guard page makes one particular address invalid by removing its mapping, but pages are 4096 bytes and objects are not, so most of the space between an object’s end and the next page boundary remains mapped and writable. AddressSanitizer takes the opposite approach: leave every page mapped and record, in a separate table, which bytes are currently legal to touch. The check is then a lookup rather than a fault.

The design problem is making that lookup cheap enough to insert before every memory access. The answer is a shadow map at one-eighth scale, addressed by a shift.

One shadow byte per eight application bytes

For every eight bytes of application memory there is one byte of shadow, and the shadow byte describes the state of that eight-byte granule. The mapping is a shift and an addition:

/* The address computation the instrumentation performs. */
#define SHADOW_OFFSET 0x7fff8000UL

static inline unsigned char *shadow_of(void *addr)
{
    return (unsigned char *)(((uintptr_t)addr >> 3) + SHADOW_OFFSET);
}

The shift is by three because 8 = 2³, so eight application bytes collapse to one shadow byte and the table is one eighth of the application’s address space. On 64-bit Linux the offset is 0x7fff8000, chosen so that the shadow of the low half of the address space does not collide with the application’s own mappings; the exact constant differs between operating systems and between 32- and 64-bit targets, and is fixed at link time.

The contents of a shadow byte are a count. Zero means all eight bytes of the granule are addressable. A value from 1 to 7 means the first that many bytes are addressable and the rest are not, which is how a partially used granule at the end of an allocation is described. A negative value means the entire granule is poisoned, and the specific negative value records why: distinct constants mark heap redzones, stack redzones, freed heap memory, memory that has gone out of scope on the stack, and container annotations.

The partial-granule encoding is what makes the scheme precise for small objects. An allocation of five bytes occupies one granule whose shadow byte is 5; a write to byte five reads that shadow byte, compares it against the offset within the granule, and reports because 5 is not greater than 5. Without the count, the granularity of the check would be eight bytes and a five-byte overflow would be invisible.

What the instrumentation emits

The compiler inserts a check before an access, not after it, and the check’s shape depends on the access size. For an access of one, two, four or eight bytes the generated code loads the shadow byte and compares it against zero, the fast path, valid when the access is aligned and does not cross a granule boundary. For larger accesses, and for unaligned or straddling ones, the check becomes a call into the runtime, which walks the granules the access touches.

/* Conceptually, the check emitted before a four-byte load from p. */
static inline unsigned int checked_load4(const unsigned int *p)
{
    unsigned char s = *shadow_of((void *)p);
    if (s != 0 && (uintptr_t)p % 8 + 4 > s)
        __asan_report_load4(p);
    return *p;
}

The cost per access is one shift, one add, one load and one predictable branch. The branch predicts correctly because the answer is almost always “valid”, which is why the scheme is affordable where a call into a checker on every access would not be. The runtime call exists only for the slow cases, and the report it produces carries the address, the access size, whether it was a read or a write, and a stack trace of both the faulting access and, when the region is known, the allocation that created the surrounding object.

Instrumentation is a compiler transformation, which sets a hard boundary: only code compiled with the sanitizer is checked. A program that links an uninstrumented library gets no checks inside that library, and an overflow that happens there corrupts memory the instrumented code will later read without noticing. The sanitizer is a property of the build, not of the process.

Redzones are how the bounds become visible

The shadow map can only answer questions about bytes the allocator has described. To catch an overflow at the end of an object, the allocator must poison the bytes after it, and to catch an underflow it must poison the bytes before it. Those poisoned margins are redzones, and they are the part of the design that costs memory rather than time.

For heap allocations, the interceptor around malloc requests extra bytes, aligns the user region, and poisons the leading and trailing margins with the heap-redzone value. The allocation is recorded in a per-thread structure so that a report can name the size and the call stack. On free, the entire user region is poisoned with the freed-heap value and the block is placed in a quarantine rather than returned to the allocator immediately, which is what turns a use-after-free into a report at the first access instead of a silent read of recycled data.

For stack variables, the compiler computes the frame layout and inserts poison and unpoison calls around the function body, with redzones between variables. The redzones are sized to catch the common overflows, and they are not uniform: adjacent small variables get small gaps, and the frame gets a larger poisoned region on the side facing the return address. A write into a stack redzone is reported at the store.

For globals, the compiler emits a descriptor for each global variable and the runtime poisons the bytes between globals at startup, using the same mechanism as the heap. This is the cheapest of the three, because the layout is fixed and the poisoning happens once.

Stack use-after-return needs more machinery than poisoning. A pointer to a local that escapes the function is a dangling pointer into a frame that has been reused, and poisoning the frame on return would report only accesses that happen before the next call reuses that stack slot. The precise answer is a fake stack: each function that has address-taken locals allocates its frames from a separate region, so a returned frame can stay poisoned while the real stack moves on. That mode is not enabled by default because it costs a real allocation per call, and without it a use-after-return is reported only when the frame has not yet been overwritten.

The factor-of-eight overhead and what it buys

The shadow map is one eighth of the address space, so the address-space cost is fixed at 12.5% plus the redzones and the quarantine. The runtime cost is the per-access check plus the interception on every allocation and free. Both are order-of-magnitude figures rather than precise ones: instrumentation of this kind is generally described as costing a factor of roughly two in execution time, and programs dominated by memory operations pay more than programs dominated by computation.

The quarantine is the tunable that trades memory for detection. A larger quarantine keeps freed blocks out of circulation longer, so stale accesses are more likely to land on still-poisoned memory; the price is that the process’s footprint includes the quarantine rather than just its live data. Debugging builds accept a generous bound; continuous fuzzing builds often lower it to keep the process within a memory budget.

What the scheme cannot see follows from what it checks. It checks whether an address is inside some object the runtime knows about, at the granularity of the shadow byte. It does not check whether the access is legal for the object the program thinks it is using. An overflow from one field of a struct into the next field of the same struct stays inside the allocation, so no shadow byte changes and no report is produced; the same is true of an index that walks past one element of an array into another element of the same array. Those are intra-object overflows, and catching them requires either finer granularity or a different mechanism entirely, the capability approach and the tagged-memory approach both narrow this gap by moving the check into the hardware.

It also cannot see uninitialised reads, because a byte that has been written once and read later is perfectly valid as far as the shadow map is concerned. Detecting that requires tracking definedness rather than addressability, which is a different shadow encoding and a different sanitizer.

Why the arithmetic survives translation

A natural objection is that the check is a compiler transformation and can be optimised away or miscompiled. The sanitizer’s answer is that the checks are inserted late enough to see the final address computation but early enough to be treated as having side effects, so the optimiser cannot delete them as dead code. The shadow arithmetic is on the raw address, after all indexing has been folded, which means it observes exactly the address the hardware will use.

The cost of that placement is that the check is not aware of the source-level object. It knows the address is inside a heap block of a recorded size; it does not know the address is the seventh element of a twelve-element array. That gap is the reason the sanitizer is a debugging tool rather than a safety guarantee, and the reason the language-level mechanisms, such as bounds checks, ownership, and tagged pointers, exist alongside it rather than being replaced by it.