Assignment 6: Crash reporter

Due date: Mon Mar 02 11:59 pm - Hard deadline: Fri Mar 06 11:59 pm

[Quick Links: Implementation details, Advice page, Grading]

Assignment by Julie Zelenski

Learning goals

After completing this assignment, you can proudly say that you have learned how to:

1. dissect an ELF object file
2. write a signal handler
3. manually troll the runtime stack
4. build a custom library and link it with other programs

The problem

When a program crashes outside of the debugger, its dying words, often nothing more than Segmentation fault, are little help in pinpointing the problem. With knowledge of the runtime stack and the executable file layout, you can come to the rescue by writing a fault handler. The handler can be linked into a program and will intercede on a crash and walk up the stack to give a symbolic backtrace of where the crash occurred. Fault handlers are often built into commercial applications to capture crash reports out in the field.

The assignment consists of two tasks:

1. Implement the namelist program that prints the list of functions contained in an object file. This program is a simplified version of the nm utility. This intermediate milestone verifies your handling of the ELF function symbol data.
2. Implement the crash reporter library that contains a fault handler to print a backtrace when a program crashes. It maps return addresses to symbolic name using the same symbol data as namelist.

The ELF format

Both namelist and crash reporter require you to do a little dissection of an object file. An object file is the result of compiling, assembling, and possibly linking, C source code. It contains global variables, string constants, function names, IA32 code, etc., all encoded as binary data. Object files on our Linux machines are in the Executable and Linking Format (ELF). The elf man page and sections 7.3-7.5 of Bryant and O'Hallaron provide explanation and diagrams for ELF. (And for the insomniacs, here is the full 100-page ELF specification). The helpful readelf command can be used to print the contents of a specific part of an ELF file to see how the data is stored. And here is a neat ELF file diagram that passed by HackerNews the other day. (Thanks to Dmitri and Daltron for sharing!)

For this assignment, you will dig into the ELF file to extract the function symbol information. The relevant ELF data includes:

• File header. Every ELF file begins with a file header. The file header describes the object file characteristics (endianness, architecture) and contains a roadmap to the file contents. readelf -h filename prints the ELF file header.
• Sections. The data within an ELF file is divided into sections. An object file commonly includes a text section (IA32 instructions), data section (global variables), symtab section (symbols), and strtab section (strings). The object file may also include additional sections for debugging, relocation, and other information.
• Section header table. This section header table is a table of contents for the sections. Each section is listed with its type, size, and offset within the file. readelf -S filename prints the section header table.
• Symbol table section. The "symtab" section contains a list of symbols. A symbol is a function or global variable and has a type, address, and size. The symbol name is also included, but in a roundabout way, as a numeric offset into the symtab's companion string table section. readelf -s filename prints the symbol table section.
• String table section. A "strtab" section consist of a list of strings, laid out end-to-end with terminating null characters. readelf -x index filename prints the contents of the section at the specified index (index is a number) in the section header table; this will dump the entire string table section.

The diagram below shows the parts of the ELF format you will access (uint is used as an abbreviation for unsigned int and uintptr_t types):

An ELF file is designed to be directly accessed with minimal translation from its on-disk representation. For example, the section header table is a contiguous sequence of section headers, where each section header is the same size and has the same fields in the same order. Thus, the section header table is laid out as an array of section header structures. Similarly, the symtab section is an array of symbol structs. This means that you can apply a typecast to the location of the data within the file and treat it like an array, directly accessing entries using ordinary array notation.

Here are the specific steps to read the symbols from an ELF file:

1. Read the initial characters of file and compare to the expected 32-bit ELF header. If header is valid, read the entire ELF file into memory. The starter project includes code for this task.
2. Use the offset and nsectionheaders fields from the file header to identify the location and length of the section header table.
3. Apply a typecast to location of the section header table to process it as an array of section headers. Loop over the array to find the section header whose type field is equal to SHT_SYMTAB. This is the header for the symbol table (symtab) section. An ELF file will have at most one symtab section.
4. Use the offset and size fields from the symtab section header to identify the location and size of the symtab section data. The offset for a section header is the number of bytes between the beginning of the ELF file and the first byte of the section data.
5. Apply a typecast to location of the symtab section data to process it as an array of symbols. Loop over the array to access each symbol in the table.
6. The strings for the symbol names are not directly stored in the symtab section. Instead, there is a separate companion string table (strtab) section that contains the string data for all symbol names. The symtab section header has a strtab_index field, which is the index into the section header table for the companion string table section header. There can be more than one string table section in an ELF file, so be sure to use strtab_index to access the correct one.
7. Use the offset and size fields from the strtab section header to identify the location and size of the strtab section data.
8. Apply a typecast to location of the strtab section data to access the strings. The strtab section data is a sequence of null-terminated strings laid out contiguously. A symbol's name field identifies where to find the symbol's name. The name offset is expressed as the number of bytes from the start of the strtab table section data to the start of the symbol's name string.

The symbols module

Your first task is to write code to extract the function symbols from an ELF file. Both namelist and crash reporter build on this functionality, thus you will put this code into a shared module that is compiled into both. You are to design the public interface of the symbols module. The goal of any interface is to provide useful functionality via routines that are sensibly designed and easy to use. A client should be able to make a simple request to get the desired information which is returned in a tidy package. Your interface should have the necessary flexibility to support its two known clients (namelist and crash reporter), but you don't need to anticipate needs of other potential clients in an attempt to predict the future.

Just because the internals of the symbols module have to deal with ELF in its ugly, native format doesn't mean it should return data to the clients in this raw state. The symbols module can, and should, abstract away the goopy details and provide the requested information in a form that doesn't require the client to get entangled in the low-level technicalities of ELF.

The namelist program

The namelist program prints the function symbols from an object file. It is a simplified version of the standard nm utility.

• The arguments to namelist are a required filename and an optional address. The filename is the name of an object file, either a relocatable .o file or an executable. The optional additional argument is a hexadecimal address. It is a usage error if no filename is given, the named file doesn't contain a valid 32-bit ELF file header, or the address is not well-formed. A well-formed hexadecimal address consists of up to 8 hexadecimal digits, upper or lower case, optionally prefixed with 0x. On any usage error, namelist prints an appropriate, informative error message and exits.
• Namelist is required to handle only properly formatted 32-bit ELF files. Anything else (including 64-bit ELF) is rejected.
• If the object file has no symbol table section (i.e. strip was used), namelist prints a message indicating there was no symbol table and exits. If the file has a symbol table section but it contains no defined function symbols, namelist prints nothing.

• If the optional address argument was not given, namelist prints every defined function symbol from the symbol table. The symbols are printed one per line; the symbols are output in case-insensitive lexicographic order by name. The four columns are the symbol address, size, binding (T for extern or t for static), and name. The required format is shown below. For both the address and the size, use the printf format %08x which outputs 8 hex digits aligned with leading zeros.

  00000064 00000014 T binky
  00000000 00000015 t crash_here
  00000036 0000002e t dinky
  00000078 00000017 T main
  00000029 0000000d T pinky
  00000015 00000014 t winky
  

• Namelist prints only defined function symbols with static or extern binding. Non-function symbols (i.e. symbol's type != STT_FUNC), other bindings (symbol's binding != STB_GLOBAL or STB_LOCAL), and undefined symbols (i.e. symbol's section_tag == SHN_UNDEF) are all discarded.

• The optional address argument is a hexadecimal address. If given, namelist searches for a matching function symbol for that address. The address matches a symbol if it is within the range spanned by the symbol's start and size. If symbol binky starts at 0xa3 and has size 16 bytes, all addresses from 0xa3 to 0xb2 are within its range. If a match is found, it prints the symbol name and hex offset (distance from the function start to the matched address). If the address is not within any function range, namelist responds that no match was found. The required format for found and not-found is shown below. Your program should exactly match this wording and print both the address and offset using format %#x.

  > namelist buggy.o 0x6a
  Address 0x6a matches binky+0x6
  > namelist buggy.o 0x107
  Address 0x107 not found in any symbol range
  

• You'll discover some symbols are "synonyms"--- two or more symbols names with identical or overlapping ranges. If an address is within the range of more than one symbol, namelist matches it to the one whose name is first lexicographically.

Once you can reliably produce a list of function symbols and match an address to a symbol, you're ready for the fun job--- building on this work to create a crash reporter!

The libreporter library

When a program crashes outside the debugger, it leaves few clues to follow up on. If the bug is reproducible, running again under gdb can get you a backtrace. But what about those elusive bugs that aren't repeatable or only occur outside of gdb? A crash reporter can provide critical information about a crash without requiring a debugger.

You are to write the libreporter library that provides a crash reporter tool that can be linked into any program. Once initialized, the crash reporter monitors the executing program and on fatal error, it intercedes to produce a symbolic backtrace of the runtime stack before terminating. How does the crash reporter work?

1. When initialized, it harvests the list of function symbols/addresses using the symbols module and tucks them away for later use.
2. Also at initialization, it registers a callback function to be executed on a fatal error. This is done with a signal handler (more on that in a bit).
3. If a fatal error occurs, the callback function is invoked. It examines the runtime stack by traversing backwards from current frame to previous frames. The return address in each stack frame is mapped to its symbolic name.

When an exceptional event occurs (memory access violation, divide by zero, etc.), the kernel sends the process a signal. The default action for fatal signals is to terminate the program. Alternatively, you can register a function as the callback (called a signal handler) to instead process the signal. That callback might attempt error recovery, do cleanup, give information to the user, and so on. Our starting code in reporter.c shows the boilerplate code required to set up a signal handler. If you're curious, you can read more about signals from the man page for sigaction and in section 8.5 of Bryant and O'Hallaron.

The crash reporter signal handler will register for fatal signals that prints information about the event (signal number/name, faulting instruction) along with a stack backtrace. A sample crash report looks like this:

Program received signal 11 (Segmentation fault)
Faulting instruction at [0x08048f00] crash_here (+0x10)
[0xf778d410] <unknown>
[0x08048f52] dinky (+0x2c)
[0x08048f17] winky (+0x12)
[0x08048f24] pinky (+0xb)
[0x08048f3f] dinky (+0x19)
[0x08048f66] binky (+0x12)
[0x08048f78] main (+0x10)

Here is what is expected from your libreporter:

• To get crash reporting, a client program must link with libreporter.a and make a call to init_reporter(). A client program typically makes this call somewhere early in main, but it is valid to initiate crash reporting later in execution as well.
• When called, init_reporter harvests the symbol information and stashes it for later use. We make an exception to our standard prohibition against global variables and allow you to store this data globally within the reporter module, but you should confine the global state to the minimum needed and be sure to mark it static so it is not broadcast into the global namespace.
• The special path "/proc/self/exe" refers to the executable file of the currently executing program. You can open this path as an ELF file to get the symbol data for the currently executing program.
• If the executable itself is stripped (i.e. has no symbol table at all), then init_reporter does nothing. Without symbol information, it will not be able to produce a symbolic backtrace and it does not register for any signal-handling. In this way, a client can selectively disable all crash reporting for an executable by stripping its symbol table, instead of requiring a recompile. If init_reporter is called from a stripped executable, it behaves as a no-op: no error message is printed, no signal-handling is installed, and the program runs without crash detection.
• The reporter should register to handle the fatal signals SIGABRT, SIGBUS, SIGFPE, SIGILL and, SIGSEGV.
• The crash report needs to identify the function that was executing at the time of the fault. However, the return address of the topmost stack frame stores the caller of the executing function, the address of the executing function itself is not on the stack at all! Identifying which function was executing during the crash requires a different strategy. The signal handler is passed a machine context that includes the saved value of the %eip register (see starter code). This will be the address of the faulting instruction.
• The top of the stack is a little wonky after a signal because the innermost stack frame is forced off and replaced by the kernel's signal-dispatching function. This means the first frame (and, in some cases, first two frames) under your fault handler is an oddball. Don't worry about trying to recognize or skip this, just print what you find on the stack starting from directly under the fault handler.
• Each line represents one stack frame in the backtrace. Print the return address inside square brackets, followed by the function name and the hex offset enclosed in parentheses. The offset is the distance from the function start to the return address; it identifies how far into the function execution reached. Print the address using the %#010x format and print the offset using %#x.
• If an address is not present in the symbol table, looking up its address will not find a matching symbol name. This is not an error, nor cause for alarm. In the backtrace, print those addresses without an offset and identify them as <unknown>. Symbol names will not be present for dynamically-linked libraries or selectively stripped symbols.
• As noted above for namelist, there are some symbol "synonyms" where an address range is matched with two or more different symbol names. Choose the synonym with the lexicographically first name as the match for the backtrace.
• The backtrace stops at frame that is matched to the symbol main. There can be other frames behind main in the stack, but stop here, do not attempt to trudge through those frames or print them. You may assume that the symbol table will always contain a symbol named main.
• In the signal handler callback, you are trying to tread lightly to avoid making a bad situation even worse. Prepare everything you can in advance at initialization time when the state is still good. When/if the signal handler is called, be mindful it is operating in a fragile context, and you want to do only the absolute minimal work to print the backtrace and exit. In particular, do not initiate calls to malloc/free in the signal handler function as the heap may be in a corrupt state, so all allocation should be done in advance and you can ignore deallocation. The last line of your signal handler calls exit which halts and tears down the entire address space. You may also ignore clean up of the crash reporter globals even if the client program runs to completion without error.

• The crash reporter can be misled when the stack itself has been corrupted, such as when a buffer overflow has stomped on the return address and base pointer. An invalid return address will cause the reporter to mis-identify the function for a particular stack frame, which is not a big deal, but dereferencing an invalid saved base pointer can turn the backtrace into total garbage or more likely, crash the reporter during its stack crawl. The reporter should make an attempt to detect stack trouble by including a heuristic that stops the backtrace if it reaches a saved base pointer that appears whacked. A simple heuristic for identifying trouble is to reject a base pointer which points outside the bounds of the current extent of the stack. Here is an example crash report that shows the required error message to print when halting the backtrace.

  Program received signal 11 (Segmentation fault)
  Faulting instruction at [0x0804923a] crash_here (+0xb)
  [0xf7731410] <unknown>
  [0x08049267] dinky (+0x19)
  Halting backtrace: cannot follow saved base pointer [0x30000000] not within stack segment
  

• There are various other ill-behaved programs (infinite recursion that attempts to grow the stack beyond the maximum size, one that stomps global data and destroys your saved function symbols, etc) that cause problems that are not easily detected or handled. You are not expected to devise handling for these, nor will we test on them.

• Valgrind will be its usual helpful self for debugging any memory trouble that comes up in namelist, but running crash reporter executables under Valgrind doesn't make sense; the buggy program has memory errors and leaks due to incomplete execution. Furthermore, we static-link the buggy executables and Valgrind produces a multitude of spurious and misleading errors for statically-linked executables. We won't test crash reporter under Valgrind.
• You are expected to manually dissect the stack and symbols using your own C code. You must not use functions such as those from execinfo.h, dlfcn.h, or the gcc built-ins, nor should you use inline assembly.
• Important note: Given that library code is aggressively optimized for performance, the libc functions are compiled using the gcc option -fomit-frame-pointer which means some of those functions may not include the standard function prologue/epilogue to save and restore %ebp using the stack. These functions are called frameless. If a frameless function appears in the backtrace, your crash reporter is likely to be misled into skipping over this call or halting the backtrace due to this non-conforming use of the %ebp register. You do not need to take precautions or make a special case of this, just unwind the backtrace assuming all functions store a base pointer on the stack in the expected location. We will not test crash reporter on backtraces containing frameless functions.

Summary of project

• The starter project files include:

  • Makefile The Makefile has three targets that are built by default: namelist, libreporter.a, and buggy, a sample client program that links with the libreporter library. The Makefile makes it easy to extend with additional client programs. Custom sanity check can be used to compare the output of yours versus the solution--- very handy!
  • symbols.c This module extracts the function symbols from an ELF file and provides functions to manipulate that symbol data. This module is part of both the namelist and libreporter targets. You are to design an appropriate interface in symbols.h and implement it in symbols.c.
  • namelist.c This program prints and looks up function symbols. This file will contain only a trivial amount of code.
  • reporter.c The module is where you write the code for the signal handling and stack crawling.
  • buggy.c This sample program links with libreporter and deliberately causes a fatal error. You can use/change/cannibalize this program to test your reporter.

• Output format. Please pay careful attention to the output requirements for both namelist and the crash report, especially the required wording and printf formats. Use sanity check to verify that your output is conforming.

• Memory. We expect the symbols module and namelist to run cleanly under valgrind with no errors nor leaks reported. We will not test crash reporter under valgrind.
• Efficiency. We expect reasonable use of time/space. Memory should be not be grossly overallocated, nor time squandered.
• Design/style/readability. This code has potential to become rather ugly if you aren't keeping your eye on your goal to write publication-quality code. Keep it clean!
• Don't miss our page of hints and advice about this assignment.

Grading

Background information on how we grade assignments.

Functionality (100 points)

• Namelist cases (30 points) Verify that correct symbols are printed, with correct information, in correct order, from various well-formed ELF files.
• Namelist robustness (15 points) Handling of required error conditions and incorrect usage.
• Crash reporter cases (30 points) Verify correct backtrace for simple cases similar to given buggy program, as well as more complex cases (deeper stacks, different signals, unknown addresses).
• Crash reporter robustness (15 points) Handling of required unusual/edge conditions (invalid base pointer, stripped).
• Clean compile (4 points) We expect your code to compile cleanly without warnings.
• Clean run under valgrind (4 points) Namelist is expected to have a clean run under valgrind. The crash reporter will not be tested under valgrind.
• Reasonable efficiency (2 points) We expect your code to be reasonably efficient in its use of space/time.

Code quality (buckets weighted to contribute ~20 points)

Here we will read and evaluate your code in areas such as:

• Design of symbols interface. We expect the symbols module to export clean and appropriate features that can be easily used by the namelist and libreporter clients.
• Style and readability. We expect your code to be clean and readable. We will look for descriptive names, helpful comments, and consistent layout. Be sure to use the most clear and direct C syntax and constructs available to you.
• Clean use of pointers and memory. We expect you to show proficiency in handling pointers/memory, as demonstrated by appropriate use of stack versus heap allocation, no unnecessary levels of indirection, pointee types and typecasts used correctly, and so on. Show you are wise in the ways of pointers!
• Program design. We expect your code to show thoughtful design and appropriate decomposition. Data should be logically structured and accessed. Control flow should be clear and direct. Common code between the operations should be factored out and unified, not duplicated. Private shared helpers used for appropriate code-sharing. Leverage existing C library functions (e.g. qsort, lfind, strtoul) rather than re-implement that functionality.

Getting started

Check out a copy of the starter project from your cs107 repository using the command

hg clone /afs/ir/class/cs107/repos/assign6/$USER assign6

The assign6 samples directory is linked in your repo as slink and includes a sample namelist program and solution version of the crash reporter library.

Finishing

There is a sanity check that verifies output conformance of both namelist and crash reporter. Be sure that all debugging print statements are removed/disabled as extraneous output can interfere with the autotester. When finished, submit your code for grading. If needed, be sure to familiarize yourself with our late policy.