x86ミニデコンパイラを作ってみた。

学習目的にx86 ELFバイナリのミニデコンパイラを作成しました。

開発中ですが一段落した(飽きた)のでブログを書きます。

特徴

  • OCamlで書いた。(特に理由はありません)
  • objdumpの逆アセンブル結果を利用した。
  • if, for文の復元ができる。
  • その場しのぎの実装なので失敗することがたまにある。
  • 最適化がかかると(たぶん)失敗する。

成果

サンプルケースとして用意しておいたデコンパイル結果を載せます。

その1

関数呼び出し
元のソースコード

int add(int a, int b) {
    return a + b;
}
int main() {
    int a = 0;
    int b = 2;
    int c = add(a, b);
    add(b, c);
    return 0;
}

デコンパイル

add(arg_0x8, arg_0xc) {
  __x86.get_pc_thunk.ax();
  return (arg_0xc + arg_0x8);
}
main() {
  __x86.get_pc_thunk.ax();
  local_0xc = 0x0;
  local_0x8 = 0x2;
  local_0x4 = add(local_0xc, local_0x8);
  add(local_0x8, local_0x4);
  return 0x0;
}

その2

if文
元のソースコード

int main() {
    int a = 1;
    int b = 2;
    if(a == 1 && b == 2) {
        int c = 0;
        a = a + b + c;
    }
    return 0;
}

デコンパイル

main() {
  __x86.get_pc_thunk.ax();
  local_0xc = 0x1;
  local_0x8 = 0x2;
  if ((local_0xc == 0x1)) {
    if ((local_0x8 == 0x2)) {
      local_0x4 = 0x0;
      local_0xc = (local_0x4 + (local_0xc + local_0x8));
    }
  }
  return 0x0;
}

その3

for文
元のソースコード

int main() {
    int sum = 0;
    for(int i=0;i<10;i++) {
        sum += i;
    }
    return sum;
}

デコンパイル

main() {
  __x86.get_pc_thunk.ax();
  local_0x8 = 0x0;
  for (local_0x4 = 0x0; (local_0x4 <= 0x9); local_0x4 = (local_0x4 + 0x1)) {
    local_0x8 = (local_0x8 + local_0x4);
  }
  return local_0x8;
}

手順

今回実装したデコンパイル方法についてです。

以下のアセンブリ

mov edx,DWORD PTR [ebp-0x10]
mov eax,DWORD PTR [ebp-0xc]
add eax,edx
mov DWORD PTR [ebp-0x8],eax

v1 = v2 + v3;

に変換する処理について考えます。

まず ローカル変数とおぼしきDOWRD PTR [ebp-n]にv1, v2, v3と名前を割り当てます。

mov edx, v3
mov eax, v2
add eax,edx
mov v1,eax

つぎにmov, add命令を擬似コードへ変換します。

edx = v3
eax = v2
eax = eax + edx
v1 = eax

次にv1の代入までに使用した式にレジスタが含まれていれば代入元がレジスタでなくなるまで式を遡っていき、コードに復元すると、

v1 = v2 + v3;

となります。

実際の実装では下記のように木を作って代入関係を表現しています。 f:id:kotarou777775:20170919191008p:plain

こういったことを関数の逆アセンブル結果に適用してやればよいわけです。

感想

アセンブリ命令を1行づつ見て各命令ごとに処理を書かなければいけなく、実装量が多いのでまだ対応していない命令がたくさんありますが、今回はデコンパイラの仕組みの学習が目的だったので(リポジトリ内の)サンプルケースで期待どおりの動作をすることしか確認していません。
OCamlとかいう書き慣れてない言語でやったおかげかかなりしんどかったです。

githubリポジトリです。

github.com

ちゃんとしたデコンパイルを作っている人はすごいですね。

参考

dccというデコンパイラに関する論文
https://yurichev.com/mirrors/DCC_decompilation_thesis.pdf

デコンパイル方法について書いてある。
http://www.debugmode.com/dcompile/