Building the smallest elf program

In this post we will have fun trying to create the smallest possible 64 bits Linux program (ELF binary) that simply outputs “Hello world!” when it is executed.

The idea here is to understand the compilation process, linking, how loader works, how ELF file format is structured, and so on.

State of the art

So let’s simply create a program in C that outputs our string. In this default case we will not optimize anything nor try to reduce our binary size.

#include <stdio.h>

void main(void)
{
	printf("Hello world!");
}

Let’s compile it with GCC and run it:

$ gcc smallest_elf.c -o smallest_elf.bin
$ ./smallest_elf.bin
Hello world!

The default compiled binary is quite big for only 65 bytes of written code. Why is that? Let’s analyse out binary and check what we can remove to reduce its size.

Too many sections

.interp
.note.gnu.propert
.note.gnu.build-i
.note.ABI-tag
.gnu.hash
.dynsym
.dynstr
.gnu.version
.gnu.version_r
.rela.dyn
.rela.plt
.init
.plt
.plt.got
.plt.sec
.text
.fini
.rodata
.eh_frame_hdr
.eh_frame
.init_array
.fini_array
.dynamic
.got
.data
.bss
.comment
.symtab
.strtab
.shstrtab

Well first of all, our binary has 30 sections inside, we don’t need all of them. We do not need relocations, symbols, or even PLT/GOT and a lot of other stuff. The compiler produced the default binary it would produce even for longer code.

Too many symbols

0000000000003dc8 d _DYNAMIC
0000000000003fb8 d _GLOBAL_OFFSET_TABLE_
0000000000002000 R _IO_stdin_used
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
000000000000215c r __FRAME_END__
0000000000002014 r __GNU_EH_FRAME_HDR
0000000000004010 D __TMC_END__
0000000000004010 B __bss_start
                 w __cxa_finalize@@GLIBC_2.2.5
0000000000004000 D __data_start
0000000000001100 t __do_global_dtors_aux
0000000000003dc0 d __do_global_dtors_aux_fini_array_entry
0000000000004008 D __dso_handle
0000000000003db8 d __frame_dummy_init_array_entry
                 w __gmon_start__
0000000000003dc0 d __init_array_end
0000000000003db8 d __init_array_start
00000000000011e0 T __libc_csu_fini
0000000000001170 T __libc_csu_init
                 U __libc_start_main@@GLIBC_2.2.5
0000000000004010 D _edata
0000000000004018 B _end
00000000000011e8 T _fini
0000000000001000 t _init
0000000000001060 T _start
0000000000004010 b completed.8061
0000000000004000 W data_start
0000000000001090 t deregister_tm_clones
0000000000001140 t frame_dummy
0000000000001149 T main
                 U printf@@GLIBC_2.2.5
00000000000010c0 t register_tm_clones

Our program has symbols, that’s additional information we don’t need to display our string.

Too much code

First of all, the only executable section we need is .text, that’s where our main code is. But we notice there are instructions outside this section:

0000000000001000 <.init>:
    1000:	f3 0f 1e fa          	endbr64
    1004:	48 83 ec 08          	sub    rsp,0x8
    1008:	48 8b 05 d9 2f 00 00 	mov    rax,QWORD PTR [rip+0x2fd9]
    100f:	48 85 c0             	test   rax,rax
    1012:	74 02                	je     1016 <__cxa_finalize@plt-0x2a>
    1014:	ff d0                	call   rax
    1016:	48 83 c4 08          	add    rsp,0x8
    101a:	c3                   	ret

Also, there are 388 bytes of instructions in .text section, that’s a lot considering we just want to output "Hello world!".

Too much empty space

We also notice something interesting in our binary, there is a lot of empty space, filled with zeroes.

00000600: 0000 0000 0000 0000 0000 0000 0000 0000  
00000610: 0000 0000 0000 0000 0000 0000 0000 0000  
00000620: 0000 0000 0000 0000 0000 0000 0000 0000  
00000630: 0000 0000 0000 0000 0000 0000 0000 0000  
00000640: 0000 0000 0000 0000 0000 0000 0000 0000  
00000650: 0000 0000 0000 0000 0000 0000 0000 0000  
00000660: 0000 0000 0000 0000 0000 0000 0000 0000  
00000670: 0000 0000 0000 0000 0000 0000 0000 0000  
[...]

For example the space above has 2544 bytes of zeroes in total. There are several empty spaces like this.

Quick optimizations

We will go ahead to try and reduce our executable’s size, we will implement several methods so you can get an idea of what can be done to produce the smallest possible binary by manipulating compiled binary.

Strip symbols

First of all, let’s remove all the symbols and relocation information from the executable.

$ nm smallest_elf.bin
nm: smallest_elf.bin: no symbols

After the operation, the size of the binary goes from to 16704 to 14472.

Remove unnecessary sections

We can also remove some sections that are unnecessary to the main task of our program, for example .data, or .gnu.version.

Indeed, we do not need those sections, for example our string “Hello world!” is already stored in .rodata section :

00002000: 0100 0200 4865 6c6c 6f20 776f 726c 6421  ....Hello world!

Major modifications

We will go ahead to try and reduce our executable’s size even more, we will implement several methods so you can get an idea of what can be done to produce the smallest possible binary while still keeping its initial function : displaying a string.

Get rid of programming language

We all now programming languages are converted to assembly language by the compiler during the compilation process and the code can even be optimized automatically. The output may result in more instructions than needed for our task.

Let’s re-write our code in assembly language!

section .data
	msg:	db "Hello world", 33, 10, 0
	format:	db "%s", 10, 0

section .text
	global main

main:
	extern printf
	push rbp
	mov rbp, rsp
	mov rdi, msg
	call printf
	pop rbp
	ret

We assemble the code with nasm then link the object with gcc then run it.

$ nasm -f elf64 smallest_elf.asm && gcc smallest_elf.o -o smallest_elf.bin -no-pie
$ ./smallest_elf.bin
Hello world!

We only reduced our file size by 104 bytes by completely rewriting it in assembly. Why?

Well by giving the assembled code object to gcc we only told it what the .text content should look like, but all the other sections and additional data are still here. In order to get rid of it, we will have to link our binary ourselves, getting rid of gcc routines.

Getting straight to the point

We have rewritten the whole file in assembly and compiling it with GCC, but we’re kind of stuck here. How do we reduce the size even more? Maybe trying another compiler? Reducing code even more?

Let’s get straight to the point: we need the program to display “Hello world!”, that’s it. We don’t want external dependencies like the printf() function.

Let’s rewrite the whole assembly code and remove all external references and symbols!

Removing external references

We will make the following changes to our assembly code:

• Removing any call to external functions like printf(). Instead, we’ll use direct system calls like write() and exit().
• Removing references to a "main" function, we don’t need that, we don’t need "functions" in our program.
• Removing prologues, epilogues, and stack frames: yes, those useless bytes at the beginning and end of our code, why would we need them here?
• The whole code will be strictly about printing our buffer and exiting the program.

global _start

section .data
        msg:    db "Hello world", 33, 10, 0

section .text

_start:
        mov rdi, 1      ; standard output
        mov rsi, msg    ; buffer to print
        mov rdx, 14     ; size of the buffer

        mov rax, 1      ; set write syscall

        syscall         ; call write

        mov rdi, 0      ; value to return
        mov rax, 0x3C   ; set exit syscall

        syscall         ; call exit

Get rid of compilers

We don’t have any C code anymore, why would we even need a compiler? Let’s get rid of gcc and directly link the code ourselves.

$ nasm -f elf64 smallest_elf.asm
$ ld -m elf_x86_64 smallest_elf.o -o smallest_elf.bin

Let’s run it and check:

$ ./smallest_elf.bin
Hello world!

With the rewritten assembly code and linking without using any compiler, we reduced the size to 8488 bytes.

Get rid of the data section

We initially put our "Hello world!" string in the .data section, but at this point we’re not following any convention and we’ll just remove the .data section to put our string directly inside the .text code section. Yeah it’s a bit weird but don’t worry, it will work.

global _start

section .text

_start:
        mov rdi, 1      ; standard output
        mov rsi, msg    ; buffer to print
        mov rdx, 14     ; size of the buffer

        mov rax, 1      ; set write syscall

        syscall         ; call write

        mov rdi, 0      ; value to return
        mov rax, 0x3C   ; set exit syscall

        syscall         ; call exit
msg:
        db      "Hello world", 33, 10, 0

Doing this small manipulation, we manage to divide by two the last size of the binary!

Analysing the situation

We did pretty much everything we could to reduce the binary size:

• Writing directly assembly code
• No external function, no stack frames, only code section
• No compiler, directly linking
• Stripping the symbols

At this point, there isn’t much more we can do in a conventional way to reduce the binary size. By the way, why is it still that big?

We can notice through readelf command that our binary still has a lot of stuff inside of it. We have the .shstrtab section header, and a huge amount of empty space, because some tables and sections have been encoded as “empty spaces” filled with null bytes in the binary.

Nearly 92% of our binary is filled with useless empty spaces.

Going further

Some step in the linking process will produce this kind of ELF binary filled with a lot of empty space, that will simply increase our binary size.

Now we will have to build our binary ourselves, manually, without relying on the assembler or the linker.

Identifying the needed information

There is a lot of useless information in our binary so let’s start by identification strictly what we need:

• The ELF header, otherwise it would not be considered an an ELF by the system and could not be loaded
• Our actual code

This portion at the beginning is our header:

00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 3e00 0100 0000 0010 4000 0000 0000  ..>.......@.....
00000020: 4000 0000 0000 0000 4810 0000 0000 0000  @.......H.......
00000030: 0000 0000 4000 3800 0200 4000 0300 0200  [email protected]...@.....
00000040: 0100 0000 0400 0000 0000 0000 0000 0000  ................
00000050: 0000 4000 0000 0000 0000 4000 0000 0000  ..@.......@.....
00000060: b000 0000 0000 0000 b000 0000 0000 0000  ................
00000070: 0010 0000 0000 0000                      ........

And this portion is our code:

00001000: bf01 0000 0048 be27 1040 0000 0000 00ba  .....H.'.@......
00001010: 0e00 0000 b801 0000 000f 05bf 0000 0000  ................
00001020: b83c 0000 000f 0548 656c 6c6f 2077 6f72  .<.....Hello wor
00001030: 6c64 210a 00                             ld!..

And that’s it, we don’t really care what all the remaining is.

Let’s manually construct our new binary with only these two blocks of data. Use any method you like to do that, I used simple Linux commands.

$ head -c 120 smallest_elf.bin > new_smallest_elf.bin.header # extract header
$ tail -c 264 smallest_elf.bin > tmp.bin # extract end of file starting from our code
$ head -c 53 tmp.bin > new_smallest_elf.bin.code # extract our code from it
$ cat new_smallest_elf.bin.header new_smallest_elf.bin.code > new_smallest_elf.bin # assemble both blocks into one final ELF executable

So this is what we get:

00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 3e00 0100 0000 0010 4000 0000 0000  ..>.......@.....
00000020: 4000 0000 0000 0000 4810 0000 0000 0000  @.......H.......
00000030: 0000 0000 4000 3800 0200 4000 0300 0200  [email protected]...@.....
00000040: 0100 0000 0400 0000 0000 0000 0000 0000  ................
00000050: 0000 4000 0000 0000 0000 4000 0000 0000  ..@.......@.....
00000060: b000 0000 0000 0000 b000 0000 0000 0000  ................
00000070: 0010 0000 0000 0000 bf01 0000 0048 be27  .............H.'
00000080: 1040 0000 0000 00ba 0e00 0000 b801 0000  .@..............
00000090: 000f 05bf 0000 0000 b83c 0000 000f 0548  .........<.....H
000000a0: 656c 6c6f 2077 6f72 6c64 210a 00         ello world!..

Obviously, a lot of information from the headers is inaccurate since we modified the whole structure of the file and the program will not execute:

$ ./new_smallest_elf.bin
-bash: ./new_smallest_elf.bin: cannot execute binary file: Exec format error

Let’s check what’s happening with readelf:

$ readelf -a new_smallest_elf.bin
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x401000
  Start of program headers:          64 (bytes into file)
  Start of section headers:          4168 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         2
  Size of section headers:           64 (bytes)
  Number of section headers:         3
  Section header string table index: 2
readelf: Error: Reading 192 bytes extends past end of file for section headers
readelf: Error: Section headers are not available!
readelf: Error: Reading 112 bytes extends past end of file for program headers

There is no dynamic section in this file.
readelf: Error: Reading 112 bytes extends past end of file for program headers

Several issues identified here:

• Entry point address incorrect: our new code starts at offset 0x78, not 0x1000.
• Start of section headers incorrect: we do not have any section header, this should be zero.
• Number of program headers incorrect: we only have 1 program header and not 2.
• Size of section headers incorrect: we do not have any section header, this should be zero.
• Number of section headers incorrect: we do not have any section header, this should be zero.
• Section header string table index: we do not have any section header, this should be zero.

We also need to adjust several stuff in the program header:

• Virtual address of program needs to be changed from 0x400000 to 0x400078 because this is where our program starts. Not aligned? We don’t care.
• Permissions of the segment in the program header is read-only (0x004) and needs to be readable, writable and executable for simplicity (0x007).

We manually apply all those modification directly through a hexadecimal editor and run readelf again:

$ readelf -a new_smallest_elf.bin
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x400078
  Start of program headers:          64 (bytes into file)
  Start of section headers:          0 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         1
  Size of section headers:           0 (bytes)
  Number of section headers:         0
  Section header string table index: 0

There are no sections in this file.

There are no section groups in this file.

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  LOAD           0x0000000000000078 0x0000000000400078 0x0000000000400000
                 0x00000000000000b0 0x00000000000000b0  RWE    0x1000

There is no dynamic section in this file.

There are no relocations in this file.
No processor specific unwind information to decode

Dynamic symbol information is not available for displaying symbols.

No version information found in this file.

This time, no error. But we still need to adjust one small detail inside our actual code. Indeed, we assembled the code before making all those modifications and we are calling the write function: write(1, buffer, 13);

Indeed, the "Hello world!" buffer is no longer located at offset 0x1027, the new offset is 0x9f.

Here is the final modified binary (modified bytes in bold):

00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000 .ELF............
00000010: 0200 3e00 0100 0000 7800 4000 0000 0000 ..>.....x.@.....
00000020: 4000 0000 0000 0000 0000 0000 0000 0000 @...............
00000030: 0000 0000 4000 3800 0100 0000 0000 0000 [email protected].........
00000040: 0100 0000 0700 0000 7800 0000 0000 0000 ........x.......
00000050: 7800 4000 0000 0000 0000 4000 0000 0000 x.@.......@.....
00000060: b000 0000 0000 0000 b000 0000 0000 0000 ................
00000070: 0010 0000 0000 0000 bf01 0000 0048 be9f .............H..
00000080: 0040 0000 0000 00ba 0e00 0000 b801 0000 .@..............
00000090: 000f 05bf 0000 0000 b83c 0000 000f 0548 .........<.....H
000000a0: 656c 6c6f 2077 6f72 6c64 210a ???? ???? ello world!.

Let’s test it now:

./new_smallest_elf.bin
Hello world!

We have hit a new record by reducing our initial program size from 16704 to only 172 bytes.

We could call it a day, but hey, can we actually do better?

Going even further

Let’s try to shrink even more our executable. But in order to do that, let’s modify a little bit the initial exercise. We no longer need to display “Hello world!” string, but just compile any ELF executable, smallest as possible.

In order to be considered a valid executable:

• It must execute at least one assembly instruction
• It must not crash

Let’s take our functional header and remove all the custom code at offset 0x78. We will append new code there.

00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 3e00 0100 0000 7800 4000 0000 0000  ..>.....x.@.....
00000020: 4000 0000 0000 0000 0000 0000 0000 0000  @...............
00000030: 0000 0000 4000 3800 0100 0000 0000 0000  [email protected].........
00000040: 0100 0000 0700 0000 7800 0000 0000 0000  ........x.......
00000050: 7800 4000 0000 0000 0000 4000 0000 0000  x.@.......@.....
00000060: b000 0000 0000 0000 b000 0000 0000 0000  ................
00000070: 0010 0000 0000 0000                      ........

Smallest possible code

Considering the previous conditions, our new code must include a routine to properly exit the program. We could try something like this:

mov rax, 0x3C   ; set exit syscall
syscall         ; call exit

Yes, we did omit the rdi register containing the value to be returned by the program. We don’t really care, the return value is not a condition. We’ll let the program return whatever will be in the register.

Once converted to opcodes we get b8 3c 00 00 00 0f 05, so 7 bytes. Instead of using a mov instruction, let’s use push and pop for the same result.

push 0x3C       ; set exit syscall
pop rax
syscall         ; call exit

This gets us the opcodes 6a 3c 58 0f 05 (5 bytes) which is slightly better, we’ll stick with that one. Let’s append it to our header and run it!

00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 3e00 0100 0000 7800 4000 0000 0000  ..>.....x.@.....
00000020: 4000 0000 0000 0000 0000 0000 0000 0000  @...............
00000030: 0000 0000 4000 3800 0100 0000 0000 0000  [email protected].........
00000040: 0100 0000 0700 0000 7800 0000 0000 0000  ........x.......
00000050: 7800 4000 0000 0000 0000 4000 0000 0000  x.@.......@.....
00000060: b000 0000 0000 0000 b000 0000 0000 0000  ................
00000070: 0010 0000 0000 0000 6a3c 580f 05         ........j<X..

We notice that the program runs fine and even returns the default zero value.

$ ./smallest_elf_v2.bin
$ echo $?
0

Going beyond the documentation

Actually we can still save a few bytes by taking advantage of the fact that some portions of the header will not be verified upon execution. For example the 7-bytes "padding" after the magic byte or the last elements of the ELF header.

First, let’s move our actual code, from the end of the program, directly inside the padding of the ELF header, and update the offsets accordingly. It will no longer be located at 0x78, but 0x08.

Then, let’s overlap the ELF header and the program header at the very end of the ELF header, by starting the program header at offset 0x38 instead of 0x40. This works because the original overwritten data is 0100 0000, and our program header starts with 0100 0000 as well.

Which gives us the following binary:

00000000: 7f45 4c46 0201 0100 6a3c 580f 0500 0000  .ELF....j<X.....
00000010: 0200 3e00 0100 0000 0800 4000 0000 0000  ..>.......@.....
00000020: 3800 0000 0000 0000 0000 0000 0000 0000  8...............
00000030: 0000 0000 4000 3800 0100 0000 0700 0000  [email protected].........
00000040: 0800 0000 0000 0000 0800 4000 0000 0000  ..........@.....
00000050: 0000 4000 0000 0000 b000 0000 0000 0000  ..@.............
00000060: b000 0000 0000 0000 0010 0000 0000 0000  ................

Tricks and more tricks

The previous idea of overlapping the two headers can actually be applied to a larger scale.

The range from 0x18 to 0x40 can actually contain both ELF header and program header overlapped. The values that can be modified without impacting the program’s functionality are in bold.

By modifying the image address of our program and relocating our code right after the magic number, we get this executable of 80 bytes:

00000000: 7f45 4c46 6a3c 580f 0500 0000 0000 0000  .ELFj<X.........
00000010: 0200 3e00 0100 0000 0100 0000 0100 0000  ..>.............
00000020: 1800 0000 0000 0000 1800 0000 0100 0000  ................
00000030: 0000 0100 0000 3800 0100 0000 0000 0000  ......8.........
00000040: 0100 0000 0000 0000 0000 0000 0000 0000  ................

What we notice first is that most tools are lost with this binary. The Linux file command can only tell that this is an ELF, and readelf doesn’t like it either.

$ file smallest_elf.bin
smallest_elf.bin: ELF (AROS Research Operating System), unknown class 106

$ readelf -a smallest_elf.bin
ELF Header:
  Magic:   7f 45 4c 46 6a 3c 58 0f 05 00 00 00 00 00 00 00
  Class:                             <unknown: 6a>
  Data:                              <unknown: 3c>
  Version:                           88 <unknown>
  OS/ABI:                            AROS
  ABI Version:                       5
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x1
  Start of program headers:          1 (bytes into file)
  Start of section headers:          24 (bytes into file)
  Flags:                             0x0
  Size of this header:               24 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         1
  Size of section headers:           0 (bytes)
  Number of section headers:         0
  Section header string table index: 1 <corrupt: out of range>
readelf: Warning: possibly corrupt ELF file header - it has a non-zero section header offset, but no section headers

There are no sections to group in this file.

There is no dynamic section in this file.

Same thing for GDB debugger, it doesn’t recognize this file and refuses to debug it: not in executable format: file format not recognized.

But all things considered, this program actually runs fine and respects all our conditions:

# Normal run
$ ./smallest_elf.bin
$ echo $?
0

# Checking with strace
$ strace ./smallest_elf.bin
execve("./smallest_elf.bin", ["./smallest_elf.bin"], 0x7fffd6fb2730 /* 25 vars */) = 0
exit(0)                                 = ?
+++ exited with 0 +++

Just for the art, let’s clean up the executable by setting to zero all bytes that are not needed.

00000000: 7f45 4c46 6a3c 580f 0500 0000 0000 0000 .ELFj<X.........
00000010: 0200 3e00 0000 0000 0100 0000 0100 0000 ..>.............
00000020: 1800 0000 0000 0000 1800 0000 0100 0000 ................
00000030: 0000 0000 0000 3800 0100 0000 0000 0000 ......8.........
00000040: 0100 0000 0000 0000 0000 0000 0000 0000 ................

Is it the end?

We have probably reached the limits of the ELF 64 bits format, we produced the smallest 64 bits ELF possible that does not crash upon execution and correctly exists with a 0 status code.

Final binary:

7f454c466a3c580f050000000000000002003e0000000000010000000100
000018000000000000001800000001000000000000000000380001000000
0000000001000000000000000000000000000000

If you found other ways or better solutions, don’t hesitate to share them with me! Also don’t forget to check my other posts.