[發明專利]基于半監督密度聚類的惡意代碼家族同源性分析方法

有效

• 申請號: 201810744345.6
• 申請日: 2018-07-09
• 公開（公告）號: CN109190653B
• 公開（公告）日: 2020-06-05
• 發明（設計）人: 方勇;劉亮;黃誠;榮俸萍;張與弛
• 申請（專利權）人: 四川大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F21/56
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于半監督聚類的惡意代碼同源性分析方法，其特征在于，所述方法包括如下步驟：

A、基于API調用序列數據的典型序列模式的挖掘，是結合廣義序貫模式挖掘算法(GSP)和面向對象關聯挖掘技術(OOA)的一個改進，輸入：最小支持度ms％，最小置信度mc％，關鍵API集合K＝U_f∈FK_f，已知惡意家族集合F和已知惡意樣本數據庫DB1，輸出：典型API調用序列模式集合TP，TP中存儲挖掘出的每個已知惡意代碼家族的關鍵API調用模式；輸入中，ms％和mc％分別表示為用戶定義的API調用序列模式關于惡意家族的最小支持度和最小置信度，K表示惡意家族的關鍵API集合，K_f表示惡意家族f的關鍵API；輸入輸出之間具體的實現過程步驟：C_k用來存儲長度為len的候選API調用序列模式，L_k用來存儲第i輪迭代過程中選出的長度為len的用于生成C_k+1的API調用序列模式，TPE用來存儲挖掘出的指定惡意家族的典型API調用序列模式；掃描已知樣本數據庫DB1，對C_k中的每個候選序列模式關于指定惡意家族的支持度s％和置信度c％進行計算；通過與用戶定義的最小支持度ms％、最小置信度mc％和長度為len-1的子序列模式的最大置信度c’％進行比較，選出支持度大于ms％，置信度大于c’％的序列模式添加到L_k中用于生成候選模式集C_k+1，選出支持度大于ms％，置信度大于c’％和mc％的典型序列模式添加到TPE中；使用廣義序貫模式挖掘算法GSP中的候選序列模式生成算法利用集合L_k生成候選序列模式集C_k+1；

B、基于半監督密度聚類算法的惡意代碼家族聚類，此半監督密度聚類算法命名為S-DBSCAN，輸入：數據集D＝{x₁，x₂，...，x_n}，已知惡意家族的已知樣例相似度值eps，eps鄰域至少包含的樣本個數MinPts，輸出：數據集D上的聚類結果；S-DBSCAN的實現過程：首先指定子空間最少包含的數據點個數，KD-Tree通過分割垂直于坐標軸的平面來將數據空間不斷劃分為子空間，直到每個子空間包含最小數量的數據點個數；KD-Tree的劃分結果為一棵不平衡二叉樹，其中小葉節點代表局部密集的子區域，而大葉節點代表低密度的子區域；然后對每個葉節點中的數據樣例點進行處理，首先默認標記所有數據樣例點都為核心對象，系統將eps鄰域至少包含的樣本個數Minpts也設置為KD-Tree劃分過程中子空間最少包含的數據點個數，因為這兩個值的目標都是為了定義并選擇密集子區域；如果某數據樣例點x的eps鄰域包含的樣例點個數少于MinPts，則標記點x為噪聲點，如果點x的eps鄰域至少包含MinPts個同屬于該點所屬葉節點中的樣例點且這些樣例點連同點x不來自一個以上的已知家族，則把這些樣例點和點x合并成一個本地聚類簇，使用LCLUSTER來標記本地聚類簇，如果這些樣例點連同點x來自不同已知家族，則這些樣例點和點x各自形成一個本地聚類簇，如果點x的eps鄰域包含的同屬該點所屬葉節點的樣例點個數少于MinPts，則點x單獨形成一個本地聚類簇；這一步得到的結果是一組本地聚類簇和一些異常點，某些聚類簇中只包含單個數據點；遍歷每個已知惡意家族中的已知樣例，如果該樣例還未合并到已知的家族聚類簇中，則把其所在的本地聚類簇合并到該已知惡意家族的家族聚類簇中；這些合并操作可以跨越KD-Tree葉節點的邊界，也就是說，KD-Tree的不同葉節點所代表的不同子空間內的本地聚類簇可進行合并；算法使用家族聚類簇FCLUSTER來標識這一聚類過程中形成的已知惡意家族的聚類簇，這一步得到的聚類結果包含聚類不完全的標識為FCLUSTER的已知家族聚類簇和標識為LCLUSTER的本地聚類簇；對剩余的本地聚類簇進行迭代處理，每次迭代過程中對每個本地聚類簇查找其最近的聚類簇，并把本地聚類簇合并到最近的聚類簇中，新的聚類簇使用合并前的最近密度可達聚類簇的標識，直到剩余本地聚類簇個數不再變化時停止迭代過程；這一步得到聚類結果包含標識為FCLUSTER的已知惡意家族聚類簇和標識為LCLUSTER的新的未知惡意家族聚類簇；

C、基于不對稱相似度計算的家族演化圖構建算法，輸入：S-DBSCAN算法得到的聚類簇存在基于定制修改的直接演化關系的最小相似度值MinSim，輸出：每個聚類簇的家族演化圖；此家族演化圖構建算法實現過程：對某個家族聚類簇中的由同一個原始執行體經過多態和變形技術得到的變種惡意代碼加到同一個集合中，具體判定時使用兩個惡意代碼樣例的杰卡德相似度來決定其是否具有基于變形技術的基礎同源關系；對每個集合中的樣例按照其文件創建時間從早到晚進行排序，對于創建時間相同的樣例再按照其文件修改時間從早到晚進行排序，排序后對每個集合按順序把樣例點依次添加到家族演化圖中并對每對相鄰排列的樣例點添加一條短的有向邊來表示樣例間基于變形技術的直接演化關系；對于某家族聚類簇中每兩個樣例集合對S_j、S_k，使用集合排序后的第一個樣例x和y代表集合S_j和S_k，計算相似度Asym-J(x→y)和Asym-J(y→x)的值，如果其中一值大于設定的最小相似度值MinSim，則說明樣例x與樣例y間存在直接演化關系；此時，通過Asym-J(x→y)和Asym-J(y→x)的大小來確定演化方向，當Asym-J(x→y)＞Asym-J(y→x)時，得到其演化方向為x到y，否則為y到x，然后在演化圖中添加一條長的有向邊來表示樣例間基于定制修改的直接演化關系；由于相似性度量是不對稱的，最終得到該聚類簇的演化圖為一個有向無環圖；基于不對稱相似度計算的家族演化圖構建算法所構建的家族演化圖中的圓圈代表了樣本，有向邊標示了樣本的演化方向并且其代表的演化關系具體可分為兩種：短的有向邊表示樣本在傳播過程中為躲避特征碼匹配檢測技術使用多態或變形技術生成變種所產生的直接演化關系，長的有向邊表示樣本在定制修改、版本迭代和程序嵌入過程中生成變種所產生的直接演化關系。