Definedness Tracking: What Valgrind Memcheck Knows That Shadow Bytes Do Not

AddressSanitizer answers a question about location: is this address inside a live object? Memcheck answers a different question about provenance: was this value ever written? The two overlap on use-after-free and on some overflows, and they diverge completely on the case that motivates Memcheck: a branch taken on a value that came from an uninitialised buffer, where every address involved is perfectly valid.

No address-based scheme can catch that, because the invalid thing is not an address. The invalid thing is the value itself, and tracking it requires carrying extra state alongside every byte of program data, updated by every instruction that produces or consumes a value.

A second CPU, and a bit per bit

Valgrind does not instrument the program at compile time. It translates the machine code into an intermediate representation at run time, block by block, and executes that representation on a synthetic CPU. Instrumentation is added to the intermediate representation, so it applies to every instruction the program executes, including instructions inside libraries that were compiled without any cooperation and instructions generated at run time by a just-in-time compiler.

The extra state Memcheck maintains is a shadow value for each register and each memory byte. The shadow is not a byte per byte; it is a bit per bit, held in a vector of bits matching the width of the value. A 64-bit register has a 64-bit shadow, and each bit says whether the corresponding bit of the real value is defined. For memory, the shadow is stored in a parallel map keyed by address, allocated lazily as pages are touched.

Bit granularity is the design decision that separates Memcheck from a coarser scheme. Consider a four-byte integer initialised by two separate two-byte stores. With byte granularity, the value would be either defined or not, and the tool would have to pick one. With bit granularity, the shadow records exactly which bits were written, so a later use that reads the whole integer can be reported as partially undefined, and the report can name which bits are the problem. The same applies to a structure with padding: a memcmp over a structure whose padding was never initialised reads defined fields and undefined padding, and Memcheck reports it, because the padding bits are genuinely undefined.

The propagation rules follow the instruction semantics. An operation whose inputs are all defined produces a defined result. An operation with an undefined input produces an undefined result, with the exception of operations that mask the undefined bits away. An and with zero clears them, a shift that discards them removes them, and a comparison of an undefined value against a constant may produce a defined result if all inputs agree. That last rule is why Memcheck’s shadow arithmetic is more than a copy: it implements a simplified abstract interpretation of each opcode.

/* The abstract rule for a 32-bit add, in the shape the IR uses. */
typedef struct { unsigned v, defined; } shadow_u32;

shadow_u32 add32(shadow_u32 a, shadow_u32 b)
{
    shadow_u32 r;
    r.v = a.v + b.v;
    /* A bit is defined if both operand bits are, and the carry into it
       is defined. The carry chain is approximated conservatively. */
    unsigned carry_undef = (a.defined & b.defined) ? 0u : 0xffffffffu;
    r.defined = a.defined & b.defined & ~carry_undef;
    return r;
}

The real implementation tracks carry propagation precisely enough to avoid false positives on common code, which is why the simplified rule above is conservative rather than exact: a conservative rule reports some defined results as undefined, and a report on a defined value is a false positive, which erodes trust in the tool faster than a missed bug.

Where the definedness comes from

Memory starts undefined. A fresh malloc returns bytes whose shadow is all zero bits of definedness, which is exactly the C standard’s position: the contents of newly allocated memory are indeterminate. Writing to memory defines the bits written. Reading from it transfers the shadow to the destination register. Copying transfers the shadow wholesale, so an uninitialised buffer copied into a struct keeps its undefined bits.

Kernel-supplied data is defined by fiat. When a read returns, Memcheck marks the returned range as defined, because the bytes came from outside the program and the tool cannot know whether the kernel left them uninitialised. That is a deliberate approximation, and it is why a program that reads a partially filled buffer and then uses the whole buffer is not reported: from Memcheck’s perspective, the kernel defined all of it. The same applies to gettimeofday, stat, and other calls that fill structures. The syscall wrappers are annotated with parameter descriptions in the tool’s own configuration, so the tool knows which argument is an output buffer and how large it is.

Stack memory is treated differently again. Locals are not poisoned on entry to a function the way a redzone scheme would; instead, the stack region’s shadow is invalidated when the stack pointer moves past it, so a local that is declared but never assigned reads undefined. This is what catches the classic bug of returning a pointer to a local, or of using a variable before the branch that assigns it.

Partial writes produce partial definedness, and this is where the tool’s precision is most visible. A struct passed by pointer to a function that fills only some fields leaves the rest undefined. A subsequent write of the whole struct to a file descriptor is reported, because the syscall would transmit undefined bytes to the outside world. That report class — “syscall param points to uninitialised byte(s)” — is one of the most common, and it is also the one most often a false positive in the sense that the program may not care about the padding.

What the synthetic CPU costs

Translation is the price. Every basic block the program executes is decoded, converted to the intermediate representation, instrumented, and only then executed. Blocks are cached, so a loop that runs a million times pays the translation once, but code that runs each block once pays it every time, as happens on a large program’s startup path or in an interpreter executing a new path per input. The cost is an order of magnitude in run time, not a factor of two.

Memory is the second cost. The shadow map for memory is allocated per page as it is touched, and the tool’s own structures are substantial. A program with a large heap gets a proportionally large shadow, and the tool’s bookkeeping for allocation tracking adds more. This is why Memcheck is run on a reduced workload rather than on a full production trace.

The synthetic CPU also changes the observable behaviour of anything that inspects the machine. Code that reads the stack pointer, executes cpuid and branches on the result, or measures time by reading a cycle counter sees the tool’s emulation rather than the real machine. Self-modifying code is supported through a mechanism that detects writes to translated blocks and re-translates them, but the detection is per page and the re-translation is a cost. Programs with a hand-written thread scheduler that manipulates the stack pointer directly can confuse the stack tracking, which is why the tool serialises threads onto a single real thread and schedules them itself: it needs to know which stack belongs to which thread at every point.

Detection limits and the price of approximation

Memcheck does not detect buffer overflows inside the heap the way a redzone scheme does. Its heap blocks have no redzones, so an overflow into the neighbouring block’s memory is a write to valid, defined memory and passes unnoticed. What it does detect is the consequence: reading an address that was never allocated at all, which it tracks through its own record of every allocation, so a read 64 bytes past a block that lands in unmapped space is caught as an invalid read. The gap between those two cases is the reason both tools exist and are used together.

Use-after-free is detected because the tool marks freed blocks as inaccessible in its own address bookkeeping, not because a shadow byte was poisoned. That bookkeeping is also what produces the leak report at exit: blocks with no remaining pointer into them are listed with the stack trace of their allocation. The leak check runs after the program exits, and its accuracy depends on the program not having hidden pointers — an integer that happens to hold an address is not a pointer, and the tool’s heuristic of scanning for values that look like addresses produces both false leak reports and missed ones.

Conditional jumps on undefined values are detected precisely because the tool can see the shadow of the flags register. A branch whose condition depends on an undefined bit is reported with both stack traces: the one where the undefined value was created, and the one where it was used. That pair is the tool’s most valuable output, because the creation site and the use site are usually far apart and neither alone identifies the bug.

The interaction with debug information is a practical constraint. Memcheck can report source lines only if the program has line tables, and it reads them through the same DWARF machinery every other tool uses, described in DWARF line tables. Without them, reports contain addresses and function names from the symbol table at best. A statically linked binary with symbols but no line tables gives a report that names the function and the offset, which is often enough to find the bug by disassembly but never as fast as a line number.

Choosing between the two schemes

The decision is not which tool is better but which class of bug is being hunted. For spatial errors such as overflow, underflow, and use-after-free, the compile-time shadow scheme is faster, has lower memory overhead, and integrates with a normal debugger. For provenance errors such as uninitialised reads and partially initialised structures passed across a boundary, only the bit-level scheme can see the problem, and its cost is the price of that visibility.

Running both is common and not redundant, because a bug that the first misses on one input may be caught by the second on another. The sanitizer’s report is produced at the moment of the access and identifies the object; the dynamic tool’s report identifies the value’s history. Neither replaces the other, and the coverage argument in AddressSanitizer shadow memory explains why the spatial check can be blind to errors that stay inside a live allocation, which is exactly where the value-history check begins.