Monday Apr 05, 2010

Hello from a libc-free world! (Part 2)

In the previous post we conquered compilation by constructing a small program that can be compiled without using libc. Understanding object code and the details of an ELF executable are the next step in our adventure.

We left off with the following program pieces:

jesstess@kid-charlemagne:~$ cat stubstart.S
.globl _start _start: call main movl $1, %eax xorl %ebx, %ebx int $0x80
jesstess@kid-charlemagne:~$ cat hello.c
int main() { char *str = "Hello World"; return 0; }
jesstess@kid-charlemagne:~/c$ gcc -nostdlib stubstart.S hello.c -o hello
What did all that work get us?
jesstess@kid-charlemagne:~/c$ wc -c hello
1373 hello
jesstess@kid-charlemagne:~$ objdump -D hello | wc -l
We're down to a little over 1300 bytes of executable and what at under 100 lines seems like a very reasonable amount of assembly to dissect. Since no little bit of assembly is going to scare us at this point, let's look at the assembly now, with objdump -D so we see the assembly for all sections (output here). If it looks intimidating at first, just give it a quick once-over and I promise it won't be by the end of this post.

Alright, we have 5 sections: .text, which contains the familiar _start and main symbols, .rodata, .eh_frame_hdr, .eh_frame, and .comment.

Step 1: Back up - what the heck is a "section"?

If we dust off our favorite copy of the Tool Interface Standard ELF Specification and have a look inside, it tells us this:

An ELF executable like the result of our compilation has two views: it has a program header describing the segments, which contain information used at run-time, and a section header describing the sections, which contain information for linking and relocation. We can look at the program header's segment information or the section header's section information with readelf -l or readelf -S, respectively (output here). The output from these commands on our program is summarized in Figure 1. We won't worry about segments again during this post.

ELF segments and sections Figure 1: our ELF segments and sections

Step 2: What goes in our sections?

The specification also tells us what goes where in our executable:

.text: The executable instructions for a program.

.rodata: Constant data. This is the "read-only data" segment.

.eh_frame: Information necessary for frame-unwinding during exception handling.

.eh_frame_hdr: To quote the Linux Standard Base Specification: "This section contains a pointer to the .eh_frame section which is accessible to the runtime support code of a C++ application. This section may also contain a binary search table which may be used by the runtime support code to more efficiently access records in the .eh_frame section."

We don't have to worry about exceptions with this example, so .eh_frame and .eh_frame_hdr aren't doing much that we care about, and on this machine, compiling with -fno-asynchronous-unwind-tables will suppress creation of these two sections.

.comment: Compiler version information.

Speaking of getting rid of sections: for those of us with a minimalist aesthetic, strip(1) is our friend. We can --remove-section on non-essential sections like .comment to get rid of them entirely; file(1) will tell us if an ELF executable has been stripped.

Other common sections we don't see with our example because they'd be empty:

.data: Initialized global variables and initialized static local variables.

.bss: Uninitialized global and local variables; filled with zeroes. A popular section to bring up during CS interviews!

That's the story on sections. Now, we know that symbols, like _start and main, live in these sections, but are there any more symbols in this program?

Step 3: Understand the symbols and why they live where they live.

We can get symbol information for our executable with objdump -t:
jesstess@kid-charlemagne:~/c$ objdump -t hello
hello:     file format elf64-x86-64

00000000004000e8 l    d  .text                   0000000000000000 .text
0000000000400107 l    d  .rodata                 0000000000000000 .rodata
0000000000400114 l    d  .eh_frame_hdr           0000000000000000 .eh_frame_hdr
0000000000400128 l    d  .eh_frame               0000000000000000 .eh_frame
0000000000000000 l    d  .comment                0000000000000000 .comment
0000000000000000 l    df *ABS*                   0000000000000000 hello.c
00000000004000e8 g       .text                   0000000000000000 _start
0000000000600fe8 g       *ABS*                   0000000000000000 __bss_start
00000000004000f4 g     F .text                   0000000000000013 main
0000000000600fe8 g       *ABS*                   0000000000000000 _edata
0000000000600fe8 g       *ABS*                   0000000000000000 _end
The symbol table for our executable has 11 entries. Weirdly, only rare versions of the objdump man page, like this one, will actually explain the symbol table column by column. It breaks the table down as follows:

Column 1: the symbol's value/address.
Column 2: a set of characters and spaces representing the flag bits set for the symbol. There are 7 groupings, three of which are represented in this symbol table. The first can be l, g, <space>, or !, if the symbol is local, global, neither, or both, respectively. The sixth can be d, D, or <space>, for debugging, dynamic, or normal, respectively. The seventh can be F, f, O, or <space>, for function, file, object, or normal symbol, respectively. Descriptions of the 4 remaining grouping can be found in that unusally comprehensive objdump manpage.
Column 3: which section the symbol lives in. *ABS*, or absolute, means the symbol is not associated with a certain section.
Column 4: the symbol's size/alignment.
Column 5: the symbol's name.

Our 5 sections all have associated local (l) debugging (d) symbols. main is indeed a function (F), and hello.c is in fact a file (f), and it isn't associated with any particular section (*ABS*). _start and main are part of the executable instructions for our program and thus live in the .text section as we'd expect. The only oddities here are __bss_start, _edata, and _end, all *ABS*olute, global symbols that we certainly didn't write into our program. Where did they come from?

The culprit this time is the linker script. gcc implicitly called ld to do the linking on this machine as part of the compilation process. ld --verbose will spit out the linker script that was used, and looking at this script (output here) we see that _edata is defined as the end of the .data section, and __bss_start and _end mark the beginning and end of the .bss section. These symbols could be used by memory management schemes (for example if sbrk wants to know where the heap could start) and garbage collectors.

Note that str, our initialized local variable, doesn't show up in the symbol table. Why? Because it gets allocated on the stack (or possibly in a register) at runtime. However, something related to str is in the .rodata section, even though we don't see it in the symbol table...

With char *str = "Hello, World"; we're actually creating two different objects. The first is the string literal "Hello, World", which is just that array of characters, and has some address but no explicit way of naming it. That array is read-only and lives in .rodata. The second is the local variable str, which is of type "pointer to char". That is what lives on the stack. Its initial value is the address of the string literal that was created.

We can prove this, and see some other useful information, by looking at the contents of our sections with the strings decoded:
jesstess@kid-charlemagne:~$ objdump -s hello

hello:     file format elf64-x86-64

Contents of section .text:
 4000e8 e80b0000 00b80100 000031db cd809090  ..........1.....
 4000f8 554889e5 48c745f8 0b014000 b8000000  UH..H.E...@.....
 400108 00c9c3                               ...             
Contents of section .rodata:
 40010b 48656c6c 6f20576f 726c6400           Hello World.    
Contents of section .eh_frame_hdr:
 400118 011b033b 14000000 01000000 e0ffffff  ...;............
 400128 30000000                             0...            
Contents of section .eh_frame:
 400130 14000000 00000000 017a5200 01781001  .........zR..x..
 400140 030c0708 90010000 1c000000 1c000000  ................
 400150 f8004000 13000000 00410e10 8602430d  ..@......A....C.
 400160 06000000 00000000                    ........        
Contents of section .comment:
 0000 00474343 3a202855 62756e74 7520342e  .GCC: (Ubuntu 4.
 0010 332e332d 35756275 6e747534 2920342e  3.3-5ubuntu4) 4.
 0020 332e3300                             3.3. 
Voila! Our "Hello World" string is in .rodata, and our .comment section is now explained: it just holds a string with the gcc version used to compile the program.

Step 4: Trim the fat and put it all together

This executable has 5 sections: .text, .rodata, .eh_frame_hdr, .eh_frame, and .comment. Really, only one of them, .text, has assembly that's germane to what this little program does. This can be confirmed by doing an objdump -d (only disassemble those sections which are expected to contain instructions) instead of the objdump -D (disassemble the contents of all sections, not just those expected to contain instructions) done at the beginning of the post and noting that only the content of .text is displayed.

.rodata really only contains the string "Hello World", and .comment really only contains a gcc version string. The "instructions" for those sections seen in the objdump -D output come from objdump treating the hexadecimal representations of the ASCII characters in those strings as instructions and trying to disassemble them. We can convert the first couple of numbers in the .comment section to ASCII characters to prove this. In Python:
>>> "".join(chr(int(x, 16)) for x in "47 43 43 3a 20 28 55 62 75 6e 74 75".split())
'GCC: (Ubuntu'

In .text, _start calls main, and in main a pointer to the memory location where "Hello World" is stored, 0x40010b (where .rodata starts, as seen in the obdjump -D output), is pushed onto the stack. We then return from main to _start, which takes care of returning from the program, as described in Part I.

And that's everything! All sections and symbols are accounted for. Nothing is magic (and I mean magic in a good I-would-ace-this-test way, not a sorry-Jimmy-Santa-isn't-real way). Whew.

Looking at and really understanding the core parts of an ELF executable means that we can add complexity now without cheating our way around parts we don't understand. To that end, stay tuned for Part 3, where we'll stuff this program with a veritable variable smörgåsbord and see where everything ends up in the program's memory.


Tuesday Mar 16, 2010

Hello from a libc-free world! (Part 1)

As an exercise, I want to write a Hello World program in C simple enough that I can disassemble it and be able to explain all of the assembly to myself.

This should be easy, right?

This adventure assumes compilation and execution on a Linux machine. Some familiarity with reading assembly is helpful.

Here's our basic Hello World program:

jesstess@kid-charlemagne:~/c$ cat hello.c
#include <stdio.h>

int main()
  printf("Hello World\n");
  return 0;

Let's compile it and get a bytecount:

jesstess@kid-charlemagne:~/c$ gcc -o hello hello.c
jesstess@kid-charlemagne:~/c$ wc -c hello
10931 hello

Yikes! Where are 11 Kilobytes worth of executable coming from? objdump -t hello gives us 79 symbol-table entries, most of which we can blame on our using the standard library.

So let's stop using it. We won't use printf so we can get rid of our include file:

jesstess@kid-charlemagne:~/c$ cat hello.c
int main()
  char *str = "Hello World";
  return 0;

Recompiling and checking the bytecount:

jesstess@kid-charlemagne:~/c$ gcc -o hello hello.c
jesstess@kid-charlemagne:~/c$ wc -c hello
10892 hello

What? That barely changed anything!

The problem is that gcc is still using standard library startup files when linking. Want proof? We'll compile with -nostdlib, which according to the gcc man page won't "use the standard system libraries and startup files when linking. Only the files you specify will be passed to the linker".

jesstess@kid-charlemagne:~/c$ gcc -nostdlib -o hello hello.c
/usr/bin/ld: warning: cannot find entry symbol _start; defaulting to 00000000004000e8

Well, it's just a warning; let's check it anyway:

jesstess@kid-charlemagne:~/c$ wc -c hello
1329 hello

That looks pretty good! We got our bytecount down to a much more reasonable size (an order of magnitude smaller!)...

jesstess@kid-charlemagne:~/c$ ./hello
Segmentation fault the expense of segfaulting when it runs. Hrmph.

For fun, let's get our program to be actually runnable before digging into the assembly.

So what is this _start entry symbol that appears to be required for our program to run? Where is it usually defined if you're using libc?

From the perspective of the linker, by default _start is the actual entry point to your program, not main. It is normally defined in the crt1.o ELF relocatable. We can verify this by linking against crt1.o and noting that _start is now found (although we develop other problems by not having defined other necessary libc startup symbols):

# Compile the source files but don't link
jesstess@kid-charlemagne:~/c$ gcc -Os -c hello.c
# Now try to link
jesstess@kid-charlemagne:~/c$ ld /usr/lib/crt1.o -o hello hello.o
/usr/lib/crt1.o: In function `_start':
/build/buildd/glibc-2.9/csu/../sysdeps/x86_64/elf/start.S:106: undefined reference to `__libc_csu_fini'
/build/buildd/glibc-2.9/csu/../sysdeps/x86_64/elf/start.S:107: undefined reference to `__libc_csu_init'
/build/buildd/glibc-2.9/csu/../sysdeps/x86_64/elf/start.S:113: undefined reference to `__libc_start_main'

This check conveniently also tells us where _start lives in the libc source: sysdeps/x86_64/elf/start.S for this particular machine. This delightfully well-commented file exports the _start symbol, sets up the stack and some registers, and calls __libc_start_main. If we look at the very bottom of csu/libc-start.c we see the call to our program's main:

result = main (argc, argv, __environ MAIN_AUXVEC_PARAM);

and down the rabbit hole we go.

So that's what _start is all about. Conveniently, we can summarize what happens between _start and the call to main as "set up a bunch of stuff for libc and then call main'', and since we don't care about libc, let's just export our own _start symbol that just calls main and link against that:

jesstess@kid-charlemagne:~/c$ cat stubstart.S
.globl _start

    call main

Compiling and running with our stub _start assembly file:

jesstess@kid-charlemagne:~/c$ gcc -nostdlib stubstart.S -o hello hello.c
jesstess@kid-charlemagne:~/c$ ./hello
Segmentation fault

Hurrah, our compilation problems go away! However, we still segfault. Why? Let's compile with debugging information and take a look in gdb. We'll set a breakpoint at main and step through until the segfault:

jesstess@kid-charlemagne:~/c$ gcc -g -nostdlib stubstart.S -o hello hello.c
jesstess@kid-charlemagne:~/c$ gdb hello
GNU gdb 6.8-debian
Copyright (C) 2008 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu"...
(gdb) break main
Breakpoint 1 at 0x4000f4: file hello.c, line 3.
(gdb) run
Starting program: /home/jesstess/c/hello

Breakpoint 1, main () at hello.c:5
5      char *str = "Hello World";
(gdb) step
6      return 0;
(gdb) step
7    }
(gdb) step
0x00000000004000ed in _start ()
(gdb) step
Single stepping until exit from function _start,
which has no line number information.
main () at helloint.c:4
4    {
(gdb) step
Breakpoint 1, main () at helloint.c:5
5      char *str = "Hello World";
(gdb) step
6      return 0;
(gdb) step
7    }
(gdb) step
Program received signal SIGSEGV, Segmentation fault.
0x0000000000000001 in ?? ()

Wait, what? Why are we running through main twice? ...It's time to look at the assembly:

jesstess@kid-charlemagne:~/c$ objdump -d hello
hello:     file format elf64-x86-64

Disassembly of section .text:

00000000004000e8 <_start>:
4000e8: e8 03 00 00 00            callq 4000f0
4000ed: 90                        nop
4000ee: 90                        nop
4000ef: 90                        nop
00000000004000f0 :
4000f0: 55                        push %rbp
4000f1: 48 89 e5                  mov %rsp,%rbp
4000f4: 48 c7 45 f8 03 01 40      movq $0x400103,-0x8(%rbp)
4000fb: 00
4000fc: b8 00 00 00 00            mov $0x0,%eax
400101: c9                        leaveq
400102: c3                        retq

D'oh! Let's save a detailed examination of the assembly for later, but in brief: when we return from the callq to main we hit some nops and run right back into main. Since we re-entered main without putting a return instruction pointer on the stack as part of the standard prologue for calling a function, the second call to retq tries to pop a bogus return instruction pointer off the stack and jump to it and we bomb out. We need an exit strategy.

Literally. After the return from callq, push 1, the syscall number for SYS_exit, into %eax, and because we want to say that we're exiting cleanly, put a status of 0, SYS_exit's only argument, into %ebx. Then make the interrupt to drop into the kernel with int $0x80.

jesstess@kid-charlemagne:~/c$ cat stubstart.S
.globl _start

    call main
    movl $1, %eax
    xorl %ebx, %ebx
    int $0x80
jesstess@kid-charlemagne:~/c$ gcc -nostdlib stubstart.S -o hello hello.c
jesstess@kid-charlemagne:~/c$ ./hello

Success! It compiles, it runs, and if we step through this new version under gdb it even exits normally.

Hello from a libc-free world!

Stay tuned for Part 2, where we'll walk through the parts of the executable in earnest and watch what happens to it as we add complexity, in the process understanding more about x86 linking and calling conventions and the structure of an ELF binary.



Tired of rebooting to update systems? So are we -- which is why we invented Ksplice, technology that lets you update the Linux kernel without rebooting. It's currently available as part of Oracle Linux Premier Support, Fedora, and Ubuntu desktop. This blog is our place to ramble about technical topics that we (and hopefully you) think are interesting.


« July 2016