Tiny ELF Files: Revisited in 2021 – Blog for guest posting

October 11, 2021

Quick edit: While I work on a proper update, I’ll note here that
several posters on reddit and hackernews have pointed out ways to bring the
total size of the program down to 105 bytes while still printing the full
“Hello, world!” Much credit goes to
Josh Triplett, who produced
the 105-byte version which you can find here.
I fully plan to include this in an updated version of the page!

Here are the tricks I wasn’t aware of when
writing the article:

The Inspiration

Many years ago, I came across
this famous article,
which I largely credit changing the trajectory of my career. At the time, I
was an intern working on a the build system for a fairly large Java code base,
so I was particularly susceptible to an article attempting to do the polar
opposite of “enterprise Java:” strip away all but the most essential
components required to define a valid Linux program. (Before removing even more!)

In short, the article walks through the creation of a 45 byte (!) Linux binary.
While the resulting binary is arguably not an entirely “valid” ELF
file, it was at least one that Linux could run. Or at least at the time.
Perhaps unfortunately, Linux has gotten more strict about ELF loading since
the article’s original publication (I haven’t been able to track down the
original date, but it was already around in the early 2000’s), and the
migration of many systems to 64-bit CPUs has rendered the older 32-bit ELF
binary less relevant.

My Goals

Like the article I take for inspriation, I set out to create the smallest ELF
file that runs on modern Linux (kernel 5.14 at the time of writing). Like the
original article, I will still use the
nasm assembler, since it is easy to install,
I love its syntax, and it remains one of the best x86 assemblers available.

However, I have a few goals that aren’t quite like the original article:

I will target x64_64 (64-bit AMD/Intel) Linux, since it’s a stretch to
claim that 32-bit Intel (used in the original article) is particularly
modern at this point.
As an added challenge, I figured I would try to make a “Hello,
world!” program (that writes “Hello, world!” followed by a
newline to stdout), rather than the original article’s less-exciting
program that exits with a code of 42. As I will discuss later, this ended
up costing very few bytes.
My program must exit successfully, with a code of 0.

Background Information: The ELF64 File Format

ELF files are used everywhere in Linux (and plenty of other operating systems),
and serve as plain executables, static libraries produced by compilers, dynamic
libraries, and more. Executable ELF files, the focus of this article,
typically contain the following components:

The top-level ELF header.
A program header table, which lists chunks of the ELF file
that need to be loaded into memory, and where they need to be loaded. This
is also sometimes called a segment header table.
A section header table, which list sections of the
ELF file. This is not necessary for simply loading an executable
ELF, but section information is essential for other ELF functionality,
such as linking.
Actual executable bytecode and any data it needs.

The ELF format has remarkably few hard requirements on where the various
pieces of metadata appear in the file, apart from the fact that the top-level
ELF header must appear at the beginning. The location of the program header
table and section header table may be anywhere in the file, as the top-level
ELF header will contain their offsets.

If you want more details, the wikipedia article on the ELF format, and especially

this accompanying graphic, offers a sufficient summary that is not worth
repeating here.

Starting Point: A Reasonably Valid, Minimal Hello-world ELF

Even those who haven’t looked into it have likely figured out that typical
gcc-produced executables are full of unecessary stuff for a simple hello-world.
For those who need convincing, the
original article
covers several iterations of a C version, which does not need any updating to
be relevant to modern times.

So, rather than reproduce the entirety of the prior article, I’ll skip straight
to assembly code, and define a valid ELF in its entirety. Here’s what I came up
with:

Click here for a version without comments.

If you need a quick primer on nasm‘s syntax:

Lines starting with ; are comments.
db, dw, dd, and dq
are pseudo-instructions that output initialized bytes, 2-byte
words, 4-byte double words, and 8-byte quad words,
respectively.
Labels appear at the start of a line and end with a :.
nasm allows using labels in simple arithmetic expressions anywhere in place
of numbers.
The equ directive is used to associate a label with an
arbitrary number, rather than a location in the file.
The $ symbol can be used in expressions to represent the
current offset, in bytes, into the generated bytecode. (There are more
nuances to this, but they basically don’t apply when producing a flat
binary.)
All code is written using Intel-format x86 assembly syntax.

This assembly directly defines the necessary metadata for an executable 64-bit
Linux ELF, so you don’t need to use a linker to obtain an executable. Instead,
we’ll just assemble it using nasm‘s ability to output flat binary,
and call chmod to mark it as executable.

Assuming you save it as hello_world.asm, you can compile and run it
using:

nasm -f bin -o hello_world hello_world.asm
chmod +x hello_world
./hello_world

Obviously, you’ll need to be using 64-bit Linux and have nasm
installed and available on your PATH for this to work. nasm is
small and lightweight, and I’d recommend it to anyone interested in writing
a significant amount of x86 assembly.

What is included in this file?

This was basically the most minimal “proper” ELF file I could come up
with. It contains a list of sections, including a .text section
for executable code and a .shstrtab (Section Header
String Table) section, which contains the names of the sections
(including its own). The entire ELF file is 383 bytes when assembled, which
is already decently small, though a far cry from what is possible.

As this initial version was intended to be faithful to the ELF format, viewing
its content using standard linux tools works correctly. As we remove more
content from it, we will gradually lose these abilities. For example,
readelf -SW currently shows that our .text and .shstrtab sections
are correctly defined:

There are 3 section headers, starting at offset 0x78:

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            0000000000000000 000000 000000 00      0   0  0
  [ 1] .text             PROGBITS        0000000000028138 000138 000027 00  AX  0   0 16
  [ 2] .shstrtab         STRTAB          000000000002816e 00016e 000011 00      0   0  1

Similarly, objdump -M intel -d disassembles the code in the
.text section without a problem:

Disassembly of section .text:

0000000000028138 <.text>:
   28138:	b8 01 00 00 00       	mov    eax,0x1
   2813d:	bf 01 00 00 00       	mov    edi,0x1
   28142:	48 be 5f 81 02 00 00 	movabs rsi,0x2815f
   28149:	00 00 00 
   2814c:	ba 0f 00 00 00       	mov    edx,0xf
   28151:	0f 05                	syscall 
   28153:	b8 3c 00 00 00       	mov    eax,0x3c
   28158:	bf 00 00 00 00       	mov    edi,0x0
   2815d:	0f 05

Before moving on, we can look at the actual bytes in the ELF, and annotate
what they’re used for in the file:

Even at a glance, the section-related information seems to be taking too
much space. As mentioned earlier, this should not be needed if we only care
about loading the ELF into memory and running it. But can it be simply taken
out?

Removing Section Information

The answer is yes. We can just delete the section information.

To do so, set the number of section headers to 0 and delete the sections.
Here is the assembly afterwards. It can be assembled and run the same way as
the previous version. I’ve also taken out any comments, apart from those
annotating the changed lines:

Removing the section information brings the file size down to 173 bytes,
saving over 200 bytes from our original attempt (which was already small)!
Obviously, this means that our ELF loses some useful metadata, meaning that
some utilities, like objdump now have trouble finding the code.
But nothing is entirely broken yet. For example, readelf -SW
still works, and correctly points out that the ELF contains no sections.

Once again, we can dump the actual bytes in the ELF to see where the space
is going. There’s nothing too interesting here; it’s like before, but the
section information is gone:

So what’s next? We can’t simply delete any more information: we need the
code, the “Hello, world!” string, the ELF header, and the program
header. However, there’s still one more thing that we can shrink without
breaking anything: the code itself.

Reducing the Code Size

The x86 bytecode is certainly not the largest part of our file, but it still
is not as size-optimized as it could be—accounting for 39 out of the 173
bytes in the ELF. Currently, our program’s entire code is only eight
instructions. Not bad! But we can replace them with shorter instructions.
Since there are only eight to begin with, I’ll just go through them one at a
time:

mov rax, 1: We start by setting the rax
register to hold the syscall number for the write syscall: 1.
(Check here if you
aren’t familiar with the Linux system call numbers. This is how
we request the Linux kernel to do some work on behalf of our program.)
If you looked at the disassembly earlier, you may have noticed that our
assembler automatically converted this to mov eax, 1, since
setting eax (the lower 32 bits of rax), will
automatically clear the upper 32 bits of rax. However,
mov eax, 1 still takes 5 bytes. We can do a little better:
- xor eax, eax: Clear all bits in the eax register to
  zero. This also clears the upper 32 bits of rax, and takes two bytes.
- inc eax: Increment eax by 1. This takes two bytes.
In conjunction, these two instructions take 4 bytes, saving us a single
byte over mov eax, 1.
mov rdi, 1: We next set the first argument to our syscall in
the rax register, as required by the
Linux x86_64 syscall interface. The file descriptor for the stdout
“file” is 1, so we set rdi to 1. Once again, our
assembler automatically replaced this with the equivalent
mov edi, 1, a 5-byte instruction. However, we already have
rax set to 1, so we can instead use mov edi, eax
to copy the contents of eax to edi (and clear
the upper bits of rdi). This new instruction takes two bytes:
a 3-byte reduction.
mov rsi, file_load_va + message: The next argument to the
syscall, the virtual address of the string to print, goes in the
rsi register. We calculate it here based on the file’s
arbitrary virtual address (which we choose ourselves), and the offset of
the string in the file. This instruction ends up taking 10 bytes: two
bytes for the opcode, and a full 8 bytes for the address. We can replace
this with mov esi, file_load_va + message to save 5 bytes:
switching to esi uses one fewer byte for the opcode, and uses
a four byte immediate. (This trick obviously won’t work if
file_load_va won’t fit in 32 bits.)
mov rdx, message_length: The last argument to the syscall
is the length of the string to print. Here again, nasm automatically
replaced this with the equivalent mov edx, message_length.
However, this still requires 5 bytes, and we can do a bit better:
- xor edx, edx: Set edx (and in turn,
  rdx) to 0. This takes two bytes.
- mov dl, message_length: Set the bottom 8 bits of rdx to
  the message length. This takes two bytes, and works as long as the
  length of the string is less than 256.
So, we reduced this code from 5 bytes to 4 bytes.
syscall: This will invoke the write system call
to print our string. This instruction takes two bytes. We can’t do much
better, as far as I know.
mov rax, 60: Now that we’ve invoked the write system call,
we need to invoke the exit system call. Its number is 60. Once
again, this instruction is taking 5 bytes. In this case, we can do much
better if we assumed our write syscall was successful: the
syscall’s return value is written into the rax register, and
it should be 0 on success. Assuming this is true, we won’t need to zero
out the bits of rax, and can simply set its low byte to 60 using the
following instruction: mov al, 60. This only takes two bytes,
saving three more bytes overall.
mov rdi, 0: The only argument to the exit syscall is the
exit code. This should be 0 to indicate a successful exit, so we’ll set
rdi to 0. Once again, nasm will emit a 5-byte instruction
here, which we can replace with xor edi, edi, taking only
two bytes and accomplishing the same thing.
syscall: We now invoke the exit syscall to end the program.
Once again, I don’t know of a shorter replacement.

After making all of these changes, the assembly looks like this:

The code can be assembled and run in the same way as the previous examples, and
shortening the executable bytecode won’t have any impact on the ELF format.
Making these changes reduces the file size to 157 bytes—a reduction by 16
bytes, and still a reasonably valid Linux executable. We went from eight
instructions taking 39 bytes to ten instructions taking 23 bytes. The hex dump
of the bytes hasn’t changed much from before:

The code has noticably shortened, and 157 bytes is a very tiny executable!
Additionally, despite lacking plenty of metadata, there is nothing totally
“broken” about this program—it has a full, correctly-populated
ELF and program header, and small chunk of code to run. In other words,
there’s no good reason for Linux to refuse to run this. That’s about to
change.

Moving the Code

It turns out that shortening the code has another benefit: it uses shorter
instructions, which we can break into fine-grained short chunks, and join
them together with jmp instructions. But why is this useful?

If you’ve followed my previous suggestions and read
this article’s inspriation,
you likely know where I’m going: several fields in the ELF and program header
aren’t validated by Linux’s ELF loader, and we can overwrite these with our
code. This allows us to completely remove the bytes taken by code in our
program by dual-purposing existing header bytes.

But what header bytes can be clobbered and replaced? We can easily test
this: replace them with random junk in the assembly, and see if the program
still runs. I actually did so, and recorded the results in a spreadsheet:

In this spreadsheet, each byte in the ELF and program header are shown on
separate lines. Fields that can be overwritten with junk are highlighted in
green, and fields that are checked or required are highlighted in red. We’ll
take advantage of this to pack our code (and even the “Hello,
world!n” string) into unused bytes (well, technically, unvalidated
bytes). The new assembly looks like this:

As before, this can be assembled and run the same way as all of the examples so
far. It now only takes 126 bytes: a reduction by a full 31 bytes due to
removing all code bytes and 8 bytes from the “Hello,
world” string. Unfortunately, we can’t pack the full string into any
available gaps, since it requires 14 bytes, and no sequence of 14 clobber-able
bytes exists in the headers. As it stands, the ELF and program header require
120 bytes, and the string “sticks out” past the end of the program
header by an additional 6 bytes.

At this point, several of the common tools we discussed earlier do not
like the fact that we clobbered so many fields in the headers. For example,
readelf -WlS now complains that the section header offset
is nonzero. The objdump utility simply gives a
File truncated error when we try to use it on the file. While not
very specific, I suspect this error is also due to the section header offset,
since the other fields we clobbered were simply padding, the unused physical
address, and the alignment of segment in memory. While clobbering the
alignment seems like it could be breaking objdump,
I actually verified that it isn’t: setting the segment’s aligment back to 1
(its value prior to clobbering it with the string) did not cause
objdump to start working again.

Finally, the hex dump of this current version has gotten pretty interesting,
and is a good illustration of how we contorted the file:

However, we’re not quite done yet!

The Final Version

There’s still one thing we can do: just like we overlapped the code, we can
also overlap the ELF and program headers themselves.

The end of the ELF header contains the number of program headers, followed by
the size and number of section headers, and ends with the index of the
section containing the section name table. We absolutely must leave the number
of program headers as 1 and the number of section headers as 0, but it turns
out the size of a section header and the index of the section-name table can
be clobbered as long as we aren’t defining any sections. Individually, each of
these fields is only two bytes.

What happens if we start our first program header immediately after the number
of program headers, though? It turns out that this works perfectly: even
though the program header starts with a four-byte type field that
must not be zero, only the bottom byte of the field is set—the rest are zero.
So, if we start our program header six bytes before the end of the ELF
header, the type field overlaps with the clobber-able
section header size; ELF header field, as well as the number of
section headers. However, the bytes overlapping the number of section headers
are zero: just what we need. Afterwards, the program header’s
flags field (which also can’t be zero) overlaps the
section-name-string-table field, which, as mentioned, seems to be unused so
long as we don’t have any sections.

The assembly for this program hasn’t changed very much, but it does happen to
be our final version:

As always, this code can be assembled and run in the same way as the first
example. After the six-byte overlap between headers, it is now down to 120
bytes. Ordinarily, this would be the same size as the sum of the ELF header
and a single program header—the smallest you could expect for an executable
ELF file containing no code at all! For completeness, we can also look at the
final bytecode we produced:

Can we go farther?

120 bytes is quite a feat—it could fit in a single text message. It takes
up less than 1/34th of a single 4kB page; far smaller than we have any reason
to care about. If we compromised our original goal of writing a full
“Hello, world!” program, we could shave off six more bytes, for a
total size of 114 bytes. Feel free to try this yourself, by modifying
the assembly so that the “Hello, world!n” string is exactly 8 bytes.
For example, replacing the relevant line with message: db `Hi!!!!!n`
will produce a working 114-byte executable.

Trying to shorten the string any farther will result in the program header
being too short, producing an exectuable that Linux will refuse to run. This
brings up an interesting point. This means that even if we decide to use the
original article’s “return 42” program rather than our hello-world,
we wouldn’t get below 114 bytes—the limiting factor is entirely our inability
to further overlap the ELF header and single required program header.

But can we really not overlap the headers any more? After all, the
original article managed to shrink their ELF all the way down to 45 bytes.
Sadly, this is simply no longer possible: it requires Linux to automatically
pad the incomplete remainder of the ELF and program header with zeros, which
it no longer does. However, the original 45-byte version starts the program
header immediately after the 0x7f, E, L, F signature at the start
of the file. Is really impossible for us to find a better way to overlap our
ELF header and program header?

Unfortunately, it seems to me like we’re doing the best that is currently
possible. Refer back to the screenshot of the spreadsheet showing which
bytes can be clobbered in the ELF header and program header. The larger sizes
of the 64-bit program header significantly limit any options for overlap, and
after an exhaustive byte-by-byte check, I am confident that we can’t do better,
at least on modern, x86-64 Linux. For completeness’ sake, here are the steps
I took to reach such a conclusion:

The program header offset in the ELF header and the
size in file field in the program header must both fit
within a single byte (as otherwise it would imply a file larger than
255 bytes). They can’t be identical, either, so these two 8-byte fields
can’t overlap at all.
The size of the headers and the fact that the ELF header must start at
the start of the file, combined with the previous point, means that the
size in file field in the program header must come entirely
after the ELF header’s program header offset field.
If we try to address the previous point by placing the size in file field immediately after the program header offset
field, then the program header’s type and flags
fields (which can’t be zero) end up in the program header offset
field instead, which, as mentioned, can’t be clobbered.
If we try to address the previous point by moving the program header’s
flags and type fields immediately after the
program header offset field, then the ELF header size
and program header entry size fields of the ELF header end
up overlapping with the program header’s offset in file field,
which must be at most a single byte, can’t match the ELF header or
program header sizes, and therefore can’t be clobbered. Unfortunately,
these size fields are checked by the Linux kernel (which didn’t seem
to be the case in the older article).
If we move the program header’s flags and type
fields so that they are immediately after the two aforementioned size
fields, then they overlap the ELF header’s number of program headers
field, which must be 1. Our program header’s type is also 1, so
good news, right? Unfortunately, it won’t work… since this overlap would
cause the flags field to fall on the number of section
headers. The number of section headers must be zero, and flags can’t be
zero because the readable+executable bits must be set.
Finally, if we move the program header’s flags field past
program-header and ELF-header sizes, it will be overlapping the
section header size field in the ELF header. This ends up
working, for the reasons discussed earlier, and is where our final version
stands.

Conclusion

Even though it’s not nearly as impressive as the 45-byte executable possible
years ago, many of the extreme minimization tricks continue to be possible on
modern 64-bit Linux. 120 bytes (or as low as 114 bytes) is an incredibly tiny
program in days when software bloat is too often simply accepted.

Obviously, plenty of what we did went far beyond eliminating “bloat”,
but the message remains valuable: it may be possible to remove more software
bloat than you think! Whether that justifies the effort involved is another
debate.