極小実行ファイル再考
The Teensy Executable Revisited (muppetlabs.com)
要約
この記事は、以前の「極小実行ファイル」に関するエッセイへの反論に応え、ELF実行ファイルのサイズを極限まで小さく保ちつつ、厳密なELF標準に準拠させる方法を探求しています。著者は、ELFヘッダーとプログラムヘッダーの重複利用や、未指定フィールドへのコード埋め込み、プログラムロードアドレスの調整といった巧妙なテクニックを駆使して、最終的に76バイトの実行ファイルを作成することに成功しました。これは、ELF仕様の柔軟性を最大限に活用しながら、最小限のコードで実行可能なファイルを実現する試みです。
全文翻訳
超小型実行可能ファイル 再訪
(あるいは、「地平線に雷雲が立ち込める」)
何度か、私の元のエッセイに対する応答として、最終的に私が作成したものは真のELF実行可能ファイルではない、というコメントがありました。むしろ、それはLinuxカーネルが現在の実装で、たまたまELF実行可能ファイルと誤認するファイルである、というものです。
それはもっともな指摘です。あの45バイトのファイルは、明らかにELF仕様の数多くの要件を満たしていません。しかし、私を責めることができますか? 何が可能になるかを知りながら、ELF仕様を窓の外に投げ捨てる直前の時点で、どうやって止めることができたでしょうか?
しかし、これらの純粋主義者、そして私たち全員の中の純粋主義的な側面を満たすために、私はこの続編を作成しました。
さて。私たちは45バイトにまで削り込んだ実行可能ファイルを持っています。今、私たちはそれを公開されている標準に厳密に準拠させつつ、可能な限り小さく保ちたいと考えています。
私たちがまっすぐな道から逸れたのは、「未使用」フィールドをいじり始めたときでした。では、その時点まで戻りましょう。
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 ehdrsz ; e_ehsize
dw phdrsz ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx
ehdrsz equ $ - ehdr
phdr:
db 1 ; p_type
db 0 ; p_offset
dd $$ ; p_vaddr
dd $$ ; p_paddr
dd filesz ; p_filesz
dd filesz ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsz equ $ - phdr
_start:
xor eax, eax
inc eax
mov bl, 42
int 0x80
filesz equ $ - $$
これは91バイトのバージョンでした。では、これで最良のサイズとして満足しなければならないのでしょうか? いいえ、まだそうではありません。ELFヘッダーとプログラムヘッダーテーブルを8バイト重ねても、ルールを破っていません。ELF仕様では、異なるデータ構造のファイル内での重ね合わせが明示的に許可されています。では、ここでそれを実行しましょう。
; tiny.asm
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 ehdrsz ; e_ehsize
dw phdrsz ; e_phentsize
phdr: dd 1 ; e_phnum ; p_type
; e_shentsize
dd 0 ; e_shnum ; p_offset
; e_shstrndx
ehdrsz equ $ - ehdr
dd $$ ; p_vaddr
dd $$ ; p_paddr
dd filesz ; p_filesz
dd filesz ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsz equ $ - phdr
_start: xor eax, eax
inc eax
mov bl, 42
int 0x80
filesz equ $ - $$
これで83バイトになりました。他に何ができるでしょうか? あまりないようです。絶望的な状況で、ELF仕様に戻ってもう一度読み返し、何かを探すかもしれません。
初期レジスタ値について、何か保証はありますか? edxレジスタだけです。そして、それがゼロか、最終的なシャットダウン手続きのアドレスのどちらかを含むと述べています。つまり、実際には全く保証はありません。探し続けましょう。
アハ:プログラムヘッダーテーブル構造の p_paddr フィールド! Intelアーキテクチャに適用されない、または実行可能ファイルに適用されないヘッダーの他のすべてのフィールドは、ELF仕様によってゼロに設定される必要があります。しかし、p_paddr フィールドについては、仕様ではそのフィールドの内容は未指定であると述べています。ですから、結局4バイトを自由に使うことができます。
それらをどう使うか? 当然、プログラムの一部を格納するために使用します。もちろん、プログラム全体をそこに配置することはできません。そのため、残りの部分に到達するためにjmp命令で4バイトのうち2バイトを無駄にする必要があります。しかし、それでも2バイトが残ります。そして、プログラムの最初の命令はちょうど2バイトの長さです。
; tiny.asm
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 ehdrsz ; e_ehsize
dw phdrsz ; e_phentsize
phdr: dd 1 ; e_phnum ; p_type
; e_shentsize
dd 0 ; e_shnum ; p_offset
; e_shstrndx
ehdrsz equ $ - ehdr
dd $$ ; p_vaddr
_start: xor eax, eax ; p_paddr
jmp short part2
dd filesz ; p_filesz
dd filesz ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsz equ $ - phdr
part2: inc eax
mov bl, 42
int 0x80
filesz equ $ - $$
これで81バイトになりました。これだけでしょうか?
p_paddrフィールドの次のフィールドはp_fileszフィールドです。もしこのjmp命令をそれに重ねることができれば、さらに命令を詰め込むことができるでしょう。しかし、残念ながら、そのフィールドの最初のバイトはファイル全体のサイズであり、それはジャンプするには賢明ではないでしょう。そして残りのバイトはゼロです。そのアプローチはあまり有望に見えません。
p_paddrの前のフィールドはどうでしょうか? それはプログラムがロードされるアドレスです。さて、デフォルト値の0x08048000を使用する必要はないことはすでにわかっています。少なくともページアラインメントを維持する必要がありますが、アドレスの上半分に2バイトの命令を収めることができるはずです。しかし、私たちのxor命令はここでは機能しません。これはリトルエンディアンであることを忘れないでください。プログラムのバイトは現在次のようになっています。
31C0 xor eax, eax
EB10 jmp short part2
40 part2: inc eax
B32A mov bl, 42
CD80 int 0x80
xor命令は最上位バイトとしてC0を残します。これは上位ビットがセットされており、Linuxはそれを好ましく思いません。(一般的なルールとして、32ビット実行可能ファイルでは、メモリの上半分は動的に割り当てられるアドレス、つまりヒープ、スタック、共有オブジェクトライブラリのために予約されています。)
一方、「mov bl, 42」命令は、完全に許容できる最上位アドレスバイトを提供します。したがって、ロードアドレスを0x2AB30000に変更し、少し並べ替えると次のようになります。
; tiny.asm
BITS 32
org 0x2AB30000
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 ehdrsz ; e_ehsize
dw phdrsz ; e_phentsize
phdr: dd 1 ; e_phnum ; p_type
; e_shentsize
dd 0 ; e_shnum ; p_offset
; e_shstrndx
ehdrsz equ $ - ehdr
dw 0 ; p_vaddr
_start: mov bl, 42
xor eax, eax ; p_paddr
jmp short part2
dd filesz ; p_filesz
dd filesz ; p_memsz
dd 5 ; p_flags
dd 0x1000 ; p_align
phdrsz equ $ - phdr
part2: inc eax
int 0x80
filesz equ $ - $$
これで79バイトになりました。もし「inc eax」命令のためにあと1バイトのスペースを見つけることができれば、p_addrフィールドのジャンプを「int 0x80」に置き換えることができ、プログラム全体を合法的にヘッダー内に収めることができます! あと1バイトだけ…
最後のバイトを次のフィールドにオーバーフローさせることはできないでしょうか? それはp_fileszフィールド、つまりファイル内のプログラムセグメントのサイズを指定します。プログラムの最後のバイトは0x80ですが、これはファイルサイズとしては大きすぎます。つまり、ファイルサイズを偽ることはできますが、Linuxは見て見ぬふりをします。しかし、ここではまっすぐな道を進むはずです。
p_fileszの後のフィールドはp_memszです。もしこの2つのフィールドが逆だったら、問題はなかったでしょう。このフィールドは以前にも検討しました。プログラムをメモリにロードする際にどれだけのメモリを割り当てるかを指定します。このフィールドをファイルサイズより大きく設定しても問題ありません。
しかし、このフィールドを使用する方法があります。p_fileszを飛び越えてp_memszにジャンプすることができます。これを試すと、実際には利益を得られることがわかります。
; tiny.asm
BITS 32
org 0x2AB30000
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 ehdrsz ; e_ehsize
dw phdrsz ; e_phentsize
phdr: dd 1 ; e_phnum ; p_type
; e_shentsize
dd 0 ; e_shnum ; p_offset
; e_shstrndx
ehdrsz equ $ - ehdr
dw 0 ; p_vaddr
_start: mov bl, 42
xor eax, eax ; p_paddr
jmp short part2
dd filesz ; p_filesz
part2: inc eax ; p_memsz
int 0x80
db 0
dd 7 ; p_flags
dd 0x1000 ; p_align
phdrsz equ $ - phdr
filesz equ $ - $$
そして76バイトに到達しました!
このバージョンには、プログラムがかなりのメモリを要求するという欠点があります。具体的には0x0080CD40バイト、つまり8メガバイトです。(そして、このメモリがゼロ初期化されるのを許可するために、p_flagsに書き込み可能フラグを追加する必要があることに注意してください。)もちろん、メモリは実際にはアクセスされないため、仮想メモリなどのおかげで、ほとんど問題になりません。この数値は、LinuxがRAMページを割り当てようとする代わりにセグメンテーション違反を報告するアドレスを示しているだけです。したがって、実際には害はありません。
しかし、5バイトの命令を使用して4バイトを飛び越える方法があることがわかりました。どうやって? 5バイトの命令を使用するからです! 「cmp eax, imm32」のような、無害で素敵な命令を考えてみてください。唯一の効果はフラグを設定することです。まあ、それと命令ポインタを進めることです。
; tiny.asm
BITS 32
org 0x2AB30000
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 ehdrsz ; e_ehsize
dw phdrsz ; e_phentsize
phdr: dd 1 ; e_phnum ; p_type
; e_shentsize
dd 0 ; e_shnum ; p_offset
; e_shstrndx
ehdrsz equ $ - ehdr
dw 0 ; p_vaddr
_start: mov bl, 42
xor eax, eax ; p_paddr
inc eax
cmp eax, strict dword filesz ; p_filesz
int 0x80 ; p_memsz
dw 0
dd 7 ; p_flags
dd 0x1000 ; p_align
phdrsz equ $ - phdr
filesz equ $ - $$
比較命令の最初のバイトはp_paddrフィールドの最後のバイトにあり、4バイトの即値データを残します。私たちのプログラムは、p_fileszの値を半分のコストで通過させることができ、これによりincrement命令をp_memszフィールドから移動させることができます。これにより、このフィールドには0x000080CD、つまり32K強という、はるかに扱いやすい無駄なメモリ割り当て値が保持されます。
これが私たちの新しいプログラムの最終バージョンです。長さは76バイトです。これにより、31バイトのコストでELF仕様への準拠を確立しました。すべてを考慮すると、悪くはありません。そして今、私たちはすべてのバイトが説明されていると主張できる2つのプログラムを持っています。
しかし、私たちは本当に純粋主義者を黙らせたのでしょうか?
一部の純粋主義者は黙らせました。しかし、まだ数人が残っており、私たちのint命令を非難するように指を鳴らしています。ああ、そうです。それです。直接のシステムコールは、カーネルとの文書化されたインターフェースの一部ではありません。(少なくとも私たちのような者にとっては。)システムコール番号1がexitであるという事実は、将来の改訂で同じままであることが保証されていません。誰が知っているでしょうか? 後続のカーネルがexit関数に新しい機能を追加する必要があり、バイナリの後方互換性を維持するために、現在未使用のシステムコール番号を持つ新しいexit関数を導入し、古い方を非推奨にする可能性があります。
確かに、exitのような基本的な必要性でこれが起こる可能性は非常に低いです。しかし、それは起こります。例えば、uname関数を実装するシステムコールは3つあり、最初の2つは両方とも非推奨になっています。utsname構造にさらに情報を追加するために、新しいシステムコールを導入する必要があり、古いものが後方互換性のために元のABIを遵守し続けることができました。(もし、ある時点で、古いバイナリがもう存在しないと確信できれば、それらのシステムコールは完全に削除され、その後新しいものがそれらの番号を再利用できるかもしれません。もちろん、私のような邪魔な人々が直接システムコールをハードコーディングすることでそのような進歩を妨げている場合を除いて!)
わかりました。完全に正当であろうとするなら、私たちはまだ問題の中にいます。そして抜け出す唯一の方法は、文書化されたABIを厳密に遵守することです。この場合、それは_exitを使用する必要があることを意味します。システムコールではなく、関数です。libcによって提供されるものです。それは(うんざりしながら)これまで喜んで避けてきたすべての動的リンクのオーバーヘッドを再導入する必要があることを意味します。
それは、ELFバイナリがどのように動的リンクを行っているかを正確に学ぶ必要があることを意味します。そうすれば、それを自分たちで行うことができます(そして、うまくいけばより少ないスペースで)。しかし、それは簡単なトピックではないので、次のエッセイに保存する必要があります。