Full Memory Safety

Lecture 4 described defenses against the exploitation of memory errors {{ cite.eternalwar }}. A canary may detect an overwrite when the function returns; ASLR makes useful addresses harder to predict. Neither establishes that every memory access is valid. This lecture examines checks that stop an access if it falls outside the pointer's permitted bounds or if the allocation has ended.

Stated as obligations on a program, memory safety is three things, and it is worth reading them as three rather than one:

How it gets enforced

The same machinery as Part B of lecture 4: a compiler pass, or a binary rewriter when there is no source, inserts metadata describing what each pointer is allowed to touch, and inline monitors that consult it. Every scheme below is an inline reference monitor. What changes is the policy, and the policy here is far stricter than CFI: not “is this jump in the graph” but “is this byte inside this object, right now”.

Which brings back the assumption that made IRMs uncomfortable in the first place, and it is worth saying out loud before any of the designs, because all of them rest on it:

A property can be established before the program runs or while it runs, and the choice is a spectrum rather than a switch.

An ordinary C pointer representation does not carry explicit bounds or lifetime metadata. Compilers can still prove some accesses safe from the surrounding code, but arbitrary aliases, casts and separate compilation make complete static enforcement difficult. The systems below add and propagate the missing metadata.

Static and dynamic techniques can be combined in either language. Rust, the next lecture's subject, makes ownership and borrowing part of its type system. That enables many lifetime guarantees at compile time, while some bounds and shared-access checks still run dynamically.

Spatial safety needs one fact at every access: the range this pointer is allowed to touch. Associate a [start, end) with each pointer, or with each object, and check before every dereference. The idea is a sentence. The engineering is entirely in the next question, which is where you put those two numbers.

It matters more than it sounds, because a C program does not politely hold a pointer still. It increments it, casts it, stores it in a struct, passes it to a library you did not compile and gets it back. Wherever the bounds live, they have to survive all of that. There are three places to put them:

The representation affects compatibility, memory use and lookup cost. A base-and-bound check compares the entire access with a permitted range, but obtaining and propagating that range can be more expensive than the comparisons themselves.

CCured uses widened pointers where its analysis requires them {{ cite.ccured }}. Jones and Kelly record object ranges in a splay tree {{ cite.jonespkelly }}. Baggy bounds checking rounds and aligns allocations to simplify object-bound lookup {{ cite.baggy }}. SoftBound instead associates bounds with individual pointers and keeps that metadata separately; it does not require Baggy's allocation strategy.

The name comes from the first option above: conceptually, every pointer gets fatter, because it now carries a base and a bound as well as an address. SoftBound {{ cite.softbound }} is the design worth studying, and it is the one that keeps the semantics of a fat pointer while declining to make the pointer itself any wider. Its bounds live in a disjoint table, so the program's memory layout is byte for byte what it was, and a pointer is still one word.

These five rules describe how bounds are created, propagated and checked. The last distinguishes allocation bounds from optional subobject bounds:

{{ ruleCode }}

SoftBound places the bounds check at the memory access. This permits a valid one-past pointer to exist without being dereferenced. It does not make arbitrary out-of-range arithmetic legal C or C++: the language permits arithmetic within an array and one position past its end, subject to its pointer rules {{ cite.pointerarith }}.

Lecture 1B introduced bad-casting. The C++ example below illustrates one possible consequence: accessing a field beyond the allocated object. Assume four-byte integers and the illustrated layout, with Base occupying four bytes and Derived eight. In the comments, B is the allocation's byte address; B+4 means four bytes later.

struct Base { int x; };
struct Derived : Base { int y; };

void foo(Base *b) {
    Derived *d = static_cast<Derived*>(b); // invalid for a plain Base
    // A bounds-propagating monitor retains [B, B+4).
    d->y = 0; // attempted write [B+4, B+8): outside those bounds
}

int main() {
    Base *b = new Base(); // allocation range [B, B+4)
    foo(b);
    delete b;
}

This program has undefined behavior under C++ rules, so an ordinary build has no promised outcome. The attempted write illustrates what a bounds monitor can detect if it instruments that access: it exceeds the original allocation. This is an illustration of the bounds principle, not a guarantee about a particular C++ compiler's handling of invalid downcasts. A wrong-type access that stays within the permitted range can pass a bounds check; spatial safety is not general type safety.

Allocation bounds or subobject bounds?

The slides use a valid upcast to illustrate a separate policy choice. For the same simplified layout, a pointer to the base subobject could carry either that subobject's range or the whole allocation's range:

Derived *d = new Derived(); // allocation range [B, B+8)
Base *b = d;               // valid upcast; no new allocation
// Policy question: [B, B+4) or [B, B+8)?
delete d;

Both ranges stay within the allocation, but they enforce different boundaries. In the original SoftBound design for C, pointer casts propagate the existing bounds. Optional narrowing occurs when deriving pointers to structure fields, not simply because a cast names a smaller type {{ cite.softbound }}.

Spatial checks alone do not establish that an allocation is still alive. A stale pointer can still name bytes within its recorded bounds. Detecting that access requires lifetime information as well.

Temporal safety requires tracking the lifetime of an allocation. A common defensive practice addresses one pointer at a time: after freeing through a pointer, set that variable to NULL.

free(NULL) is defined to do nothing, so clearing the variable prevents a second free through that variable. Dereferencing NULL is still undefined behavior in C; it often faults on systems that leave the zero page unmapped, but that is not a language guarantee.

In both examples below, assume SIZE is positive and allocation succeeds.

Partial fix: prevents a second free through p

char *p = malloc(SIZE);
if (abrt) {
    free(p);
    p = NULL;                // clear this pointer variable
}
// If abrt is true: free(NULL), which does nothing.
// Otherwise: the allocation is freed for the first time.
free(p);

Failure through an alias

Now add an alias, r = p, before the conditional, and change the final operation from free(p) to free(r). Clearing p does not change r:

char *p = malloc(SIZE);
char *r = p;                 // another pointer to the same allocation
if (abrt) {
    free(p);
    p = NULL;                // p is cleared; r is left dangling
}
// If abrt is true: double free through the stale alias.
// Otherwise: the allocation is freed for the first time.
free(r);

Nullification is per-pointer. Temporal safety is per-object. The assignment p = NULL changes only p; it does not find or clear other pointers to the allocation. Such aliases can also be stored in structure fields and containers, or passed as function arguments. Clearing one pointer therefore does not establish complete temporal safety.

This is exactly why nullification, done properly, is a research problem rather than a style rule. Doing it properly means nulling every pointer to a dying object, which means keeping a reverse map from each object to all the pointers that currently reference it, maintained at runtime, in a program that has millions of both {{ cite.dangnull }}. Lecture 2 raised that as an aside. Here it is the reason the next design does something completely different.

CETS {{ cite.cets }} associates an allocation with a fresh key and a lock cell holding that key. Each pointer's metadata contains the key and the lock address. Before an access, compare the pointer's key with the lock. An instrumented free validates the pointer and invalidates the lock. Lock cells are managed separately so the check can still read them after the object's storage has been freed.

The model assumes keys are not reissued. A finite implementation must avoid reusing a key that a stale pointer could still hold. Step through the mechanism below; the final step shows an alternative continuation after the free.

In step 2, the instrumented pointer copy propagates both the key and the lock address. Every alias therefore checks the same lock cell. Freeing invalidates that cell without finding or modifying the aliases themselves. The system still needs to propagate metadata correctly on pointer copies; it avoids maintaining a reverse list of all aliases.

Keys are never reissued, which handles the case lecture 2's double-free lab lives in. When the allocator hands the same chunk to a new object, that object gets its own fresh key, so a stale pointer holding the old key matches nothing. Reuse of the memory does not restore the right to use it.

The 2010 CETS evaluation measured the following average runtime overheads on 17 SPEC benchmarks {{ cite.cets }}. An overhead of +116% means 2.16 times the baseline execution time. These are experimental results for that implementation and workload, not a fixed price for memory safety.

The original 2009 SoftBound paper separately reported +67% for full spatial checking across its 23 benchmarks {{ cite.softbound }}. That figure uses a different experiment from the +83% spatial-only result above. Metadata propagation, extra memory traffic, allocation bookkeeping and remaining access checks all contribute to the cost. Static optimizations can eliminate redundant checks.

The 2024 study in lecture slide 31 uses LLVM 12 and SPEC CPU 2017, with different results {{ cite.revisited }}. Its table reports the following percentage overheads; the geometric mean combines runtime ratios, while the arithmetic mean averages their percentage overheads:

The published artifact is available for reproducing the study; its README states that it is not maintained {{ cite.artifact }}. The two studies illustrate both runtime cost and the engineering work required to support a compiler and its libraries.

The trade-off involves coverage, runtime cost, compatibility and maintenance. Deployment varies by platform and application. A language that checks ownership and borrowing can establish many lifetime properties statically, while retaining runtime checks where necessary. That is where the course goes next.