4.最長パスに関する検討

4-1.最長パスを求める方法

APIの推移の中で最も長いAPIの呼び出しの並びは、そのプログラムにとっての成功ルートであると仮定できる。例えばグラフ4-1-1の場合にはApiA→ApiB、ApiB→ApiC、ApiC→ApiD、ApiD→ApiEはプログラムとして正常なルートであると推測できる。それに対してApiA→ApiE、ApiB→ApiE、ApiC→ApiEはエラーが発生している可能性が高い。

グラフ4-1-1
digraph "g" {
  "ApiA" -> "ApiB";
  "ApiB" -> "ApiC";
  "ApiC" -> "ApiD";
  "ApiA" -> "ApiE";
  "ApiB" -> "ApiE";
  "ApiC" -> "ApiE";
  "ApiD" -> "ApiE";
}

最長片道きっぷの経路を求める問題[14]を応用して最長パスを求める。最長片道きっぷとは異なり有向グラフである。また同一のノードを何度も経由できる。スタートは固定されている。ここでグラフ4-1-2を例にして、最長パスを求める方法を考える。このグラフの最長パスはa→c→e→g→i→g→jである。

グラフ4-1-2
digraph "g" {
  "a" -> "b";
  "a" -> "c";
  "b" -> "d";
  "c" -> "e";
  "c" -> "f";
  "d" -> "b";
  "e" -> "g";
  "e" -> "h";
  "f" -> "j";
  "g" -> "i";
  "g" -> "j";
  "h" -> "j";
  "i" -> "g";
}

各エッジをそれぞれEab:a→b、Eac:a→c、...、Eig:i→gとする。Eは経由するならば1、経由しないならば0となる。各ノードに対応する変数NをそれぞれNa=-Eab-Eac、Nb=Eab-Ebd、...、Nj=Efj+Egj+Ehjとする。ノードに入るエッジが有効ならばNに1を加え、ノードから出るエッジが有効ならばNから1を引く。このときスタートのNは-1になる。またゴールのNは1になる。それ以外のNは経由する回数に関係なく0になる。また、スタートを除くすべてのNの合計は1になる。

これらの法則を下にして整数計画法で最長パスを求めようとすると、GLPKのモデルファイルはリスト4-1-1のようになる。

リスト4-1-1
var ab binary;
var ac binary;
var bd binary;
var ce binary;
var cf binary;
var db binary;
var eg binary;
var eh binary;
var fj binary;
var gi binary;
var gj binary;
var hj binary;
var ig binary;
var b binary;
var c binary;
var d binary;
var e binary;
var f binary;
var g binary;
var h binary;
var i binary;
var j binary;

maximize profit: ab + ac + bd + ce + cf + db + eg + eh + fj + gi + gj + hj + ig;
s.t. nodea: - ab - ac = -1;
s.t. nodeb: ab + db - bd = b;
s.t. nodec: ac - ce - cf = c;
s.t. noded: bd - db = d;
s.t. nodee: ce - eg - eh = e;
s.t. nodef: cf - fj = f;
s.t. nodeg: eg + ig - gi - gj = g;
s.t. nodeh: eh - hj = h;
s.t. nodei: gi - ig = i;
s.t. nodej: fj + gj + hj = j;
s.t. node: b + c + d + e + f + g + h + i + j = 1;

これをGLPKで解を求めるとリスト4-1-2のようになる。

リスト4-1-2
Problem:    graph4-1-2
Rows:       12
Columns:    22 (22 integer, 22 binary)
Non-zeros:  57
Status:     INTEGER OPTIMAL
Objective:  profit = 8 (MAXimum) 8 (LP)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 profit                      8
     2 nodea                      -1            -1             =
     3 nodeb                       0            -0             =
     4 nodec                       0            -0             =
     5 noded                       0            -0             =
     6 nodee                       0            -0             =
     7 nodef                       0            -0             =
     8 nodeg                       0            -0             =
     9 nodeh                       0            -0             =
    10 nodei                       0            -0             =
    11 nodej                       0            -0             =
    12 node                        1             1             =

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 ab           *              0             0             1
     2 ac           *              1             0             1
     3 bd           *              1             0             1
     4 ce           *              1             0             1
     5 cf           *              0             0             1
     6 db           *              1             0             1
     7 eg           *              0             0             1
     8 eh           *              1             0             1
     9 fj           *              0             0             1
    10 gi           *              1             0             1
    11 gj           *              0             0             1
    12 hj           *              1             0             1
    13 ig           *              1             0             1
    14 b            *              0             0             1
    15 c            *              0             0             1
    16 d            *              0             0             1
    17 e            *              0             0             1
    18 f            *              0             0             1
    19 g            *              0             0             1
    20 h            *              0             0             1
    21 i            *              0             0             1
    22 j            *              1             0             1

Integer feasibility conditions:

INT.PE: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

INT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output

これをグラフ4-1-2に図示するとグラフ4-1-3のようになる。

グラフ4-1-3
digraph "g" {
  "a" -> "b";
  "a" -> "c" [color = red];
  "b" -> "d" [color = red];
  "c" -> "e" [color = red];
  "c" -> "f";
  "d" -> "b" [color = red];
  "e" -> "g";
  "e" -> "h" [color = red];
  "f" -> "j";
  "g" -> "i" [color = red];
  "g" -> "j";
  "h" -> "j" [color = red];
  "i" -> "g" [color = red];
}

最長片道きっぷの経路を求める問題と同様に孤立したループが生じている。最長片道きっぷと同様に式を追加することで孤立したループを排除していく。この場合にはbd + db - ab <= 1とgi + ig - eg - gj <= 1を追加する。

ノードaをスタートとするグラフ4-1-4のような事例を考える。この場合にはまずはじめに赤線で示した解が導かれる。

グラフ4-1-4
digraph "g" {
  "a" -> "b" [color = red];
  "a" -> "d";
  "b" -> "c" [color = red];
  "d" -> "e" [color = red];
  "d" -> "g" [color = red];
  "e" -> "d" [color = red];
  "e" -> "f" [color = red];
  "f" -> "e" [color = red];
  "f" -> "g" [color = red];
  "g" -> "d" [color = red];
  "g" -> "f" [color = red];
}

次に孤立したループを排除するために、de + dg + ed + ef + fe + fg + gd + gf - ad <= 7を追加する。しかし次のステップでは期待した結果は得られない。例えばグラフ4-1-5のような解が得られる。

グラフ4-1-5
digraph "g" {
  "a" -> "b" [color = red];
  "a" -> "d";
  "b" -> "c" [color = red];
  "d" -> "e" [color = red];
  "d" -> "g";
  "e" -> "d" [color = red];
  "e" -> "f" [color = red];
  "f" -> "e" [color = red];
  "f" -> "g" [color = red];
  "g" -> "d";
  "g" -> "f" [color = red];
}

さらに孤立したループを削除する式、例えばde + ed + ef + fe + fg + gf - ad <= 5を追加しても、次もノードdefgによって構成される異なる孤立したループが解として出力される。ノードdefgによって構成される孤立したループをすべて列挙するまでこれは続く。ノードが4つ程度ならばすべてを列挙することは可能だが、ノードとエッジの数が増えた場合にはすべてを列挙することは事実上不可能である。そこで次のように考える。

スタートから作られる最長ルート(この場合a→b→c)の距離(この場合は2)に比べて大きいか等しい距離を持つ孤立したループ(この場合d→e→f→g→d→g→f→e→d)が出現したとき、そのスタートから作られる最長ルートは求める解にはならない。なぜならばスタートからその孤立したループに至るルートの方がそのスタートから作られる最長ルートよりも長いことは明らかである。よってスタートから作られる最長ルートを排除する式(この場合ab + bc - ad <= 1)を追加することができる。

4-2.最長API推移の発見

API推移の最長パスを発見するためにmxroot.plを作った。これはapiflw.plの出力結果から最長パスを見つけ出し、parser.plの出力結果と互換性がある形式で最長パスを出力する。(ゆえに3-1-3.API抽出の比較と同様に比較を行うことが可能である。比較に関しては次節で扱う。)

さらにmxroot.plの出力結果とそれに対応するapiflw.plの出力結果をあわせてグラフ上に最長パスを図示するスクリプトmxrtmk.plを作成した。

W32/Bagleの亜種とW32/Korgoの亜種、W32/Mydoomの亜種、W32/Netskyの亜種、Text maidの各バージョン、ネットワーク関連のプログラムについてmxroot.plを用いてAPIリストを作った。またmxrtmk.plを用いてグラフを作った。

4-3.最長API推移の比較

3-1-3.API抽出の比較と同様に上記のAPIのリストを1つの配列とみなし、多重配列アライメントを行う。図4-3-1はW32/Bagleの各亜種、図4-3-2はW32/Korgoの各亜種、図4-3-3はW32/Mydoomの各亜種、図4-3-4はW32/Netskyの各亜種、図4-3-5はText maidの各バージョンの多重配列アライメントである。Text maidはコンピュータウイルスではないが各バージョンを亜種とみなし解析を行った。

図4-3-1 W32/Bagleの各亜種間の多重配列アライメント

図4-3-2 W32/Korgoの各亜種間の多重配列アライメント

図4-3-3 W32/Mydoomの各亜種間の多重配列アライメント

図4-3-4 W32/Netskyの各亜種間の多重配列アライメント

図4-3-5 Text maidの各バージョンの多重配列アライメント

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

2つの配列の距離は完全に一致するときには0となり、まったく一致しないときには10000になる。なお、完全に一致する場合には項目を1つにまとめるため出力結果で距離は0にならない。