3-2.制御フロー解析

3-2-1.制御フロー解析の可視化

関数の呼び出し関係に基づいてAPIを抽出するのではなく、コンパイラが最適化のために行う制御フロー解析を応用してプログラムを解析して特徴を抽出する。この方法ならば関数の内部の分岐やループなども対象となるので、リスト3-1-4-1とリスト3-1-4-2のプログラムのように関数内部でのコードの順番に依存しない結果が得られる。しかしどちらを先に行ってもプログラムの機能が同一であるという場合に、その順番を入れ換えた場合には同一の結果は得られない。

リスト3-1-2-1のプログラムを制御フロー解析した場合にはグラフ3-2-1-1のようになる。

グラフ3-2-1-1
digraph "g" {
  "block1" -> "block2";
  "block1" -> "block3";
  "block2" -> "block1";
  "block3" -> "block4";
  "block3" -> "block5";
  "block4" -> "block5";
  "block5" -> "block5";
  "block2" [label = "block2\nApiB"];
  "block4" [label = "block4\nApiA"];
  "block5" [label = "block5\nApiC"];
}

制御フロー解析を行い可視化するスクリプトctlflw.plを作成した。ctlflw.plはIDA Proの出力結果からGraphvizのデータを作る。グラフは関数ごとにサブグラフを作るようにした。W32/Bagleの亜種とW32/Korgoの亜種、W32/Mydoomの亜種、W32/Netskyの亜種、Text maidの各バージョン、ネットワーク関連のプログラムについてctlflw.plを用いてグラフを作った。(しかしこれらのグラフはあまりにも大きいため、多くは後述の400行の制限に該当する。)

3-2-2.制御フロー解析の共通構造の発見

2つのctlflw.plの出力である有向グラフを比較して共通構造を発見するC言語のプログラムgm.cを作成した。gm.cはすべてのノードの組み合わせを列挙して最も共通するエッジが多い組み合わせを求める。単純に全パターンを計算すると効率が悪いので次のような工夫をした。

1. 予め探索の深度毎に残りのエッジの数を計算しておく
2. 探索する毎にエッジが一致/不一致することが確定した部分を計算し、残りのエッジがすべて一致したと仮定して最後まで探索したときの一致数を求める
3. 2の点数がすでにわかっている最大の一致数以下ならば探索を打ち切る
4. エッジを多く持つノードから順番に探索する

gm.cでグラフ3-2-2-1とグラフ3-2-2-2の共通構造を探した場合、出力結果はグラフ3-2-2-3になる。

グラフ3-2-2-1
digraph "g" {
  "0" -> "1";
  "1" -> "2";
  "1" -> "3";
  "2" -> "4";
  "2" -> "5";
}

グラフ3-2-2-2
digraph "g" {
  "a" -> "b";
  "b" -> "c";
  "b" -> "d";
  "d" -> "e";
  "e" -> "d";
  "e" -> "g";
  "f" -> "d";
  "f" -> "g";
}

グラフ3-2-2-3
digraph "g" {
  "0-0000" -> "0-0001";
  "0-0000" -> "0-0003";
  "0-0000" [label = "1\nb"];
  "0-0001" -> "0-0004";
  "0-0001" -> "0-0005" [color = red];
  "0-0001" [label = "2\nd"];
  "0-0002" -> "0-0000";
  "0-0002" [label = "0\na"];
  "0-0003" [label = "3\nc"];
  "0-0004" [label = "4\ne"];
  "0-0005" [label = "5", color = red, fontcolor = red];
  "0-0004" -> "0-0001" [color = blue];
  "0-0004" -> "1-0003" [color = blue];
  "1-0003" [label = "g", color = blue, fontcolor = blue];
  "1-0004" -> "0-0001" [color = blue];
  "1-0004" -> "1-0003" [color = blue];
  "1-0004" [label = "f", color = blue, fontcolor = blue];
}

グラフ3-2-2-1やグラフ3-2-2-2のようにノードの数が数個程度ならば計算には時間がかからない。しかし計算量はおおよそノードの数の階乗に比例して計算量が増加する。制御フロー解析の結果はノードの数が100を越えるので現在のPCでは計算困難である。

3-2-3.グラフ同型判定問題

制御フロー解析の共通構造の発見とは、2つのグラフG1とG2が与えられたとき、G1とG2の部分グラフのうち同型となる最大のグラフを求める問題である。この問題は部分グラフ同型判定問題[12]を含んでいる。部分グラフ同型判定問題とは2つのグラフG1とG2与えられたとき、G1がG2の部分グラフと同型か否かを判定する問題である。部分グラフ同型判定問題はNP完全なので計算困難である。計算困難とされる部分グラフ同型判定問題を含んでいるこの問題もまた計算困難である。

一方、グラフ同型判定問題はNP完全にはならないと考えられる[13]。グラフ同型判定問題は部分グラフ同型判定問題に比べて計算量は少なくなると考えられる。ゆえにグラフ同型判定の利用を検討する。

3-2-4.同一構造の関数の発見

ctlflw.plによる制御フロー解析の結果は関数ごとにサブグラフを出力する。ここに注目してサブグラフ同士の比較を行い、一致するサブグラフに含まれるノードの数からコンピュータウイルスの比較を行うC言語のプログラムgeq.cを作成した。geq.cは任意の数の逆アセンブルリストを比較してHTML形式のテーブルを出力する。geq.cはサブグラフにならない関数(即ち、1つのノードだけで構成される関数)は比較の対象としない。

表3-2-4-1はW32/Bagleの各亜種、表3-2-4-2はW32/Korgoの各亜種、表3-2-4-3はW32/Mydoomの各亜種、表3-2-4-4はW32/Netskyの各亜種、表3-2-4-5はText maidの各バージョンについてgeq.cを用いて比較を行い距離を求めた表である。Text maidはコンピュータウイルスではないが各バージョンを亜種とみなし比較を行った。また表3-2-4-6は誤認が生じないか確かめるために各亜種とネットワーク関連のプログラムの比較を行った表である。

サブグラフにならない関数も含めて、またサブグラフをまたぐエッジも含めて全体が同型となる場合には項目を1つにまとめる。3-1-3.API抽出の比較とは異なり出力結果で距離が0になることもありうる。