Minimalistic program in ELF format

Inspired by the article Hello from the libc-free world , I also decided to do something similar. In order not to do this aimlessly, I decided to set myself the following task. Make a program that prints some simple string, like "ELF, hello!". Understand how it will be represented in the executable file. Well, along the way, try to keep within 100 bytes.

For starters, the standard helloworld in C ++

#include 
using namespace std;
int main()
{
        cout << "ELF, hello!\n";
        return 0;
}

Compile, look at the size:

$ g++ test.cpp -static && ls -s -h a.out
1,3M a.out

How much, how much? 1.3 Mb? To output a single message of 12 bytes? Hmm ... Okay, let's try C.

#include "stdio.h"
int main()
{
        printf("ELF, hello!\n");
        return 0;
}

We compile it as well. When compiling, I specified the -static option - I’m interested in the whole code that will be executed. With dynamic compilation, the sizes are certainly smaller, but still not as much as we would like.

$ gcc test.c -static && ls -s -h a.out
568K a.out

Half a megabyte less. Here it is, pay for the STL. But, still a lot. Apparently, heavy artillery in the form of assembler is indispensable. We write helloworld on asm, and without stdlib. I prefer the AT&T syntax.

.data
str:
        .ascii "ELF, hello!"
        .byte 10
.text
.global _start
_start:
        movl    $4, %eax
        movl    $1, %ebx
        movl    $str, %ecx
        movl    $12, %edx
        int     $0x80
        movl    $1, %eax
        movl    $0, %ebx
        int     $0x80

Two sections, in the data section - our message (and 10 for translating to a new line), in the code section (.text) - twice we call the 80th interrupt (with the necessary parameters in the registers), the first time to display the message, second time for correct completion.

We compile (or rather translate and link) the created program:

$ gcc easy.s -nostdlib && du -sb a.out
752     a.out

752 bytes - this is already much closer to what is required. Remove debugging symbols with strip utility:

$ strip a.out && du -sb a.out
476     a.out

Better, but still not enough. What's in our file for as much as 476 bytes? Disassemble a.out using objdump:

$ objdump -D a.out
a.out:     file format elf32-i386
Disassembly of section .note.gnu.build-id:
08048094 <.note.gnu.build-id>:
 8048094:       04 00                   add    $0x0,%al
 ...
               Какой-то код, который мы не писали
 ...
 80480b6:       b6 08                   mov    $0x8,%dh
Disassembly of section .text:
080480b8 <.text>:
 80480b8:       b8 04 00 00 00          mov    $0x4,%eax
 80480bd:       bb 01 00 00 00          mov    $0x1,%ebx
 80480c2:       b9 dc 90 04 08          mov    $0x80490dc,%ecx
 80480c7:       ba 0c 00 00 00          mov    $0xc,%edx
 80480cc:       cd 80                          int    $0x80
 80480ce:       b8 01 00 00 00          mov    $0x1,%eax
 80480d3:       bb 00 00 00 00          mov    $0x0,%ebx
 80480d8:       cd 80                         int    $0x80
Disassembly of section .data:
080490dc <.data>:
 80490dc:       45                      inc    %ebp
 80490dd:       4c                      dec    %esp
 80490de:       46                      inc    %esi
 80490df:       2c 20                   sub    $0x20,%al
 80490e1:       68 65 6c 6c 6f     push   $0x6f6c6c65
 80490e6:       21 0a                  and    %ecx,(%edx)

And so, we see three sections, although only two were written. In the .text section is our code. In the data section - our elf hello in the form of 12 bytes (objdump also disassembled them). And what else is the .note.gnu.build-id section? We did not order it, so we boldly delete it:

$ strip -R .note.gnu.build-id a.out && du -sb a.out
416     a.out

Another 60 bytes won. Not bad. Let's try to optimize our code a bit. Firstly, a program can, in principle, end with any code, and not necessarily with zero. Secondly, when the program starts, the registers are reset (however, you should not rely on this when creating real programs - check the ABI of the system for which you are writing).
As a result, instead of movl $ 4,% eax, which translates to 5 bytes, we can use movb $ 4,% al, which translate to 2 bytes. Thirdly, we will get rid of the .data section by placing our line in the code after the last interruption (anyway, the program does not execute further):

.text
.global _start
_start:
        movb    $4, %al
        movb    $1, %bl
        movl    $str, %ecx
        movb    $12, %dl
        int     $0x80
        movb    $1, %al
        int     $0x80
str:
        .ascii "ELF, hello!"
        .byte 10

Compile, delete the excess, look at the size:

$ gcc -nostdlib easy.s
$ strip a.out
$ strip -R .note.gnu.build-id a.out
$ du -sb a.out
320     a.out

It seems we have reached the limit. 320 bytes - nothing more. Or not? Where do these 320 bytes come from? Our code is clearly less. However, in addition to the code, our binary also has an ELF header. And if we want to make a truly minimal program, we will have to open the ELF description (for example, here ), and form the header manually.

Manually - this does not mean in a hex editor. It’s just possible to make it clear to the linker that you don’t need to assign anything to our file, and it will output exactly what we write on the output. The truth in this case is the whole responsibility for the file to start to fall on us.
The implementation of the program with a manually compiled header, I got this:

        .set    ofs, 0x10000            /* ofs - тут храним смещение */
/* ELF Заголовок: */
        .byte   0x7F
        .ascii  "ELF"
        .long   0, 0, 0                 /* ident */
        .word   2                       /* type */
        .word   3                       /* machine */
        .long   0                       /* version */
        .long   _start + ofs            /* entry - адрес начала кода (абсолютный) */
        .long   phdr                    /* phoff - адрес программного заголовка
                                                (phdr) (относительный ) */
        .long   0                       /* shoff */
        .long   0                       /* flags */
        .word   0                       /* ehsize - размер elf заголовка */
        .word   phdrsize                /* phentsize - размер прогр. заголовка */
        .word   1                       /* phnum - количество пр. заголовк. */
        .word   0                       /* shentsize */
        .word   0                       /* shnum */
        .word   0                       /* e_shstrndx */
/* Программный заголовок */
phdr:
        .long   1                       /* type */
        .long   0                       /* offset */
        .long   ofs                     /* vaddr - абсолютный адрес начала кода
                                        программы (с учетом смещения) */
        .long   0                       /* paddr */
        .long   filesize                /* filesz - размер программы на носителе */
        .long   filesize                /* memsz - размер программы в памяти */
        .long   5                       /* pflags */
        .long   0                       /* palign */
.set phdrsize, . - phdr
_start:
/* Код программы */
        movb    $4, %al
        movb    $1, %bl
        movl    $(str+ofs), %ecx
        movb    $12, %dl
        int     $0x80
        movb    $1, %al
        int     $0x80
str:
        .ascii  "ELF, hello!"
        .byte   10
.set filesize, .

Now we also have to manually operate with the program offset. Simplified, by offset we can understand the difference in addressing between the code that lies in our program and where it will be located in RAM (in fact, in RAM it will not be at all there, but that's another story). Usually the linker is engaged in determining the necessary offsets, but now we are on our own. I put the offset in the ofs parameter. The offset size took the lowest possible on my car (10,000). By default, it is 8048000, but this is not a prerequisite.

The ELF header itself is actually not one ELF header. There should be at least two of them - an elf header, and a program header. In general, there are still section headers, but we will not use them to save space. Empirically, the header fields that are used have been set. The rest were filled with zeros.

We broadcast the program, this time manually calling as and ld:

$ as w3test.s -o w3test.o
$ ld -Ttext 0 --oformat binary -o w3test w3test.o
$ du -sb w3test
115     w3test

115 bytes! ~ 10,000 times smaller than the original version. Everything would seem. There is only the minimum necessary to run, and nothing more. And the initial task to overcome 100 bytes will fail. However, this is not the limit! There are unused bytes in the header, which means that we can use them for our purposes. Unfortunately, the code itself will not fit into any field, it is too large. But the line will fit.

If you look closely, then immediately after the ELF identifier we have three unused fields of type long (four bytes each). This means that we can put a line there. And besides, not the entire line, but only the last part of it, because we already have the "ELF" in the form of ascii characters.

In addition, we can shorten the code by placing the phd header not after elf, but immediately after the last byte used in ELF. That is, the phd header will be slightly layered on elf, but this will not cause any consequences, since those fields that are layered are not used in elf.
In the same way, we can place our program “layering” it on the phd header (for the same reasons).

The result is the following code:

        .set    ofs, 0x10000            /* ofs - тут храним смещение */
/* ELF Заголовок: 8*/
        .byte   0x7F
str:    .ascii  "ELF"
        .ascii  ", hello!"
        .byte   10, 0, 0, 0
        .word   2                       /* type */
        .word   3                       /* machine */
        .long   0                       /* version */
        .long   _start+ofs              /* entry - адрес начала кода (абсолютный) */
        .long   phdr                    /* phoff - адрес программного заголовка
                                                (phdr) (относительный ) */
        .long   0                       /* shoff */
        .long   0                       /* flags */
        .word   0                       /* ehsize - размер elf заголовка */
        .word   phdrsize                /* phentsize - размер прогр. заголовка */
/* Программный заголовок */
phdr:
        .long   1                       /* type */
        .long   0                       /* offset */
        .long   ofs                     /* vaddr - абсолютный адрес начала кода
                                        программы (с учетом смещения) */
        .long   0                       /* paddr */
        .long   filesize                /* filesz - размер программы на носителе */
        .long   filesize                /* memsz - размер программы в памяти */
        .long   5                       /* pflags */
.set phdrsize, . - phdr + 4
_start:
/* Код программы */
        movb    $4, %al
        movb    $1, %bl
        movl    $(str+ofs), %ecx
        movb    $12, %dl
        int     $0x80
        movb    $1, %al
        int     $0x80
.set filesize, .

After the broadcast, we get a program of 89 bytes in size. You can consider the task completed.

There was also an idea for optimization - to push the phd header inside the elf header. But this idea failed, because the minimum displacement of 10,000 did not allow one to choose such parameters so that the necessary fields of the structures coincided.

PS In the comments, an even more optimized version was proposed, with a size of 61 bytes, in which it was possible to superimpose phd on elf. Compiled using nasm / yasm with the -f bin option.

BITS 32;
ORG 05430000h;
DB 0x7F, "ELF";
DD 01h, 00h, $$;
DW 02h, 03h;
DD @main;
DW @main - $$;
@main:
  INC EBX;
  DB 05h; <-- ADD EAX,
  DD 04h; <-- LONG(04h)
  MOV ECX, @text;
  MOV DL, 12;
  INT 80h;
  AND EAX, 00010020h;
  XCHG EAX, EBX;
  INT 80h;
@text:
  DB "ELF, hello!", 0Ah;

Sources of information

wikibooks.org - Assembler on Linux for programmers C
stackoverflow.com - “Hello World” in less than 20 bytes
muppetlabs.com - Teensy ELF Executables for Linux