Safe-Linking and Allocator Checks

The HeapLesson 6 of 675 minutesLessonNo lab next

Protecting the free-list links

The allocator keeps its free-list links in memory that used to belong to the program. That’s convenient for reuse, but a stale write like the one from Use After Free and Controlled Reuse can reach those links too. If a link were just an ordinary address, changing it could change where the allocator looks next.

glibc makes that harder by encoding the link using the address where it is stored. The strange word at +0x00 in the discarded card is that encoded pointer. We’ll decode it from the addresses printed by our own program, then inspect the second word and the double-free check that uses it.

Learning objectives

By the end of this lesson

• Decode the pointer in a freed chunk by hand, and explain what safe-linking protects.
• Explain what the second word is for, having watched it catch a double free.
• Explain which checks the observed free paths apply, and what a successful free does not establish.
• Say which measurements in this section were about the allocator and which were about your tools.

An inspection bench

Create the working directory if needed and enter it in the Ubuntu terminal:

mkdir -p ~/underdunn-course/heap ~/underdunn-course/notes
cd ~/underdunn-course/heap
ldd --version

The recorded allocator is glibc 2.39 on x86-64 Ubuntu, with ASLR enabled. Keep your version with your results. Save the complete program below as bench.c. Keep these deliberate invalid reads and frees inside the supplied target in the isolated course VM, using the shown slot numbers and sizes.

/*
 * Inspection bench. Opens crates, hands them back, and shows what the
 * allocator wrote into them. Deliberately reads freed storage and can
 * double-free a slot to observe the allocator's checks.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <stdint.h>

#define SLOTS 8

static void  *slot[SLOTS];
static size_t asked[SLOTS];

static void open_slot(int n, size_t bytes)
{
    slot[n] = malloc(bytes);
    asked[n] = bytes;
    memset(slot[n], 'A', bytes);
    printf("  slot %d at %p\n", n, slot[n]);
}

static void back(int n)
{
    free(slot[n]);
    printf("  slot %d handed back, bench still knows %p\n", n, slot[n]);
}

static void peek(int n)
{
    uint64_t *p = slot[n];

    if (!p) {
        puts("  no such slot");
        return;
    }
    printf("  slot %d at 0x%012lx\n", n, (unsigned long)(uintptr_t)p);
    printf("    +0x00  0x%016lx\n", (unsigned long)p[0]);
    printf("    +0x08  0x%016lx\n", (unsigned long)p[1]);
    printf("    this address >> 12 = 0x%012lx\n",
           (unsigned long)((uintptr_t)p >> 12));
}

static void again(int n)
{
    puts("  handing slot back a second time");
    free(slot[n]);
    puts("  survived");
}

static void probe(size_t bytes)
{
    void *p = malloc(bytes);

    printf("  asked %zu, usable %zu, size field 0x%zx\n",
           bytes, malloc_usable_size(p), ((size_t *)p)[-1]);
    free(p);
}

static void reuse(size_t bytes)
{
    void *a = malloc(bytes);
    void *b = malloc(bytes);

    free(a);
    free(b);
    void *x = malloc(bytes);
    void *y = malloc(bytes);
    printf("  freed a=%p b=%p, then got x=%p y=%p\n", a, b, x, y);
    printf("  x==b? %s   y==a? %s\n", x == b ? "yes" : "no", y == a ? "yes" : "no");
    free(x);
    free(y);
}

int main(void)
{
    char line[256];

    setvbuf(stdout, NULL, _IONBF, 0);
    puts("Inspection bench.");
    puts("Commands: open <n> <bytes>, back <n>, peek <n>, again <n>,");
    puts("          probe <bytes>, reuse <bytes>, quit");

    memset(line, 0, sizeof line);
    while (fgets(line, sizeof line, stdin)) {
        line[strcspn(line, "\n")] = '\0';
        if (strncmp(line, "open ", 5) == 0) {
            int n = atoi(line + 5);
            const char *sp = strchr(line + 5, ' ');
            open_slot(n % SLOTS, sp ? (size_t)atol(sp + 1) : 64);
        } else if (strncmp(line, "back ", 5) == 0) {
            back(atoi(line + 5) % SLOTS);
        } else if (strncmp(line, "peek ", 5) == 0) {
            peek(atoi(line + 5) % SLOTS);
        } else if (strncmp(line, "again ", 6) == 0) {
            again(atoi(line + 6) % SLOTS);
        } else if (strncmp(line, "probe ", 6) == 0) {
            probe((size_t)atol(line + 6));
        } else if (strncmp(line, "reuse ", 6) == 0) {
            reuse((size_t)atol(line + 6));
        } else if (strcmp(line, "quit") == 0) {
            break;
        } else if (line[0] != '\0') {
            puts("  unknown command");
        }
        memset(line, 0, sizeof line);
    }
    return 0;
}

gcc -g -O0 -fno-omit-frame-pointer -Wall -Wextra bench.c -o bench

The commands below use the plain build first. This program intentionally retains freed pointers; compiler versions may warn about those uses even though they are the operations we want to inspect.

The two integer types used by peek are inspection scaffolding. uint64_t is an unsigned 64-bit integer, while uintptr_t is an unsigned integer type large enough to hold a pointer. They let the program print and shift the raw words without teaching us anything new about the allocator itself.

The link in a one-entry list

The discarded card in the controlled-reuse lesson had a word that resembled its address. Let’s start with one returned crate and look at that relationship again.

Run ./bench and enter:

open 0 64
back 0
peek 0
quit

  slot 0 at 0x55af30a6b2b0
    +0x00  0x000000055af30a6b
    +0x08  0x8e4fd202cd5dc091
    this address >> 12 = 0x00055af30a6b

The word at +0x00 is the chunk’s own address shifted right by twelve. Not a coincidence and not a hash: those are the same digits, with the last three thrown away.

Following the link between two chunks

One chunk on its own is a special case: its list has no next entry. Now hand back two and inspect the list. Run ./bench and enter:

open 0 64
open 1 64
back 0
back 1
peek 1
peek 0
quit

  slot 1 at 0x5a7bedc1c300
    +0x00  0x00005a7e4a7f1eac
    +0x08  0x67c285676fea7e15
    this address >> 12 = 0x0005a7bedc1c
  slot 0 at 0x5a7bedc1c2b0
    +0x00  0x00000005a7bedc1c
    +0x08  0x67c285676fea7e15
    this address >> 12 = 0x0005a7bedc1c

Slot 1 was handed back last, so it is at the head of the list of free chunks, and its +0x00 no longer looks like its own address. The calculation below shows how it relates to the other entry:

  stored      0x5a7e4a7f1eac
  address>>12 0x0005a7bedc1c
  XOR         0x5a7bedc1c2b0

That result is the other freed chunk’s address. The word at +0x00 is the address of the next free chunk, exclusive-ORed with this chunk’s own address shifted right by twelve.

Exclusive OR, written XOR, is reversible: applying the same mask a second time recovers the original value. That is why the shifted address can both encode and decode the link.

Slot 0 is the last in the list, so its “next” is zero, and XORing zero with the shifted address leaves the shifted address on its own. That is the special case you saw first.

This is safe-linking, and it has been in glibc since 2.32. The list of free chunks is a linked list, and the links are scrambled with something an attacker is presumed not to know: where the chunk is.

To encode a chosen next address, you’d need the mask derived from the location holding the link. Writing the raw address instead causes glibc to XOR it with that mask when decoding, producing a different pointer. A disclosure of the holding location supplies the mask, although knowing it alone doesn’t satisfy the allocator’s other checks. The glibc PROTECT_PTR and REVEAL_PTR macros show this operation directly.

The last entry also shows a limitation: because its next pointer is zero, its encoded link exposes its own location shifted right by twelve. Those bytes reveal the upper address bits even though they don’t reveal the exact low twelve bits. Safe-linking protects the list against an uninformed overwrite; it doesn’t make a freed chunk’s contents safe to disclose.

The key at +0x08

Both peeks above printed the same value at +0x08, in chunks at different addresses. Try two different sizes. Run ./bench and enter:

open 0 64
open 1 200
back 0
back 1
peek 0
peek 1
quit

    +0x08  0xddc0cdde9e2ae37e
    +0x08  0xddc0cdde9e2ae37e

Both entries carry the same key. In glibc 2.39 this is a process-wide random value, not a per-thread one, although the caches themselves are per-thread.

The key marks a chunk as a possible cache entry so that a later free can decide whether to search for it. You can see the separate key and cache definitions in tcache_key and tcache_perthread_struct in the implementation linked above.

Handing the same crate back twice

Run ./bench and enter:

open 0 64
back 0
again 0
quit

  slot 0 handed back, bench still knows 0x643f162112b0
  handing slot back a second time
free(): double free detected in tcache 2

echo $? reports 134. The survived line never prints.

On this free path, glibc checks whether +0x08 equals the process key. A match suggests that the chunk may already be cached, but ordinary application data could coincidentally have the same value.

glibc therefore searches the relevant bin in the current thread’s cache and aborts if it finds the chunk. The key is a quick filter, while membership in the list confirms the duplicate.

What happens when a chunk can’t enter the cache? In a fresh process, fill all eight slots before freeing them, so the eighth 64-byte allocation goes into a fastbin after the seven-entry cache fills:

python3 -c 'print("\n".join([f"open {i} 64" for i in range(8)] + [f"back {i}" for i in range(8)] + ["again 7", "quit"]))' | ./bench
echo $?

double free or corruption (fasttop)

This immediate duplicate is also caught, with status 134, because the chunk is already at the head of the fastbin. It is a different check from the tcache search, not evidence that every possible double-free sequence is detected. The message identifies the path this sequence reached.

A successful free can still leave bad metadata

Both duplicate frees were caught. Why, then, did some of the damaged size fields in the overflow lesson pass?

The checks were asking different questions:

• The size checks rejected a value below the minimum, but accepted some false sizes that met the minimum and alignment requirements.
• The tcache check looked for the chunk in the relevant list after its key matched.
• The fastbin check caught a chunk being returned when it was already at the head of that list.

A size can pass the checks we observed while describing more memory than the chunk actually occupies. Other free paths consult neighbouring chunks too, so a successful free here doesn’t tell us whether the heap will remain consistent on the next operation.

Keep the links intact in these experiments.

Compare the allocator used by each tool

The plain build gives us glibc’s layout. Running under a diagnostic tool can change both that layout and the reuse policy, which matters if we try to explain the tool’s output using glibc’s headers.

Let’s run the same two commands three ways, starting with the plain build. Run ./bench and enter:

probe 17
reuse 64
quit

  asked 17, usable 24, size field 0x21
  freed a=0x6197f3ce32d0 b=0x6197f3ce3320, then got x=0x6197f3ce3320 y=0x6197f3ce32d0
  x==b? yes   y==a? yes

Now under Valgrind:

printf 'probe 17\nreuse 64\nquit\n' > in.txt
valgrind -q ./bench < in.txt

  asked 17, usable 17, size field 0x0
  freed a=0x4a780e0 b=0x4a78160, then got x=0x4a781e0 y=0x4a78260
  x==b? no   y==a? no

The reported usable size is now the requested 17 bytes, and the immediate reuse comparison fails. Valgrind’s replacement allocator is not using the glibc layout we inspected earlier.

The header read is invalid here and should also produce an invalid-read diagnostic. A zero from that read is not evidence that no metadata exists. It is simply not a glibc size field we can interpret.

Build a separate ASan binary and run the same input:

gcc -g -O0 -fsanitize=address bench.c -o bench-asan
./bench-asan < in.txt

It stops on the attempted header read:

==34632==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x503000000038
READ of size 8 at 0x503000000038 thread T0
0x503000000038 is located 8 bytes before 17-byte region [0x503000000040,0x503000000051)
SUMMARY: AddressSanitizer: heap-buffer-overflow bench.c:57 in probe

Reading eight bytes before the allocation reaches a poisoned redzone: an AddressSanitizer guard region placed around the requested allocation rather than memory belonging to the program. ASan therefore reports the invalid access before the program reaches reuse. The 17-byte region is the requested allocation boundary; it doesn’t tell us whether the tool has bookkeeping elsewhere.

So the three runs answer different questions:

• The plain build lets us inspect the glibc chunk layout and reuse behavior.
• The diagnostic runs show invalid accesses, but their replacement allocation machinery changes the layout and reuse behavior we’re measuring.

That replacement is useful for tracking requested boundaries and delaying reuse. It just means we can’t explain its addresses using glibc’s headers. The Memcheck manual describes the replacement allocation functions and redzones.

Decode a different free order

Start a fresh plain process, open slots 0, 1, and 2 with 64 bytes each, then return them in the order 1, 0, 2.

Before using peek, predict the head and tail. Decode all three links using the address holding each link, and check that the chain accounts for every returned slot and ends at zero.

Check your chain

The list is slot 2, then slot 0, then slot 1, then null. Each free pushes onto the front, so the first slot freed is the tail. If decoding gives the wrong address, check that you shifted the address of the slot being inspected, not the next slot’s address. Only the tail’s encoded word equals its holding address shifted right by twelve.

Knowledge check

Question 1 of 3

A freed chunk's +0x00 holds 0x00005a7e4a7f1eac and the chunk is at 0x5a7bedc1c300. What is stored there?

A hash of the chunk's contents, used to detect corruptionThe next free chunk's address, XORed with this chunk's address shifted right by twelveThe chunk's own address, obfuscated so it cannot be read directly

Check answer

When the results don’t match

• If +0x00 does not equal the address shifted right by twelve on a single freed chunk, check that nothing else of that size was freed first. The relationship only looks that simple for the chunk at the end of the list.
• If your XOR does not produce the other chunk’s address, check you shifted the address of the chunk holding the pointer rather than the one being pointed at. That is the asymmetry the scheme depends on.
• If +0x08 differs between two chunks in the same run, you are looking at chunks that did not both go into the tcache. Lesson 3 is the reference for how many fit.
• If the double free aborts with double free or corruption (fasttop) rather than the tcache message, that chunk was past the cache. Both are correct results, and which one you get is a fact about how many of that size you had already freed.
• If the valgrind run prints the same numbers as the plain run, check that valgrind actually ran. Run valgrind --version and inspect stderr. -q suppresses introductory output, not invalid-access diagnostics, and a missing executable should produce an error.

To recover a known state, quit and start the program again. The bench keeps nothing between runs.

Check your understanding

For a use-after-free in another program, what would you need to know before estimating which data it could expose or change?

Compare your reasoning

The allocation history determines which object, if any, occupies the stale address when it is used. Relevant details include:

• the size of the freed object;
• the sizes and order of subsequent allocations;
• which of those requests or contents can be influenced;
• the allocator version and configuration.

Before reuse, ask which old bytes survived the allocator’s bookkeeping and which bytes the stale operation actually reads.

After reuse, inspect the replacement’s initialized contents, including its first sixteen bytes. The free-list fields no longer describe that storage once the new object has overwritten them.

These decoded links explain this glibc free list. A different allocator may keep metadata elsewhere or use a different reuse policy, so the inspection program itself may need to change. Start with the same concrete questions: where is the allocation boundary, what remains after free, and which request can obtain that storage next?