Analýza ELF binárky - jak ji oholit o přebytečné bajty

8.6.2017 23:33 | Přečteno: 1664× | programování |

Na embedded systémech člověk pořád narazí na problém, že se mu jeho binárka nevejde na flash. První, co vás asi napadne, bude něco jako -Os gcc flag a stripnout výslední binárku, ale existují ještě další triky jak donutit linker zahodit přebytečné symboly. Co se hodí v případě, že máte před sebou binárku, která do sebe linkuje miliony řádek kódu, má statisíce symbolů, umí od routingu přes SNMP, integrovaný web server snad i řešení P?=NP problému?

ELF formát má výhodu, že funguje +/- stejně nezávisle od toho, jestli je na x86, MIPS nebo ARM architektuře. Prakticky rozdíly existují a můžou se projevit dost nenápadně, k tomu se ještě dostaneme. Některé nástroje jako nm a readelf fungují nezávisle od architektury, jiné jako objdump je potřeba použít z příslušného toolchainu pro cílový triplet architektury (třeba arm-linux-gnueabi).

Rychlá okomentrická analýza

Statistika velikosti sekcí:

size -A -d binary

section               size       addr
.interp                 20      33076
.hash                 2992      33096
.dynsym               7728      36088
.dynstr               6788      43816
.gnu.version           966      50604
.gnu.version_r          32      51572
.rel.dyn              1328      51604
.rel.plt              2248      52932
.init                   16      55180
.plt                  3392      55196
.text             16186316      58588
.fini                   16   16244904
.rodata            6959461   16244920
.ARM.extab           46264   23204384
.ARM.exidx          285072   23250648
.eh_frame                4   23535720
.tbss                    4   23568492
.init_array              4   23568492
.fini_array              4   23568496
.jcr                     4   23568500
.data.rel.ro          2388   23568504
.dynamic               288   23570892
.got                  1772   23571180
.data              9250956   23572952
.bss               5225372   32823912
.comment                74          0
.ARM.attributes         45          0
Total             37983554

Zde je vidět, že největší sekce jsou .data (read-write data), .rodata (read-only data), a .text (kód programu). Sekce .bss je sice celkem veliká, ale ta se na disk neukládá - je inicializována po spuštění v RAM na samé nuly.

Seřazení symbolů podle velikosti:

nm --print-size --size-sort --radix=d binary

27403032 00290304 D soc_mem_list
39231600 00295008 B dsv6DbCfgData
36415100 00296808 b mgmdv3Msg.26775
38049132 00498024 B lb2_work
36877696 00514332 B ssi
37477704 00528768 B lb_work
28134264 01720384 D soc_reg_list

Druhý sloupec je velikost symbolu, třetí je typ. Zde je důležité dívat se na typ, typ B je z .bss sekce, která se do ELF neukládá a je tvořena samými nulami. Typ D je globálně viditelný datový symbol, který zabírá příslušné místo (modulo alignment). Výčet typů viz manuálu nm (podstatné pro nás jsou d/D, g/G, t/T, r/R, v/V, w/W). Z předchozího výčtu je patrné, že se podle možnosti chceme zbavit např. soc_reg_list, který zabírá 1.7 MB.

Jak se zbavit zbytečných symbolů

Nejlépe je donutit linker udělat to automagicky. Linker má option --gc-sections nebo -Wl,--gc-sections pokud mu to předáváme přes gcc/g++, který způsobí, že se zahodí nepoužité sekce ze vstupních knihoven, object fajlů, atd. Má to ale jeden zásadní háček, že pokud je jenom jeden symbol ze sekce object fajlu použit, celá sekce se skopíruje do výslední binárky. Na řešení tohoto problému se hodí dva flagy pro kompilaci, -fdata-sections a -ffunction-sections. Ty mají za výsledek, že každý symbol se obalí do separátní sekce a --gc-sections funguje mnohem lépe.

Je dobré zkontrolovat, zda se to tak překládá, protože to není podporováno na každé architektuře. S linker optionami -Xlinker -Map=output.map si při linkování necháme vygenerovat mapu symbolů output.map. Správně obalené symboly vypadají pak následovně:

 .text.ERR_load_crypto_strings
                0x0000000000f8a938       0x6c 
                0x0000000000f8a938                ERR_load_crypto_strings
 .text.ERR_print_errors_cb
                0x0000000000f8a9a4       0xd0 
                0x0000000000f8a9a4                ERR_print_errors_cb
 .text.ERR_load_EVP_strings
                0x0000000000f8aa74       0x38 
                0x0000000000f8aa74                ERR_load_EVP_strings

Teď linker udělal asi maximum, dále musíme symboly vyklestit ručně. To lze udělat ručně pomocou analýzy kódu, ale já jsem narazil na spoustu generovaného a těžce o-ifdefovaného kódu o statisících LOC, který byl absolutně nečitelný.

Automatické generování závislostí mezi symboly

Pokud nemáte štěstí na nějaký rozumný projekt, je C notoricky těžký jazyk pro statickou analýzu kvůli makrošílenostem a "breathariánským" build systémům, kde se generují Makefily téměř z čistého vzduchu, z různých koutů multiverza tahají tolik makrodefinic -DMAGIC_MACRO1=whatever pro gcc, že to nestíhá při překladu vypisovat konzole.

Co s tím? Nejlepší by bylo nějak ohackovat linker, aby vypsal vzájemne závislosti v momentě, kdy to linkuje, ale nepřišel jsem na jednoduchý způsob, jak na to. Shodou okolností jsem našel několik zajímavých featur dynamického linkeru, kdy vypíše, který symbol odkud linkuje, atd., ale neumí to ty vzájemné závislosti mezi symboly.

Zkoušel jsem různé nástroje, i reverse-engineering frameworky jako radare2 (ten se na analýze zacyklil), nakonec jsem na stack overflow našel tenhle nenápadný ale velmi chytrý one-liner, který využívá disassemblovacích vlastností objdumpu:

#!/bin/bash
objdump -d "$1" \
| grep '<' \
| sed -e 's/^[^<]*//' \
| sed 's/<\([^+]*\)[^>]*>/\1/' \
| awk 'BEGIN { FS = ":" } \
       NF>1 { w=$1; } \
       NF==1 && w != $1 { print  w " " $0  }' \
| sort -u

Nejprve jsem si říkal, že to je takový divný awk/sed/grep hack, že to nemůže fungovat. Jaké bylo mé překvapení, když to vygenerovalo závislosti mezi symbolama Když budete mít chvíli, projděte si jak to funguje, je to překvapivě jednoduché a vynalézavé. V té odpovědi se sice píše, že to vygeneruje caller-callee závislosti, ale generuje to i závislosti i funkce na datech (o tom ještě dále).

Použít graphviz na graf o stovkách tisíc hran fakt nefunguje (zkoušel jsem), tak jsem si napsal krátký pythoní kód, který mi ten graf prolezl od main a spočítal kumulativní velikosti symbolů, kde co na čem závisí.

Zde by byl šťastný konec, kdyby se neobjevilo pár zádrhelů:

1. objdump na x86 správně v disassembleru referencuje datové symboly, na ARM-u ale vůbec, nevím proč (ani ARM gdb to neumí)
2. na ARMu z nějakého důvodu mnoho závislostí mezi symboly chybí, tak se mi graf rozpadnul na spoustu komponent. Nevím zatím proč, zkoušel jsem různé triky jako vypnout inlinování a další magické compile optiony. Na malém příkladu ten problém neumím zreplikovat. Možná za to mohou nějaké záludnosti jako weak symboly, indirekce/trampolíny, whatever. Symboly označené se static linkage jsem podezříval taky, ale ty se mi objevují jako lokální symboly, těmi to nejspíš nebude.

       

Komentáře

[Sten]

Nepůsobí -fdata-sections a -ffunction-sections naopak zvětšení binárky, když má každá funkce svou sekci, která je uvedena ve výsledkem souboru, nebo ty sekce linker nakonec spojí do jedné?

[limit_false]

Ze zkušenosti ne. Když se na ty symboly dívám, tak akorát vyžadují zarování na 32-bit hranici, ale to potřebovali i předtím. Ten trik se sekcemi jen jenom hack na linker.

Zřejmě každý typ sekce má jiný alignment. Tyhle .text.symbol se mi zarovnávají na 4 bajty, .text sekce celá na 16 bajtů. Aktuální objdump dokonce ukazuje i "fill" (nepoužité bajty kvůli zarovnání).

Zřejmě víc by bylo vidět z linker scriptu.

[limit_false]

Manuál gcc má taky zmínku o zvětšení object fajlu, ale když to zkouším, tak mi to vychází opačně - zmenší se.

V mém případě (kvůli kterému jsem tohle řešil) jenom ty dva flagy ořezali z cca 35 MB ARM binárky asi 2.5 MB.

S -Wl,-verbose lze vypsat aktuální linker script, ale zatím jsem z toho nevyčetl podstatní rozdíl.

[pc2005]

Zkoušels i -fwhole-program a zda nějak zmenší binárku?

[limit_false]

Vyzkoušel jsem to, ale nemá to žádný efekt.

[iptriz]

Výborně, něco takového jsem před pár dny řešil (jen s řádově menší binárkou), akorát by to chtělo ještě ten kumulativní výpočet velikosti symbolů, no snad mi to moc nepotrvá. Kdyby se mezitím někomu nelíbil sed/awk, tohle se tváří funkčně ekvivalentně...

objdump -d "$1" | perl -lne 'if(/<([^+]*).*?>(:?)/){if($2){$w=$1}elsif($w ne$1){print"$w $1"}}' | sort -u

[iptriz]

Tak bohužel se ukázalo, že to moc nefunguje – když jdu grafem od mainu, posbírám jen 1/3 velikosti programu. Ověřil jsem si, že to je problém v objdump, kde minimálně jedna funkce nemá jiný odkaz než sama na sebe. Nějaké nápady, co s tím?

#!/bin/sh
objdump -d "$1" | perl -lne 'next unless/<([^+]*).*?>(:?)/;
	if($2){$w=$1}elsif($w ne$1){print"$w $1"}' | sort -u > deps

nm --synthetic --print-size --size-sort --radix=d "$1" | awk '
	function collect(name, set,  i) {
		used[name]++
		if (set[name]++)
			return
		for (i = 0; i < deps[name]; i++)
			collect(deps[name, i], set)
	}
	function run(name,  set, sum, i) {
		set[name] = sum = 0
		collect(name, set)
		for (i in set) sum += sizes[i]
		print name, sizes[name], sum
	}
	{ sizes[$4] = $2 + 0 } END {
		while ((getline < "deps") > 0) { deps[$1, deps[$1]++] = $2 }
		for (name in sizes) run(name)
		for (name in used) if (used[name] < 2) print name > "unreferenced"
	}' | sort -nk3

[iptriz]

000000000041865f <my_funny_callback>:
  41865f:       55                      push   %rbp

[...]

  418739:       be 5f 86 41 00          mov    $0x41865f,%esi

Vypadá to, že to bude chtít mnohem víc Perlu.

[iptriz]

Abych z toho udělal nějaký závěr:

• objdump neresolvuje callbacky předávané argumentem – lze vyřešit
• objdump neresolvuje callbacky z dat – nelze vyřešit

Tedy vždy to bude pouze orientační, každopádně velmi rychlé a jednoduché.

[limit_false]

Jop, čekal jsem něco podobného. objdump někdy resolvuje parametry předáváné odkazem (původně jsem třeba podezříval pthread_create za skrývání symbolů) a někdy resolvuje callbacky z dat (nevím nakolik je tolerantní na zanořené reference).

Každopádně mi to přijde jako zajímavý problém, kterého řešení by mohlo zajímat i někoho jiného. Linker (GNU ld) všechny potřebné informace má, otázka zní, jak to z něj dostat?

Nějaký tip kam se zeptat? Našel jsem binutils mailing-list, ale nevím zda je to vhodný mailinglist (plus nevidím způsob jak se subscribnout).

[pc2005]

Co když mám pole callbacků (a generuju adresu přes nějakej index)? O tom snad linker nemůže vědět ne?

Je nutné se subscribovat? Já když posílám patche do kernelu, tak jen pošlu mail na mailing list z MAINTAINERS. V nejhorším ti přijde mail ať pošleš subscribe majordom botovi. Takže bych jen poslal mail na binutils at sourceware dot org (okopírované z jednoho mailu) a hotovo .

[limit_false]

Úplně nerozumím, jaký je problém s polem callbacků. Linker prostě musí vzít všechny symboly, které jsou referencované a doplnit je do binárky buď kopírovaním nebo jako UNDEFINED odkaz.

[pc2005]

Jo on ten callback bude vlastně někde přiřazenej a to udělá referenci :-/.

[pc2005]

Jo callbacky jsou zlo!

[iptriz]

Víc Perlu vypadá takto:

objdump -d "$1" | perl -lne '
	if (/^0*([\da-f]+) <(.+?)>:/) { $a{$1} = $w = $2
	} elsif (/<([^+]*).*?>/) { print "$w $1" if $w ne $1
	} elsif (/0x([\da-f]+),/) { push @{$deps{$w}}, $1
	} END { while (my ($w, $refs) = each %deps) {
		for (@$refs) { print "$w $a{$_}" if exists $a{$_} }
	}}' | sort -u > deps

Skóre: main vzrostl z 26.1% na 35.6% velikosti sstripnuté binárky. _start začal být větší než main. Konkrétní program obsahuje callbacky v datech s nemalým podstromem.

[iptriz]

Drobnou úpravou se dostáváme k 21.8% → 51.7% sstripnutého release buildu:

objdump -d "$1" | perl -lne '
	if (/^0*([\da-f]+) <(.+?)>:/) { $a{$1} = $w = $2; next }
	print "$w $1" if /<([^+]*).*?>/ && $w ne $1;
	push @{$deps{$w}}, $1 if /0x([\da-f]+),/;
	END { while (my ($w, $refs) = each %deps) {
		for (@$refs) { print "$w $a{$_}" if exists $a{$_} }
	}}' | sort -u > deps

[iptriz]

Ještě jde resolvnout pár zbylých odkazů na data a zde asi definitivně končím:

nm "$1" | perl -lne 'print for /^0*(\S+) . (\S+)/' > addresses
objdump -d "$1" | perl -lne '
	if (/<([^+]*).*?>(:?)/) { $w = $1 if $2; print "$w $1" if $w ne $1 }
	BEGIN { %a = (split " ", `cat addresses`) }
	print "$w $a{$1}" if /0x([\da-f]+),/ && exists $a{$1}' | sort -u > deps

Další krok je omílaný linker nebo potenciálně DWARF.

[iptriz]

Mimovolně jsem ještě došel k tomu, že ty informace jdou vytahat z object souborů, přes objdump -x. Člověk si ze "symbol table" posbírá offsety a velikosti a pak projíždí "relocation records" a zpětně resolvuje. Object soubory jenom už může být trochu problém posbírat, možná přes nějaký falešný kompilátor/linker jak to dělá scan-build analyzátor, ccache a podobné, a pořád to nemusí být triviální (více object files na jedny zdrojáky s různými defines), tak možná počkat na finální link příkaz do binárky a poprat se i s .a soubory. Teoreticky by se to dalo sledovat i přes strace/ptrace místo wrapperů.

[iptriz]

Ono to jde vytahat i z toho output.map souboru ze sekce "Linker script and memory map", řádky LOAD s názvy souborů se dají docela snadno vyparsovat. Problém je, když se linkuje víc věcí, pak se ty output.map přepisují.

[limit_false]

Celkem bych se mi hodil nějaký krátký příklad, na kterém se to projevuje. (Plus compile a link flagy).

[pc2005]

BTW o co že takhle diskuze nakonec skončí u analýzy pomocí spuštění v QEMU .