Exploiting heap use-after-free to manipulate control flow

This mission requires a CheriBSD sysroot and image with temporal safety! The executable can be built for both RISC-V and CHERI-RISC-V (and exploring both may be worthwhile), but the mission is for CHERI-RISC-V with heap temporal safety enforcement in place.

This mission is a potted exercise inspired by real-world vulnerabilities where an active adversary can influence the contents of a server's heap and, often without completing authentication, walk the server's protocol state machine through erroneous states. Popular bugs facilitating these exploits include double free, use-after-reallocation, and type confusion (esp. of temporally aliased objects). For this mission, we have simplified the interface to be a little "command language" read over stdin, detailed below.

The success criterion is executing the success function. To ease testing, this is the only case in which the program source claims to exit with a code of 42. Ordinary termination is signaled with 0 and invalid input results in the program terminating with 1. While the source does not overtly claim any other outcome, if control flow can be redirected, almost anything goes.

Program Overview

This is a (very) minimal simulation of a program that manages multiple sessions, objects within each session, and limited information flow between those sessions. Rather than network sockets, each session is represented by a struct farm and there are up to four such active at any moment. Within each struct farm is a circular collection of struct crops, at most one of which may be selected by the cursor of its owning struct farm. If no crop is selected, the cursor is said to be "in the gap". The crop at the cursor, if any, can be asked to describe itself, using a function pointer within the struct crop itself.

To make matters more exciting, a UFO may be summoned to perform particular kinds of mischief. The UFO may "abduct" a pointer into itself and can create crop signs within struct crop (with data) or struct farm (with a capability to the success() function).

The gadgets offered by the UFO are somewhat limited (that is, they are not "write what where" or arbitrary control transfer) as one might expect to see in a real application. Nevertheless, they are sufficiently powerful to provide myriad exploitation vectors on RISC-V without CHERI, and even a few on CHERI-RISC-V. However, we believe that enforced heap temporal safety will ensure that any use of them is either overwritten by subsequent program operations before the gadgets' effects influence control flow or will cause the program to fail-stop with a default-fatal signal (e.g., SIGSEGV or SIGPROT).

Building and running

We suggest using the ccc tool provided with this book, building for riscv64-purecap. For experimentation, this program also builds for riscv64, without CHERI. On riscv64-purecap builds, heap temporal safety enforcement may be disabled at program load time by setting the environment variable MALLOC_DISABLE_REVOCATION to a non-empty value. (While setting this flag prior to program loading disqualifies such invocations from completing the mission, being able to disable revocation from within main() would be quite interesting indeed.)

As said before, the program expects to read a command language from stdin. It will print "Ready" and then await input. Unlike real applications, this program is fairly chatty about its own operation to ease exploration. Nevertheless, it may be useful to run it within gdb, especially to differentiate causes of crashes.

Command Language Directives

Whitespace is quietly ignored in most cases; this may simplify reading programs.
Digits 0 through 3 focus on the corresponding farm slots, making it the locus of subsequent commands until altered.
F allocates a new farm at the current slot.
f frees the current slot's farm (along with any crops in its collection)
C creates a new crop in the current farm and puts it at the left of the collection. The cursor is left in the gap or pointing at the crop it was before. If the cursor is not in the gap, the new crop will inherit the description of the selected crop; otherwise, the program chooses one of two varieties of cherry.
L and R move the current farm's cursor left and right, respectively. The farm's collection is circular with a gap; moving left (right) from the gap places the cursor at the rightmost (leftmost) element, and walking off either end returns the cursor to the gap.
Z moves the current farm's cursor to the gap.
D describes the crop at the current farm's cursor, if that cursor is not in the gap.
c removes the crop at the current farm's cursor from the collection and frees it.
U causes a UFO to arrive; u causes it to leave. There is at most one UFO at any moment.
A causes the UFO, if present, to abduct the current farm's cursor, presumably for further scrutiny.
S causes the UFO to make a crop sign on the current farm; s causes the UFO to read the next sizeof(void*) characters from stdin (whitespace is not ignored for this) and use that to sign the crop indicated by the current farm's cursor (a smaller crop sign, if you will). Writing crop signs of either variety is very destabilizing and likely to lead to crashes!
On CHERI-RISC-V builds running with heap temporal safety enforcement, ! will force a revocation pass, destroying pointers to free objects and allowing reuse of memory and address space.

Example Session

Here is a short session which creates one struct farm, two struct crops, exhibits cursor control and description of struct crops, and then tears down the struct farm:

$ echo FCC RD ZLD f | ./temporal-mission
Ready (CHERI-RISC-V)
New farm (index 0) at 0x41201080
New crop at 0x41201100
New crop at 0x41201180
Farm 0 cursor 0x41201180
FYI: Current farm is 0x41201080
FYI:  cursor 0x41201180
FYI:  cursor->describe 0x102fd2
Chelan at 0x41201180
Farm 0 cursor 0x41201100
FYI: Current farm is 0x41201080
FYI:  cursor 0x41201100
FYI:  cursor->describe 0x10300e
Colt at 0x41201100
Tear down farm (index 0) at 0x41201080

Source code

temporal-mission.c

/*
 * SPDX-License-Identifier: BSD-2-Clause
 * Copyright (c) 2020 Microsoft, Inc.
 */
#include <assert.h>
#include <ctype.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <sys/queue.h>

#if defined(__CHERI_PURE_CAPABILITY__)
#include <cheri/revoke.h>
static void __attribute__((used)) *check_cheri_revoke = cheri_revoke;
extern void malloc_revoke(void);
static void __attribute__((used)) *check_malloc_revoke = malloc_revoke;
#endif

struct farm;
struct crop;

static void
success(struct farm *f)
{
	fprintf(stderr, "Exploit successful: computer bought the farm!\n");
	exit(42);
}

TAILQ_HEAD(cropq, crop);

struct farm {
	struct cropq	cropq;
	struct crop	*cursor;
};

struct crop {
	void			(*describe)(struct crop *);
	TAILQ_ENTRY(crop)	farm_cropq;
};

_Static_assert(sizeof(struct crop) == sizeof(struct farm),
    "Structure size mismatch");

union ufo {
	void	*ptrA;
	char	buf[sizeof(struct crop)];
};

_Static_assert(sizeof(struct crop) == sizeof(union ufo),
    "Structure size mismatch");

static void
descr_1(struct crop *c)
{
	fprintf(stderr, "Chelan at %p\n", c); /* Pacific Northwest */
}

static void
descr_2(struct crop *c)
{
	fprintf(stderr, "Colt at %p\n", c); /* United Kingdom */
}

static unsigned int cid;
static union ufo *ufo;

#define NFARM 4
struct farm *farmp[NFARM];

static void
rm_farm(int fix)
{
	struct farm *f = farmp[fix];

	farmp[fix] = NULL;
	if (f != NULL) {
		struct crop *c, *tc;

		TAILQ_FOREACH_SAFE(c, &f->cropq, farm_cropq, tc) {
			TAILQ_REMOVE(&f->cropq, c, farm_cropq);
			free(c);
		}

		fprintf(stderr, "Tear down farm (index %d) at %p\n", fix, f);
		free(f);
	}
}

static struct farm *
mk_farm(int fix)
{
	struct farm *f;

	rm_farm(fix);

	f = malloc(sizeof(struct farm));
	assert(f != NULL); /* Surely infinite memory */

	TAILQ_INIT(&f->cropq);
	f->cursor = NULL;

	farmp[fix] = f;

	fprintf(stderr, "New farm (index %d) at %p\n", fix, f);
	return f;
}

static void
rm_crop(struct farm *f, struct crop *c)
{
	fprintf(stderr, "Del crop at %p\n", c);
	TAILQ_REMOVE(&f->cropq, c, farm_cropq);
	free(c);
}

static struct crop *
mk_crop(struct farm *f)
{
	struct crop *c;

	c = malloc(sizeof(struct crop));
	assert(c != NULL);

	if (f->cursor != NULL) {
		/* Inherit description of current cursor */
		c->describe = f->cursor->describe;
	} else {
		c->describe = (cid & 1) ? descr_1 : descr_2 ;
	}
	cid++;

	TAILQ_INSERT_HEAD(&f->cropq, c, farm_cropq);

	fprintf(stderr, "New crop at %p\n", c);

	return c;
}

static void
rm_ufo(void)
{
	if (ufo != NULL) {
		fprintf(stderr, "Del UFO at %p\n", ufo);
		free(ufo);
	}
}

int
main(void)
{
	int c;
	size_t fix = 0;

#if defined(__CHERI_PURE_CAPABILITY__)
	if (getenv("MALLOC_DISABLE_REVOCATION") == NULL) {
		fprintf(stderr, "Ready (CHERI-RISC-V)\n");
	} else {
		fprintf(stderr, "Ready (CHERI-RISC-V, reduced heap safety)\n");
	}
#else
	fprintf(stderr, "Ready (RISC-V)\n");
#endif

	while ((c = getchar()) != EOF) {
		if (isspace(c))
			continue;

		if (('0' <= c) && (c < '0' + NFARM)) {
			fix = c - '0';
			fprintf(stderr, "Selected farm %zu (%p)\n", fix,
			    farmp[fix]);
			continue;
		}

		struct farm *f = farmp[fix];
		switch (c) {
		case '!':
#if defined(__CHERI_PURE_CAPABILITY__)
			malloc_revoke();
#else
			fprintf(stderr, "No revocation without CHERI!\n");
#endif
			break;

		/* Crop management */
		case 'C':
			if (f != NULL)
				mk_crop(f);
			break;
		case 'c':
			if ((f != NULL) && (f->cursor != NULL))
				rm_crop(f, f->cursor);
			break;
		case 'D':
			fprintf(stderr, "FYI: Current farm is %p\n", f);
			if ((f != NULL) && (f->cursor != NULL)) {
				fprintf(stderr, "FYI:  cursor %p\n", f->cursor);
				fprintf(stderr, "FYI:  cursor->describe %p\n",
				    f->cursor->describe);
				f->cursor->describe(f->cursor);
			}
			break;

		/* Farm management */
		case 'F':
			mk_farm(fix);
			break;
		case 'f':
			rm_farm(fix);
			break;

		/* Cursor control */
		case 'L':
			if (f != NULL) {
				if (f->cursor != NULL) {
					f->cursor = TAILQ_PREV(f->cursor, cropq,
					    farm_cropq);
				} else {
					f->cursor = TAILQ_LAST(&f->cropq,
					    cropq);
				}
			}
			fprintf(stderr, "Farm %zu cursor %p\n", fix, f->cursor);
			break;
		case 'R':
			if (f != NULL) {
				if (f->cursor != NULL) {
					f->cursor = TAILQ_NEXT(f->cursor,
					    farm_cropq);
				} else {
					f->cursor = TAILQ_FIRST(&f->cropq);
				}
			}
			fprintf(stderr, "Farm %zu cursor %p\n", fix, f->cursor);
			break;
		case 'Z':
			if (f != NULL)
				f->cursor = NULL;
			break;

		/* UFO control sequences */
		case 'A':
			if ((ufo != NULL) && (f != NULL)) {
				fprintf(stderr, "UFO abduct %p\n", f->cursor);
				ufo->ptrA = f->cursor;
			}
			break;
		case 'S':
			if (f != NULL) {
				/* Jess's Organic Farm-to-Vtable Capability */
				fprintf(stderr, "Crop sign at farm %p\n", f);
				f->cursor = (void *)success;
			}
			break;
		case 's':
			if ((f != NULL) && (f->cursor != NULL)) {
				char buf[sizeof(void *)];
				for (size_t i = 0; i < sizeof buf; i++) {
					buf[i] = getchar();
				}
				fprintf(stderr, "Signing crop %p\n", f->cursor);
				memmove((char *)f->cursor, buf, sizeof(buf));
			}
			break;
		case 'U':
			rm_ufo();
			ufo = malloc(sizeof(union ufo));
			assert(ufo != NULL);
			fprintf(stderr, "UFO at %p\n", ufo);
			break;
		case 'u':
			rm_ufo();
			break;

		default:
			fprintf(stderr, "Did not understand %x; bail!\n", c);
			return 1;
		}
	}

	return 0;
}