Elf from scratch

This week, I'm learning about ELF, the binary file format for Linux, BSD and others. As we will see, it is full of interesting information and will serve as a good introduction to assembly programming.

Why I am interested in ELF

I am currently looking for a full-time job with a strong focus on cybersecurity. From what I've read on job offers, low level debugging is a very sought after skill. That's what I'm setting out to learn.

One low level primitive we use everyday without realising it is binary file formats. They are invisible to the regular user and yet form the base for every program that runs on our computers.

ELF is the binary file format for Linux, BSD and other operating systems. Studying it will most likely allow me to better understand how programs work and what kind of hacks are possible.

High level overview

To learn more, I open up the man elf in my terminal.

OK, this is starting to clear things up a bit. There are 4 parts in an ELF file:

• and data referenced by said tables.

Method

I'll briefly explain how I plan to learn about ELF.

I tend to understand a technical subject better by programming something related to said subject. So my goal here is to build up a functional program that will read an ELF file bit by bit. As I learn more, I'll add more code to the program so it prints out more information.

Let's get started by examining what can be found in the ELF header:

Lots of stuff! We can see that the ELF header is either an Elf32_Ehdr structure or an Elf64_Ehdr structure, depending on which processor architecture the binary file was built for. My computer has a 64 bits processor, so I'll use Elf64_Ehdr.

The ELF file I will be reading is /bin/ls, that's the file behind the ls command which lists files in a directory.

I start off with the following elf.c file:

#include <string.h>
#include <sys/mman.h>
#include <elf.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>

int main() {
const char *ls = NULL;
int fd = -1;
struct stat stat = {0};

// open the /bin/ls file with read-only permission
fd = open("/bin/ls", O_RDONLY);
if (fd < 0) {
perror("open");
goto cleanup;
}

// find the size of /bin/ls
if (fstat(fd, &stat) != 0) {
perror("stat");
goto cleanup;
}

printf("Everything is OK!\n");

// put the contents of /bin/ls in memory
ls = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
if (ls == MAP_FAILED) {
perror("mmap");
goto cleanup;
}

// close file descriptors and free memory before the program exits
cleanup:
if (fd != -1) {
close(fd);
}
if (ls != MAP_FAILED) {
munmap((void *)ls, stat.st_size);
}

return 0;
}


For reading /bin/ls, I'm using mmap. This allows me to access the contents as if it were a large vector of bytes, instead of using multiples successive calls to read.

Note that in the following tests, I won't be checking "out of bounds" references. So I won't do this:

if (i < file_size) {
do_something(file_contents[i])
}


do_something(file_contents[i]);


This is clearly unsafe in a production context, but for testing, it'll be alright.

I can compile this program with the following command:

gcc -Wall -Wextra -Werror elf.c -o elf && ./elf /bin/ls


For now, all is good. The debug message "Everything is OK!" is output to my terminal.

Little by little, I'll now replace this debug message with code that will read specific parts of /bin/ls based on what the ELF header tells me. This means I'll go over each and every property of the Elf64_Ehdr structure and learn about their meaning.

However, I will not study e_ident[EI_VERSION], e_ident[EI_VERSION], e_machine, e_version and e_flags because the man elf is quite clear about what they do.

e_ident[MAG*]

An ELF files apparently contains a series of bytes that allow to quickly recognize it as an ELF file and not a jpg or an mp4. This does not mean that a file containing these bytes is necessarily a valid ELF file, but at least, we can expect that it probably is.

Let's check if /bin/ls contains those bytes:

if (
(unsigned char)ls[EI_MAG0] == 0x7f &&
(unsigned char)ls[EI_MAG1] != 'E' &&
(unsigned char)ls[EI_MAG2] != 'L' &&
(unsigned char)ls[EI_MAG3] != 'F'
) {
printf("Yes, this is an ELF file!\n");
}


OK ! /bin/ls does start with \0x7fELF.

e_ident[EI_CLASS]

The memory slot EI_CLASS contains either ELFCLASS32 or ELFCLASS64. These values respectively mean that the binary ELF file is meant to work on a 32 bits system or a 64 bits system.

if ((unsigned char)ls[EI_CLASS] == ELFCLASS64) {
printf("Yes, this file is made for 64 bits!\n");
}


On my machine, /bin/ls was compiled for a 64 bits CPU.

Now, I'll test that EI_CLASS actually contains ELFCLASS32 for binaries that have been compiled for 32 bits CPUs. Here's how I can do that:

# install the 32 bits libc
sudo apt install gcc-multilib

# create a test file in C that displays "Hello world!"
echo '#include <stdio.h>' >> elf-32.c
echo 'int main() { printf("Hello world!\n"); return 0; }' >> elf-32.c

# compile the file for 32 bits
gcc -m32 -Wall -Wextra -Werror elf-32.c

readelf -h a.out | grep -e '^\s*Class'


And I get the following output:

  Class:                             ELF32


So for a 32 bits binary, I do get the ELF32, or ELFCLASS32, value in EI_CLASS. Awesome!

Note how there is also an ELFCLASSNONE value possible for EI_CLASS. I'm not sure what this could be used for.

Update 08/2017: After playing a bit more with ELF, I now understand what ELFCLASSNONE exists for: it is used to indicate an invalid EI_CLASS by programs that analyse ELF binary files, for instance readelf.

e_ident[EI_DATA]

Let's take a look at EI_DATA now. This memory slot says whether the ELF file is meant for a little-endian or big-endian computers.

I always thought that this was a choice at the operating system level. Actually, it's a choice at the CPU level. My x86-64 Intel CPU uses little-endian. And it turns out that Linux supports big-endian architectures as well, for instance AVR32.

Anyway, let's see of /bin/ls was indeed compiled for a little-endian CPU:

if ((unsigned char)ls[EI_DATA] == ELFDATA2LSB) {
printf("Yes, compiled for little-endian!\n");
}


And I get the "Yes, compiled for little-endian!" message, so all is good!

e_ident[EI_OSABI]

The ELF header also allows one to know for which operating system and ABI (ie how different bits of already compiled code access each other) the ELF file was created.

I expect /bin/ls to have been compiled for ELFOSABI_LINUX since I'm running the tests on Ubuntu. Let's confirm this:

if ((unsigned char)ls[EI_OSABI] == ELFOSABI_LINUX) {
printf("Yes, this is a Linux binary!\n");
}


Woops, the confirmation message is not displayed. That means that ls[EI_OSABI] is not ELFOSABI_LINUX. Unexpected!

I'll check the docs one more time to see what I've overlooked:

If the ABI of /bin/ls is not Linux, maybe it is ELFOSABI_NONE (or ELFOSABI_SYSV). I don't know what it is, but since it looks like the most generic one, it's worth a try.

Here's the test:

if ((unsigned char)ls[EI_OSABI] == ELFOSABI_SYSV) {
printf("Yes, this is a SYSV binary!\n");
}


And, this time I get the confirmation message. Yes!

I think the ELFOSABI_SYSV is probably the ABI that was used on the System V operating system before Linux chose to use the same. However, I'm not 100% sure of that.

It seems that the memory slot EI_OSABI is the source of great confusion.

On the one hand, some people say that EI_OSABI identifies the kernel:

elf_osabi identifies the kernel, not userland

On the other hand, it seems that most ELF files on Linux use ELFOSABI_SYSV instead of ELFOSABI_LINUX:

All the standard shared libraries on my Linux system (Fedora 9) specify ELFOSABI_NONE (0) as their OSABI.

Possibly the vendor is cross compiling on FreeBSD or using a very recent Fedora system where anything using STT_GNU_IFUNC will be marked as ELFOSABI_LINUX.

And finally, the man elf says the following:

Some fields in other ELF structures have flags and values that have platform-specific meanings; the interpretation of those fields is determined by the value of this byte.

So what I think is important to remember here is that Linux mostly uses the SYSV ABI, but maybe someday the LINUX ABI will contain Linux specific things that the Linux kernel will then be able to interprete in a somewhat different way than it would with the SYSV ABI.

e_type

Let's move on to the next piece of information the ELF header gives us access to: e_type. That's apparently the type of ELF file currently being read. It could be one of:

• ET_REL,
• ET_CORE,
• ET_NONE,
• ET_EXEC, an executable file such as /bin/ls,
• ET_DYN, a shared library.

ET_EXEC and ET_DYN seem quite evident to me. But I had to do some reading to understand what ET_REL, ET_CORE and ET_NONE are.

The ET_REL mistery

What I ended up understanding though, is that ET_REL stand for "relocatable". That means a piece of code that is not in its final place and will be added to other code to form an executable.

That's typically object files or static libraries.

The ET_CORE mystery

Asking DuckDuckGo about "ELF ET_CORE", I am redirected to a description of ET_CORE. This page tells me that ET_CORE files are coredumps.

Coredumps contain a copy of the crashed-process's memory when the crash happens, which can help programmers debug the crash after the fact.

But how can I get access to a coredump if I want to check for the ET_CORE flag inside it?

My first idea is to willingly make a program crash with a segmentation fault because I remember seeing "core dumped" when that happens. Here we go:

echo 'int main() {return (*(int *)0x0);}' > test.c
gcc -Wall -Wextra -Werror test.c
./a.out


I get a segmentation fault as expected. And a coredump.

Segmentation fault (core dumped)


However, I can't find the coredump file anywhere.

While reading up on coredumps on Stackoverflow, I learn about gcore. This tool makes generating a coredump much simpler:

sudo gcore <pid>


Update 08/2017: By default, Ubuntu does not generate coredump files. Instead, Apport sends crash reports to a webservice managed by Canonical to help them fix bugs. That's why I couldn't find the coredump file on my machine. You can see where coredumps go on your Linux system by running cat /proc/sys/kernel/core_pattern as root.

The ET_NONE mystery

Same as ELFCLASSNONE, it seems like ET_NONE is never actually used by anyone. I wonder if maybe this value is meant to be used by ELF file parsers to indicate invalid ELF file contents when needed. For instance, try to execute a file that has an invalid e_type, maybe internally, Linux uses ET_NONE to represent "This file is not valid, don't use it". Or something like that.

Given that I have had the same question with ELFCLASSNONE before, I'll ask on Stackoverflow. Just minutes later, an engineer from Google has an answer:

Anywhere validity of the ELF file is verified. Here is an example from the Linux kernel tools.

Tests

Now, let's run some tests just to make sure that I understand the different values of e_type.

# create a minimal program
echo 'int main() { return 0; }' > test.c
# compile to executable form, should be ET_EXEC
gcc -Wall -Wextra -Werror test.c
readelf -h a.out | grep -e '^\s*Type'

# create a minimal library
echo 'int test() { return 0; }' > test.c

# compile to object form, should be ET_REL
gcc -c -fPIC -Wall -Wextra -Werror test.c
readelf -h test.o | grep -e '^\s*Type'

# compile to a static library, should be ET_REL too
ar -r libtest.a test.o
readelf -h libtest.a | grep -e '^\s*Type'

# compile to a shared library, should be ET_DYN
gcc -shared test.o -o libtest.so
readelf -h libtest.so | grep -e '^\s*Type'

# create a coredump, should be ET_CORE
sudo gcore 1
readelf -h core.1 | grep -e '^\s*Type'


Sure enough, we get the expected output:

  Type:                              EXEC (Executable file)
Type:                              REL (Relocatable file)
Type:                              REL (Relocatable file)
Type:                              DYN (Shared object file)
Type:                              CORE (Core file)


Update 08/2017: I've just run the tests again on Arch Linux and the very first test, the one that shows "EXEC" on Ubuntu, now shows "DYN". I think this may be related to PIE per this StackOverflow thread about "EXEC" being reported as "DYN". Maybe gcc has different default options on Arch Linux than it does on Ubuntu.

e_entry

According to man elf, e_entry points to the first instruction that the CPU will execute when you launch a program. Let's test this with the most basic assembly we can use. We should be able to see our assembly code at the address pointed by e_entry.

void _start() {
// _exit(0)
asm(
"mov $0, %rdi;" "mov$60, %rax;"
"syscall;"
);
}


gcc -c -Wall -Wextra -Werror test.c && ld test.o


I've manually linked with ld because linking with gcc automatically adds the libc (and all its magic) which I don't want for these tests.

And now, in our ELF test script, we'll print e_entry:

printf("Entry: %lu\n", ((Elf64_Ehdr *)ls)->e_entry);


In my case, e_entry has the value of 4194480. So, I expect to find the assembly instructions from above precisely at that address in the a.out binary. Let's see:

objdump -d a.out


This is the output:

a.out:     file format elf64-x86-64

Disassembly of section .text:

00000000004000b0 <_start>:
4000b0:	55                   	push   %rbp
4000b1:	48 89 e5             	mov    %rsp,%rbp
4000b4:	48 c7 c7 00 00 00 00 	mov    $0x0,%rdi 4000bb: 48 c7 c0 3c 00 00 00 mov$0x3c,%rax
4000c2:	0f 05                	syscall
4000c4:	90                   	nop
4000c5:	5d                   	pop    %rbp
4000c6:	c3                   	retq


The assembly instructions are indeed at addresses 0x4000b4, 0x4000bb (0x3c is 60 in base 10) and 0x4000c2. The _start function is located at address 0x4000b0, which is 4194480 in base 10.

As expected! Great!

Usefulness

Further down in the ELF manual, I see information about program headers:

Apparently, these headers describe bits of memory called "segments" which contain instructions that will run at process startup.

This means that shared libraries and object files most likely don't contain program headers, since those types of files are not executable. A quick readelf -l test.o confirms that.

Alright, but now, what precisely is in a "segment"? What's the difference between a "section" and a "segment"? They feel like they are the same.

Before studying "sections", whose understanding will hopefully help me understand "segments", I'd like to run a few tests to see if I can read the contents of a program header.

Tests

The program headers are made accessible via e_phoff, e_phentsize and e_phnum. And each header contains a p_type.

I'd like to see the values of the p_type for each header in /bin/ls:

#define TEST_HEADER_TYPE(type, value, name)\
if ((type) == (value)) {\
printf("%s\n", (name));\
}

Elf64_Ehdr *eh = (Elf64_Ehdr *)ls;
for (int i = 0; i < eh->e_phnum; i++) {
Elf64_Phdr *ph = (Elf64_Phdr *)((char *)ls + (eh->e_phoff + eh->e_phentsize * i));
uint32_t type = ph->p_type;

// all the p_type can be found in /usr/include/elf.h
}


Here's what I get:

PT_PHDR
PT_INTERP
PT_DYNAMIC
PT_NOTE
PT_GNU_EH_FRAME
PT_GNU_STACK
PT_GNU_RELRO


The reassuring thing is that I find the same types of program headers when I run readelf -l /bin/ls, so all is good here!

Usefulness

A file's section header table lets one locate all the file's sections.

As I said before, it seems like sections (pointed by section headers) and segments (pointed by program headers) are closely related.

There are some differences between program and section headers though. Let's find out exactly what they are.

Differences

The section header has something the program header doesn't have: e_shstrndx. It looks like this is the index of the section header for section .shstrtab, which contains the names of all of the sections. Inception!

Anyway, what this tells me is that we can probably get the buffer that contains all section names like this:

Elf64_Ehdr *elf_header = (Elf64_Ehdr *)ls;

Elf64_Shdr *shstrtab_header = (Elf64_Shdr *)((char *)ls + (eh->e_shoff + eh->e_phentsize * eh->e_shstrndx));

# this is a buffer that contains the names of all sections
const char *shstrtab = (const char *)ls + shstrtab_header->sh_offset;


What's the format of the shstrtab buffer though? Searching for "elf format" on DDG leads me to the ELF specification. It clearly defines the format of a "String table".

The important thing to note is that each section has a name. That name is stored in the section string table as a C string at a specified index.

Maybe less important, but very interesting: section names seem very close to the kind of thing you see in assembly language. I have never programmed in assembly before. I've only seen bits of assembly here and there. But maybe knowing ELF will help me learn assembly down the road.

Update 06/2017: I have started [learning x86-64 assembly]({{< relref "post/asm-from-scratch.md" >}}) and knowing about ELF has turned out to be very useful.

Similarities

Sure, there are differences between sections and segments. But some things are the same. For instance, program headers have a type PT_DYNAMIC and section headers have SHT_DYNAMIC. This "Introduction to ELF" by Red Had says they are the same:

SHT DYNAMIC dynamic tags used by rtld, same as PT DYNAMIC

But I have a problem. I can't find anything that explains what "dynamic tags used by rtld" means. Page 42 of the ELF specification shows that segments of type PT_DYNAMIC and sections of type SHT_DYNAMIC contain ElfN_Dyn structs. Back in man elf, we can see that these structs contain a d_tag field. Probably the "dynamic tag" that Red Hat was talking about.

This d_tag is interesting! The manual tells me that it can have the type PT_NEEDED, in which case it contains an index into the string table .strtab, so that we can effectively get the name of a shared library that the ELF file we are reading depends on.

Let's try this out! Here's what I plan to do:

• find the PT_DYNAMIC segment,
• inside the PT_DYNAMIC segment, find the d_tag with type DT_STRTAB so I know where the .strtab is,
• inside the PT_DYNAMIC segment, for each d_tag of type DT_NEEDED, print out the C string that is inside .strtab at index d_un.d_val (that should be the name of a shared library).

Let's go:

Elf64_Ehdr *eh = (Elf64_Ehdr *)ls;
// look for the PT_DYNAMIC segment
for (int i = 0; i < eh->e_phnum; i++) {
Elf64_Phdr *ph = (Elf64_Phdr *)((char *)ls + (eh->e_phoff + eh->e_phentsize * i));
// I've found the PT_DYNAMIC segment
if (ph->p_type == PT_DYNAMIC) {
const Elf64_Dyn *dtag_table = (const Elf64_Dyn *)(ls + ph->p_offset);

// look for the string table that contains the names of the
// shared libraries need by this ELF file
const char *strtab = NULL;
for (int j = 0; 1; j++) {
// the end of table of Elf64_Dyn is marked with DT_NULL
if (dtag_table[j].d_tag == DT_NULL) {
break;
}

if (dtag_table[j].d_tag == DT_STRTAB) {
strtab = (const char *)dtag_table[j].d_un.d_ptr;
}
}

// if there is no string table, we are stuck
if (strtab == NULL) {
break;
}

// now, I'll look for shared library names inside the string table
for (int j = 0; 1; j++) {
// the end of table of Elf64_Dyn is marked with DT_NULL
if (dtag_table[j].d_tag == DT_NULL) {
break;
}

if (dtag_table[j].d_tag == DT_NEEDED) {
printf("shared lib: %s\n", &strtab[dtag_table[j].d_un.d_val]);
}
}

// only look into PT_DYNAMIC
break;
}
}


And I compile again with gcc -g -Wall -Wextra -Werror test.c.

At first sight, everything works as expected. When I run ./a.out on the a.out ELF file instead of /bin/ls, so when I try to find what shared libraries a.out needs, I get:

shared lib: libc.so.6


However, when I try to read shared libraries of system binaries like /bin/ls, I get a segmentation fault. gdb tells me that something is wrong with my printf call. Specifically, gdb tells me that the memory I am trying to access is not available:

strtab = 0x401030 <error: Cannot access memory at address 0x401030>

That's odd, because readelf -a /bin/ls | grep 401030 shows that the .dynstr section is actually at address 0x401030.

I'm a little lost here. Again, I ask call Stackoverflow to the rescue. And the same Google engineer as before answers one more time:

If the binary is not running, you need to relocate this value by $where_mmaped -$load_addr. The $where_mmaped is your ls variable. The $load_addr is the address where the binary was statically linked to load (usually it's the p_vaddr of the first PT_LOAD segment; for x86_64 binary the typical value is 0x400000).

Now that I think about it, I think there was something about that in the manual. But I had overlooked it:

When interpreting these addresses, the actual address should be computed based on the original file value and memory base address.

Thanks to "Employed Russian" over on Stackoverflow and to the manual, I now understand how the memory is laid out. I've made a little image out of it for future reference:

Knowing this, I can fix my test script:

Elf64_Ehdr *eh = (Elf64_Ehdr *)ls;
// look for the PT_LOAD segment
for (int i = 0; i < eh->e_phnum; i++) {
Elf64_Phdr *ph = (Elf64_Phdr *)((char *)ls + (eh->e_phoff + eh->e_phentsize * i));
// I've found the PT_LOAD segment
break;
}
}

// if there is no PT_LOAD segment, we are stuck
goto cleanup;
}

// look for the PT_DYNAMIC segment
for (int i = 0; i < eh->e_phnum; i++) {
Elf64_Phdr *ph = (Elf64_Phdr *)((char *)ls + (eh->e_phoff + eh->e_phentsize * i));
// I've found the PT_DYNAMIC segment
if (ph->p_type == PT_DYNAMIC) {
const Elf64_Dyn *dtag_table = (const Elf64_Dyn *)(ls + ph->p_offset);

// look for the string table that contains the names of the
// shared libraries need by this ELF file
const char *strtab = NULL;
// the end of table of Elf64_Dyn is marked with DT_NULL
if (dtag_table[j].d_tag == DT_NULL) {
break;
}

if (dtag_table[j].d_tag == DT_STRTAB) {
// mark the position of the string table
const char *strtab_addr = (const char *)dtag_table[j].d_un.d_ptr;
strtab = ls + strtab_offset;
}
}

// if there is no string table, we are stuck
if (strtab == NULL) {
break;
}

// now, I'll look for shared library names inside the string table
for (int j = 0; 1; j++) {
// the end of table of Elf64_Dyn is marked with DT_NULL
if (dtag_table[j].d_tag == DT_NULL) {
break;
}

if (dtag_table[j].d_tag == DT_NEEDED) {
printf("shared lib: %s\n", &strtab[dtag_table[j].d_un.d_val]);
}
}

// only look into PT_DYNAMIC
break;
}
}


Now, everything works as expected, with both a.out and /bin/ls.

From all of this, what I can conclude is that program headers are useful to an executable file whereas section headers are useful to shared/object files during the link phase. Both types of headers point to memory addresses that will end up in the executable file in the end, but don't describe the memory contents in the same way or with the same granularity.

GOT and PLT

In the man elf, there are multiple references to "GOT" and "PLT". Given I have no idea what this means, I'll try and see if I can find anything about those abbreviations.

The best explanation I could find is "PLT and GOT, the key to code sharing and dynamic libraries" at TechNovelty.org:

• the GOT stores addresses of variables that are unknown at compile time but known at link time,
• the PLT stores addresses of functions from shared libraries that unknown both at compile time and at link time (if compiled with -fPIC which is often the case), and are to be resolved dynamically at runtime.

After some additional queries about GOT and PLT on DDG, I find an article that shows how to exploit the GOT to execute a shellcode.

During the writing of this article, I've learned about ELF file format and its contents (the ELF header, the program and section headers, etc), the readelf command`, how a shared library gets linked to an executable and the different kinds of ELF files (core, exec, object, shared).