Copyright(c)2009 NTT corp. All Rights Reserved.

機械語命令列の類似性に基づく自動マルウェア分類システム
2009年10月28日
岩村 誠*1*2, 伊藤 光恭*1, 村岡 洋一*2
*1 NTT情報流通プラットフォーム研究所*2 早稲田大学© 2009 NTT Information Sharing Platform Laboratories

Tree of LifeDavid M. Hillis, et al.
Science, 2003, 300:1692-1697

2© 2009 NTT Information Sharing Platform Laboratories

発表の流れ• 研究の背景，動機• 自動マルウェア分類システムの全体像• プログラムコードに基づくマルウェアの分類• LCSと，ビットベクトル化と，縮約命令と，• 分類結果–CCC DATAset 2009
–我々のハニーポットで収集した最近のマルウェア–京都大学で収集されたマルウェア• まとめ3© 2009 NTT Information Sharing Platform Laboratories

研究の背景，動機• 近年，マルウェアの種類数が急増している–何が流行っているのか，何が廃れたのか，も見えにくい．
–アンチウィルスソフトの命名もあやふやに？？
• 命名することより，検知・駆除することが重要なんでしょうけど．

• マルウェアの全容を解明し（続け）たい！
–まずは，収集したマルウェアの傾向（流行り廃り）を掴む．
–できれば，【全てのマルウェアを静的解析済み】と同じ状態にしたい．

• マルウェアの分類技術が有効

4© 2009 NTT Information Sharing Platform Laboratories

マルウェアの分類技術• やり方は大雑把に二通り．
–挙動に基づく分類
通信ログとか，システムコールの呼び出し履歴とか，【長所】監視の仕組みさえ構築すれば，後はマルウェアを動かすだけ．
【短所】動作しない箇所の特徴は出てこない．（時限式だったり，コマンド待ちだったり）–プログラムコードに基づく分類【長所】潜在する機能も踏まえて分類可能【短所】アンパックや逆アセンブルが必要．ものによっては，コールツリーやIATを再構築したり．

5© 2009 NTT Information Sharing Platform Laboratories

マルウェア自動分類の戦略

マルウェア

オリジナルコードを含むメモリダンプ

動的生成コード抽出用
カーネルドライバ

逆アセンブル結果

HMMに基づく
確率的逆アセンブル手法

類似度行列

もごもご6A

B

CA---

B

0.9--

C

0.5

0.7

-

階層的クラスタリング

Tree ofMalware© 2009 NTT Information Sharing Platform Laboratories

従来研究：プログラムコードに基づくマルウェアの分類•

プログラムコードの何に着目するかによって色々
1. Nグラム，Nパーム
連続するN個の命令（正確にはオペコード）に着目し，各々何回出現したかをマルウェアの特徴ベクトルとして分類．速い．
2. コール・ツリー
コール･ツリーの類似度を算出する．木構造の類似度を算出するのは大変なので，葉となるWin32 API呼び出し部分の情報を使って，計算量を減らす．

7© 2009 NTT Information Sharing Platform Laboratories

従来研究：どの方法がいいの？

• 速い–速いに越したことはない．

• 適切に分類可能–Nグラムが似ている→ふーん．
–コール・ツリーが似ている→あぁ，そー．

適切って何だ？
分類の目的によって良し悪しは変わる．
- 全体の傾向を早く掴みたい．
- コンパイラによる差異を吸収したい．
8© 2009 NTT Information Sharing Platform Laboratories

目的に立ち返る• 「できれば，【全てのマルウェアを静的解析済み】と同じ状態にしたい．」–２つのマルウェアのコール・ツリーが似ている→片方だけ解析すればよいの？
• コール・ツリーは似ているけど，関数の中身は違う場合．
• 結局，両方のアセンブリを読まなきゃいけない・・・orz• 命令単位で類似度を求めたい！
–命令列がほぼ一緒→片方だけ解析すれば，両方解析したようなもの．

9© 2009 NTT Information Sharing Platform Laboratories

LCSについて• Longest Common Subsequence（最長一致部分列）の略• {A,B,C}と{A,D,C}のLCSは{A,C}–連続している必要は無く，間に挿入・削除が入ってよい．
–要するにdiffの逆．

10© 2009 NTT Information Sharing Platform Laboratories動的計画法を使ったLCSの求め方• {a,b,c,d}と{b,a,c,d}のLCSを求める場合

φbacd

φ00000a0

b0c0

d00
1111111111
12223（動的計画法）
小さな問題から大きな問題を解いていく方法．

11LCSの長さ

S  s1m , T  t1nのLCS長をL( s1m , t1n )とすると次式が成り立つ．
i  0 or j  0  0
L( s1i , t1j )  si  t j  L( s1i 1 , t1j 1 )  1
i 1jij 1si  t j  max L( s1 , t1 ), L( s1 , t1 )© 2009 NTT Information Sharing Platform Laboratories

時間はどれくらいかかる？

• 計算量，メモリ使用量–2つのマルウェアの命令数をそれぞれM,N（M<N）とすると，• 動的計画法を使えば，計算量はO(MN)• Hirschbergらの方法を使えば，メモリ使用量はO(M)• １マルウェアあたり多いと１０万命令くらい．
–素直にdiffをとろうとすると，１ペアで最大５分くらいかかる．
（Intel Core2Quad 2.6GHz ，1コア）．平均でも１分くらい．
–３０００検体の分類には8.5年！？

3000Ｃ2 x 1分≒

12© 2009 NTT Information Sharing Platform Laboratories

分類結果はＭＷＳ２０１７で！？

13© 2009 NTT Information Sharing Platform Laboratories

・・・

14

© 2009 NTT Information Sharing Platform Laboratories

世の中には賢い人がいるもので15© 2009 NTT Information Sharing Platform Laboratoriesビットベクトル化•

単純なDPベースのLCS算出アルゴリズムを演算ワード長倍高速化する方法．

bacda0
1
1
1b1
111L

c1
122d1
123bacda10
1
1b0
1
11c0
101V

d0
100bacda0
100b1000

c0010M

d0001bacda1011b0111c1
101d1
110M’

1111, if j  0V [ j]  (V [ j  1]  (V [ j  1] & M [ y j ])) | (V [ j  1] & M '[ y j ]), if 1  j  n
ここで出てくるキャリーがL[m,j]-L[m,j-1]になる．

16© 2009 NTT Information Sharing Platform Laboratories

縮約命令• 縮約命令– １機械語命令のオペランド以外の情報を32ビットで表現．
– オペコードは勿論，オペランドの型情報や命令プレフィックスの情報も含まれる．

• 効果– 縮約命令の種類数＜機械語命令の種類数
ビットベクトル化の際のメモリ使用量を減らせる．
– 分岐命令と分岐先の間で命令が挿入・削除されても，類似度への影響は挿入・削除分だけで済む．
– 絶対アドレスを意味するオペランドがあった場合，コードセグメントのリロケーションによりオペランドが変化するが，この影響も無くなる．
01 2

Prefix1174 5 6 7 8

Prefix2

Prefix315Prefix4

1623

Opcode Len.

Opcode2431

Mod R/MSIB© 2009 NTT Information Sharing Platform Laboratoriesビットベクトル化の効果• SSE2を使うと・・・– and, andnot, orが128ビットでいける．
– addは64ビット．ただしキャリーフラグがないため，実質63ビット．
– それでも（メモリアクセスを除けば）10クロック程度で126ビット（マス）の計算をこなせるようになった．
– 単純なCの実装と比較すると，100倍超の高速化！

• Core2Quad Dual（2.6GHz）フル回転，約４日で 3000Ｃ2 のペアのLCSを算出が可能．

1818© 2009 NTT Information Sharing Platform Laboratories

類似度の定義• マルウェアの逆アセンブル結果から縮約命令列を生成し，2つの縮約命令列A,BのLCSをLとしたとき，類似度Sを以下のように定義する．
–A,Bを集合，LをAとBの積集合とみなしたときのJaccard係数に相当する．
|L|S
| A|  | B | | L|A

19

LB© 2009 NTT Information Sharing Platform Laboratories

ＭＷＳ２０１７を待たずして，いよいよ分類結果です20© 2009 NTT Information Sharing Platform Laboratories

CCC DATAset 2009マルウェア検体の分類結果
似てない

似ている

Delphiつながり？
次項にて・・・
ほぼ
３９３Ｆ⊂８４Ｅ９な関係

21© 2009 NTT Information Sharing Platform Laboratories

ＣＤ９１より７１９０の方が機能が豊富に見えるが・・・
７１９０（IRCを使うボットっぽい）ＣＤ９１（ワームっぽい，autorun.inf関連も）

ＣＤ９１検体では，明らかにクリティカルセクション関連の処理が不要．
元となったマルウェアの残骸か．
汎用ボットから感染に特化したワームへ？

22© 2009 NTT Information Sharing Platform Laboratories

次，３０００検体です！

23© 2009 NTT Information Sharing Platform Laboratories

ある環境で収集したマルウェア

Downadup
RahackIRCBotVirut
SpybotBackdoor.Trojan
静的解析してみると，主なクラスタは・Downadup
・Rahack
・IRCBot
・その他
Virutが入り混じっているのは宿主で分類したため．
24© 2009 NTT Information Sharing Platform Laboratories

京都大学で収集されたマルウェア７０２種類の分類結果• 我々が開発しているハニーポットで収集．シェルコードによる１次検体のみ．
– 680種類（96.9%）がDownadup• うちAが1種類，BおよびB++が679種類– Rahack（Allaple）が15種類．
アンチウィルスソフトの検出名が少し揺れている？

25© 2009 NTT Information Sharing Platform Laboratoriesまとめと今後の課題• アンパック・逆アセンブル・類似度算出・クラスタリングの全過程を自動化するシステムを提案– 縮約命令の導入– SSE2を使ってLCS算出アルゴリズムをビットベクトル化• 約３０００検体のマルウェアを分類してみた– （類似度の閾値にもよるが）かなり少ないクラスタ数．
１０個くらい解析すれば，大勢は掴めそう．
– 差分もわりときちんと見える• レジスタのカラーリング変更まで見える• 約７００検体＠京都はもっとすごい– 類似度80%で考えるとクラスタ数はわずか７つ．

• 今後の課題は– アンパック・逆アセンブル精度の向上– コンパイラ（オプション）変更に伴う変化への対応方法を検討
26© 2009 NTT Information Sharing Platform Laboratories