Een beknopte handleiding voor het maken van extreem kleine ELF-executables voor Linux
"Er staat iets op," zei ze met een frons, "maar het is echt minuscuul."
— [Dave Barry, "The Columnist's Caper"]
Als je een programmeur bent die klaar is met software bloat, dan is dit het perfecte tegengif.
Dit document onderzoekt methoden om overtollige bytes uit eenvoudige programma's te persen. Het praktische doel is om enkele interne werkingen van het ELF-bestandsformaat en het Linux-besturingssysteem te beschrijven, terwijl je leert hoe je extreem kleine ELF-executables maakt.
Let op:
- De informatie en voorbeelden zijn grotendeels specifiek voor ELF-executables op een Linux-platform met een Intel x86-architectuur. Veel informatie is waarschijnlijk toepasbaar op andere ELF-gebaseerde Unix-systemen, maar dit is niet met zekerheid te zeggen.
- Als je niet bekend bent met assembly-code, kunnen delen van dit document lastig te volgen zijn. De gebruikte assembly-code is geschreven met Nasm (zie http://www.nasm.us/).
De basis: Een simpel C-programma
Om te beginnen hebben we een programma nodig. Hoe eenvoudiger, hoe beter. We maken een programma dat niets anders doet dan een getal teruggeven aan het besturingssysteem. Aangezien 0 en 1 al bezet zijn (door true en false), gebruiken we het getal 42.
Versie 1:
/* tiny.c */
int main(void) { return 42; }We compileren en testen dit als volgt:
$ gcc -Wall tiny.c
$ ./a.out ; echo $?
42Hoe groot is het bestand?
$ wc -c a.out
3998 a.outDit is naar huidige maatstaven klein, maar het kan zeker kleiner.
Strippen en optimaliseren
De eerste stap is het strippen van het executable:
$ gcc -Wall -s tiny.c
$ ./a.out ; echo $?
42
$ wc -c a.out
2632 a.outVervolgens proberen we optimalisatie:
$ gcc -Wall -s -O3 tiny.c
$ wc -c a.out
2616 a.outDit helpt nauwelijks, wat logisch is: er is simpelweg bijna niets om te optimaliseren.
Overstap naar Assembly
Om verder te gaan, moeten we C achter ons laten en assembly gebruiken om de overhead van C-programma's te vermijden. In assembly moet de functie de accumulator (eax) op 42 zetten en vervolgens terugkeren.
Versie 2:
; tiny.asm
BITS 32
GLOBAL main
SECTION .text
main:
mov eax, 42
retBouwen en testen:
$ nasm -f elf tiny.asm
$ gcc -Wall -s tiny.o
$ ./a.out ; echo $?
42
$ wc -c a.out
2604 a.outWe hebben slechts twaalf bytes bespaard. Het probleem is dat we nog steeds de overhead van de main()-interface hebben. De linker voegt een interface naar het OS toe die main() aanroept.
De _start routine omzeilen
Het standaard startpunt dat de linker gebruikt is het symbool start. Wanneer we met gcc linken, wordt automatisch een start-routine opgenomen die onder andere argc en argv instelt en dan main() aanroept. Laten we onze eigen _start definiëren.
Aangepaste assembly:
; tiny.asm
BITS 32
GLOBAL _start
SECTION .text
_start:
mov eax, 42
retAls we dit proberen te compileren met gcc, krijgen we een foutmelding over een dubbele definitie van _start. We moeten gcc vertellen dat hij de standaard startup-bestanden niet moet gebruiken met de optie -nostartfiles.
$ nasm -f elf tiny.asm
$ gcc -Wall -s -nostartfiles tiny.o
$ ./a.out ; echo $?
Segmentation fault
139Het programma crasht. Waarom? Omdat we start behandelden als een C-functie en probeerden eruit terug te keren (ret). start is echter geen functie, maar een symbool voor het startpunt. Er staat geen retouradres op de stack; er staan alleen argc, argv en envp.
Gebruik van _exit
Om correct af te sluiten, moet start de functie exit() aanroepen. We omzeilen de standaard bibliotheek-shutdowncode en gaan direct naar de shutdown-verwerking van het OS.
Versie 3:
; tiny.asm
BITS 32
EXTERN _exit
GLOBAL _start
SECTION .text
_start:
push dword 42
call _exitBouwen en testen:
$ nasm -f elf tiny.asm
$ gcc -Wall -s -nostartfiles tiny.o
$ ./a.out ; echo $?
42
$ wc -c a.out
1340 a.outDe grootte is bijna gehalveerd.
Systeemoproepen (System Calls)
We kunnen nog verder gaan door de standaard bibliotheken volledig te verwijderen met -nostdlib. Echter, _exit() is een bibliotheekfunctie. Om zonder bibliotheken af te sluiten, moeten we een systeemoproep doen.
Onder Linux gebeurt dit via de instructie int 0x80.
eaxbevat het nummer van de systeemoproep.ebxbevat het eerste argument.ecx,edx,esi,edibevatten eventuele volgende argumenten.
In /usr/include/asm/unistd.h zien we dat de exit systeemoproep nummer 1 is.
Versie 4:
; tiny.asm
BITS 32
GLOBAL _start
SECTION .text
_start:
mov eax, 1
mov ebx, 42
int 0x80Bouwen en testen:
$ nasm -f elf tiny.asm
$ gcc -Wall -s -nostdlib tiny.o
$ ./a.out ; echo $?
42
$ wc -c a.out
372 a.outOptimalisatie van instructies en de linker
We kunnen de instructies verder verkorten. In plaats van mov eax, 1 (5 bytes), kunnen we xor eax, eax gevolgd door inc eax gebruiken. In plaats van mov ebx, 42 (5 bytes), kunnen we mov bl, 42 gebruiken (2 bytes), omdat het OS alleen de laagste byte gebruikt.
Daarnaast kunnen we gcc vervangen door de linker ld om extra overhead te vermijden.
Geoptimaliseerde assembly:
; tiny.asm
BITS 32
GLOBAL _start
SECTION .text
_start:
xor eax, eax
inc eax
mov bl, 42
int 0x80Bouwen en testen:
$ nasm -f elf tiny.asm
$ ld -s tiny.o
$ ./a.out ; echo $?
42
$ wc -c a.out
368 a.outAnalyse van het ELF-formaat
Ons programma is nu slechts 7 bytes lang, maar het bestand is 368 bytes. Wat zit er in? Met objdump -x a.out zien we verschillende secties, waaronder een .comment sectie van 28 bytes waarin "The Netwide Assembler 0.398" staat.
Om echt klein te gaan, moeten we het ELF-formaat begrijpen. Een ELF-bestand bestaat uit:
- ELF Header (52 bytes): Bevat de magic-number signature (
7F 45 4C 46), architectuur, startadres, en locaties van de tabellen. - Program Header Table: Beschrijft hoe delen van het bestand in het geheugen geladen moeten worden. Wordt gebruikt door de programmalader.
- Section Header Table: Beschrijft waar delen van het programma in het bestand staan. Wordt gebruikt door de compiler en linker.
Voor een executable is de Section Header Table optioneel, maar standaardtools voegen deze bijna altijd toe. Om deze te verwijderen, moeten we het bestand handmatig construeren.
Handmatige constructie van een ELF-bestand
Met Nasm kunnen we een plat binair bestand (-f bin) maken. We definiëren zelf de ELF-header en de Program Header Table.
Handmatige ELF-structuur:
BITS 32
org 0x08048000
ehdr: ; Elf32_Ehdr
db 0x7F, "ELF", 1, 1, 1, 0 ; e_ident
times 8 db 0
dw 2 ; e_type
dw 3 ; e_machine
dd 1 ; e_version
dd _start ; e_entry
dd phdr - $$ ; e_phoff
dd 0 ; e_shoff
dd 0 ; e_flags
dw ehdrsize ; e_ehsize
dw phdrsize ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx
ehdrsize equ $ - ehdr
phdr: ; Elf32_Phdr
dd 1 ; p_type
dd 0 ; p_offset
dd $$ ; p_vaddr
dd $$ ; p_paddr
dd filesize ; p_filesz
dd filesize ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsize equ $ - phdr
_start:
mov bl, 42
xor eax, eax
inc eax
int 0x80
filesize equ $ - $$Bouwen en testen:
$ nasm -f bin -o a.out tiny.asm
$ chmod +x a.out
$ ./a.out ; echo $?
42
$ wc -c a.out
91 a.outExtreme overlap-technieken
We kunnen de grootte verder reduceren door delen van het bestand te laten overlappen.
Code in de ELF-header
De identificatievelden in de ELF-header bevatten padding die door het OS wordt genegeerd. We kunnen onze code hierin plaatsen. Resultaat: 84 bytes.
Overlap van de Program Header Table
De laatste bytes van de ELF-header lijken op de eerste bytes van de Program Header Table. Door deze te laten overlappen, besparen we meer ruimte. Resultaat: 76 bytes.
Maximale manipulatie van velden
Door te onderzoeken welke velden Linux echt controleert, kunnen we nog meer overlap creëren. Veldjes zoals eversion, eflags en p_paddr worden grotendeels genegeerd. Door een niet-standaard laadadres te kiezen (bijv. 0x00200000), kunnen we de headers nog sterker laten samenvallen. Resultaat: 64 bytes.
De absolute limiet: Volledige embedding
Het is mogelijk om zowel de Program Header Table als het programma zelf volledig in de ELF-header te embedden. We passen pflags aan naar 4 (alleen leesbaar) en verhogen pfilesz zodat de lader niet hoeft te schrijven naar read-only geheugen.
Versie: Volledig embedded
BITS 32
org 0x00010000
db 0x7F, "ELF" ; e_ident
dd 1 ; p_type
dd 0 ; p_offset
dd $$ ; p_vaddr
dw 2 ; e_type ; p_paddr
dw 3 ; e_machine
dd _start ; e_version ; p_filesz
dd _start ; e_entry ; p_memsz
dd 4 ; e_phoff ; p_flags
_start:
mov bl, 42 ; e_shoff ; p_align
xor eax, eax
inc eax ; e_flags
int 0x80
db 0
dw 0x34 ; e_ehsize
dw 0x20 ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx
filesize equ $ - $$Resultaat: 52 bytes.
De laatste truc
Als een bestand niet precies de grootte van een volledige ELF-header heeft, vult Linux de ontbrekende bytes aan met nullen. We kunnen dus de laatste zeven nullen weglaten.
De finale versie:
BITS 32
org 0x00010000
db 0x7F, "ELF" ; e_ident
dd 1 ; p_type
dd 0 ; p_offset
dd $$ ; p_vaddr
dw 2 ; e_type ; p_paddr
dw 3 ; e_machine
dd _start ; e_version ; p_filesz
dd _start ; e_entry ; p_memsz
dd 4 ; e_phoff ; p_flags
_start:
mov bl, 42 ; e_shoff ; p_align
xor eax, eax
inc eax ; e_flags
int 0x80
db 0
dw 0x34 ; e_ehsize
dw 0x20 ; e_phentsize
db 1 ; e_phnum
filesize equ $ - $$Eindresultaat:
$ nasm -f bin -o a.out tiny.asm
$ chmod +x a.out
$ ./a.out ; echo $?
42
$ wc -c a.out
45 a.outDit bestand van 45 bytes is minder dan een achtste van de kleinste ELF-executable die met standaardtools gemaakt kan worden, en minder dan een vijftigste van een programma geschreven in pure C. Elke byte is nu verantwoord en gerechtvaardigd.
Groetjes,