how-to-exploit-a-double-free

This bug doesn’t exist on x86: Exploiting an ARM-only race condition

How to exploit a double free and get a shell. "Use-After-Free for dummies"

By cts

In this article, I'll teach you about real-world, modern binary exploitation, and a little about processor microarchitecture as well :D You will learn how to exploit a double free vulnerability or exploit a Use After Free vulnerability.

My CTF team, perfect blue, just concluded hosting our annual CTF, pbctf. One challenge I contributed was centered around a race condition vulnerability that only existed on ARM. In this article I'll explain the bug, why it doesn't happen on x86 processors, and finally how it can be exploited to land a shell.

This article is quite long, so I've added bookmarks. It consists of three main sections:

1. Walkthrough of the binary, and a peek into the mindset of a vulnerability researcher.
2. Memory ordering, lock-free programming, and how this can lead to sneaky bugs.
3. Exploiting an object lifetime heap corruption bug. How to get arbitrary read and write and finally, a shell.

0. Introduction

Let's get the show on the road! Might as well start with the challenge description from the CTF:

The pwnable, or the vulnerable binary, that players are tasked to exploit, is a simple command-line application accessible through netcat. When you connect, you're greeted with a prompt:

$ nc out-of-order.chal.perfect.blue 1337
hihgly scalable strlen() service
1. New job
2. Receive results
3. Manage results
3.1. View result
3.2. Delete result
4. Clear results history
5. Exit
>

The pwnable is essentially a fancy multi-threaded strlen() wrapper, designed around the consumer-producer pattern. The main functionality lets you 1) submit some strings, 2) wait for the program to process the strings, and 3) view and delete results. Our goal is to exploit the binary and read the flag from a file on disk (flag.txt).

To aid in exploitation, the source code for this challenge was provided with the binary and libc. This is pretty realistic: many major targets nowadays are open source. Examples include Chromium, Firefox, Linux, XNU, and even Windows offers symbols.

But what's the process of actually finding and exploiting a vulnerability like?

Well, if you want to find bugs, then it's time to get your hands dirty and start reading code. Nowadays with everything fuzzed to death, tools alone usually won't get you the good bugs that are worth big money. So let's dig in.

1. Source code audit

0. Internal data structures

When exploiting a new target it's absolutely crucial to understand all of the nitty-gritty details about the objects we can play with. In the pwnable, the two main data structures are a Request object and a "thread-safe" ring buffer.

Request object

struct Request
{
    char *str;
    uint64_t result;

    Request(char *str, int result) : str(strdup(str)), result(result) {}
    ~Request() { free(str); }
};

The Request object is little more than a RAII char* wrapper. It's 16 bytes big.

• Observation 1: Interestingly, the copy constructor isn't deleted. If we can double free a Request object, its backing char *str will also get double freed. Depending on the situation, this can either be useful or a hindrance.

• Observation 2: Since we control the length of the input string, we therefore control the chunk size of the strdup allocation. We can play with whatever size bins we want.

⟹ Key observation: We can play with the 16-byte bin that is used to service Request objects from the heap. If we could somehow get a dangling pointer to a Request object, we could corrupt that Request and then carefully use the corrupted object's overwritten char *str pointer to perform arbitrary pointer operations.

Well okay, if our goal is to corrupt one of these Request objects, we should probably look for some "complicated-looking" part of the program for bugs to do that with.

RingBuffer object

…

This is a supposedly "lock-free, thread-safe" generic queue with a fixed-size backing circular array. Writing advances the head pointer; reading advances the tail pointer; it blocks when writing while full or reading while empty. It's what you would expect.

Let's check out the consumer thread side of things.

// Reader-side functions
bool empty(const unsigned int& tail_local) const
{
    return head == tail_local;
}

T read(unsigned int& tail_local)
{
    while (empty(tail_local)); // Buffer is empty, block.

    T data = std::move(backing_buf[tail_local]);
    tail_local = (tail_local + 1) % buffer_size;
    tail = tail_local;
    return std::move(data);
}

All of the index arithmetic checks out, and the queue takes precise care of object lifetimes, even going as far as to explicitly specify std::move. What about the producer side?

// Writer-side functions
bool full(const unsigned int& head_local) const
{
    return (head_local + 1) % buffer_size == tail;
}

void write(T data, unsigned int& head_local)
{
    while (full(head_local)); // Buffer is full, block.

    backing_buf[head_local] = std::move(data);
    head_local = (head_local + 1) % buffer_size;
    head = head_local;
}

Okay, it wastes a slot to distinguish between full and empty; however this isn't a safety issue. And it looks just as careful as the other side. It looks like this queue was coded very carefully. There are no clear buffer overflows. On x86 in fact, it's pretty much correct[^7]---if you compile the given source code on a desktop, the program is essentially bug-free. So that's discouraging. But what can we leverage still?

[^7]: OK yes, the code still needs to have a compiler barrier to prevent compiler reordering. But both clang and gcc did not reorder on O3, probably because head and tail are both marked volatile (although volatile in general does not guarantee the absence of reordering). Also, it will not work if there are multiple producers or consumers. The point is, if you compile the code on x86 with -O3 on clang 10 or gcc 9.3.0, the resulting binary is not vulnerable.

Observation 1: For wq, Even though a Request* object is std::moved when it's read back out, it is not erased from the backing array. The pointers are still chilling in there (unlike std::unique_ptr, which zeroes its contents when moved). They will only be overwritten once the ring buffer wraps around again and those slots are filled with new elements.

Observation 2: This lock-free, volatile business is obviously fishy. The programmer clearly expects things to happen in a very specific, precise order. If we could somehow violate those assumptions, it may lead to a race condition. It's a common misconception that volatile acts like a barrier. Although some compilers may respect that, it is not a guarantee. And of course, the challenge name ("Out of Order") is a hint here. Since the most complex part of the program is often the most suspect, we'd better pay special attention to this code.

⟹ Key observation: If we could somehow get the ring buffer to return the stale contents of an uninitialized slot from the backing array, this could lead to a dangling pointer which points to an already-referenced Request object.

1. "New job"

case 1: {
    puts("How many requests in this job?");
    unsigned int count = get_number();
    if (count > 100000) { puts("Too many!"); exit(1); }
    for (unsigned int i = 0; i < count; i++) {
        if (!fgets_unlocked(buf, sizeof(buf), stdin))
            exit(0);

        wq.write(new Request{buf, 0}, wq_head);
    }
    break;
}

Okay, This lets us spray a lot of new Request objects into the work queue, and quite quickly too. Who is processing these requests?

void* thread_consumer(void* arg)
{
    uint64_t i = 0;
    unsigned int wq_tail = 0;
    unsigned int rq_head = 0;

    while (1) {
        auto data = wq.read(wq_tail);
        data->result = strlen(data->str);
        rq.write(std::unique_ptr<Request>(data), rq_head);
    }
}

Ahh, so a second thread reads from the other end of the FIFO, performs the work (strlen), and queues the results to the main thread on a results queue. The two threads communicate with a pair of half-duplex queues.

Where do the results go?

2. "Receive results"

case 2: {
    unsigned int n = 0;
    while (!rq.empty(rq_tail)) {
        results.push_back(std::unique_ptr<Request>(rq.read(rq_tail))), n++;
    }
    printf("Received %u results\n", n);
    break;
}

Nothing too crazy here, we receive back std::unique_ptr<Result> pointers from the results queue rq, and jam them into a vector. This vector thereby extends the object lifetime of the Result indefinitely until we free them.

3. "Manage results"

printf("%lu results:\n", results.size());
if (!results.size())
    return;
for (int i = 0; i < results.size(); i++) {
    auto& result = results[i];
    printf("#%d: %s", i, result.get() ? result->str : "<deleted>");
}

It prints out all of the results for us, and lets us choose one to play with.

3.1. "View result"

    case 1:
    printf("Input: %s\n", result->str);
    printf("Result: %ld\n", result->result);
    return;

This lets us read the char *str pointer. If we could control the value of str, we could use this to arbitrary read.

3.2. "Delete result"

    case 2:
    puts("Result deleted");
    result.reset();
    return;

It calls std::unique_ptr<Request>::reset, which destructs the Request and frees it. So we can totally control the object lifetime of Request objects.

4. "Clear results history"

case 4:
puts("All saved results cleared");
results.clear();
break;

I guess this lets us reset the program if things don't go our way. If we have some kind of UAF (Use-After-Free) or heap corruption situation going on, this will probably cause a segmentation fault or abort in free().

After a brief audit of the source code, we can see that the program's functionality is little more than a thin facade in front of glibc heap operations. This "heap note" interface might seem bare-bones, but it closely models how modern heap exploitation works. Typically, attackers will collect primitives for spraying and freeing memory and use them in concert with a bug like UAF or Double Free to construct a working exploit. Examples of popular primitives in "real life" targets include Javascript ArrayBuffers in browser exploitation, or IOSurface objects in iOS Kernel exploitation.

Still, though, it seems like we've hit a brick wall. We have no vulnerability in sight, and the code quality looks excellent. Where do we go from here? Before we can progress any further, we need to take a brief detour...

2. Lock-free programming

And now for something completely different! Welcome to the land of Systems Architecture.

In cool leg, we teach CS undergrads to protect their multi-threaded data structures with a lock. This is probably a Test-and-Set (TAS) lock, and if they went to a good university, they have a homework assignment where they are told to use lock cmpxchg to implement a mutex. Once they're all grown up however, (i.e., grad school) we teach them the truth: Locks are slow. Specifically, lock contention is slow.

(Disclaimer: the following explanation is an oversimplification. Please forgive me if I made any errors)

Lock contention is slow because of cache coherence. To synchronize two cores, the processors need some shared resource. So you put the lock variable somewhere in main memory. Of course, any reasonable expectation of performance in 2021 is not possible without caching. Typically, every core has its own local cache (even if there is possibly a shared last-level cache, depending on the architecture). **So e