Rules

You are permitted to use a compiler (or any part of llvm/gcc/etc.) for the whole exam. You may spend up to 24 hours of active work on the exam. This time does not have to be contiguous.

Setup

Like usual, you should register for the assignment by going to https://grinch.caltech.edu/register which will create you a repository on gitlab with the starter code.

Written Questions

Heap and Stack (10 points)

typedef struct {
    int *input;
    size_t idx;
} arg_t;

void *do_it(void *_arg) {
    arg_t *arg = _arg;
    printf("%d\n", arg->input[arg->idx]);
    return NULL;
}

int main() {
    int input[10];
    for (size_t i = 0; i < 10; i++) {
        input[i] = i;
    }

    pthread_t tids[10];

    for (size_t i = 0; i < 10; i++) {
        arg_t arg = {.input=input, .idx=i};
        pthread_create(&tids[i], NULL, do_it, &arg);
    }
        
    for (size_t i = 0; i < 10; i++) {
        pthread_join(tids[i], NULL);
    }
}

Segmentation Fault (10 points)

Here is a “simple” program:

#include <stdio.h>

int main() {
    int *p = NULL;
    printf("Value is: %d\n", *p);
    return 0;
}

This program is compiled to a file named prog, which is then run from the command-shell via the command ./prog. When you run it, it completes in a way that you may have seen once or twice in CS 24. In this question, you will enumerate all steps in the program’s execution from beginning to end. The goal of this question is to demonstrate you understand how the various mechanisms of your system work.

shellcode & meltdown (10 points)

For each of the following exploits you’ve written, we’d like you to give a detailed description of how the exploit works. We’re not looking for you to tell us what the code does step by step; instead, we’re looking for you to explain why those steps are necessary and how they work.

Programming Question

Introduction

You’ve used asan…it prints error messages when bad stuff happens. In this miniproject, you’ll be implementing a mini version of asan. We’ve provided you with a partial implementation of a “bump allocator” malloc. Although this may look similar to the malloc project, we’re actually asking you to do something very different here. We no longer care about utilization or throughput at all. In fact, the final version of the project will still make no attempt to reuse memory after it’s been allocated. Instead, we will focus on user program correctness. Your malloc, like asan, will report various errors user code might have made while running. In particular, the types of errors we will focus on are:

• Invalid Free
• Double Free
• Memory Leak
• Invalid Heap Addresses

We’ll tackle these one at a time. Each individual feature has its own set of tests, and you will get credit for whatever subset of the features you implement. The last one is by far the hardest.

malloc with mmap (10 points)

Here is a brief description of the provided (partial) malloc implementation:

Allocations begin from the address START_PAGE and are always multiples of sizeof(page_t). The header is a single page before the first page of the payload with three (consecutive) pieces of data:

• A “magic number”: 0x0123456789ABCDEF (of type size_t)
• The exact size requested by the user (of type size_t). Do NOT round or edit this size. Since part of our implementation will determine if an invalid heap address was accessed, we will need to know this information later.
• An allocated flag (of type bool) Notably, we are not bothering to compress any of this information into a single size_t, because we do not care about utilization.

We maintain the invariant that the global variable current_page points to the page after the last page we’ve allocated using malloc. We ignore alignment requirements of the returned payload pointer. However, we insist that end of the payload is page aligned. That is, the remainder of the payload that does not make up a full page begins at the end of the first page of the allocation. This will be necessary for the last part.

As written, the provided implementation of malloc calls a few helper functions which are not yet written. Your job in this stage is to write the two following unimplemented functions:

• void set_header(page_t *header_page, size_t size, bool is_allocated)

  Sets the contents of the beginning of the provided header_page to the three pieces of data as described in the above description of the malloc implementation.

• ` void *get_payload(page_t *header_page, size_t size)`

  Given a header_page, get_payload determines the beginning of the actual allocated bytes. As mentioned above, it must be the case that the very end of the allocation be at the very end of a 4096-byte page.

Double Frees (10 points)

The provided implementation of free does nothing. In this stage, you will (1) mark the blocks as unallocated, and (2) check for double frees.

We have provided a function for you to call to report a double free and crash the program:

void report_double_free(void *allocation, size_t allocation_size)

Reports a “double free” (i.e., a user call to free with a “payload” that was previously allocated but is no longer allocated) and exits the program with a special error code.

Invalid Frees (10 points)

Currently, your free code assumes that the provided pointer is actually one that was returned by malloc. A user might make a mistake and send in an invalid pointer. In this stage, you will check (to the best of your ability) that the pointer provided to free was originally returned by malloc. In the case of an error, you should call the provided report_invalid_free function:

void report_invalid_free(void *address)

Reports an “invalid free” (i.e., a user call to free with a payload that was not previously allocated) and exits the program with a special error code.

Leak Checking (15 points)

The atexit function takes in a function pointer which gets executed when exit is called before actually exiting. This can be useful if you want to clean up (or, in our case, check) something before the program exits. In this stage, you will implement check_for_leaks, which has been installed by atexit, to determine if a user program forgot to free memory and thus has a memory leak. In the case of a memory leak, you should call the provided report_memory_leak function:

void report_memory_leak(void *allocation, size_t allocation_size)

Reports a “memory leak” (i.e., a situation in which there is memory that is still allocated after the user program has finished running) and exits the program with a special error code.

Invalid Memory Accesses (25 points)

The final task is quite a bit more involved than the others. In this task, you will use mprotect and a SIGSEGV handler to determine if an invalid read or write has happened on the heap. In the case of an invalid heap access, you should call the provided report_invalid_heap_access function:

void report_invalid_heap_access(void *address)

Reports an “invalid heap access” (i.e., a memory read or write to a location that is part of the “heap”, but was not part of a currently allocated block) and exits the program with a special error code.

Since you will be catching all Segmentation Faults, you’ll also have to respond to errors the user makes that are not invalid heap accesses; in such cases, you should call the provided report_seg_fault function:

void report_seg_fault(void *address)

Reports a Segmentation Fault that was not an invalid heap access and exits the program with a special error code.