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

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

表示数据流的接受方进程 P,s 表示事件数据流大小即信息的字节数,t 表示事件发生的时间.为了简化模型,我们
对同一对实体间的事件进行合并而不是创建各自的事件.在数据流图中具体表现,节点 A 流向另一个节点 B 的
事件存在多起,即 e 1 (A,B,s 1 ,t 1 )与 e 2 (A,B,s 2 ,t 2 ),则合并为事件 e(A,B,s 1 +s 2 ,min(t 1 ,t 2 )).这种简化无疑是精度向效率的
妥协,我们认为这种妥协是可行.

s
P F
Fig.2 Data flow diagram
图 2 数据流示意图

本文使用 G(N,E,λ)来表示数据流图,其中,N 表示系统实体集合,E 表示系统事件,函数λ表示系统事件的更
新.使用 update(G,e)来表示数据流图的生成过程,每次捕获系统实体间的事件就对数据流图进行更新.若该事件
已存在,则合并流图 G 中该事件附加的信息;若不存在,则保存该事件信息到流图中.其表示如式(1)所示.
⎧⎛ N ⎞
⎪⎜ ⎟
⎜ E ⎟ ⎪ , if e∈ E
⎜ (, esize ← ⎡ ) ( , e size + ) s ⎤ ⎟ ⎪
⎜ λ ⎟ ⎪
⎜ ⎝ ⎢ ⎣ (, e time ← (min( ( , e time t ⎥ ⎦ ⎟ ⎠ ⎪
λ
)
), )
update G , , , ) (1)
(,(src dest s t = ⎨
⎛ N ∪ {src dest ⎞ ⎪ , }
⎪ ⎜ E ∪ {} e ⎟
⎪ ⎜ ⎟ , otherwise
⎪ ⎜ ⎡ (, esize ← ⎤ ) s ⎟
⎪ ⎜ ⎜ λ ⎢ ⎥ ⎟ ⎟
)
⎝ ⎣ (, e time ← t ⎦ ⎠ ⎩
2.2 特征子图提取
上一节介绍了从恶意程序捕获系统实体间数据流生成数据流图,这一节我们将详细介绍从数据流图中提
取特征子图的过程.我们使用 TreeWalk 算法提取数据流图的特征子图,该算法如算法 1 所示.
算法 1. TreeWalk(v,G,d).
输入:v 表示子图根节点且 v∈G,G 表示数据流图,d 表示提取深度.
d
输出: sg 表示根节点 v、深度为 d 的子图.
v
d
1. sg 初始只有根节点 v.
v
2. 若 d 大于 0,则将图 G 中节点 v 的后继节点 N v 作为树根节点的孩子节点,d 的大小减 1.
3. 判断 d 是否大于 0:若大于 0,则将树中叶子节点在图 G 中的邻接节点作为该叶子节点的孩子节点,图
中已处理的节点对应的叶子节点除外.
4. 重复步骤 3,直至 d 的大小为 0,返回子图.
算法 1 表示从图 G 中提取根节点 v、深度为 d 的特征子图.我们使用图 3 来进行具体说明.图 3(a)是某个恶
意程序的数据流图 G,图 3(b)是以 A 为根节点、深度为 2 提取的子图.其具体过程如下:初始时,子图只有根节点
A 且 d 为 2;然后,将图 G 中节点 A 的后继节点 B 和 C 作为子图根节点的孩子节点且 d 的大小减 1;之后,将树中
叶子节点 B 和 C 在图 G 的后继节点作为该叶子节点的孩子节点,如节点 B 的孩子节点是 A 和 D,C 的孩子节点
是 D,此时,d 为 0,则返回该特征子图.若初始 d 为 3,则需对图 3(b)中叶子节点 D 进行后继节点处理,而叶子节点
A 不处理.这是因为节点 A 的后继节点信息已存在子图中,这样可以减小子图的结构复杂性.
使用 TreeWalk 算法可以从图中以任意节点提取深度为 d 的特征子图,这些特征子图包含了图的恶意行为.
然而,恶意程序间的差异性使得恶意行为也不同,仅通过深度为 d 的特征子图是不足以涵盖所有的恶意行为.因
而,我们通过给定阈值 D,即最大提取深度来尽可能提取出恶意程序的恶意行为,即从图中以任意节点提取深度
d∈{0,1,…,D}的特征子图,来尽可能地挖掘可能的恶意行为.