LLVM bitcodeのCFGを生成する

LLVM bitcodeとは

LLVM内ではLLVM IRという中間言語表現が用いられる。 ソースコードをLLVM IRコードに変換したあと、そのLLVM IRコードをターゲットのアーキテクチャのバイナリに変換...という流れでコンパイルは行われる。 LLVM bitcode は LLVMの独自バイナリフォーマットで、LLVM IRと相互変換可能である。 LLVM IRは.llファイル、LLVM bitcodeは.bcファイルでそれぞれ表される。

$ llvm-as sample.ll # LLVM IRをLLVM bitcodeに変換
$ llvm-dis sample.bc # LLVM bitcodeをLLVM IRに変換

LLVM bitcodeはclangに-emit-llvmオプションを指定することで生成できる。

$ clang -emit-llvm -c -g test.c

CFGを生成する

optコマンドにより、dot-cfg passを実行することでLLVM bitcodeからdotファイルを生成する。 passはLLVM内で機能を構成する1単位であり、 最適化機構などはpassとして実装され、各passはoptコマンドのオプションで指定することで実行できる。 dotファイルにはグラフ構造が書き込まれており、Graphviz内のdotコマンドを使うことで画像として出力することができる。 macだとGraphvizのインストールはHomebrewでできる。

ソースコード

ここではたまたま手元にあったDynamic Opaque Predicateを施されたCのソースを使った。 Dynamic Opaque Predicateは難読化の一種で、どの分岐を通っても最終的に同じ処理を行うよう分岐を施す難読化である。 Opaque Predicateについては、 LOOPや Generalized Dynamic Opaque Predicatesがくわしい。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  if(argc != 2)
    exit(1);

  int x = atoi(argv[1]); 
  int y = 0;

  if (x % 2 == 0) {
    y = x + 2;
  } else {
    y = x + 100;
  }

  if (y % 2 == 0) {
    y = y + 100;
  } else {
    y = y + 2;
  }

  printf("y = %d\n", y);

  return 0;
}

コマンド

$ clang -emit-llvm -m32 -c -g test.c 
$ opt test.bc  -dot-cfg
$ dot -Tpng cfg.main.dot > test.png

生成されたCFG