しかくいさんかく

解答略のメモ

11日目: [x86] アーキテクチャとバイナリ解析最速マスター

アドベントカレンダー2017 低レイヤ x86

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の11日目の記事です。

昨日まではCPUの回路実装の話だった。つまりトランジスタをいかに配置するか、という話だった。 そういう回路視点でCPUを考えることをマイクロアーキテクチャという。

今日からは命令セットアーキテクチャの視点でCPUを考えていく。 命令セットは全ニーモニックを集めた一覧表と思えば良い。 つまりレジスタは何個で、ニーモニックはどんな感じで、どういう機械語に変換されるのかという視点で、これからCPUを考えていく。

CPUの種類が変われば命令セットも変わる。 全てのCPUを解説することはできないので、今後はx86と呼ばれるCPUに特化する。

x86はintelが30年以上前に策定した命令セットで、今日までPCとサーバーのCPU市場を席巻してきた。 日常で使用するCPUは今後もx86であり続けるだろう1。 手元のPCの仕組みを理解する上で、x86の命令セットは外せないと思う。

x86を知るメリットは山のようにある。

  • 普段使うPCの実行可能ファイルが解析できるようになる (この記事の最後でやる)
  • 普段使うPCで様々な言語をデバッグする際の最終兵器になる
  • 普段使うPCでC言語のソース内にアセンブラを埋め込み、超カリカリに最適化できる
  • 普段使うPCで動くOSを自作するにはx86の細かい知識がいる
  • 普段使うPC用のコンパイラを作るのに必要
  • 普段使うPC用のデバイスドライバも書けるらしい

適当に書き並べてみたが、まだまだあると思う。

つまるところ、日常用途の実行可能ファイルを解析する手段があると安心感が違う。 他の命令セットをベースにすると、この安心感が得られない。 「MIPSはキレイで学びやすい。初心者におすすめ」などと言ってx86を知らずに生きるのは、もったいなさすぎる。

そういう偏った信念に基づき、あと4日間かけてx86の機能(のごく一部)を説明し、最後にエミュレータを作ろうと思う。

レジスタの種類

x86 (IA-32)のレジスタ構成を見てみる。

名称 サイズ タイプ 昨日のCPUの対応物 movで値変更
eax 32bit 計算用 a O
ecx 32bit 計算用 c O
edx 32bit 計算用 d O
ebx 32bit 計算用 b O
esp 32bit スタックポインタ sp O
ebp 32bit 関数呼出で使う なし O
esi 32bit 計算用 aかも O
edi 32bit 計算用 cかも O
eip 32bit プログラムカウンタ ip X
eflags 32bit フラグの集まり zf X

ebp以外は、昨日作ったしょぼいCPUに対応物がある。 ebpは「関数呼出で使う」などと難しそうに書かれているが、結局のところeaxと同じようなレジスタだ。恐れる必要はない。

eipとeflagsはmovで値が変更できないと書かれている。 昨日作ったCPUでも、プログラムカウンタやゼロフラグは自動で値が変化するので、mov命令で恣意的に値を変える必要は無かった。

他にもレジスタはある2のだが、話をややこしくするだけなので無視する。 参考用に 昨日作ったCPUの仕様書へのリンク を貼っておく。是非見比べて欲しい。

命令セット表

これがx86(IA-32)の命令セットだ!

f:id:kaitou_ryaku:20171211195350p:plain

土日の間に頑張って作った。

jmp imm8

この表の使い方を説明するため、例として右下(e行b列)のjmp imm8を考える。 これはジャンプ命令で、昨日作ったCPUに存在したニーモニックなので意味はわかると思う。

表の使い方だが、まずhoge.asmというファイルに

; hoge.asm

jmp 0x12 ; 0x12は8bitの即値、つまりimm8

と書いて、nasmコマンドで機械語に変換する

$ nasm hoge.asm -o hoge.o   # アセンブルするコマンド

これで機械語に変換された。 1byte(8bit)ずつ区切って16進表示すると

$ xxd -g 1 hoge.o   # バイナリを表示するコマンド
00000000: eb 12

つまりjmp 0x12をアセンブラで機械語に変換すると、eb 12になる。

jmp imm32

jmp imm8の左にはimm8をimm32に変えたやつがいる。この場合

jmp 0x12345678 ; 0x12345678は32bitの即値、つまりimm32
               ; 対応する機械語は e9 78 56 34 12

なんか12345678の順番が変なことになっているが、この理屈はややこしいので明日に回そう。

実は表の空欄の部分にも命令があるのだが、今回は無視した3。 表に記載した命令は、後日解説予定のx86エミュレータに実装されている。

命令セット毎に分割

各命令の詳細は明日以降に回すとして、さっきの表の全体を眺めると、おおむね4行毎に分割されている。 また左右が対称的になっている。左側だけ上から順に見ていくと

0-3行:計算系

f:id:kaitou_ryaku:20171211195414p:plain:w400

最初の4行は計算演算で構成されている。

  • addは言うまでもなく加算
  • adcも加算なのだが、キャリーフラグが立ってる場合は結果にプラス1する
  • andはbid毎に論理積をとる演算
  • xorはbid毎に排他的論理和をとる演算

枠内に小文字で[M+imm]やRなどと書かれているが、これはModRMというややこしいやつなので、明後日解説する。

4-7行:inc, push, jcc

f:id:kaitou_ryaku:20171211195425p:plain:w400

一番目のincはレジスタの値を1増やす命令だ。

枠内には小文字でeaxやらediなどと書かれているが、これは

inc eax ; 対応する機械語は 40
inc edi ; 対応する機械語は 47

を意味している。

pushは昨日のCPUにも出てきたが、スタックに値を詰む命令だった。

最下段にはjoやらjnoやらたくさん書かれているが、これは昨日のCPUのjzとjnz命令に対応する。 つまりフラグレジスタのeflagsの値を見て、ジャンプするかどうか決める命令だ。 昨日のCPUはゼロフラグ(zf)しか無かったが、x86のeflagsは32bitなのでジャンプの条件が大量にある。 これらの条件ジャンプ命令をまとめてjccと呼ぶのだが、詳細は明日に回そう。

8-b行:movがメイン

f:id:kaitou_ryaku:20171211195449p:plain:w400

一番上のcalcだが、これはさっき出てきたaddやadcなどの演算をまとめたものだ。 ModRMが絡んできてややっこしいので説明は控える。

次のnopは、メモリやレジスタを一切変化させず、プログラムカウンタだけを進める命令。 クロックが過ぎ去るのを何もせずに待つだけ。

右隣のxchgは、eaxレジスタと他のレジスタの値を交換する命令。 つまりx86において、nop命令はxchg eax, eaxと考えられているのだ。

最後はmov命令だが、mov eax, [imm32]の場合は

mov eax, [0x12345678] ; メモリの0x12345678番地の値を、eaxにコピーしたい
                      ; 対応する機械語は
                      ; a1 78 56 34 12

ここで、0x12345678は32bitの即値なのでimm32と表記されている。 またアセンブラには四角カッコでくくると、メモリを表すというルールがある。 つまりこの命令は、eaxレジスタにメモリから値を読み込むという命令だ。

右隣のmov eax, [imm32]の場合はさっきと真逆で、eaxレジスタの値をメモリにコピーする命令になっている。

8-b行:関数呼び出し

f:id:kaitou_ryaku:20171211195502p:plain:w400

最初はret命令だが、これは重要な命令である。 関数呼び出しに使用するのだが、昨日までのCPUには無かった命令なので説明しずらい。 詳細は、他の関数呼び出し命令(leaveとcall)とあわせて後日書くことにする。

その右にmov命令がいるけど、またしても[M+imm], imm32のMがModRMなので、詳細は明後日に回す。

最後の命令は、CPUを停止するhltだ。 これは昨日のCPUで実装したので説明不要だろう。

C言語の機械語を解析

駆け足だったが、x86の命令セットの概要(オペコードの種類)はおおむね掴めたと思う。 残りの時間で、今知った命令セットの知識を応用してみる。

普段使うPC上で、a.outやa.exeなどの実行ファイルは馴染み深いと思うが、それらの機械語がどんな感じ科調べてみる。

やる内容を先にまとめると

f:id:kaitou_ryaku:20171211195645p:plain:w400

赤矢印を辿るのだが、詳細は

  1. org.cを好きなように作る
  2. $ gcc -m32 -O0 -c org.c -o fat.o でコンパイル
  3. fat.oが得られる。このバイナリにはOSに関する余計な情報が入っている。
  4. $ objdump -d -M i386,intel fat.o > org.txtで逆アセンブル。余計な情報は削がれるものの、出力形式がイマイチ
  5. org.txtの出力形式を手で変更し、org.asmとして保存
  6. $ nasm org.asm -o org.oでorg.asmをアセンブル
  7. org.oのバイナリが得られる。これがorg.cに対応する機械語である

重要なのはorg.asmとorg.oの2つだ。 これらは元のorg.cをアセンブリ言語に翻訳したものと、それを機械語に翻訳したファイルだ。

1 : C言語ソースファイルorg.cの用意

こんな感じでいこう

org.cの中身

/* org.c */
int foo(int a, int b) {
  return a+b;
}

void bar(void) {
  int c;
  c = foo(2,3);
}
2,3 : コンパイル
$ gcc -m32 -O0 -c org.c -o fat.o

こうしてできたバイナリfat.oには、実はfat.c以外の情報が多数含まれている。 その根本的な原因はOSにある。 バイナリに書かれた機械語は直接CPUで実行されるのではなく、OSを介してCPUに渡される。 今回作ったfat.oには、gcc氏の粋な計らいにより、OSに色々と指示を与えるための余分な情報が付与されてしまっている。 我々の欲しいのはfat.cに対応する機械語だけなので、この余分な情報を削ぎ落とす必要がある。

ちなみにここまでC言語を使ったが、他の言語でも機械語形式のfat.oに対応するファイルが得られれば、以降の解析は全く同様に行うことができる。

4 : 機械語とニーモニックの対応表org.txtの取得

そこで以下のコマンドを叩く。 これはOSへの指示部分を無視し、org.cの処理に対応する部分だけを逆アセンブルするコマンドだ。

$ objdump -d -M i386,intel fat.o > org.txt

これでorg.cに対応するニーモニックのファイルorg.txtが得られた。その中身は

00000000 <_foo>:
   0:   55                      push   ebp
   1:   89 e5                   mov    ebp,esp
   3:   8b 55 08                mov    edx,DWORD PTR [ebp+0x8]
   6:   8b 45 0c                mov    eax,DWORD PTR [ebp+0xc]
   9:   01 d0                   add    eax,edx
   b:   5d                      pop    ebp
   c:   c3                      ret

0000000d <_bar>:
   d:   55                      push   ebp
以下略

今度は左側にアドレスと機械語、右側にニーモニックという形式で吐き出されてしまった。 人間にとっては見やすいが、このままではアセンブルすることができない。

5 : アセンブラ言語のソースコードorg.asmの作成

nasmの文法に対応させるためには

  • 左側の行番号と機械語列
  • PTR
  • <...>

これらを削除する必要がある。 nasm文法ではPTR が使えず、またニーモニック中の 0 <_foo> は、アドレス0がラベル_fooだと説明しているだけなので消しても問題ない。 これをorg.asmとして保存する。

org.asmの中身

;org.asm
push   ebp
mov    ebp,esp
mov    edx,DWORD [ebp+0x8]
mov    eax,DWORD [ebp+0xc]
add    eax,edx
pop    ebp
ret

push   ebp
; 以下略
6,7 : アセンブルとシンプルなバイナリファイル

org.asmをnasmでアセンブルする

$ nasm org.asm -o org.o

こうして得られたorg.oは、org.cをシンプルに機械語に変換したバイナリファイルである。 つまりOSへの指示等の余分な情報は含まれていない。

全て揃った

以上の手続きでorg.cに対応するニーモニックのorg.asmと機械語のorg.oが得られた。

org.oを逆アセンブルすると、org.asmと同じ結果が得られるはずだ。試してみよう。

$ objdump -d -b binary -m i386 -M i386l,intel -D org.o

手順4で叩いたobjdumpコマンドとオプションが変わっている。 今回はバイナリファイル全体を逆アセンブルするコマンドになっている。 前回はバイナリファイルの中でOSへの指示部分は無視して、org.cの処理に対応する部分だけを逆アセンブルするオプションだった。

表示結果を見ると、たしかにorg.asmと対応している。

00000000 <.data>:
 0: 55                   push  ebp
 1: 89 e5                mov   ebp,esp
 3: 8b 55 08             mov   edx,DWORD PTR [ebp+0x8]
 6: 8b 45 0c             mov   eax,DWORD PTR [ebp+0xc]
 9: 01 d0                add   eax,edx
 b: 5d                   pop   ebp
 c: c3                   ret
 d: 55                   push  ebp
 e: 89 e5                mov   ebp,esp
10: 83 ec 18             sub   esp,0x18
13: c7 44 24 04 03 00 00 mov   DWORD PTR [esp+0x4],0x3
1a: 00
1b: c7 04 24 02 00 00 00 mov   DWORD PTR [esp],0x2
22: e8 d9 ff ff ff       call  0x0
27: 89 45 fc             mov   DWORD PTR [ebp-0x4],eax
2a: 90                   nop
2b: c9                   leave
2c: c3                   ret
2d: 90                   nop
2e: 90                   nop
2f: 90                   nop

DWORDとPTRについては無視して構わない。

ニーモニック観察

表示結果を眺めてみる。

1行目を見ると、機械語は55で、ニーモニックはpush ebpとなっている。 命令セット表の55の場所を見ると、push ebpと書かれている。ちゃんと対応している。

2行目を見ると、機械語は89で、ニーモニックはmov ebp,espとなっている。 命令セットの表の89の場所を見ると、mov [M+imm], Rと書かれている。 この[M+imm], RはModRMで、未解説なので意味不明だと思うが、ebp,espに対応しそうな雰囲気だ。

オペコードの部分を縦に眺めてみると、push, mov, add, pop, ret, sub, call, nop, leave, retの10種類が存在している。 どれも命令セット表に記載されている。 あの表は空欄だらけだが、頻出の機械語命令はほぼ網羅されているのだ。

初日から今日まで丁寧に記事を読んでくださった方は、今感動してるんじゃないかな。 ニーモニックを回路で実装する方法は 昨日の記事 を読めばイメージできると思う。 pushやmovが回路素子に見えれば、かなりいい感じだ。 こうした回路素子で、あの抽象的なC言語の処理が実現するなんて！！という具合に感動して欲しい。

どうでもいい話

一口にx86と言っても、歴史が長く種類も多い。 最初のバージョンは1985年製の80386というCPUに搭載されていた命令セットで、i386と呼ばれている。 レジスタやアドレスバスは32bitだった。 その後i486、i586、i686などの拡張版が作られた。 これらをまとめてIA-32と呼ぶ。

その後レジスタやアドレスバスを64bitに拡張した命令セット(x64と呼ばれる)が作られた。 重要なのは後方互換性で、IA-32の機械語は最新のx64でも動作する。 なのでIA-32がわかれば、過去数十年間の全CPUに直接命令を下せるようになる。ような気がする。

  1. スマホのCPUはx86じゃないけど↩

  2. ディスクの読み込みに使うセグメントレジスタやら、起動時のモード切替に使うコントロールレジスタやら↩

  3. 割り込みのint命令を無視してるのは切腹モノだと思うが、許せ。↩