Page 127 - 《软件学报》2020年第11期

汪洁 等:子图相似性的恶意程序检测方法 3443

然而,算法 2 只是对目标子图上下文的一次更新.而神经网络需要对所有的子图进行反复学习,即:需要对子
图库中的子图每出现一次在训练集的数据流图时,就对该子图的上下文进行一次更新,通过不断地学习,会使得
语境相似(上下文)的子图其向量表示距离也相近.并且在算法具体实现过程中,我们从数据流图提取子图的同
时也保存了该子图的上下文信息,因而后续的过程只需要读取相关信息即可,这可以减小大量的时间开销.

4 恶意程序检测模型构建

在上一节介绍了子图间相似性的学习,这一节将详细介绍如何使用子图向量构建图相似性函数以及使用
图相似函数来进行分类和检测.
4.1 图相似函数
本文使用深度图内核来计算图间的相似度,深度图内核 [22] 是一种非常流行并广泛应用于计算两个图间相
似度,通过将一对图递归分成子结构,并定义子结构相似度函数来计算图间相似度.其表示如下.
T
S(G,G′)=Φ(G) ⋅M⋅Φ(G′) (6)
其中,S(G,G′)是表示图 G 与 G′的相似度;Φ(G)表示数据流图 G 的图向量;M 是个|V×V|矩阵,本文中用来表示子图
间的相似性矩阵,|V|表示子图库中子图的数量.
图相似函数考虑了子图间的相关性,这可以有效缓解对角线优势问题,即给定的图形容易仅与自身相似.关
于公式(6)必须要说明的是,Φ(G)表示流图 G 的图向量,且图向量的维度与特征子图库的大小相同.那么如何将
一个图映射成一个向量?我们将子图库中的子图与图向量的维度一一对应,同时图向量中使用 1 和 0 来表示该
图是否包含这个维度对应的特征子图.假设特征子图库只有{a,b,c,d,e}这 5 个子图,若图 G 只包含子图 b 和 d,那
么其图向量为(0,1,0,1,0),同时,矩阵 M 设计成上述 5 个子图的相似矩阵.这里有一个难点,就是判断图 G 中包含
的特征子图.图与子图匹配过程是非常复杂并且耗时的,而我们采取的方法是非常迅速,从图中提取特征子图
时,采取逆拓扑标识的手段表示成字符串并保存到文件中,一个图对应一份文件,那么每份文件就存储了一个图
所有的子图信息.之后,只需要使用子图库中的子图字符串与文件进行字符串匹配,就可以判断该图所包含的特
征子图.
矩阵 M 表示子图库中子图间相似性矩阵,M ij 表示子图 sg i 与 sg j 的相似度.使用上述 5 个子图的示例,M 13 则
表示子图 b 和 d 的相似度.关于矩阵 M 的计算我们提供了两种计算方法.
(1) 在第 3 节中,我们将“上下文”相似的子图映射成的向量在其向量空间也相近.基于这一点,我们设计子
图相似性计算方法如下.
1
,
( ssg sg j ) = (7)
i
+
dv ), (sg )) 1
((sg v
i j
其中,s 表示子图的相似度,d(v(sg i ),v(sg j ))表示子图 sg i 与 sg j 的空间距离,且 v(sg i )表示子图 sg i 的向量.
(2) 深度图内核,即公式(8),可以用来计算 G 与 G′的相似度,同样可以用来计算子图 sg i 与 sg j 的相似度,因
为子图也是图.其表示如下.
T
s(sg i ,sg j )=v(sg i ) ⋅m⋅v(sg j ) (8)
为了便于区分,使用了符号 m.这里,矩阵 m 仍是未知的.我们设计矩阵 m 是一个对角矩阵,其中,m ij 是通过计
算〈v(sg i ),v(sg j )〉且 m ij =0,i≠j.
上述两种方式均可以计算 M ij =(sg i ,sg j ),这样我们可以计算出子图库中任意子图间的相似性,即矩阵 M.
4.2 分类和检测

分类任务是将图分成两类或者多类.给定恶意程序和正常程序的图集{G 1 ,G 2 ,…,G n }以及类标签集合 Y={y 1 ,
y 2 ,…,y n },其中,标签使用 0 和 1 分别表示正常和恶意程序,图分类任务是希望找到一种模型,能够将图 G i 映射到
标签 y i .本文使用图相似函数构建核矩阵 K,K ij 表示图 G i 与 G j 的相似度,然后将核矩阵 K 放入核方法如 SVM 进
行分类训练: