Linking Assignment

Due: Thursday, October 25, 11:59pm

This assignment is about understanding how the ELF format supports run-time linking for shared libraries on x86_64, including the way that references to global variables and functions are implemented and represented.Less directly, this assignment is also about manipulating pointers and numbers and moving between them. That practice should help with assignments later in the semester, too.

Starting with linklab-handout.zip, your task is to implement enforce, which copies an ELF-format shared library and

• identifies all global functions that are exported by the shared library, where the functions may include calls to open_it and close_it;

• makes sure that a function balances any call to open_it with a call to close_it before returning;

• makes sure that a function does not access a global variable whose name starts protected_ except between an open_it and close_it pair; and

• replaces any of the following with an instruction to crash with a trace/breakpoint interrupt:

  You don’t have to know how to implement a trace/breakpoint interrupt, since that’s covered by a helper library that is included with the initial implementation.

  • a call to open_it after a call to open_it with no close_it in between;

  • a call to close_it after a call to close_it with no call to open_it in between;

  • a return after a call to open_it with no close_it in between;

  • an access to a global variable whose name starts with protected_ where the access is not between open_it and close_it.

The intent is that your enforce starts processing a function in closed mode, switches from closed to open when it sees open_it (or replaces with a crash if the current mode is already open), and switches from open mode to closed mode when it sees close_it (or replaces with a crash if the current mode is closed). An access to a protected_ variable is replaced with a crash if the current mode is closed, and a return is replaced with a crash if the current mode is open.

For example, given a shared library that is the compiled form of

then the shared library has the following initial behaviors:

• f(1) will return 4 through a bad access of protected_v4 that is not between open_it and close_it.

• f(0) will return 3 by accessing protected_v3, which is a good access since it’s between open_it and close_it.

• f(-1) will call open_it without balancing the call, so there’s a bad return of the value of other_v2.

• f(-2) will call open_it and a balancing close_it, so there’s a good return of the value of other_v1.

A copy of the shared library produced by enforce, however, will have the following behaviors:

• f(1) will crash, since the bad access is replaced by a crash.

• f(0) will return 3 by accessing protected_v3, as before.

• f(-1) will crash, since the bad return is replaced by a crash.

• f(-2) will return of the value of other_v1, since the call to open_it is balanced with a call to close_it.

You can find additional and simpler examples in "ex0.c", "ex1.c", "ex2.c", "ex3.c", and "ex4.c", which are included with the starting code.

Starting Implementation

The starting code "enforce.c" handles copying a shared-library file to a destination file based on the command-line arguments. The enforce function—which doesn’t do anything in the starting code—receives a pointer to the in-memory copy of the destination file. Your job is to fill in the implementation of enforce so that it changes the destination file.

To determine function and variable information, your enforce function will read the destination ELF file as it exists in memory. To replace certain variable accesses and function calls with a crash, your enforce function will modify the in-memory copy of the ELF file. Through the magic of mmap (which we will cover later in the semester), those in-memory changes will be reflected in the destination file.

A key step in the implementation of enforce is to decode the machine code that implements a function. Since decoding x86_64 machine code is tedious, the starting implementation includes "decode.c" and "decode.h", where "decode.c" implements a decode function. The decode function is sufficient for functions in the shared libraries that we will use to test your implementation. In addition, "decode.c" provides replace_with_crash, which can replace an instruction with one to provoke a crash through a trace/breakpoint interrupt. See Decoding Machine Code for more information on using decode and replace_with_crash.

Your submitted solution will take the form of a single C file, "enforce.c", which must be implemented in ANSI C with GNU extensions. You must not modify "decode.c" or "decode.h", since you submit only your "enforce.c" file. We’ll compile and link enforce.c in the same way as in "Makefile", so it must be self-contained other than its uses of "decode.h", "decode.c", "elf.h", limited Unix headers and libraries for open and mmap, and ANSI C headers and libraries.

Assumptions

To simplify your task, you can make several assumptions:

• Your enforce need only recognize and adjust functions that are registered in the dynamic-symbol table (i.e., the .dynsym section) as a function type with a non-zero size.

• Your enforce can assume the usual strategies for implementing relocatable variables and functions in Linux. In particular, accessing a variable will go through a memory location that is listed in the .rela.dyn section, and jumping to an imported or exported function will go through the global offset table as described by a rela.plt section.

• Your enforce can assume that all references to functions are function calls, and no references to variables are function calls.

• Your enforce need only handle functions where the implementation is supported by decode. The decode function recognizes variants of mov, ret, cmp, test, jmp, jcc, and call instructions, among others.

• Your enforce need only handle calls to the functions open_it and close_it. No other functions will be called.

• Your enforce can assume that the functions in a shared library contain no loops. Furthermore, if a function branches, then you can treat branch as reaching distinct instructions and eventually returning independently (i.e., there are no branch joins that matter). Your enforce can also assume that a function contains less than 20 conditional branches. These constraints simplify the traversal of a function’s machine code.

Evaluation

To earn points, your implementation must correctly install crashes in the form of a trace/breakpoint interrupt.

• You can earn up to 80 points by handling only functions that contain no branches and that do not access global variables that start protected_.

• You can earn up to 90 points by detecting bad references to global variables that start protected_, replacing the bad references with a crash, but still not handling functions with branches.

• You can earn full credit only by handling functions branches, still replacing bad returns, open_it calls, close_it calls, and references with a trace/breakpoint interrupt.

When grading, we will infer a level of completion based on your program’s behavior on the tests that are included with linklab-handout.zip. We will then scale your grade for each level based on the number of our test cases that pass.

Your enforce can print out any information that you find useful. Our tests will look only at the shared library produced by enforce.

Decoding Machine Code

The decode function provided by "decode.c" has the prototype

where code_ptr refers to the machine code to decode, and code_addr is the address where that code will reside at run time. (The code_addr must be provided so that decode can tell the destination of relative references in the machine code.) The type code_t is an alias for unsigned char. Use code_t* for a pointer to machine code, so that pointer arithmetic works in terms of bytes, since decode reports an instruction length in bytes.

The ins argument receives the result of decoding one instruction, so pass the address of a locally declared instruction_t to decode. The instruction_t struct type has three fields: op, length, and addr. The decode function always fills in ins->op and ins->length, and it fills in ins->addr for some values of ins->op.

The possible values for op are (as defined in "decode.h"):

• MOV_ADDR_TO_REG_OP — The instruction moves a constant address into a register, possibly to access a global variable. The ins->addr field is set to the run-time address, and it’s a reference to a global variable if that address corresponds to a variable that is registered as a dynamic symbol.

• JMP_TO_ADDR_OP — The instruction jumps to a constant address, possibly as a tail call to an global function. The ins->addr field is set to the destination of the jump as a run-time address, and it’s a call to a global function if that address corresponds to a function that is registered as a dynamic symbol. The instruction after the jump need not be considered, unless it is reached through some other jump.

• MAYBE_JMP_TO_ADDR_OP — The instruction conditionally jumps to a constant address, most likely due to an if in the original program. The ins->addr field is set to the destination of the jump as a run-time address. This jump is never a call to a function, but the code at the target of the jump may go on to call a function or access a variable. If the jump is not taken, the immediately following instructions might access a variable or call a function.

• CALL_OP — The instruction calls a function. The ins->addr field is set to the destination of the call as a run-time address, and it’s a call to a global function if that address corresponds to a function that is registered as a dynamic symbol.

• RET_OP — The instruction returns from the current function, so the instructions after the return need not be considered, unless they are reached through an earlier jump. The ins->addr field is not set.

• OTHER_OP — The instruction is a move, arithmetic operation, or comparison operation that involves only registers and non-address constants. Your enforce can assume that these operations do not somehow synthesize the address of a global variable or function, so it can effectively ignore them. The ins->addr field is not set.

For all operations, the ins->length field is set to the length of the machine-code instruction in bytes, so code_ptr + ins->length is a pointer to the next instruction, if any. The assumptions allowed for enforce means that both branches of a conditional (i.e., the target of a MAYBE_JMP_TO_ADDR_OP instruction and the immediately following instruction) can be explored by using a recursive call to an instruction-traversal procedure for one or both of the branches. Don’t try to use a loop instead of recursion to handle jumps. Branches generate a tree shape instead of a sequence shape, so recursion is the right tool (even in C, if the tree is shallow). A loop is the right choice for traversing instructions up to a branch, though.

If decode does not recognize the content at code_ptr as a machine-code instruction, it reports an error and exits. We will use test inputs where public functions conform to the constraints of decode, so you do not need to handle machine code that decode does not recognize (when used properly).

The "decode.c" library also provides replace_with_crash:

Pass code_ptr for an instruction that you want to replace with a trace/breakpoint interrupt. Also pass ins as filled with information about the existing instruction, so that replace_with_crash knows how many bytes to replace (filling with “no-op” instruction bytes as necessary to fully replace the original instruction).

Tips

The information about ELF that you need to complete this assignment is mostly covered by Videos: ELF. The map slides should be helpful to find your way through a file; see also a video explaining the map. More generally, you can use "/usr/include/elf.h" as a reference to find relevant structures, fields, and macros. You might also consult any number of other ELF references on the web.

Use readelf to get a human-readable form of the content of an ELF file to get an idea of what your program should find. Use objdump -d to disassemble functions to get an idea of what your program will recognize using decode and to compare your output shared library to the input shared library.

All of the information that you need from the ELF file can be found via section headers and section content, so you will not need to use program headers. You’ll need to consult the .dynsym, .dynstr, .rela.dyn, .plt, and .rela.plt sections, at least.

When working with ELF content, you have to keep track of which references are in terms of file offsets and which are in terms of (tentative) run-time addresses where the library will eventually run. When working with ELF content that is mmapped into memory (as in the starting "enforce.c"), then you have one more way of referencing things: a pointer in memory at present. Be careful to keep in mind which kind of reference you have at any time. Again, the maps should help.

Don’t confuse “symbol” with “string,” and keep in mind that they are referenced in different ways. Symbols are referenced by an index that corresponds to the symbol’s position in an array of symbols. Strings are referenced by an offset in bytes within the relevant string section. Every symbol has a string for its name.

Take small steps. Start out by printing the symbol index for every function that is provided by the shared library. Then, print the name instead of the symbol index. Then, print the address where each function’s implementation is found, and so on.

Avoid parsing ELF information into your own set of data structures. An ELF file in memory can be viewed as a data structure already, based on the types that "elf.h" defines. Following different kinds of references is not always trivial, but it’s not difficult, and you can write little functions to make access more convenient and readable. The task and examples are small enough that there’s no need for extra tables or data structures to speed up searches.

As a lower bound, a complete solution can fit in about 250 lines of C code, including the 120 lines in the provided in the starting "enforce.c". Depending on whitespace (fine), comments (good), error checking (commendable), and duplicated code instead abstracting into a function (bad), many solutions will be the range of 300-400 lines.

Test Cases and Test Harness

The archive linklab-handout.zip provides a "Makefile" where the default target builds

• your enforce program from "enforce.c";

• a call program to try a function from a shared library; and

• shared libraries "ex0.so" through "ex4.so" from the sources "ex0.c" through "ex4.c".

For example, after running make with the initial files, you can check that calling "ex0.so"’s always_ok with the argument 1 produces the result 1 and never_ok with the argument 1 produces the result 3:

After you have completed enforce for enforcing paired open_it and close_it, then

Alternatively, you can use objdump -d dest.so and compare to objdump -d ex0.so to check whether your enforce has replaced the return in never_ok with an int3 instruction that triggers a trace/breakpoint interrupt.

The test makefile target runs your enforce on the "exn.so" shared libraries (overwriting "dest.so" for each attempt) and checks that the result behaves as predicted at the top of the "exn.c" source. You can use The make test80 to run only tests for the 80-point level of completeness, which is "ex0.so". You can make test90 to run only tests for the 90-point level of completeness, which is "ex0.so" and "ex1.so".

For grading, we will run your program on additional shared-library files. We may also compile your program with different optimization or debugging options; as always, your program must build with gcc on CADE machines with no language-adjusting command-line flags.