Binary Ninjaで不要な変数代入を除去する

Binary Ninjaのdead store eliminationを使うと不要な変数代入をデコンパイル結果から除去することができます。

問題設定

以下のようなプログラムを考えます。

#include <stdio.h>

int global_var;

int main() {
  {
    int v1 = global_var;
    int v2 = v1 % 9;
    int v3 = v1 >> v2;
    int v4 = v1 & v2;
    int v5 = v3 % v4;
  }
  puts("Hello world");
  {
    int v1 = global_var;
    int v2 = v1 / v1;
    int v3 = v2 / v1;
    int v4 = v3 % 2;
    int v5 = v2 >> v1;
  }
  return 0;
}

このプログラムはputs("Hello world");が本質部分で、その前後では計算結果がどこからも参照されない不要な処理をしています。

このプログラムを以下のコマンドでコンパイルし、prog1という名前のバイナリを得ます。

$ gcc -o prog1 prog1.c

このバイナリをBinary Ninjaでデコンパイルすると以下のようになります。

デコンパイル結果に不要な処理が残ってしまっています。参照されない変数は灰色で描画されるためある程度読み飛ばすことが可能ですが、例えばこのような不要な処理が複数ページに渡って行われるようなコードは単純に読みにくいです。また、コードサイズの増加に伴ってデコンパイルが行えなくなったり、ツールの動作が重くなったりといった現象が発生することがあります。

dead store elimination機能の使用例

このような状況でBinary Ninjaのdead store elimination機能が役に立つことがあります。

変数の代入箇所を右クリックすると、以下の画像のようにDead Store Eliminationという項目があります。

ここでAllowを選択すると、var_3cへの代入がデコンパイル結果から除去されました。

他の変数に対しても同様の操作を行うと、最終的にデコンパイル結果は以下のようになります。

不要な処理が全て除去されて本質部分のみが残りました。なぜかglobal_varへの参照は残ってしまうのですが、この挙動はよくわかっていません。

なお、すべての変数に対して操作を手で行うのは大変なので、以下のスクリプトで自動化することもできます。

def set_dse(func) -> int:
    vars = [
        var
        for var in func.vars
        if var.dead_store_elimination != DeadStoreElimination.AllowDeadStoreElimination
    ]
    for var in vars:
        var.dead_store_elimination = DeadStoreElimination.AllowDeadStoreElimination

    print(f"  Marked {len(vars)} vars for dead store elimination")
    return len(vars)


bv.begin_undo_actions()
while True:
    if set_dse(current_function) == 0:
        break
    bv.update_analysis_and_wait()
bv.commit_undo_actions()

注意点

変数への代入が真に不要なものであることを確認した上で、慎重にdead store elimination機能を適用すべきです。

例えば以下のようなプログラムを考えます。

int second(int *v) {
  return v[1];
}

int main() {
  int v[2];
  v[0] = 1;
  v[1] = 2;

  return second(v);
}

このプログラムを以下のコマンドでコンパイルします。

$ gcc -o prog2 prog2.c

得られたバイナリをBinary Ninjaでデコンパイルすると以下のようになります。

さらにdead store eliminationを全ての変数に適用すると以下のようになります。

元々のプログラムではv[1]に対応する変数var_1cの値をmain関数の戻り値としていますが、dead store eliminationによって変数var_1cへの代入が除去されてしまいました。

結果としてmain関数が何を返すのかが読み取れなくなり、正しくバイナリを解析することが難しくなります。この理由から、dead store eliminationを適用するのは、真に不要であるとわかった変数代入のみとしたほうが良いでしょう。