ELF program velicine 76 bajtova ili Da, velicina JE vazna! (C) Igor Pozgaj, 2004. (nadopunjeno 2005) ------------------------------------------------------------------------------- Sadrzaj: 1. Uvod 2. And the K&R created C... 3. Asembler 4. Earth to Linux kernel 5. ELF header 6. Where no one has gone before 7. The saga continues 8. Secer na kraju 1) Uvod -------- Ovo je djelomicno moje autorsko djelo a djelomicno prijevod dokumenta koji se u izvornom obliku nalazi (to jest tamo se nalazio u trenutku kada je ovo pisano) na adresi http://www.muppetlabs.com Cilj koji cemo si zadati na pocetku glasi: "Napisati sto kraci program". Program ce se izvrsavati na platformama koje mogu izvrsavati ELF format izvrsnih datoteka. Posto tezimo sto vecem minimalizmu, program nece raditi nista korisno, vec ce jednostavno vracati ljusci broj 13 (nema simbolike, broj je izabran "slucajno" :) Tekst je prvenstveno namjenjen dobrim poznavateljima x86 arhitekture i asemblera, poznavateljima ELF formata izvrsnih datoteka, svima koji uzivaju u pisanju krajnje optimiziranog koda, te svim istinskim hackerima i onima koji se tako osjecaju :) Alati koje cete trebati: gcc, nasm (gas), ld, objdump, hexedit 2) And the K&R created C... ----------------------------- "Talk is cheap, show me the code" -- Linus Torvalds Pogledajmo sljedeci kod u C-u: % cat program.c int main () { return 13; } To je taj spektakularni kod koji cemo promatrati. % gcc program.c % ./a.out ; echo $? 13 Program radi kako smo i ocekivali, a ima samo jedan nedostatak: PREVELIK JE! % wc -c a.out 4701 a.out Vise od 4kb za ovakav program??? Something must have gone wrong! Otkuda toliko "smeca" u konacnom programu? Logican prvi potez je uklanjanje debug simbola iz izvrsne datoteke: % strip a.out % wc -c a.out 2940 a.out 1761 bajt manje... nije lose. (velicine koje cete dobiti nakon kompajliranja naravno ne moraju i vjerojatno nece biti jednake, ali red velicine ce biti isti). Pogledajmo sto optimizirajuci prevodilac moze uciniti za nas (uz proces prevodjenja koda odmah cemo i ukloniti debug simbole iz izvrsne datoteke): % gcc -O2 -s program.c % wc -c a.out 2924 a.out 16 bajtova manje i nije preveliki dobitak kad uzmemo u obzir da program u biti ne radi nista korisno. U C-u gotovo da nista ne mozemo uciniti na daljnjem smanjenju izvrsne datoteke. Ovo je pravo vrijeme da krenemo na nizu razinu. 3) Asembler ------------ Na gcc C prevodiocu funkcija vraca parametre preko registra eax. Tocnije, 32 bitne brojeve vraca preko registra eax, 64 bitne brojeve vraca preko registara eax i edx (eax:edx), a realne brojeve vraca na FPU stog. Znaci, samo moramo staviti broj 13 u registar eax i vratiti se iz funkcije main: ; program.asm GLOBAL main SECTION .text main: mov eax, 13 ret % nasm -f elf program.asm % gcc -s program.o % ./a.out ; echo $? 13 % wc -c a.out 2888 a.out Ponovno "mrsava" usteda od svega nesto vise od 50 bajtova. Problem je u C-ovoj funkciji main(). Stvarna ulazna tocka u program je _start, dok se u funkciji main() nalazi mnogo nama nepotrebnog overheada. Pokusajmo izbjeci koristenje funkcije main() i definirati vlastitu ulaznu tocku u program (_start) ; program.asm GLOBAL _start SECTION .text _start: mov eax, 13 ret % nasm -f elf program.asm % gcc -s program.o program.o: In function `_start': program.o(.text+0x0): multiple definition of `_start' /usr/lib/crt1.o(.text+0x0): first defined here /usr/lib/crt1.o: In function `_start': /usr/lib/crt1.o(.text+0x18): undefined reference to `main' collect2: ld returned 1 exit status Ocito ne radi. U dokumentaciji za gcc stoji da prevodilac ima opciju -nostartfiles. Evo sto kaze man gcc: -nostartfiles Do not use the standard system startup files when linking. To je ocito to sto nam treba. Probajmo sa tom opcijom: % gcc -s -nostartfiles program.o Radi! Pokrenimo program: % ./a.out ; echo $? zsh: segmentation fault ./a.out 139 A mozda i ne radi. U cemu je sad problem? gcc nam nije prijavio nikakvu gresku. Problem je u tome sto smo _start tretirali kao obicnu C funkciju i pokusali se vratiti iz nje. Preciznije _start nije funkcija nego obicni simbol u datoteci sa relokatibilnim kodom koji linker koristi kao ulaznu tocku u program. Do "segmentation faulta" dolazi zbog instrukcije "ret" jer se u tom trenutku na stogu ne nalazi povratna adresa na koju bi ret skocio, vec se na stogu nalaze argc te lista argv terminirana sa NULL karakterom. Povratne adrese NEMA. Kako se onda "izlazi" iz _start? Kratak odgovor: pozivom funkcije exit() ; program.asm GLOBAL _start EXTERN exit SECTION .text _start: push dword 13 call exit % nasm -f elf program.asm % gcc -s -nostartfiles program.o % ./a.out ; echo $? 13 % wc -c a.out 1332 a.out Sa 2888 bajtova stigli smo na 1332. Ovo je vec znacajniji napredak. Promotrimo neke druge obecavajuce gcc-ove opcije... Jedna vrlo brzo navodi na razmisljanje: -nostdlib Don't use the standard system libraries and startup files when linking. Only the files you specify will be passed to the linker. Sto nas kosta da probamo i sa time: % gcc -s -nostdlib program.o program.o: In function `_start': program.o(.text+0x6): undefined reference to `exit' collect2: ld returned 1 exit status Naravno! exit() je dio standardnog C librarya! Dosta ovakvih glupih pokusaja. Sve dok koristimo C library, prisiljeni smo koristiti brdo overheada koji se u njemu nalazi. ZAKLJUCAK: Ne treba nam C library! Ostavimo se na trenutak prenosivosti programa i koristimo direktno linux sistemske pozive! 4) Earth to Linux kernel... ---------------------------- Linux, kao i svaki moderni operativni sustav pruza programima mogucnost obavljanja osnovnih operacija preko sistemskih poziva. Ovo ukljucuje akcije poput stvaranja i brisanja datoteka, te medju ostalim, izlazak iz procesa. Linux sistemski pozivi obavljaju se preko prekida 0x80. Pozivi se medjusobno razlikuju prema vrijednosti koja se nalazi u registru eax. Registri ebx, ecx, edx, esi, edi i ebp koriste se za prijenos parametra ukoliko poziv ima manje od sest parametara. U suprotnom slucaju ebx pokazuje na listu parametara (iako ja ne znam za syscall koji ima vise od sest parametara). Za poziv exit vrijedi sljedece: eax - mora biti 1 (poziv broj 1) ebx - vrijednost koju ce exit vratiti ljusci Vrijednosti za pojedine sistemske pozive mozete pronaci u datoteci: /usr/include/asm/unistd.h Dakle, ostavimo se libc-a i pokusajmo sa sistemskim pozivom exit: ; program.asm GLOBAL _start SECTION .text _start: mov eax, 1 mov ebx, 13 int 0x80 % nasm -f elf program.asm % ld -s program.o % ./a.out ; echo $? 13 Ovdje smo koristili ld jer nam gcc vise ne treba. % wc -c a.out 404 a.out Velicina je sada 404 bajta! (Page not found error :) Podsjecam vas da je pocetni program imao cak 4701 bajtova! Mozemo li jos smanjiti program? Pogledajmo sto kaze disasembler: (probajte sa ndisasm -u a.out ili nekim drugim disasemblerom) [cut] 00000000 B801000000 mov eax, 1 00000005 BB2A000000 mov ebx, 13 0000000A CD80 int 0x80 Problem je u tome sto koristimo dugacke instrukcije (ukupno u ovom slucaju imamo dvanaest bajtova koda). Posto u registre stavljamo male brojeve mozemo koristiti 8 bitne dijelove registara (al, ah, itd). Nadalje, umjesto sa "mov" mozemo staviti nulu u registar sa instrukcijom "xor" te ga onda uvecati za 1. 00000000 31C0 xor eax, eax 00000002 40 inc eax 00000003 B32A mov bl, 13 00000005 CD80 int 0x80 Umjesto 12, sada koristimo 7 bajtova. Usteda: 5 bajtova. % nasm -f elf program.asm % ld -s program.o % wc -c a.out 400 a.out Ali otkuda sad ovo?!? Nismo li ustedili 5 bajtova? Otkuda samo 4 bajta manje? Stvar je u tome da se ELF datoteke poravnavaju na 4 bajta, tako da je jedan bajt morao biti dodan zbog poravnanja (eng. padding). Ovo je kraj sto se tice optimizacije samog koda. Prije nego sto pocnemo likovati nad ovim drasticno smanjenim programom, pogledajmo sto kaze objdump: % objdump -x a.out [cut] Sections: Idx Name Size VMA LMA File off Algn 0 .text 00000007 08048080 08048080 00000080 2**4 CONTENTS, ALLOC, LOAD, READONLY, CODE 1 .bss 00000000 08049088 08049088 00000087 2**0 CONTENTS 2 .comment 0000001f 00000000 00000000 00000087 2**0 CONTENTS, READONLY .text i .bss smo mogli ocekivati... ali sto je .comment sekcija? objdump tvrdi da se nalazi na lokaciji 00000087 i da je velicine 31 bajt (a 31 bajt je gotovo 9% od ukupne velicine naseg programa). Pogledajmo sto se nalazi u tih 31 bajtova: % hexdump -C a.out [cut] 00000080 89 c0 40 b3 0d cd 80 00 54 68 65 20 4e 65 74 77 |.À@³.Í..The Netw| 00000090 69 64 65 20 41 73 73 65 6d 62 6c 65 72 20 30 2e |ide Assembler 0.| Da... NASM je morao negdje promoliti svoju ruznu glavu i dati svima na znanje da koristimo bas njega. Mozete probati prebaciti program na AT&T sintaksu i asemblerirati ga sa GNU asemblerom (gas). Rezultat ce biti isti (samo sto nece pisati The Netwide, nego GNU assembler :) Je li nam ovo smece doista potrebno i kako ga se rjesiti? Da bi odgovorili na ovo pitanje moramo prouciti ELF zaglavlje. Sada tek dolazimo do prave optimizacije! Stvari koje nadalje opisujemo nisu za ljude sa slabim srcem i/ili zelucem :). 5) ELF header -------------- Dokument koji opisuje strukture ELF zaglavlja za i386 arhitekturu mozete naci na: http://tsx.mit.edu/pub/linux/packages/GCC/ELF.doc.tar.gz Uglavnom, da skratimo sate citanja i proucavanja: Svaka ELF datoteka pocinje sa 52 bajta dugackim zaglavljem. Zaglavlje sadrzi nekoliko informacija koje opisuju sadrzaj izvrsne datoteke. Na primjer, prvih 16 bajtova sadrzi "identifier" koji ukljucuje potpis ili magicne brojeve: 7F 45 4C 46 (zadnja tri broja su ASCII znakovi E, L, F) i nekoliko jedan bajt dugackih zastavica koje odredjuju da li koristimo 32 ili 64 bitni kod, da li koristimo little ili big endian zapis i slicno. Ostali podaci koje sadrzi ELF zaglavlje su: podaci o ciljnoj arhitekturi, zatim da li je datoteka izvrsiva ili da li pak sadrzi relokatibilni kod (.o datoteke) ili da li je library (shared object, tj. .so datoteka). Pojednostavljeno, ELF header se sastoji od dvije tablice: section header (opisuje gdje se sto nalazi u datoteci) i program header (opisuje gdje ce ti djelovi biti locirani u memoriji). Drugim rjecima: section header sluzi kao uputa linkeru, dok program header sluzi kao uputa loaderu (prekrasni hrvastki izraz je - punilac). Datoteke sa relokatibilnim kodom ne moraju imati program header. Isto tako, izvrsne datoteke ne moraju imati section header (iako ga gotovo uvijek sadrze) Nakon ovog uvodnog teoretiziranja o ELF zaglavlju, dolazimo ponovno do pitanja "kako smanjiti program?". Ocito je da nam niti jedan alat nece pomoci da smanjimo ELF header, to cemo morati obaviti rucno - upisivanjem bajta po bajt. Sluzeci se dokumentacijom iz prethodno navedenog izvora, rucno odredjujemo vrijednosti koje idu u header te dolazimo do sljedeceg koda: ; program.asm ; sljedeca linija je nuzna jer cemo asemblerirati sa -f bin a ne -f elf BITS 32 ORG 0x08048000 ehdr: DB 0x7F, "ELF", 1, 1, 1 ; e_ident TIMES 9 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: DD 1 DD 0 DD $$ DD $$ DD filesize DD filesize DD 5 DD 0x1000 phdrsize: EQU $ - phdr _start: xor eax, eax inc eax mov bl, 13 int 0x80 filesize EQU $ - $$ % nasm -f bin program.asm % chmod +x program % ./program ; echo $? 13 Program radi, a njegova velicina je: % wc -c program 91 program 91 bajt! Sa 400 bajtova smo stigli na 91 bajt! Sto je najbolje, za svaki od tih 91 bajtova mozemo tocno reci cemu koji sluzi. Kada ste zadnji put vidjeli takav program? 6) Where no one has gone before... --------------------------------------- Ako ste pazljivo procitali ELF specifikaciju, mogli ste primjetiti par stvari. Dijelovi ELF datoteke mogu se nalaziti bilo gdje (osim headera koji mora biti na pocetku). Da bi stvar bila jos bolja, ti djelovi se mogu medjusobno preklapati (eng. overlapping). Drugo sto ste mogli zakljuciti je da se neki djelovi headera uopce ne koriste. Pogledajmo ponovno prethodni kod, posebno onaj dio gdje smo stavili devet bajtova popunjenih nulama. Taj dio se nalazi iza 16 bitnog identifikacijskog dijela i sluzi za daljnja moguca prosirenja ELF-a. Drukcije receno: taj dio headera je beskoristan. S druge strane, nas kod je dugacak samo 7 bajtova, pa zasto ga ne bi ugurali u tih devet bajtova? Evo verzije prethodnog programa gdje smo kod ugurali unutar samog ELF zaglavlja: ; program.asm BITS 32 ORG 0x08048000 ehdr: DB 0x7F, "ELF" ; e_ident DB 1, 1, 1, 0, 0 _start: xor eax, eax inc eax mov bl, 13 int 0x80 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: DD 1 ; program header table DD 0 DD $$ DD $$ DD filesize DD filesize DD 5 DD 0x1000 phdrsize: EQU $ - phdr filesize EQU $ - $$ % nasm -f bin program.asm % chmod +x program % ./program ; echo $? 13 % wc -c program 84 program Ustedili smo jos 7 bajtova. Program je sada dugacak tocno toliko koliko je dugacak ELF header (52 bajta) i jedan section table (32 bajta), koji su potrebni da bi se program normalno izvrsavao. Dakle, vise nemamo sto ukloniti. ... osim ... 7) The saga continues ----------------------- Pogledajmo malo bolje (te usporedimo) zadnjih osam bajtova u ELF headeru, te osam prvih bajtova u programskoj header tablici. Na prvi pogled nikako nisu povezani, a promotrimo li malo bolje vidjet cemo da su - isti. Stoga mozemo koristiti mogucnost overlappinga: ; program.asm BITS 32 ORG 0x08048000 ehdr: DB 0x7F, "ELF" ; e_ident DB 1, 1, 1, 0, 0 _start: xor eax, eax inc eax mov bl, 13 int 0x80 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 phdr: DW 1 ; ovaj dio DW 0 ; se prekriva ehdrsize EQU $ - ehdr DD $$ DD $$ DD filesize DD filesize DD 5 DD 0x1000 phdrsize: EQU $ - phdr filesize EQU $ - $$ % nasm -f bin program.asm % chmod +x program % program ; echo $? 13 % wc -c program 76 program Sa 84 stigli smo do 76 bajtova. Vise se ne mozemo oslanjati na overlap jer nema dijelova koje bi eventualno mogli spojiti kao identicne. 8) Secer na kraju ------------------ Da li je program moguce daljnje smanjiti? Koliko informacija iz ELF headera Linux zapravo provjerava? Da li zbilja svaki put provjerava da je e_machine jednak 3 (za i386)? U ovom slucaju to polje se provjerava, ali veliki dio ostalih informacija Linux jednostavno ignorira. Evo sto je u ELF headeru nepotrebno: Prvih cetiri bajta sadrze takozvani "magic number". Te brojeve MORAMO ostaviti jer ce Linux inace odbiti izvrsiti program. Sljedeca tri bajta u e_ident polju se ne provjeravaju (znaci da imamo 12 uzastopnih bajtova u koje mozemo smjestiti sto god zelimo). e_type mora biti 2 (oznacava da je rijec o izvrsnoj datoteci), a e_machine mora biti 3 (za i386). e_version se takodjer ignorira. e_entry naravno mora biti postavljen jer pokazuje na pocetak programa. Sljedece sto, ako cemo vjerovati dokumentaciji, mozemo ignorirati je e_flags. Sto je sa program header tablicom? Ponovno, dokumentacija kaze da mozemo ignorirati p_paddr i p_align. (p_align se vecinom koristi za .so datoteke). Koristeci ove modifikacije program je moguce dalje smanjiti. Medjutim, oslanjajuci se na te stvari nitko ne garantira da ce program uskoro funkcionirati. U originalnom dokumentu navedenom na pocetku mozete vidjeti kako je program smanjen na cak 40 bajtova! U ovom trenutku, taj program vise ne radi, te je upravo to razlog sto stajemo ovdje. Pocetni program od 4701 bajtova smanjili smo na 76 bajtova. To je gotovo 61 puta manji kod! (ili ako volite postotke: pocetni program je vise od 6100% veci od konacnog!). Sjetite se ovoga kada cete iduci put instalirati program koji dolazi na minimalno dva CD-a!