Spatial Memory Errors (Advanced)

How the heap works

So far we have lived on the stack, and the stack can only do two things. It gives you memory whose size the compiler knew in advance, and it takes that memory back the moment the function returns. Many programs need neither. A server does not know how long the next request will be until it arrives, and a parsed document has to outlive the function that parsed it. For those you need memory requested at run time, in a size chosen at run time, that stays yours until you say otherwise. That is the heap.

You already know the interface: malloc(n) asks for n bytes and hands back a pointer to them, and free(p) gives them back. What the interface hides is the bookkeeping. Something has to remember how large each block was and which blocks are back in circulation, and that something keeps its notes inside the heap, interleaved with your data.

The heap is a separate region of the process's address space; the two grow towards each other:

Rather than take anyone's word for how that bookkeeping is arranged, ask the allocator. This program allocates two blocks, writes into the first, and then reads the memory immediately around them. The numbers below are one real run of it; yours will differ only in the addresses.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char *a = malloc(50);
    char *b = malloc(50);
    strcpy(a, "hello");

    printf("a           = %p\n", a);
    printf("b           = %p\n", b);
    printf("b - a       = %ld bytes, for a 50-byte request\n", (long)(b - a));
    printf("8 bytes before a = %#zx\n", ((size_t *)a)[-1]);
    printf("8 bytes at a     = %#zx\n", ((size_t *)a)[0]);

    free(a);
    printf("\nafter free(a), nothing else touched:\n");
    printf("8 bytes at a     = %#zx\n", ((size_t *)a)[0]);
    return 0;
}

a           = 0x55c36eb3d010
b           = 0x55c36eb3d050
b - a       = 64 bytes, for a 50-byte request
8 bytes before a = 0x41   <- the size field
8 bytes at a     = 0x6f6c6c6568   <- "hello", your data

after free(a), nothing else touched:
8 bytes at a     = 0x55c36eb3d   <- the allocator's bookkeeping, over your data

Three things fall out of that output.

The pointer you are given is not the start of the block. Eight bytes before it sits 0x41, the allocator's record of this block. That is 64 with the bottom bit set: 64 is the block's real size, and the bottom bits are free to carry flags because sizes are always rounded up to a multiple of 16 and so can never use them. Header and data together are called a chunk, and malloc hands you a pointer into the middle of one.

Chunks are packed back-to-back. Asking for 50 bytes twice put the two pointers 64 bytes apart, not 50: the request was rounded up and the header accounted for. Nothing separates one chunk from the next, so running off the end of the first block does not land in unused space. It lands in the second chunk's header.

The allocator stores its notes inside your data. While the block was yours, the first eight bytes read back as "hello". After free, without anything else running, the same eight bytes hold a value the allocator put there. It did not need extra space to track the freed block, because it already had space: yours. The bytes you were writing into and the bytes the allocator threads its lists through are the same bytes, taking turns.

That is why free chunks carry list pointers and chunks in use do not. There is no list of allocated chunks anywhere; an allocated chunk needs only its size, and its remaining space is yours to write. The moment you free it, the allocator reclaims that space for a forward and a backward pointer and threads the chunk into a list of free chunks, ready to be handed out again.

Which raises a question: how can chunks be “next to each other” if they also live in a linked list? Two different things are going on at once, a physical layout and a logical list:

Threading a chunk into that list, and pulling it back out, is ordinary doubly-linked-list code. Below is the shape of it, simplified from what GNU's C library actually runs but faithful in the part that matters (fd = forward / next, bk = backward / prev). Read fd and bk as occupying the same bytes the user was writing into a moment ago:

struct chunk {
    size_t         size;  /* always present, in the header    */
    /* everything below overlaps the user's data:
       these two fields exist only while the chunk is free */
    struct chunk  *fd;    /* forward  → next free chunk       */
    struct chunk  *bk;    /* backward → prev free chunk       */
};

/* Insert chunk `p` at the head of list `head`.
     head: the list's head (sentinel) node
     p: the chunk to add */
void list_insert(struct chunk *head, struct chunk *p) {
    p->fd = head->fd;
    p->bk = head;
    head->fd->bk = p;
    head->fd = p;
}

/* Unlink chunk `p` from whatever list it is in.
     p: the chunk to remove */
void list_unlink(struct chunk *p) {
    p->fd->bk = p->bk;     // p->next->prev = p->prev
    p->bk->fd = p->fd;     // p->prev->next = p->next
}

Now the two operations you call, in terms of that list. free(ptr) steps back from your pointer to the chunk header, then runs list_insert to thread that chunk into the free list. Nothing had to be unlinked, because an in-use chunk was never on a list; this is the step that writes fd and bk over what you last stored there.

malloc(n) goes the other way. It walks the free list for a chunk big enough, runs list_unlink to pull that chunk off the list, and returns its data area to you, at which point those same bytes are yours to write again.

So a chunk's life is a loop between two states, and list_unlink is the hinge it turns on. That makes it worth reading closely, because it does something quietly dangerous: it takes two addresses out of the chunk's own bytes and writes through both of them. If an attacker chooses those bytes, they choose what gets written where. That observation is what turned a memory-management routine into an attack, documented in Phrack in 2001 {{ cite.phrack_heap }}. Step through exactly what it does:

Heap overflows

The buffer overflows you have seen were on the stack. The same bug on heap-allocated memory is a heap overflow, and it corrupts something even more useful to an attacker than a return address: the allocator's own bookkeeping.

Two facts from How the heap works combine badly here. Chunks are packed back-to-back, so running past the end of your block lands in the header of the chunk after it. And a chunk that has been freed holds the allocator's fd/bk pointers in exactly that space. Put the two together: if the chunk after yours has been freed, an overflow does not merely corrupt somebody's data, it replaces two pointers the allocator is going to follow the next time it hands memory out. Step through it:

Notice the payoff, and notice what it never needed. There was no return address anywhere near this bug, so every defence built around protecting return addresses, canaries included, is watching the wrong place. What the attacker gets instead is a write-anything-anywhere primitive: a value of their choosing, at an address of their choosing, obtained purely by corrupting the allocator's own bookkeeping from a plain scanf. Once you hold that primitive, a return address is only one of the things worth overwriting, and rarely the most convenient. Lecture 2 arrives at the same primitive by a different road, freeing one chunk twice rather than overflowing into another.

↗ Lab, Program 1: four levels on two chunks sitting side by side

Integer overflow

Integers are finite. An 8-bit value spans [0, 255] unsigned, or [-128, 127] signed. Push past the edge and the value wraps, and a length check that relied on it silently becomes false. Integer bugs rarely corrupt memory by themselves; they corrupt the size that some later memcpy or malloc trusts, turning into a spatial overflow.

The root cause is that a bit pattern does not carry its own interpretation. The same eight bits stand for one number if the type is unsigned and a different one if it is signed, and nothing in the bits themselves records which was intended:

Nothing below the language will catch this for you. The ALU, the CPU's arithmetic unit, runs the same bit operations for signed and unsigned integers, because at that level there is no difference to act on: signedness is a claim the compiler makes about bits, not a property the hardware can see. So no fault is raised, no flag is checked, and the wrong number simply continues on into whatever uses it.

C then layers its own conversion rules on top, and they surprise people. Before almost any arithmetic, operands narrower than int are promoted to int, and to the signed one, whatever they started as: unsigned char + unsigned char has type int, and so does short + short. Only afterwards do the usual arithmetic conversions reconcile the operand types, and there the bias runs the other way: when a signed value meets an unsigned one of the same rank, it is the signed value that converts, so a negative number becomes an enormous positive one. Neither rule is new or optional, and neither is a compiler's choice; both have been in the language since C89 {{ cite.c_standard }}.

Integer bugs have caused real, expensive incidents, and they are common in OS code, where a wrong size becomes a kernel-level overflow {{ cite.cvedetails_linux }}. They are also far more common than they look: one study found thousands of overflows in ordinary C and C++, many of them deliberate and many not {{ cite.regehr_intoverflow }} {{ cite.wasc_intoverflow }}.

C++ subtyping

C++ is an object-oriented language built on class hierarchies and inheritance. To keep member access and method dispatch fast, the compiler must decide how each object is laid out in memory, packing the base and derived parts in a fixed order, chosen to optimise for speed and space. Those layout rules are exactly what a cast reinterprets, which is why casting is where a whole class of bugs lives.

Object layouts

When Derived inherits from Base, a Derived object is a Base sub-object followed by Derived's own members. Every variable and method of Base is therefore accessible through a Derived.

class Base { int x; };
class Derived : public Base {
  int y;
};

Derived* d = new Derived();

Now derive from more than one base class. The object simply contains each base sub-object in turn (a B1 sub-object, then a B2 sub-object) followed by Derived's own members, all laid out consecutively.

class B1 { int x; };
class B2 { int y; };
class Derived
    : public B1, public B2 { };

Derived* d = new Derived();

Upcasting: always safe

An upcast converts a derived pointer to a base pointer. It is always safe, because the base sub-object is genuinely there. With single inheritance, the base sits at the very start, so all the pointers even share the same numeric value.

Downcasting: not always safe

A downcast goes the other way: from a base pointer to a derived pointer. It is worth being clear why anyone writes one, because on its own a downcast looks like a silly thing to do, and real code is full of them. A container holds Shape* and you want the Circle-only method. A callback hands you an Event* and you know this one is a key press. Each of those rests on the programmer knowing something the type system does not. To produce the pointer the compiler subtracts the sub-object offset, the same one it added on the way up, and that arithmetic is right only if the object really is a Derived.

The trap: static_cast does no runtime check. A wrong downcast compiles without a warning and stays quiet until the program touches a field that was never there. C++ does offer a checked version, dynamic_cast, which consults the object's runtime type and yields nullptr when the cast is wrong instead of a bad pointer. It costs a lookup and needs the class to be polymorphic, and that price is why performance-minded codebases reach for static_cast and carry the risk themselves. A wrong static_cast is therefore a check you could have had and chose to skip.

Bad-casting

A bad cast is an unsafe downcast that produces a pointer to a type the object never was. Where it bites hardest is multiple inheritance: because each base sub-object sits at a different offset, a cast doesn't just relabel the pointer; the compiler adjusts its numeric value to reach the right sub-object. Get the source type wrong and that adjustment lands the pointer on memory that was never part of the object. Step through the safe case and the bad case side by side:

↗ Lab, Program 3: three levels on a cast the compiler will not question

Do it yourself

Three short programs, one per bug in this lecture, and ten tasks that climb from reading a heap layout to getting the allocator to accept corrupted bookkeeping without complaint. Each program prints its own addresses and offsets, so the distances you need are on the screen rather than in a debugger, and every input is ordinary typed text. The numbers quoted below came from running these exact sources, not from estimating them.

One thing to watch for as you go. In the stack lab the defences announced themselves: a canary fired, a program aborted, and you knew immediately that something had been noticed. Almost nothing here announces anything. Programs finish normally, free returns quietly, and the damage shows up only if you go looking for it.

{{ p.code }}

References

Links last checked July 2026. CVE Details and Stack Overflow both refuse automated requests, so those two were checked by hand.