目次: ベンチマーク
前回(2024年2月25日の日記参照)はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、アセンブラというかほぼバイナリ直書きのC言語で挑戦しました。その後、バイナリサイズを削って遊んでみたところgccのみで840バイト、stripありで520バイトとなり、バイナリでも1000バイト以下を達成しました。
今回はどこまでバイナリのサイズを切り詰められるか試してみたいと思います。ツール頼みだとこれ以上削れないと思うのでバイナリエディタで削っていきます。
前回の私のバイナリ実装はかなり適当だったので猛者に叩きなおしてもらいました。変化点としては、
といったところです。
const char _start[] __attribute__((section(".text"))) = {
0xbb, 0x40, 0x42, 0x0f, 0x00, //ebx 1000000
0x6a, 0x01, //push 0x1
0x58, //pop rax
0x89, 0xc7, //mov eax,edi
0x6a, 0x0e, //push 0xe
0x5a, //pop rdx
0xbe, 0x1c, 0x01, 0x40, 0x00, //mov 0x4011c, esi
0x0f, 0x05, //syscall
0xff, 0xcb, //dec ebx
0x75, 0xed, //jne -> push 0x1
0x6a, 0x3c, //push 0x3c
0xeb, 0xeb, //jmp -> pop rax
'H', 'e', 'l', 'l', 'o', ',', ' ',
'W', 'o', 'r', 'l', 'd', '!', '\n',
};
この改良の時点で520→512バイト(8バイト減)に改善します。素晴らしい〜。
$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none -fno-ident a.c /tmp/cczsMtLk.s: Assembler messages: /tmp/cczsMtLk.s:4: Warning: ignoring changed section attributes for .text $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 832 2月 25 13:47 a.out $ strip -s a.out $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 512 2月 25 13:47 a.out ★8バイト改善 $ objdump -DrS a.out (略) 0000000000400100 <.text>: 400100: bb 40 42 0f 00 mov $0xf4240,%ebx 400105: 6a 01 push $0x1 400107: 58 pop %rax 400108: 89 c7 mov %eax,%edi 40010a: 6a 0e push $0xe 40010c: 5a pop %rdx 40010d: be 1c 01 40 00 mov $0x40011c,%esi 400112: 0f 05 syscall 400114: ff cb dec %ebx 400116: 75 ed jne 0x400105 400118: 6a 3c push $0x3c 40011a: eb eb jmp 0x400107 ★ここから下はHello, World!の文字列なので命令列としては無意味 40011c: 48 rex.W 40011d: 65 6c gs insb (%dx),%es:(%rdi) 40011f: 6c insb (%dx),%es:(%rdi) 400120: 6f outsl %ds:(%rsi),(%dx) 400121: 2c 20 sub $0x20,%al 400123: 57 push %rdi 400124: 6f outsl %ds:(%rsi),(%dx) 400125: 72 6c jb 0x400193 400127: 64 21 0a and %ecx,%fs:(%rdx) $ ./a.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./a.out | wc 1000000 2000000 14000000
動作確認もできました。バイナリはこんな感じです。
$ hexdump -C remove_prg_section_org.out 00000000 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 |.ELF............| 00000010 02 00 3e 00 01 00 00 00 00 01 40 00 00 00 00 00 |..>.......@.....| 00000020 40 00 00 00 00 00 00 00 40 01 00 00 00 00 00 00 |@.......@.......| 00000030 00 00 00 00 40 00 38 00 03 00 40 00 03 00 02 00 |....@.8...@.....| 00000040 01 00 00 00 04 00 00 00 00 00 00 00 00 00 00 00 |................| 00000050 00 00 40 00 00 00 00 00 00 f0 3f 00 00 00 00 00 |..@.......?.....| 00000060 e8 00 00 00 00 00 00 00 e8 00 00 00 00 00 00 00 |................| 00000070 00 10 00 00 00 00 00 00 01 00 00 00 05 00 00 00 |................| 00000080 00 01 00 00 00 00 00 00 00 01 40 00 00 00 00 00 |..........@.....| 00000090 00 01 40 00 00 00 00 00 2a 00 00 00 00 00 00 00 |..@.....*.......| 000000a0 2a 00 00 00 00 00 00 00 00 10 00 00 00 00 00 00 |*...............| 000000b0 51 e5 74 64 06 00 00 00 00 00 00 00 00 00 00 00 |Q.td............| 000000c0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 000000e0 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 000000f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000100 bb 40 42 0f 00 6a 01 58 89 c7 6a 0e 5a be 1c 01 |.@B..j.X..j.Z...| 00000110 40 00 0f 05 ff cb 75 ed 6a 3c eb eb 48 65 6c 6c |@.....u.j<..Hell| 00000120 6f 2c 20 57 6f 72 6c 64 21 0a 00 2e 73 68 73 74 |o, World!...shst| 00000130 72 74 61 62 00 2e 74 65 78 74 00 00 00 00 00 00 |rtab..text......| 00000140 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00000180 0b 00 00 00 01 00 00 00 06 00 00 00 00 00 00 00 |................| 00000190 00 01 40 00 00 00 00 00 00 01 00 00 00 00 00 00 |..@.............| 000001a0 2a 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |*...............| 000001b0 20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ...............| 000001c0 01 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00 |................| 000001d0 00 00 00 00 00 00 00 00 2a 01 00 00 00 00 00 00 |........*.......| 000001e0 11 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 000001f0 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000200
サイズは小さいですが0データの羅列が目立ちます。削れそうな気がしてきませんか?
大物から削りましょう。プログラムヘッダがなぜか3つありますが2つ不要、セクションヘッダは実行には不要、セクションヘッダ削除に伴って.shstrtabも不要です。
プログラムヘッダ: タイプ オフセット 仮想Addr 物理Addr ファイルサイズ メモリサイズ フラグ 整列 LOAD 0x0000000000000000 0x0000000000400000 0x00000000003ff000 ★いらない 0x00000000000000e8 0x00000000000000e8 R 0x1000 LOAD 0x0000000000000100 0x0000000000400100 0x0000000000400100 0x000000000000002a 0x000000000000002a R E 0x1000 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 ★いらない 0x0000000000000000 0x0000000000000000 RW 0x10
削除データの位置は下記の図の通りです。
削除するデータ(プログラムヘッダ、セクションヘッダなど)の位置
単純に削除すると.textセクションの位置とヘッダに記載されているアドレスがズレて動かなくなりますから、
上記の値を調整します。調整後のバイナリが下記です。
$ ls -la remove_prg_section.out -rwxr-xr-x 1 katsuhiro suzuki 162 2月 25 14:05 remove_prg_section.out $ hexdump -C remove_prg_section.out 00000000 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 |.ELF............| ★ELFヘッダ 00000010 02 00 3e 00 01 00 00 00 78 00 40 00 00 00 00 00 |..>.....x.@.....| 00000020 40 00 00 00 00 00 00 00 40 01 00 00 00 00 00 00 |@.......@.......| 00000030 00 00 00 00 40 00 38 00 01 00 40 00 03 00 02 00 |....@.8...@.....| 00000040 01 00 00 00 05 00 00 00 60 00 00 00 00 00 00 00 |........`.......| ★プログラムヘッダ 00000050 60 00 40 00 00 00 00 00 60 00 40 00 00 00 00 00 |`.@.....`.@.....| 00000060 40 00 00 00 00 00 00 00 40 00 00 00 00 00 00 00 |@.......@.......| 00000070 00 10 00 00 00 00 00 00 bb 40 42 0f 00 6a 01 58 |.........@B..j.X| ★0x78〜: 実行する命令列 00000080 89 c7 6a 0e 5a be 94 00 40 00 0f 05 ff cb 75 ed |..j.Z...@.....u.| 00000090 6a 3c eb eb 48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 |j<..Hello, World| 000000a0 21 0a |!.| 000000a2
0データの羅列が減ってだいぶスリム化しました。サイズは162バイトです。
ELFヘッダには色々な値が並んでいますが、実行ファイルを実行(execveシステムコール)するときに全ての値をチェックしているわけではありません。これを逆手にとってELFヘッダに実行命令列やデータを詰め込むことができます。図で示した黄色い部分以外は好き勝手に変えて大丈夫です。
最初の空き地はe_identの後半(アドレス: 0x04〜0x0f、12バイト)とe_version(アドレス: 0x14〜0x17、4バイト)です。実行バイナリの先頭4命令、10バイト分、そのあとの2バイト分を入れます。各領域の終端2バイトはジャンプ命令に使います。そうしないと命令列ではないところまで実行してクラッシュするからからです。
★e_identに入れる分 400100: bb 40 42 0f 00 mov $0xf4240,%ebx 400105: 6a 01 push $0x1 400107: 58 pop %rax 400108: 89 c7 mov %eax,%edi ★e_versionに入れる分 40010a: 6a 0e push $0xe
次の空き地はe_shoff, e_flags, e_ehsize(アドレス: 0x28〜0x35、14バイト)です。ちょうど"Hello, World!\n"と同じ長さなので文字列を置きます。
最後の空き地はELFヘッダの終端、e_shentsize, e_shnum, e_shstrndx(アドレス: 0x3a〜0x3f、6バイト)です。ここは命令列を置くよりe_phnumの値とプログラムヘッダの先頭p_typeも値が0x01であることを利用して、プログラムヘッダを8バイト手前にずらした方が良いでしょう。命令列を置くとジャンプ命令分を除いて、4バイトしか改善できないからです。
プログラムヘッダの方は空き地はほぼなく、ヘッダ終端のp_align(8バイト)だけ変更OKでした。ここにも命令列を置きましょう。
最後にアドレスを調整するとこんなバイナリです。120バイトになりました。当然、実行できて100万回のHello, World!を出力します。
$ hexdump -C overwrap_elfh.out 00000000 7f 45 4c 46 bb 40 42 0f 00 6a 01 58 89 c7 eb 04 |.ELF.@B..j.X....| 00000010 02 00 3e 00 6a 0e eb 50 04 00 40 00 00 00 00 00 |..>.j..P..@.....| 00000020 38 00 00 00 00 00 00 00 48 65 6c 6c 6f 2c 20 57 |8.......Hello, W| 00000030 6f 72 6c 64 21 0a 38 00 01 00 00 00 05 00 00 00 |orld!.8.........| 00000040 60 00 00 00 00 00 00 00 60 00 40 00 00 00 00 00 |`.......`.@.....| 00000050 60 00 40 00 00 00 00 00 30 00 00 00 00 00 00 00 |`.@.....0.......| 00000060 30 00 00 00 00 00 00 00 5a be 28 00 40 00 0f 05 |0.......Z.(.@...| 00000070 ff cb 75 95 6a 3c eb 93 |..u.j<..| 00000078 $ ./overwrap_elfh.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./overwrap_elfh.out | wc 1000000 2000000 14000000
あくまでもこのバイナリは私が使っているLinux kernel 6.1系のチェックを掻い潜って実行できるだけ、です。gdbは実行ファイルとして認識してくれませんし、readelfも大量のエラーを出します。将来のLinuxカーネルでも実行できなくなる可能性があります。
$ gdb ./remove_elf.out GNU gdb (Debian 13.1-3) 13.1 (略) "(略)/./remove_elf.out": not in executable format: file format not recognized (gdb) $ readelf -a remove_elf.out ELF ヘッダ: マジック: 7f 45 4c 46 bb 40 42 0f 00 6a 01 58 89 c7 eb 04 クラス: <不明: bb> データ: <不明: 40> Version: 66 <unknown> OS/ABI: AROS ABI バージョン: 0 型: EXEC (実行可能ファイル) マシン: Advanced Micro Devices X86-64 バージョン: 0x50eb0e6a エントリポイントアドレス: 0x400004 プログラムヘッダ始点: 0 (バイト) セクションヘッダ始点: 56 (バイト) フラグ: 0x0 Size of this header: 25928 (bytes) Size of program headers: 27756 (bytes) Number of program headers: 11375 Size of section headers: 22304 (bytes) Number of section headers: 29295 Section header string table index: 25708 readelf: 警告: The e_shentsize field in the ELF header is larger than the size of an ELF section header readelf: エラー: Reading 653395680 bytes extends past end of file for セクションヘッダ readelf: エラー: セクションヘッダが利用できません! readelf: エラー: Too many program headers - 0x2c6f - the file is not that big このファイルには動的セクションがありません。 readelf: エラー: Too many program headers - 0x2c6f - the file is not that big
さらにLinuxの裏をかいて削減できるような気もしますけど……、キリがないのでこれくらいにしておきます。
GDBはセクションヘッダを削除した時点でELFファイルとして認識しなくなります。ジャンプ先を間違ったとき、アドレスが間違っていてSEGVするときのデバッグができずしんどいです。
バイナリの種類 | GDB | readelf |
---|---|---|
オリジナル512バイト版 | 認識する | エラーなし |
セクション削除162バイト版 | エラー | セクションヘッダがない、エラー |
ELFヘッダ改変120バイト版 | エラー | 読む場所がずれてる(OS/ABIが間違っているから?) |
< | 2024 | > | ||||
<< | < | 02 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | - | - | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | - | - |
合計:
本日: