CSCI 2021 Project 5: Binary ELF File Parsing

It is recommended to do some reading on the structure of the ELF format as it will assist in coming to grips with this problem. As you encounter parts of the below walk-through of how to find and print the symbol table, refer to the following resources.

• Diagrams shown below provide some information about the basics of what is provided in each portion of the file and how some of the records relate to each other.
• Manual Pages: The manual page on ELF (found online or by typing man elf in any terminal) gives excellent coverage of the structs and values in the file format. Essentially the entire format is covered here though there may be a few ambiguities.
• Wikipedia: A good overview of the file format and has some extensive tables on the structs/values that comprise it.
• Oracle Docs: A somewhat more detailed and hyper-linked version of the manual pages.

Note that we will use the 64-bit ELF format only which means most of the C types for variables should mention ELF64_xxx in them though use of 32-bit integers may still apply via uint32_t.

ELF files are divided into sections. Our main interest is to identify the .symtab (Symbol Table) and .text (Executable Code) sections. This is done in several steps.

1. Parse the File Header to identify the positions of the Section Header Array and Section Header String Table
2. Search the Section Header Array and associated string table to find the sections named .symtab which is the symbol table, .strtab which contains the string names of the symbol table, and .text which contains the binary assembly code. Note the position in the file of these three sections.
3. Iterate through the Symbol Table section which is an array of structs. Use the fields present there along with the associated string names in .strtab to check each symbol for the symbol of interest.
4. Once the symbol is found in .symtab, its value from .symtab is used to compute the offset within the .text section. This is where the function symbol's opcodes are stored.
5. Once the function opcodes are located, they can be printed or the function can be called. This behavior is dictated by command line arguments.

Since this is a binary file with a considerable amount of jumping and casting to structs, it makes sense to use mmap() to map the entire file into virtual memory. It is a requirement to use mmap() for this problem. Refer to lecture notes, textbook, and lab materials for details on how to set up a memory map and clean it up once finished. In particular Lab 14 uses mmap() to parse binary files in a way that is directly relevant to the present program.

This general approach is outlined in the provided loadfunc.c template. The reaming sections discuss tricks and techniques to use while filling in this template.

Make use of the mmap() function create a memory map for the file specified on the command line. Keep in mind that you may need to execute the code in this file so find out the correct options to use with mmap() to make its contents Readbale AND Executable.

The initial bytes in an ELF file always have a fixed structure which is the ELF64_Ehdr type. Of primary interest are the following

1. Identification bytes and types in the field e_ident[]. These initial bytes identify the file as ELF format or not. If they match the expected values, proceed. If incorrect, consult the later section on Error Conditions on what error message to print.
2. The Section Header Array byte position in the field e_shoff. The Section Header Array is like a table of contents for a book giving positions of most other sections in the file. It usually occurs near the end of the file.
3. The index of the Section Header String Table in field e_shstrndx. This integer gives an index into the Section Header Array where a string table can be found containing the names of headers.

The following diagram shows the layout of these first few important parts of an ELF file.

To keep the sizes of structures fixed while still allowing variable length names for things, all the names that are stored in ELF files are in string tables. You can see one of these laid in the middle purple section of the diagram above starting at byte offset 1000. It is simply a sequence of multiple null-terminated strings laid out adjacent to one another in the file.

When a name is required, a field will give an offset into a specific string table. For example, each entry of the Section Header Array has an sh_name field which is an offset into the .shstrtab (the sh is for "section header").. The offset indicates how far from the start of the string table to find the require name.

• The .shstrtab section begins at byte 1000 so all name positions are 1000 + sh_name
• The 0th .text section has sh_name = 0; the string .text\0 appears at position 1000.
• The 1th .symtab section has sh_name = 6; the string .symtab\0 appears at byte position 1006.
• The 4th .data section has sh_name = 32; the string .bss\0 appears at byte position 1032.

The Section Header Array is an array of Elf64_Shdr structs. By iterating over this array, fishing out the names from .shstrtab, and examining names using strcmp(), the positions for the two desired sections, .symtab and .strtab can be obtained via the associated sh_offset field.

Note that one will need to also determine length of the Section Header Array from the ELF File Header field e_shnum.

Also, on finding the Symbol Table section, note its size in bytes from the sh_size field. This will allow you to determine the number of symbol table entries.

In addition to identifying the .symtab and .strtab sections in the section header, identify and track the location of the .text section as this is where the opcodes for a function are stored. The .text section is copied directly into memory when a program is loaded. The section header struct field sh_addr is the requested location for some sections to be loaded. Often it is 0x0 for the .text section but not always. Record the value for sh_addr in your program as it is used to calculate the location of variable values from the symbol table.

Once the location of the .text section is located, print out some data about it in the following format.

.text section
- 1 section index
- 64 bytes offset from start of file
- 0x2000 preferred virtual address for .text

Similar to the Section Header Array, the Symbol Table is comprised of an array of Elf64_Sym structs. Each of these structs has a st_name field giving an offset into the .symtab section where a symbol's name resides. The following diagram shows this relationship.

Data on the symbol table is printed out in a format given in the template.

findfunc will work with the opcodes of a function described in the symbol table. To that end, one must iterate through the array of Symbol Table Elf64_Sym structs searching desired symbol. In the above diagram, my_pow is of interest and is found midway through the table at index 15. On finding the requested symbol, print out data about it in the format shown in the template which roughly corresponds to fields of the Elf64_Sym struct.

• The st_size in this case corresponds to the number of bytes of opcodes associated with the function in the .text section.
• The "value" in the st_value field is the preferred load address for the function though loaders/operating systems often select other addresses for everything in the .text section.
• The section index st_shndx field gives the ELF section in which this symbol is stored. In this case, it is section 1 which is the index of the .text section where opcodes are stored.
• The location of my_pow's opcodes in the .text section is computed by calculating its address as an offset from the address of the .text section:
  • .text will load at 0x2000 in the output above
  • my_pow is at address 0x200b
  • The opcodes of my_pow is therefore offset 0x200b - 0x2000 = 0xb = 11 from the start of the .data section
• Add 11 to the offset of .text from the beginning of the file (found in earlier when locating the .text section) to get the address of opcodes for my_pow

If the function symbol that is requested is not found in the symbol table, refer to the Error Conditions section for the appropriate error message to print.

Symbol table entries have a field called st_info which indicates some properties of the associated symbol such as whether it is an OBJECT (global variable) or a FUNC function. The field is binary data and such info must be extracted. A macro is provided to extract the type.

ELF64_ST_TYPE(somesym->st_info)

will extract type information. If this is equal to STT_FUNC symbol is a function. If not, then loadfunc should report an error as indicated in the template.

Treat the address for the function opcodes above as though it were a char * array though many values will not be in the ASCII range. These are arbitrary bytes that are best printed in hexadecimal and we will favor printing them in columns of 8. The final required output of findfunc looks like the following.

Bytes of function 'my_pow'
   0: 55 48 89 e5 89 7d ec 89 
   8: 75 e8 c7 45 f8 01 00 00 
  10: 00 c7 45 fc 00 00 00 00 
  18: eb 0e 8b 45 f8 0f af 45 
  20: ec 89 45 f8 83 45 fc 01 
  28: 8b 45 fc 3b 45 e8 7c ea 
  30: 8b 45 f8 5d c3 

• The left column is printed in hexadecimal, 4 characters wide, right adjusted. Use a format specifier of %4x for this. Note: an early version of the spec incorrectly stated to use decimal %d printing; this has been fixed to match the example provided.
• Each byte of the opcodes is printed in hexadecimal format with leading 0s in a space of 2 characters. Use a format specifier of %02hhx for this.

The template provides a number situations in which errors should be reported along with associated error messages. These are roughly:

• The file is not an ELF file as it has the wrong "magic bytes" at the beginning.
• There is no Symbol Table present in the file, associated with a "stripped" binary file. It may also be that there is no text or string table section either also leading to an error.
• The function symbol indicated on the command line is not found
• The function symbol is not actually a symbol, it is something else.

Error messages associated with each of these are provided in the template and when they should be printed in terms of program control flow.

A basic template for findfunc.c is provided in the code pack which outlines the structure of the code along with some printing formats to make the output match examples. Follow this outline closely to make sure that your code complies with tests when the become available.

One interesting aspect of dealing with functions in Binaries is that in some cases they can be run after being located. To arrange for this, several things need to be true.

1. The memory into which the function is loaded must be marked with Executable permission.
2. The types of the functions must be known (e.g. takes no arguments, returns an integer).
3. The functions must either use no global variables/other functions or be patched with addresses for these things.

It is not hard to arrange for the (1) and (2) above while (3) is much trickier.

By passing call on the command line, findfunc executes the function that is identified. Three examples from the somfuncs.o sample file are given here.

# runs return_five: takes no arguments and returns an int
>>  ./findfunc test-input/somefuncs.o return_five call 'int (*)(void)'
file_bytes at: 0x600000000000
Section Headers Found:
- 904 bytes from start of file
- 12 sections total
- 0x600000000388 section header virtual address
Section Header Names in Section 11
- 800 bytes from start of file
- 103 total bytes
- 0x600000000320 .shstrtab virtual address

Scanning Section Headers for Relevant Sections
[ 0]: 
[ 1]: .text
[ 2]: .data
[ 3]: .bss
[ 4]: .comment
[ 5]: .note.GNU-stack
[ 6]: .note.gnu.property
[ 7]: .eh_frame
[ 8]: .rela.eh_frame
[ 9]: .symtab
[10]: .strtab
[11]: .shstrtab

.symtab located
- 408 bytes from start of file
- 216 bytes total size
- 24 bytes per entry
- 9 number of entries
- 0x600000000198 .symtab virtual addres
.strtab located
- 624 bytes from start of file
- 75 total bytes in section
- 0x600000000270 .strtab virtual addres
.text located
- 64 bytes offset from start of file
- 0x0 preferred address for .text
- 0x600000000040 .text virtual addres

Scanning Symbol Table for symbol 'return_five'
[ 0]: 
[ 1]: somefuncs.c
[ 2]: 
[ 3]: return_five
[ 4]: global_int
[ 5]: my_pow
[ 6]: an_array
[ 7]: triple
[ 8]: meaning_of_life

Found 'return_five' in symbol table
- 11 size
- 1 section index
- 18 info
Calculating location of 'return_five' in .text section
- 0x0 preferred address of function (st_value)
- 0x0 preferred address of .text section
- 0 offset in .text of start of function
- 0x600000000040 virtual address of .text section
- 0x600000000040 virtual address of function

MODE: call
func_type: int (*)(void)
running function (no arguments)
returned: 5

# run my_pow: takes 2 integers, returns an integer
>> ./findfunc test-input/somefuncs.o my_pow call 'int (*)(int,int)' 3 5
file_bytes at: 0x600000000000
Section Headers Found:
- 904 bytes from start of file
...
Found 'my_pow' in symbol table
- 53 size
- 1 section index
- 18 info
Calculating location of 'my_pow' in .text section
- 0xb preferred address of function (st_value)
- 0x0 preferred address of .text section
- 11 offset in .text of start of function
- 0x600000000040 virtual address of .text section
- 0x60000000004b virtual address of function

MODE: call
func_type: int (*)(int,int)
running function with arguments (3,5)
returned: 243

# run triple: takes an integer pointer and returns nothing
>> ./findfunc test-input/somefuncs.o triple call 'void (*)(int*)' 6
file_bytes at: 0x600000000000
Section Headers Found:
- 904 bytes from start of file
...
Found 'triple' in symbol table
- 29 size
- 1 section index
- 18 info
Calculating location of 'triple' in .text section
- 0x40 preferred address of function (st_value)
- 0x0 preferred address of .text section
- 64 offset in .text of start of function
- 0x600000000040 virtual address of .text section
- 0x600000000080 virtual address of function

MODE: call
func_type: void (*)(int*)
running function, arg points to 6
arg is now: 18

Below are some notes on how to complete this portion of the project.

1. In a terminal, change to your project code directory and type make zip which will create a zip file of your code. A session should look like this:

      > cd Desktop/2021/p5-code      # location of project code
   
      > ls 
      Makefile    findfunc.c    test-input/
      ...
   
      > make zip                     # create a zip file using Makefile target
      rm -f p5-code.zip
      cd .. && zip "p5-code/p5-code.zip" -r "p5-code"
        adding: p5-code/ (stored 0%)
        adding: p5-code/findfunc.c (deflated 72%)
        adding: p5-code/Makefile (deflated 59%)
        ...
      Zip created in p5-code.zip
   
      > ls p5-code.zip
      p5-code.zip
   

2. Log into Gradescope and locate and click Project 5' which will open up submission
3. Click on the 'Drag and Drop' text which will open a file selection dialog; locate and choose your p5-code.zip file
4. This will show the contents of the Zip file and should include your C source files along with testing files and directories.
5. Click 'Upload' which will show progress uploading files. It may take a few seconds before this dialog closes to indicate that the upload is successful. Note: there is a limit of 256 files per upload; normal submissions are not likely to have problems with this but you may want to make sure that nothing has gone wrong such as infinite loops creating many files or incredibly large files.
6. Once files have successfully uploaded, the Autograder will begin running the command line tests and recording results. These are the same tests that are run via make test.
7. When the tests have completed, results will be displayed summarizing scores along with output for each batch of tests.
8. Refer to the Submission instructions for P1 for details and pictures.

You may wish to review the policy on late project submission which will cost you late tokens to submit late or credit if you run out of tokens. No projects will be accepted more than 48 hours after the deadline.

https://www-users.cs.umn.edu/~kauffman/2021/syllabus.html