基于Spark平臺的惡意軟件最大頻繁子圖挖掘方法

周顯春，肖 衡，焦萍萍，鄒琴琴

（三亞學院信息與智能工程學院，三亞 572022）

0 引言

子圖挖掘（subgraph mining）是圖數據挖掘的一個重要分支，它已經成為數據挖掘中的一個研究熱點［1］，旨在從大規模復雜圖數據中發現有意義的子圖模式。隨著社交網絡、互聯網、生物信息學等領域的快速發展，大量的圖數據已經成為現代科學研究的重要來源，在社交網絡中可以發現社交網絡中的社區結構、關系網絡等信息，在推進系統中可以發現用戶間的相關關系、用戶興趣等信息，從而提高推薦系統的準確性，在網絡安全中可以發現網絡攻擊行為、惡意軟件等信息。但是，這些數據通常是非常復雜和龐大的，很難從中提取有意義的信息。

1 圖數據挖掘算法相關研究

目前，圖數據挖掘算法可以分為三類：針對圖集合、針對單個大圖［2］及分布式頻繁子圖挖掘。

在針對圖集合的頻繁子圖挖掘中，可以使用鄰接矩陣表示圖數據，并使用基于Apriori 算法的改進算法，如AGM［3］、FSG［4］和MARGIN［5］，或者基于DFS 的改進算法gSpan［6］來挖掘頻繁子圖。其中，gSpan 算法能夠支持對邊緣屬性和標簽等更豐富的信息進行挖掘，但在大規模數據集上性能可能受到影響。為此，UBW-gSpan 算法［7］通過引入最小支持度閾值和最大標簽數目閾值兩個參數進行優化。

在針對單個大圖的頻繁子圖挖掘中，SUBDUE［8］、SIGRAM［9］算法和GRAMI［10］算法是常用的算法。SUBDUE 算法利用圖匹配和圖壓縮進行子圖挖掘，能夠有效挖掘大規模圖中的頻繁子圖，并且不需要事先指定子圖的大小，但存在不能處理具有變化的圖數據集以及可能生成重復子圖的缺點。SIGRAM 算法采用基于圖同構的方法進行子圖匹配，將每個圖轉換為一個特征向量來捕獲其結構信息，并使用隨機映射來降低計算復雜度。GRAMI［10］算法將圖形模式挖掘問題轉化為限制約束問題，從而實現高效的挖掘，但需要注意參數選擇、候選生成復雜度和內存占用等缺點。

分布式頻繁子圖挖掘算法旨在Hadoop［11］/Spark［12-13］框架大規模分布式系統中挖掘頻繁子圖。該算法將數據集劃分為多個分區，在每個分區上運行子圖挖掘算法，最后將每個分區的結果進行合并，得到全局頻繁子圖。FSMBUS算法［14-15］通過分布式計算和分治策略來解決這些問題，減少了搜索空間，提高了挖掘效率，缺點是在處理大規模圖數據庫時會面臨計算復雜度高的問題。

為了解決傳統子圖挖掘算法時效性差的問題，提出了一種基于Spark 分布式平臺的惡意軟件最大頻繁子圖挖掘方法，利用改進FSMBUS算法的優點，能夠利用子結構之間的相似性進行最大頻繁子圖挖掘，從而減少搜索空間并提高挖掘效率。該算法應用于惡意軟件同源性判定，發現惡意軟件中存在的共同子結構，以改善惡意軟件檢測的效果。通過實驗驗證了改進算法的效果。

2 最大頻繁子圖提取方法

2.1 提取方法的架構

最大頻繁子圖提取方法分為兩個階段：數據預處理和數據挖掘，流程如圖1所示。數據預處理負責從惡意代碼中提取程序依賴圖；數據挖掘是核心部分，包括任務并行化、子圖挖掘、子圖剪枝、CSP 模型判斷［16］、是否存在超圖等階段。Master結點通過并行化把任務分解并分配給Worker 結點。子圖在每個Worker 節點上對子圖擴展進行迭代計算，通過頻繁度比較完成邊的擴展和剪枝。最后，在主結點通過判定頻繁子圖是否存在超圖得到最大頻繁子圖（圖2）。

圖1 最大頻繁子圖提取流程

圖2 基于Spark集群最大頻繁子圖提取架構

2.2 函數調用圖提取

利用調試工具運行被混淆的代碼，并在運行過程中監視其行為和狀態，通過分析運行時數據和代碼執行流程，提取函數調用圖。

2.3 基于Spark的改進FSMB算法

2.3.1 FSMBUS算法［13］

它是一種基于狀態機的流式數據挖掘算法，在候選頻繁子串的每個位置中，查找所有長度為k-1的子串是否出現在之前已經確定為頻繁子串的位置中，如果未出現的次數小于最小支持度閾值，則需要剪枝。剪枝可以有效地減少計算量，提高算法的效率。其偽代碼如下：

輸入:L：一個列表，包含所有長度為k-1 的頻繁子串；S：一個字符串列表，表示序列集合；P：一個候選頻繁子串，用于判斷是否需要剪枝；threshold：頻繁子圖的最小支持度閾值。

輸出:prune：一個布爾值，表示是否需要對該候選頻繁子串進行剪枝。

（1）初始化一個計數器count為0

（2）對于每個字符串s∈S，執行以下步驟：

1）在s中使用后綴數組和后綴LCP 數組找到所有長度大于等于|P|的子串，記為Si；

2）在Si中使用位向量和比特位并行操作找到所有與P匹配的子串，記為Mi；

3）將Mi中所有與P相等的子串對應的位置記錄在一個集合中，記為Pi；

4）對于Pi中的每個位置p，執行以下步驟：

（a）將p轉化為Pi的編號，記為pid

（b）在L中查找長度為k-1 的子串是否出現在pid中，如果出現，則將count加1

（3）如果count小于threshold，則將prune設為True，否則設為False

（4）返回prune的值

2.3.2 創建給定子圖的所有不同超圖的偽代碼

輸入：一個子圖g（V′,E′），原圖G（V,E）

輸出：子圖g的所有不同超圖的列表

（1）初始化超圖列表H為包含V′的初始超圖

（2）對于原圖G中V′-|V′|+1個節點的子集S：

1）如果S中至少包含g的所有節點，則創建一個新的超圖G′

2）將S中的所有節點添加到G′的節點集合中

3）對于g的每條邊（e1,e2），如果S中同時包含e1和e2中的所有節點，則將它們添加到G′的超邊集合中

4）如果G′不是H中的任何超圖的子集，則將G′添加到H中

（3）返回超圖列表H

2.4 基于GraphFrames的大規模單圖上的子圖匹配算法

GraphFrames是一種基于DataFrame和GraphX的圖處理庫，提供了方便的API來實現圖分析任務。包括加載大規模單圖和查詢子圖、子圖查詢、子圖匹配、結果輸出。其偽代碼如下：

（1）讀取原始圖G和查詢圖Q

（2）對G和Q進行頂點和邊的特征提取

（3）在G中尋找與Q相同的頂點集合V

（4）對每個V中的頂點，尋找與Q相同的鄰居結構，生成候選子圖

（5）將候選子圖轉換為GraphFrames 格式，構建候選子圖集合CG

（6）使用GraphFrames 中的find（）對CG進行子圖同構匹配，得到匹配的子圖集合M

（7）對M進行篩選和排序，輸出最優的匹配子圖

3 實驗結果及分析

實驗使用虛擬集群，虛擬機PC 機31 臺,其中1 臺master主節點，30臺為slave從節點。每臺PC機的配置相同：操作系統為Centos7.9，CPU為Intel Core i7 3.8 GHz，16 GB 內存，使用Scala 2.12.17 開發，集群環境建立在Hadoop3.3.4、Spark3.3.1、jdk 1.8上。

3.1 數據集

http://malware.lu確實是一個公認的惡意代碼樣本庫，一共有4964137 個惡意軟件樣本，其中包含各種類型的惡意代碼家族，例如病毒、蠕蟲、木馬、后門、根包和間諜軟件等，大部分經過了加殼處理。每個實驗樣本，Mytob、Netsky、Allaple、Bagle、Mydoom、Agobot/Gaobot，均有3000個。

3.2 評價指標

采用最大頻繁子圖挖掘時間、惡意軟件檢測的準確率（PR）、誤報率（FPR）、漏報率（FNR）四個指標對模型的檢測效果進行評價。

3.3 實驗結果及分析

3.3.1 支持度對運行時間的影響

由圖3 可知，MapReduce 方法挖掘最大頻繁子圖的運行時間較多，與改進FSMBUS、傳統FSMBUS 算法相比，時間要多2～4 倍。在支持度的值為8.0 之后，三種分布式算法的運行時間基本穩定。改進FSMBUS 算法運行時間穩定在3.7 ms 左右,傳統FSMBUS 算法運行時間穩定在2.7 ms 左右，說明了兩種算法比較穩定。改進FSMBUS 算法比傳統FSMBUS 算法多了1 ms 左右，主要原因是傳統FSMBUS 算法是進行頻繁子圖挖掘，而改進FSMBUS 算法是應用于挖掘最大頻繁子圖，與傳統FSMBUS 算法多了一個超圖運算操作。

圖3 支持度與系統運行時間的關系

3.3.2 運行時間的分析

如表1所示，三種方法的最大頻繁子圖挖掘時間的對比，可以發現基于Hadoopk的方法頻繁子圖挖掘時間是基于Spark的方法的3～4倍；基于Spark 的改進FSMBUS 方法進行最大頻繁子圖挖掘時間要比Top-Down算法快20～60 ms，平均減少時間32 ms，說明了本文的方法對大圖挖掘最大頻繁子圖的效果較好。

表1 最大頻繁子圖挖掘時間

3.3.3 惡意軟件識別效果的分析

由表2 可知，改進FSMBUS 相較于傳統FSMBUS 方法，其平均準確率提高了1.3 個百分點、平均誤報率降低了3.6%個百分點；相對于MapReduce 方法，改進FSMBUS 的平均準確率提高了1.7 個百分點、平均誤報率降低了1.8 個百分點。并且改進FSMBUS 方法對大部分惡意軟件的檢測效果比較穩定，不僅說明最大頻繁子圖可以作為惡意軟件的檢測特征，而且對惡意軟件的檢測效果很好，平均準確率和平均誤報率分別為95.6%和4.4%。

表2 傳統FSMBUS、改進FSMBUS和MapReduce檢測效果/%

4 結語

為了解決傳統子圖挖掘算法時效性低的問題，本文提出了一種基于Spark 架構的惡意軟件最大頻繁子圖挖掘方法。該方法采用次優樹數據結構進行并行化處理，利用GRAMI 算法計算支持度，并采用次優樹連接和擴展邊的方式獲取最大頻繁子圖，從而提高挖掘效率。利用改進的FSMBUS 方法在Spark 分布式平臺上進行實現，用于挖掘惡意軟件中的最大頻繁子圖。實驗結果表明，該方法相對于Top-Down 算法平均挖掘時間減少了32 ms，與基于頻繁子圖的惡意軟件檢測相比，平均準確率提高了1.3 個百分點、平均誤報率降低了了3.6 個百分點。子圖相似匹配是最大頻繁子圖挖掘的關鍵，因此是下一步研究的重點和方向。