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

（三亞學(xué)院信息與智能工程學(xué)院，三亞 572022）

0 引言

子圖挖掘（subgraph mining）是圖數(shù)據(jù)挖掘的一個(gè)重要分支，它已經(jīng)成為數(shù)據(jù)挖掘中的一個(gè)研究熱點(diǎn)［1］，旨在從大規(guī)模復(fù)雜圖數(shù)據(jù)中發(fā)現(xiàn)有意義的子圖模式。隨著社交網(wǎng)絡(luò)、互聯(lián)網(wǎng)、生物信息學(xué)等領(lǐng)域的快速發(fā)展，大量的圖數(shù)據(jù)已經(jīng)成為現(xiàn)代科學(xué)研究的重要來源，在社交網(wǎng)絡(luò)中可以發(fā)現(xiàn)社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)、關(guān)系網(wǎng)絡(luò)等信息，在推進(jìn)系統(tǒng)中可以發(fā)現(xiàn)用戶間的相關(guān)關(guān)系、用戶興趣等信息，從而提高推薦系統(tǒng)的準(zhǔn)確性，在網(wǎng)絡(luò)安全中可以發(fā)現(xiàn)網(wǎng)絡(luò)攻擊行為、惡意軟件等信息。但是，這些數(shù)據(jù)通常是非常復(fù)雜和龐大的，很難從中提取有意義的信息。

1 圖數(shù)據(jù)挖掘算法相關(guān)研究

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

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

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

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

為了解決傳統(tǒng)子圖挖掘算法時(shí)效性差的問題，提出了一種基于Spark 分布式平臺(tái)的惡意軟件最大頻繁子圖挖掘方法，利用改進(jìn)FSMBUS算法的優(yōu)點(diǎn)，能夠利用子結(jié)構(gòu)之間的相似性進(jìn)行最大頻繁子圖挖掘，從而減少搜索空間并提高挖掘效率。該算法應(yīng)用于惡意軟件同源性判定，發(fā)現(xiàn)惡意軟件中存在的共同子結(jié)構(gòu)，以改善惡意軟件檢測的效果。通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的效果。

2 最大頻繁子圖提取方法

2.1 提取方法的架構(gòu)

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

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

圖2 基于Spark集群最大頻繁子圖提取架構(gòu)

2.2 函數(shù)調(diào)用圖提取

利用調(diào)試工具運(yùn)行被混淆的代碼，并在運(yùn)行過程中監(jiān)視其行為和狀態(tài)，通過分析運(yùn)行時(shí)數(shù)據(jù)和代碼執(zhí)行流程，提取函數(shù)調(diào)用圖。

2.3 基于Spark的改進(jìn)FSMB算法

2.3.1 FSMBUS算法［13］

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

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

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

（1）初始化一個(gè)計(jì)數(shù)器count為0

（2）對于每個(gè)字符串s∈S，執(zhí)行以下步驟：

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

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

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

4）對于Pi中的每個(gè)位置p，執(zhí)行以下步驟：

（a）將p轉(zhuǎn)化為Pi的編號，記為pid

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

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

（4）返回prune的值

2.3.2 創(chuàng)建給定子圖的所有不同超圖的偽代碼

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

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

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

（2）對于原圖G中V′-|V′|+1個(gè)節(jié)點(diǎn)的子集S：

1）如果S中至少包含g的所有節(jié)點(diǎn)，則創(chuàng)建一個(gè)新的超圖G′

2）將S中的所有節(jié)點(diǎn)添加到G′的節(jié)點(diǎn)集合中

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

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

（3）返回超圖列表H

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

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

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

（2）對G和Q進(jìn)行頂點(diǎn)和邊的特征提取

（3）在G中尋找與Q相同的頂點(diǎn)集合V

（4）對每個(gè)V中的頂點(diǎn)，尋找與Q相同的鄰居結(jié)構(gòu)，生成候選子圖

（5）將候選子圖轉(zhuǎn)換為GraphFrames 格式，構(gòu)建候選子圖集合CG

（6）使用GraphFrames 中的find（）對CG進(jìn)行子圖同構(gòu)匹配，得到匹配的子圖集合M

（7）對M進(jìn)行篩選和排序，輸出最優(yōu)的匹配子圖

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)使用虛擬集群，虛擬機(jī)PC 機(jī)31 臺(tái),其中1 臺(tái)master主節(jié)點(diǎn)，30臺(tái)為slave從節(jié)點(diǎn)。每臺(tái)PC機(jī)的配置相同：操作系統(tǒng)為Centos7.9，CPU為Intel Core i7 3.8 GHz，16 GB 內(nèi)存，使用Scala 2.12.17 開發(fā)，集群環(huán)境建立在Hadoop3.3.4、Spark3.3.1、jdk 1.8上。

3.1 數(shù)據(jù)集

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

3.2 評價(jià)指標(biāo)

采用最大頻繁子圖挖掘時(shí)間、惡意軟件檢測的準(zhǔn)確率（PR）、誤報(bào)率（FPR）、漏報(bào)率（FNR）四個(gè)指標(biāo)對模型的檢測效果進(jìn)行評價(jià)。

3.3 實(shí)驗(yàn)結(jié)果及分析

3.3.1 支持度對運(yùn)行時(shí)間的影響

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

圖3 支持度與系統(tǒng)運(yùn)行時(shí)間的關(guān)系

3.3.2 運(yùn)行時(shí)間的分析

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

表1 最大頻繁子圖挖掘時(shí)間

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

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

表2 傳統(tǒng)FSMBUS、改進(jìn)FSMBUS和MapReduce檢測效果/%

4 結(jié)語

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