This document explores methods for squeezing excess bytes out of simple programs. 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. 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. Familiarity with assembly code is recommended.
We start with a simple C program:
/* tiny.c */
int main(void) { return 42; }
Compiled and tested:
$ gcc -Wall tiny.c
$ ./a.out ; echo $?
42
On my machine, the size is:
$ wc -c a.out
3998 a.out
Stripping the executable improves this:
$ gcc -Wall -s tiny.c
$ wc -c a.out
2632 a.out
Optimizing further:
$ gcc -Wall -s -O3 tiny.c
$ wc -c a.out
2616 a.out
To go smaller, we switch to assembler:
; tiny.asm
BITS 32
GLOBAL main
SECTION .text
main:
mov eax, 42
ret
Building and testing:
$ nasm -f elf tiny.asm
$ gcc -Wall -s tiny.o
$ ./a.out ; echo $?
42
Size:
$ wc -c a.out
2604 a.out
To bypass the C main() interface and the default _start routine provided by gcc, we define our own _start:
; tiny.asm
BITS 32
GLOBAL _start
SECTION .text
_start:
mov eax, 42
ret
Using gcc with -nostartfiles:
$ nasm -f elf tiny.asm
$ gcc -Wall -s -nostartfiles tiny.o
$ ./a.out ; echo $?
Segmentation fault
139
This fails because _start is not a function and has no return address on the stack. We need to use the _exit() function:
; tiny.asm
BITS 32
EXTERN _exit
GLOBAL _start
SECTION .text
_start:
push dword 42
call _exit
Building and testing:
$ nasm -f elf tiny.asm
$ gcc -Wall -s -nostartfiles tiny.o
$ ./a.out ; echo $?
42
Size:
$ wc -c a.out
1340 a.out
Using -nostdlib and making a direct system call to exit (syscall number 1):
; tiny.asm
BITS 32
GLOBAL _start
SECTION .text
_start:
mov eax, 1
mov ebx, 42
int 0x80
Building and testing:
$ nasm -f elf tiny.asm
$ gcc -Wall -s -nostdlib tiny.o
$ ./a.out ; echo $?
42
Size:
$ wc -c a.out
372 a.out
Further optimization by using shorter instructions:
; tiny.asm
BITS 32
GLOBAL _start
SECTION .text
_start:
xor eax, eax
inc eax
mov bl, 42
int 0x80
Using ld directly:
$ nasm -f elf tiny.asm
$ ld -s tiny.o
$ ./a.out ; echo $?
42
Size:
$ wc -c a.out
368 a.out
Examining the ELF file structure reveals a .comment section. Using gas instead of nasm removes this section but adds .data and .bss sections:
; tiny.s
.globl _start
.text
_start:
xorl %eax, %eax
incl %eax
movb $42, %bl
int $0x80
$ gcc -s -nostdlib tiny.s
$ ./a.out ; echo $?
42
$ wc -c a.out
368 a.out
To create an executable from scratch, we use nasm's flat binary output format and manually construct the ELF header and program header table:
BITS 32
org 0x08048000
ehdr:
db 0x7F, "ELF", 1, 1, 1, 0
times 8 db 0
dw 2
dw 3
dd 1
dd _start
dd phdr - $$
dd 0
dd 0
dw ehdrsize
dw phdrsize
dw 1
dw 0
dw 0
dw 0
ehdrsize equ $ - ehdr
phdr:
dd 1
dd 0
dd $$
dd $$
dd filesize
dd filesize
dd 5
dd 0x1000
phdrsize equ $ - phdr
_start:
mov bl, 42
xor eax, eax
inc eax
int 0x80
filesize equ $ - $$
$ nasm -f bin -o a.out tiny.asm
$ chmod +x a.out
$ ./a.out ; echo $?
42
$ wc -c a.out
91 a.out
By overlapping the ELF header and program header table, and placing the code within the ELF header:
BITS 32
org 0x08048000
ehdr:
db 0x7F, "ELF"
db 1, 1, 1, 0, 0
_start: mov bl, 42
xor eax, eax
inc eax
int 0x80
dw 2
dw 3
dd 1
dd _start
dd phdr - $$
dd 0
dd 0
dw ehdrsize
dw phdrsize
dw 1
dw 0
dw 0
dw 0
ehdrsize equ $ - ehdr
phdr:
dd 1
dd 0
dd $$
dd $$
dd filesize
dd filesize
dd 5
dd 0x1000
phdrsize equ $ - phdr
filesize equ $ - $$
$ nasm -f bin -o a.out tiny.asm
$ chmod +x a.out
$ ./a.out ; echo $?
42
$ wc -c a.out
84 a.out
Further overlapping and careful field selection allows for a 64-byte executable:
BITS 32
org 0x00200000
db 0x7F, "ELF"
db 1, 1, 1, 0, 0
_start:
mov bl, 42
xor eax, eax
inc eax
int 0x80
dw 2
dw 3
dd 1
dd _start
dd phdr - $$
phdr:
dd 1
dd 0
dd $$
dw 2
dw 3
dd _start
dd _start
dd 4
_start:
mov bl, 42
xor eax, eax
inc eax
int 0x80
db 0
dw 0x34
dw 0x20
dw 1
dw 0
dw 0
dw 0
filesize equ $ - $$
$ nasm -f bin -o a.out tiny.asm
$ chmod +x a.out
$ ./a.out ; echo $?
42
$ wc -c a.out
64 a.out
Finally, by dropping trailing zeros and carefully arranging fields, a 45-byte executable is achieved:
BITS 32
org 0x00010000
db 0x7F, "ELF"
dd 1
dd 0
dd $$
dw 2
dw 3
dd _start
dd _start
dd 4
_start:
mov bl, 42
xor eax, eax
inc eax
int 0x80
db 0
dw 0x34
dw 0x20
db 1
$ nasm -f bin -o a.out tiny.asm
$ chmod +x a.out
$ ./a.out ; echo $?
42
$ wc -c a.out
45 a.out
This 45-byte file is the smallest possible ELF executable, with every byte accounted for.
