コグノスケ

未来から過去へ表示

過去から未来へ表示(*)

もっと前

2024年2月26日 >>> 2024年2月26日

もっと後

2024年2月26日

permalink

編集する

100万回のHello, World! - バイナリサイズを削って遊ぼう

目次: ベンチマーク

前回（2024年2月25日の日記参照）はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、アセンブラというかほぼバイナリ直書きのC言語で挑戦しました。その後、バイナリサイズを削って遊んでみたところgccのみで840バイト、stripありで520バイトとなり、バイナリでも1000バイト以下を達成しました。

今回はどこまでバイナリのサイズを切り詰められるか試してみたいと思います。ツール頼みだとこれ以上削れないと思うのでバイナリエディタで削っていきます。

バイナリの見直し

前回の私のバイナリ実装はかなり適当だったので猛者に叩きなおしてもらいました。変化点としては、

レジスタに0x1を代入するとき、movではなくpushとpopを使う
exitを呼ぶときwriteを呼ぶ処理を流用してmovを減らす
アドレスが固定であることを期待して、幅を取ってたlea命令をmovに置き変える

といったところです。

バイナリの改良


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

動作確認もできました。バイナリはこんな感じです。

サイズ削減前のバイナリ（512バイト）

$ 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データの羅列が目立ちます。削れそうな気がしてきませんか？

削れそうなもの - プログラムヘッダ、セクション（512→162バイト）

大物から削りましょう。プログラムヘッダがなぜか3つありますが2つ不要、セクションヘッダは実行には不要、セクションヘッダ削除に伴って.shstrtabも不要です。

プログラムヘッダが3つあるが、2つは不要

プログラムヘッダ:
  タイプ        オフセット          仮想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セクションの位置とヘッダに記載されているアドレスがズレて動かなくなりますから、

ELFヘッダ: e_entry, e_phoff, e_phnum
プログラムヘッダ: p_offset, p_vaddr, p_paddr, p_filesz, p_memsz

上記の値を調整します。調整後のバイナリが下記です。

削減第一弾（162バイト）

$ 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ヘッダ（162→120バイト）

ELFヘッダには色々な値が並んでいますが、実行ファイルを実行（execveシステムコール）するときに全ての値をチェックしているわけではありません。これを逆手にとってELFヘッダに実行命令列やデータを詰め込むことができます。図で示した黄色い部分以外は好き勝手に変えて大丈夫です。

ELFヘッダのなかで正しい値を維持しなければならない部分

最初の空き地はe_identの後半（アドレス: 0x04〜0x0f、12バイト）とe_version（アドレス: 0x14〜0x17、4バイト）です。実行バイナリの先頭4命令、10バイト分、そのあとの2バイト分を入れます。各領域の終端2バイトはジャンプ命令に使います。そうしないと命令列ではないところまで実行してクラッシュするからからです。

e_identの後半に入れる命令列、e_versionに入れる命令列

★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バイトしか改善できないからです。

ELFヘッダの終端とプログラムヘッダの先頭8バイトを重ねる

プログラムヘッダの方は空き地はほぼなく、ヘッダ終端のp_align（8バイト）だけ変更OKでした。ここにも命令列を置きましょう。

最後にアドレスを調整するとこんなバイナリです。120バイトになりました。当然、実行できて100万回のHello, World!を出力します。

削減第二弾（120バイト）

$ 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やreadelfには怒られる

$ 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するときのデバッグができずしんどいです。

ELFヘッダを書き換えるとreadelfすら訳の分からない表示になるので、デバッグがさらに辛いですね……。

バイナリの種類	GDB	readelf
オリジナル512バイト版	認識する	エラーなし
セクション削除162バイト版	エラー	セクションヘッダがない、エラー
ELFヘッダ改変120バイト版	エラー	読む場所がずれてる（OS/ABIが間違っているから？）