Large-Scale Malware Indexing Using Function-Call Graphs 3/15 黃瀚嶙 今天我要報告的xxx

REFERENCES Large-Scale Malware Indexing Using Function-Call Graphs Xin Hu ,Kang G. Shin, Tzi-cker Chiueh, CCS’09 這篇論文選自ccs2009

Outline Introduction Function-Call Graph Extraction Graph-Similarity Metric Multi-Resolution Indexing Evaluation Conclusion 這是我今天的outline

Introduction SMIT:Symantec Malware Indexing Tree 作者在這篇paper裡面介紹了一種xxx 以往病毒分析主要是以signature 或者病毒行為分析為主 不過面對大量的新型病毒signature base的方式難以辨別變種 而病毒行為分析則消耗過多的人力 因為作者在這邊提出了一個方法在smit 這個架構我在後面講

Function-Call Graph Extraction Definition (Function-Call Graph): g = (Vg,Eg, Ig,Lg), -Vg:function -Eg:directed edge -Ig:symbolic function name, mnemonic sequence and CRC value -Lg:labeling function from Vg->Ig 作者在這邊用一個叫function call graph的方式來對病毒做特徵化 這個方法跟base差別的地方在於他不是比較bit而是 把malware的code轉換成一張圖 下面有個g的一張directed graph用來表示作者設計的圖 他分別包函四個元素分別是function directed edge labeling function symbolic function

Function-Call Graph Extraction 這邊是一個簡單的範例 用來講解在labeling裡面element他的組成 作者認為變種的病毒會有相同的sequence所以他會透過一個轉換 而crc是用來做快速比較查循所使用

Graph-Similarity Metric -Graph Edit Distance Vertex-edit operations -σR : relabel a vertex -σIV :insert an isolated vertex -σRV :remove an isolated vertex Edge-edit operations -σIE :insert an edge -σRE : remove an edge 因為作者是使用graph的方式用來表示一個malware 所以作者在這邊提出一個用來計算兩個graph之間的距離的方法 分成對點和對邊的operation

Graph-Similarity Metric -Graph Edit Distance edit path Pg,h:if Pg,h = (σ1, σ2, . . . , σn) then h =σn(σn-1(. . . σ1(g) . . . )) Cost :C(P)=sum of path cost edit distance:ed(g,h) =min c(Pg,h). 而兩個graph之間的距離就用下面這個function表示 假設g經過一連串的操做會跟h相等 那他們之間的一連串的操作就是他們之間的距離 這五種不同的operation在這邊計算沒有附加權重一律相等

Multi-Resolution Indexing 因為圖邊間彼此的比較cost很大而且病毒數量眾多不可能一一比對 所以作者提出一個indexing的方式分上下兩層 分別是上層的b+ tree以及下層的vpt

Multi-Resolution Indexing -B+-tree Index feature vector v = (Ni,Nf,Nx,Nm) Ni :total number of instructions Nf :total number of functions Nx :total number of control transfer instructions Nm :median number of instructions per function 上層的b+ tree是以上面四種feature當成key來查找 作者在這邊有一個假設說類似的malware 彼此之間instrnction數目不會有太大的差距 這四種feature是以ni權重最大然後慢慢遞減

Multi-Resolution Indexing -B+-tree Index 那這是統計過後得到的結果可以看的出來最大最小值相差極大 是一個很適合做indexing的feature 不過最小值為1 or 0是因為做脫殼的動作失敗 或是malware反分析的一些機制有發動

Multi-Resolution Indexing -Optimistic Vantage Point Tree query graph g, KNN search of a VPT with a root pivot p Prune:high[i] < d(p, q) − δnow or low[i] > d(p, q) + δnow 那講到下層 Ovpt是下層的結構 當graph search達到下層則會使用knn來做分類查找的動作 不過這樣cost還是過大 所以vpt他會切割成許多均等的片段 然後使用一個threhold now來去除不必要的片段

Evaluation 1 最後是效能上的分析 這邊的n的前面n的疊代的次數 因為有時候會發生片段過小沒辦法找到k個值所以就會增加threshold 來改善這種情礦 K則是knn設定的值 這邊可以看到他的成功機率可以到達到九成還蠻高的所以作者認為可以用此方式 做以後病毒分類的方法

Evaluation 1 雖然準確率很高 但是所花的時間也是一個重要的考量 基本上做搜尋的動作都在100S以下 雖然一定不可能比signature的方式快 不過可以把時間限制在100秒以下應該已經足夠 用來分類病毒

Conclusion Contributions -efficient graph-distance computation algorithm -multi-resolution indexing -performance 最後這篇paper的貢獻 他想出了一個新的方式做病毒分類 還有一個indexing的架構 在最後他有九成的機率分類 以及所需時間100S以下 那我今天就報告到這邊有什麼問題嗎