Project 2: Control-Flow Integrity

Due: Monday 9 February, 11:59 PM

Goal

The goal of this assignment is to gain hands-on experience with implementing memory safety mitigations in a C compiler. Specifically, you will implement forward-edge control-flow integrity in the CParser/libFirm compiler.

Firm is a compiler intermediate representation (IR), in single-static assignment form; libFirm is a C library for manipulating, analyzing, and optimizing Firm IR and lowering it to machine code for a number of architectures, including (in highly experimental form) RISC-V. Cparser is a front-end that parses C99 and emits Firm IR.

Cparser is analogous to Clang; libFirm is analogous to LLVM. But the Cparser/libFirm codebase is orders of magnitude smaller than Clang/LLVM, making it less daunting to work with. And, as you will see in this project, the Cparser/libFirm code is readable, well designed, and easy to extend.

Forward-edge control-flow integrity

Control-flow integrity (CFI) is a class of mitigations that makes it harder for attackers to exploit memory vulnerabilities by means of code-reuse techniques.

In this project, we are concerned with forward-edge CFI for C: That is, with constraining the targets of function calls made through C function pointer variables.

We would like to enforce the following coarse-grained policy: An indirect function call made through a function pointer that is supposed to take $n$ arguments (according to the type of the function pointer variable) can only target address-taken functions that take $n$ arguments. Here “address-taken” means that the function is on the right-hand side of an assignment to a function-pointer typed lvalue.

We will build towards this policy in three parts. In Part A, we will allow indirect calls to all functions regardless of their arity and whether their address is taken. In Part B, we will restrict indirect calls to functions of matching arity. In Part C, we will disallow indirect calls to functions whose address is never taken.

Our CFI strategy will be the one discussed in class: each valid call target will start with a 4-byte CFI hint instruction, treated by the processor as a nop. Each indirect call will first check that the four bytes in memory at the destination address hold the byte representation of the CFI hint instruction.

Luckily, RISC-V reserves ample instruction encoding space to use as hints. For this assignment, we recommend that you use the slti instruction with rd set to x0 as the CFI hint. For Part A, set both rs1 and imm to all-0; for Part B (and Part C), use bits 16 through 23 of the instruction to encode the function arity (constrained to the range 0 to 255).

In the instruction sequence that checks the indirect call target, you can use any caller-saved registers you want as scratch registers. They are not guaranteed to be preserved by the function being called, so libFirm has already moved any values the caller cares about. But be careful not to trash the register that holds the jalr destination!

If the CFI hint fails, you will need to stop the program. The principled thing to do would be to call a special libc function that prints an error and exits. But for this project it’s easier just to execute an ebreak instruction.

If you use a branch to conditionally jump over the ebreak instruction, we recommend that you use the GNU assembler’s numeric local labels. If you use a global label name, the assembler may get confused if there is more than one checked jalr in the program; if you use hardcoded numeric offsets, you run the risk of having the assembler use a 2- or 4-byte instruction encoding where you expected the other.

The environment

We will use the class VM you installed for project 1.

In proj2.tar.gz we have supplied a patched version of Cparser and libFirm with just the RISC-V backend and with the default target set to riscv64-unknown-linux-gnu.

Running make inside the cparser subdirectory should build Cparser and libFirm and produce a compiler binary, build/debug/cparser. (If you have trouble building, let us know on Ed.) You can run make again to rebuild the compiler binary after making changes to either Cparser or libFirm.

In the tests subdirectory, we have supplied a Makefile and some test files you can use to test your cparser binary. Once you’ve compiled cparser, running

$ make hello

in the tests subdirectory should produce a hello binary. We have also included two more test files, addrtaken.c and trickier.c, that you can use as you work on the assignment. You will likely want to create additional tests as you go; just name the source file foo.c and add the binary foo to the Makefile variable TESTS.

Cparser’s source code lives in cparser/src; libFirm’s source code lives in cparser/libfirm/ir, and in this project we’ll mostly be concerned with libFirm’s backend code in cparser/libfirm/ir/be and especially with the RISC-V-specific backend code in cparser/libfirm/ir/be/riscv. (In a full libFirm checkout there are other subdirectories for other machine targets, but we’ve omitted those to make the output of code-search tools more useful.)

Because we build the cparser executable with debugging information, you can (and should!) run it under gdb. Write some simple test programs to compile, set breakpoints, examine memory, and use what you learn to guide your reading of the Cparser/libFirm source. libFirm has fantastic debugging support that you may want to take advantage of.

The assignment

Part A

Our first task is to gain flexibility in how jalr backend ops are translated to assembly, so we can add checks before the RISC-V jalr instruction. The function responsible for that is emit_riscv_jalr, but you won’t find it in the libFirm source code! Instead, like many other functions that make up the RISC-V backend, it is automatically generated from a concise Perl specification in libfirm/ir/be/riscv/riscv_spec.pl.

(Once you’ve built Cparser, the generated function will be in libfirm/build/gen/ir/be/riscv/riscv_emitter.c, which was created by the libfirm/ir/be/scripts/generate_emitter.pl script. I suppose we could edit it in place, but editing generated code is a no-no.)

Find the jalr key of the %nodes hash in riscv_spec.pl and comment out its emit key. Now, when you rebuild cparser no emit_riscv_jalr function will be generated, and if you try to compile a C program that makes an indirect call you will cause a compiler panic. Progress!

Create an emit_riscv_jalr function in libfirm/ir/be/riscv/riscv_emitter.c. Its body can consist just of the line

    riscv_emitf(node, "jalr\t%S2");

to start. Don’t forget to register it in riscv_register_emitters, in the same file. The compiler should work again.

Now you can modify your emit_riscv_jalr function to change the code emitted by the compiler for an indirect call. Add instructions that check that the jalr target starts with our special CFI hint instruction and stops the program (by executing an ebreak) otherwise.

You can use riscv_emitf to generate the additional instruction output, but you may find it easier to call the lower-level be_emit_irprintf function directly. Check out libfirm/ir/be/begnuas.c for examples of its use.

Hint: you can find the register that the jalr node is supposed to jump to by calling

    const arch_register_t *jalr_reg = arch_get_irn_register_in(node, 2);
    const char *jalr_reg_name = jalr_reg->name;

(Indeed, this is how riscv_emitf handles the %S2 directive.) Your code should not assume that a specific register was chosen by the register allocation algorithm!

Now that indirect calls check that the call target starts with a CFI hint instruction, we need to add a CFI hint instruction to the start of each function.

It’s easiest to do that by modifying riscv_emit_function, which is towards the bottom of libfirm/ir/be/riscv/riscv_emitter.c, the file you’ve been editing. This function calls be_gas_emit_function_prolog (in libfirm/ir/be/begnuas.c), which is somewhat confusingly named: It emits not what we’ve been calling a prologue in class (the instructions that set up a function’s activation record) but rather the boilerplate directives that tell the assembler that a function is about to begin. If you modify riscv_emit_function to add an instruction right after the call to be_gas_emit_function_prolog, you can be sure that this instruction will come first in the function body.

Hint: The RISC-V variant of the GNU assembler has a directive, .insn, that allows you to specify an instruction by giving its length in bytes and its numeric representation. For example, the directive .insn 0x4, 0x73 is equivalent to ecall.

You will submit a patch, parta.patch, that includes all the changes between the starting version of Cparser/libFirm to your modified version that incorporates your Part A solution.

First, unpack another copy of cparser-start.tar.gz into a directory called start instead of cparser:

$ mkdir start
$ tar xzvf path/to/cparser-start.tar.gz -C start --strip-components=1

Now create a diff between the clean version and your working version:

$ diff -durp clean cparser | grep -v '^Only in' > parta.patch

Double check that the patch shows changes to riscv_spec.pl and riscv_emitter.c only.

Part B

For Part B, we will modify function prologues so that the CFI hint encodes the function arity (i.e., the number of arguments it’s defined to take), and we will modify indirect calls to check that the target is not just any function but a function whose arity matches the function pointer type being dereferenced.

Changing the function prologue hint is straightforward: riscv_emit_function already has the ir_entity for the function, from which you can get the ir_type for the function type, from which you can find how many formal parameters the function takes. (You’ll want to look at the header files defining these types, and ways that they are manipulated elsewhere in the libFirm codebase. Code search tools will really help here.)

Changing the jalr instruction sequence as emitted by emit_riscv_jalr would also be easy if we had access to the number of formal parameters for the call, but unfortunately we don’t: It isn’t needed just to emit a jalr instruction, so it isn’t passed as part of the ir_node that is emit_riscv_jalr‘s argument.

Let’s fix that.

Look at gen_Call in libfirm/ir/be/riscv/riscv_transform.c, the function that lowers a Firm Call node to RISC-V specific nodes, including, most importantly for us, a jal or jalr node depending on the type of call. The gen_Call function knows how many formal parameters the call site has (that’s n_params), we just need to convey that information to jalr by changing the new_bd_riscv_jalr invocation to add n_params as another argument.

Except, oops, new_bd_riscv_jalr is another function in generated code (this time in libfirm/build/gen/ir/be/riscv/gen_riscv_new_nodes.c, as produced from riscv_spec.pl by the libfirm/ir/be/scripts/generate_new_opcodes.pl script).

The new_bd_riscv_jal function is also in generated code, and yet it takes extra arguments, as we can see in the line right above the one we just changed. How do we get that for new_bd_riscv_jalr?

The answer it turns out, is that backend nodes can have custom attributes. The definition of jal in riscv_spec.pl says that it has attributes of type riscv_immediate_attr_t, and that the new_bd_riscv_jal function should take additional arguments ir_entity *const ent, int32_t const val. Then the riscv_immediate_attr_t key of the %init hash specifies the code in the body of new_bd_riscv_jal (and every other function creating a new node with the same custom attributes type) that copies the function arguments into the attribute object. The type itself is defined in libfirm/ir/be/riscv/riscv_nodes_attr.h.

Let’s create a new attributes type, riscv_jalr_attr_t in that header file, with unsigned n_params as the type’s one custom attribute. We’ll need to modify the jalr object in %nodes and add a riscv_jalr_attr_t key to %init in riscv_spec.pl. Oh, we’ll also need to create a new comparison function, riscv_jalr_attrs_equal in libfirm/ir/be/riscv/riscv_new_nodes.c and put that comparison function’s prototype in libfirm/ir/be/riscv/riscv_new_nodes_t.h. And, finally, a get_riscv_jalr_attr_const getter in libfirm/ir/be/riscv/riscv_nodes_attr.h. Whew!

Now that we’ve done all that, we can use our get_riscv_jalr_attr_const getter in emit_riscv_jalr to get at our node’s custom attributes and, in particular, the n_params value that set us on this whole adventure. With n_params, we can change the instruction sequence to look for a CFI hint of the right arity.

You will submit a patch, partb.patch, that includes all the changes between the starting version of Cparser/libFirm to your modified version that incorporates your Part B solution. (This will include all the changes you made for Part A, too.)

Create a diff between the clean version and your working version:

$ diff -durp clean cparser | grep -v '^Only in' > partb.patch

Double check that the patch shows changes to riscv_spec.pl, riscv_emitter.c, riscv_transform.c, riscv_nodes_attr.h, riscv_new_nodes.c, and riscv_new_nodes_t.h.

Part C

Finally, we want to change the function prologue generation so that only address-taken functions have a CFI hint. That should be straightforward but, just as with Part B, we don’t have the information available in the backend.

Cparser constructs an abstract syntax tree (AST) corresponding to the C program it’s compiling; it then translates that syntax tree to Firm, after which libFirm takes over. During AST-to-Firm translation, the reference_addr function src/firm/ast2firm.c is called each time the AST indicates that some entity, such as a function, has its address taken by the program. (That’s because the taking-an-address-of operation is modeled in the Firm graph by an address node that Cparser needs to instantiate.)

We’ll change reference_addr to record when a function has its address taken, but first we need someplace in the AST to record that information in.

Add an address_taken member to Cparser’s function_t struct, defined in src/ast/entity_t.h. (There already is a member like that in the variable_t struct, in case you want an example.)

Now we can change reference_addr to set entity->function.address_taken = true; when entity is a function.

(Note: reference_addr has some logic that deals with a weird corner case of trying to take the address of certain built-in functions. The functions you are marking as address-taken are not built-in. Ignore this code; add your own separate if statement to reference_addr.)

Next, we’ll need to get Cparser to hand the information to libFirm when it translates a frontend function_t into a libFirm ir_entity, which is the job of get_function_entity, also in src/firm/ast2firm.c.

Cparser isn’t allowed to mess with libFirm internals; it has to go through the libFirm API. So we’ll need to change the API.

Modify the method_ent_attr struct in libfirm/ir/tr/entity_t.h to add an is_cfi_target field. Define a getter and setter for this field in libfirm/ir/tr/entity.c and put prototypes for them in libfirm/include/libfirm/typerep.h. (Note: not all files that include this header also include <stdbool.h>, so you probably don’t want to use bool in their type signatures even if that’s the type you chose for the is_cfi_target field.)

Now you can have get_function_entity use the setter to tell libFirm whether a function had its address taken and, finally, you can use the getter in riscv_emit_function to decide whether or not to emit the CFI hint.

(Actually, we’re not quite done. There’s a corner case that happens when reference_addr is called to record that some function is address-taken after get_function_entity is called to translate the function to Firm. In that corner case, function.address_taken is set too late to affect is_cfi_target. The solution is to check, in reference_addr, if the function being referenced already has a non-null function.irentity, and, if so, to call set_entity_is_cfi_target on it.)

You will submit a patch, partc.patch, that includes all the changes between the starting version of Cparser/libFirm to your modified version that incorporates your Part C solution. (This will include all the changes you made for Part A and Part B.)

Create a diff between the clean version and your working version:

$ diff -durp clean cparser | grep -v '^Only in' > partc.patch

Logistics

You will submit using Gradescope. You should submit a zip file of your solution, without directory structure. Your solution should include parta.patch, partb.patch, and partc.patch, created as above.

Grading

TBD.