A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux

(or, "Size Is Everything") She studied it carefully for about 15 minutes. Finally, she spoke. "There's something written on here," she said, frowning, "but it's really teensy." [Dave Barry, "The Columnist's Caper"] If you're a programmer who's become fed up with software bloat, then may you find herein the perfect antidote. This document explores methods for squeezing excess bytes out of simple programs. (Of course, the more practical purpose of this document is to describe a few of the inner workings of the ELF file format and the Linux operating system. But hopefully you can also learn something about how to make really teensy ELF executables in the process.) Please note that the information and examples given here are, for the most part, specific to ELF executables on a Linux platform running under an Intel x86 architecture. I imagine that a good bit of the information is applicable to other ELF-based Unices, but my experiences with such are too limited for me to say with certainty. Please also note that if you aren't a little bit familiar with assembly code, you may find parts of this document sort of hard to follow. (The assembly code that appears in this document is written using Nasm; see http://www.nasm.us/.) In order to start, we need a program. Almost any program will do, but the simpler the program the better, since we're more interested in how small we can make the executable than what the program does. Let's take an incredibly simple program, one that does nothing but return a number back to the operating system. Why not? After all, Unix already comes with no less than two such programs: true and false. Since 0 and 1 are already taken, we'll use the number 42. So, here is our first version: /* tiny.c */ int main(void) { return 42; } which we can compile and test like so: $ gcc -Wall tiny.c $ ./a.out ; echo $? 42 So. How big is it? Well, on my machine, I get: $ wc -c a.out 3998 a.out (Yours will probably differ some.) Admittedly, that's pretty small by today's standards, but it's almost certainly bigger than it needs to be. The obvious first step is to strip the executable: $ gcc -Wall -s tiny.c $ ./a.out ; echo $? 42 $ wc -c a.out 2632 a.out That's certainly an improvement. For the next step, how about optimizing? $ gcc -Wall -s -O3 tiny.c $ wc -c a.out 2616 a.out That also helped, but only just. Which makes sense: there's hardly anything there to optimize. It seems unlikely that there's much else we can do to shrink a one-statement C program. We're going to have to leave C behind, and use assembler instead. Hopefully, this will cut out all the extra overhead that C programs automatically incur. So, on to our second version. All we need to do is return 42 from main(). In assembly language, this means that the function should set the accumulator, eax, to 42, and then return: ; tiny.asm BITS 32 GLOBAL main SECTION .text main: mov eax, 42 ret We can then build and test like so: $ nasm -f elf tiny.asm $ gcc -Wall -s tiny.o $ ./a.out ; echo $? 42 (Hey, who says assembly code is difficult?) And now how big is it? $ wc -c a.out 2604 a.out Looks like we shaved off a measly twelve bytes. So much for all the extra overhead that C automatically incurs, eh? Well, the problem is that we are still incurring a lot of overhead by using the main() interface. The linker is still adding an interface to the OS for us, and it is that interface that actually calls main(). So how do we get around that if we don't need it? The actual entry point that the linker uses by default is the symbol with the name _start. When we link with gcc, it automatically includes a _start routine, one that sets up argc and argv, among other things, and then calls main(). So, let's see if we can bypass this, and define our own _start routine: ; tiny.asm BITS 32 GLOBAL _start SECTION .text _start: mov eax, 42 ret Will gcc do what we want? $ nasm -f elf tiny.asm $ gcc -Wall -s tiny.o tiny.o(.text+0x0): multiple definition of `_start' /usr/lib/crt1.o(.text+0x0): first defined here /usr/lib/crt1.o(.text+0x36): undefined reference to `main' No. Well, actually, yes it will, but first we need to learn how to ask for what we want. It so happens that gcc recognizes an option called -nostartfiles. From the gcc info pages: -nostartfiles Do not use the standard system startup files when linking. The standard libraries are used normally. Aha! Now let's see what we can do: $ nasm -f elf tiny.asm $ gcc -Wall -s -nostartfiles tiny.o $ ./a.out ; echo $? Segmentation fault 139 Well, gcc didn't complain, but the program doesn't work. What went wrong? What went wrong is that we treated _start as if it were a C function, and tried to return from it. In reality, it's not a function at all. It's just a symbol in the object file which the linker uses to locate the program's entry point. When our program is invoked, it's invoked directly. If we were to look, we would see that the value on the top of the stack was the number 1, which is certainly very un-address-like. In fact, what is on the stack is our program's argc value. After this comes the elements of the argv array, including the terminating NULL element, followed by the elements of envp. And that's all. There is no return address on the stack. So, how does _start ever exit? Well, it calls the exit() function! That's what it's there for, after all. Actually, I lied. What it really does is call the _exit() function. (Notice the leading underscore.) exit() is required to finish up some tasks on behalf of the process, but those tasks will never have been started, because we're bypassing the library's startup code. So we need to bypass the library's shutdown code as well, and go directly to the operating system's shutdown processing. So, let's try this again. We're going to call _exit(), which is a function that takes a single integer argument. So all we need to do is push the number onto the stack and call the function. (We also need to declare _exit() as external.) Here's our assembly: ; tiny.asm BITS 32 EXTERN _exit GLOBAL _start SECTION .text _start: push dword 42 call _exit And we build and test as before: $ nasm -f elf tiny.asm $ gcc -Wall -s -nostartfiles tiny.o $ ./a.out ; echo $? 42 Success at last! And now how big is it? $ wc -c a.out 1340 a.out Almost half the size! Not bad. Not bad at all. Hmmm ... so what other interesting obscure options does gcc have? Well, this one, appearing immediately after -nostartfiles in the documentation, is certainly eye-catching: -nostdlib Don't use the standard system libraries and startup files when linking. Only the files you specify will be passed to the linker. That's gotta be worth investigating: $ gcc -Wall -s -nostdlib tiny.o tiny.o(.text+0x6): undefined reference to `_exit' Oops. That's right ... _exit() is, after all, a library function. It has to be filled in from somewhere. Okay. But surely, we don't need libc's help just to end a program, do we? No, we don't. If we're willing to leave behind all pretenses of portability, we can make our program exit without having to link with anything else. First, though, we need to know how to make a system call under Linux. Linux, like most operating systems, provides basic necessities to the programs it hosts via system calls. This includes things like opening a file, reading and writing to file handles — and, of course, shutting down a process. The Linux system call interface is a single instruction: int 0x80. All system calls are done via this interrupt. To make a system call, eax should contain a number that indicates which system call is being invoked, and other registers are used to hold the arguments, if any. If the system call takes one argument, it will be in ebx; a system call with two arguments will use ebx and ecx. Likewise, edx, esi, and edi are used if a third, fourth, or fifth argument is required, respectively. Upon return from a system call, eax will contain the return value. If an error occurs, eax will contain a negative value, with the absolute value indicating the error. The numbers for the different system calls are listed in /usr/include/asm/unistd.h. A quick peek will tell us that the exit system call is assigned the number 1. Like the C function, it takes one argument, the value to return to the parent process, and so this will go into ebx. We now know all we need to know to create the next version of our program, one that won't need assistance from any external functions to work: ; tiny.asm BITS 32 GLOBAL _start SECTION .text _start: mov eax, 1 mov ebx, 42 int 0x80 Here we go: $ nasm -f elf tiny.asm $ gcc -Wall -s -nostdlib tiny.o $ ./a.out ; echo $? 42 Ta-da! And the size? $ wc -c a.out 372 a.out Now that's tiny! Almost a fourth the size of the previous version! So ... can we do anything else to make it even smaller? How about using shorter instructions? If we generate a list file for the assembly code, we'll find the following: 00000000 B801000000 mov eax, 1 00000005 BB2A000000 mov ebx, 42 0000000A CD80 int 0x80 Well, gee, we don't need to initialize all of ebx, since the operating system is only going to use the lowest byte. Setting bl alone will be sufficient, and will take two bytes instead of five. We can also set eax to one by xor'ing it to zero and then using a one-byte increment instruction; this will save two more bytes. 00000000 31C0 xor eax, eax 00000002 40 inc eax 00000003 B32A mov bl, 42 00000005 CD80 int 0x80 I think it's pretty safe to say that we're not going to make this program any smaller than that. As an aside, we might as well stop using gcc to link our executable, seeing as we're not using any of its added functionality, and just call the linker, ld, ourselves: $ nasm -f elf tiny.asm $ ld -s tiny.o $ ./a.out ; echo $? 42 $ wc -c a.out 368 a.out Four bytes smaller. (Hey! Didn't we shave five bytes off? Well, we did, but alignment considerations within the ELF file caused it to require an extra byte of padding.) So ... have we reached the end? Is this as small as we can go?