基于程序双维度特征的恶意程序相似性分析

任益辰，肖 达

1.北京邮电大学 网络空间安全学院，北京100876

2.移动互联网安全技术国家工程实验室，北京100876

随着互联网技术和计算机技术的发展，网络空间中的软件数量呈爆炸式增长。据微软官网报道，2018 年Windows 10拥有超过3 500万应用程序，超过1.75亿个软件版本[1]。网络空间中的软件泛滥给了恶意程序可趁之机，恶意程序将自身隐藏在众多的软件应用中，给网络空间安全带来了严重威胁。据《2019年上半年我国互联网网络安全态势》报告显示，仅2019 年上半年，国家互联网应急中心就捕获了3 200万个恶意程序样本[2]；据瑞星发布的《2018 年中国网络安全报告》显示，2018 年瑞星“云安全”系统共截获病毒样本总量7 786万个[3]，可见恶意软件相关态势依然十分严峻。恶意软件检测始终是网络空间安全中的关键课题之一。

目前，互联网上各种代码资源越来越多，软件复用技术也日益成熟，开发人员能够快速地在原有软件基础上开发出新的软件，从而大大缩短软件开发周期，大幅降低软件开发成本，也大大降低了软件开发门槛[4-5]。尤其是在恶意软件开发领域，在已有代码基础上进行二次开发或对已有代码进行集成已变得十分普遍，恶意软件开发者往往使用复用的手段完成恶意代码的快速更新和开发。因此，可以通过比较未知软件与已知恶意软件的相似性来对恶意软件进行检测，同时也可以通过相似性检测对软件进行溯源和家族分类[6]。恶意软件开发者为了躲避安全软件检测、对抗杀软，往往通过混淆、加壳、自压缩等操作改变恶意软件特征。因此，仅通过特征码、散列值、软件指纹等信息难以识别变形后的恶意软件与原有恶意软件的相似性，需要综合考虑恶意软件的的各种特征来进行相似性[7]。

本文针对Windows平台的恶意软件，在汇编层面提取软件动态指令流信息，并基于离线基本块序列构造软件控制流图，从软件代码语义特征和结构特征两个维度对软件进行相似性分析。动态提取软件特征能够有效避免加壳、混淆等软件变形技术的影响，提取汇编层面的信息使检测不受软件开发语言的限制，从两个维度进行检测，既考虑到软件的语义特征又考虑到软件的结构特征，能够对软件进行较为全面的分析。

1 相关工作

随着软件技术的发展，软件复用技术给软件开发带来极大便利，同时也带来了盗版软件泛滥，恶意软件开发门槛降低，恶意软件泛滥的问题。

最初，软件相似性或同源性的检测分析技术主要用于软件版权保护，解决软件版权纠纷问题，后来应用范围逐步扩展到恶意软件同源性分析、漏洞挖掘等安全领域[8-19]。

软件相似指的是定义为软件实质相似，即软件思想在表达形式上的相似。软件的表达形式指的是软件思想在技术上的实现，最初包括模块结构、模块组织、编码等，后来研究中又加入了数据结构、控制流图等[20-21]。

根据分析手段的不同，可以将分析方法划分为静态分析和动态分析两种[21]。静态分析方法通过直接分析二进制文件数据提取软件静态信息来对软件相似性进行检测。在研究的早期阶段多使用软件的一些功能特征、外部特征来研究，例如软件大小、软件工作流程等[22]。在之后的研究中，研究人员还使用了静态指令频率、字符串集合、控制流等特征[9]。静态分析不需要执行软件，仅通过读取二进制文件就可以进行分析，具有较高的分析速度和安全性，但静态分析方法无法分析经过混淆、加壳等变形技术处理过的软件，需要与软件反混淆、脱壳等技术相配合。

基于静态分析方法的局限性和虚拟技术的发展，目前大多使用动态分析方法或动静结合的分析方法。动态分析方法通过在沙箱、虚拟机等环境中运行软件，通过动态插桩、污点跟踪等技术获取软件运行过程中的信息来对软件相似性进行检测[22]。按照获取信息的内容可以将其划分为软件产生的数据和软件执行的代码两种，其中数据包括堆栈数据、函数参数、变量数据等，代码包括API 调用、系统函数调用等，按照信息组合形式可以分为集合型、序列型、树或图型。动态分析方法基于软件运行的实际数据对软件相似性进行分析，能够有效地对抗代码混淆、软件加壳等软件变形技术。由于动态分析方法需要执行二进制程序，而执行程序尤其是恶意程序会存在一定的风险，因此需要在安全环境下进行分析。

2 特征提取与分析

本文使用控制流图来描述程序的结构特征，用基本块集合描述程序的语义特征，基于这两种特征的综合相似度对恶意程序进行相似性分析。首先提取程序动态指令流信息，构建程序动态执行的基本块集合和控制流图，分别计算基本块集合相似度和控制流图相似度，从程序代码和程序结构两个角度对程序相似性进行衡量。

2.1 基于沙箱的动态指令流提取

为规避运行未知软件对分析系统造成不利影响的风险，本文使用PinFWSand Box[23]无感知沙箱提取软件动态信息。PinFWSand Box 无感知沙箱通过动态插桩技术对软件系统调用、模块加载及指令流进行监控，并且能够回滚恶意行为，有效地保护分析主机的安全性。

PinFWSand Box 是基于Pin 平台的Pintools 工具开发的一款沙箱。Pin[24]是Intel公司开发的一个二进制程序动态分析平台，支持IA-32、x86-64 和MIC 指令集架构，支持Linux、Windows 和MacOS 系统。Pin 相当于一个即时（Just in Time，JIT）编译器，能够在二进制程序的任意位置插入代码并执行，能够替换原有程序代码，能够记录系统调用、程序线程活动等情况，能够检测进程树，模拟API（Application Programming Interface）调用[25]，具有指令级、基本块级、函数级三种插桩粒度。Pintools工具是动态插桩平台Pin的扩展工具。Pin平台为用户提供了丰富的API接口，允许用户开发动态链接库（Dynamic Link Library）形式的插件，从而使用户可以自定义插入代码的内容和位置，进而提取出自己感兴趣的信息。这些插件被称为Pintools。

软件动态指令流数据量十分庞大，一个1 KB 的程序就可能要执行几十万调指令，直接对每条指令进行插桩会大大影响程序运行速度，大大降低分析效率，并且难以存储。因此，本文对PinFWSand Box 中的Pintools工具进行了调整，以基本块为单位提取软件动态指令流，并且采用基本块索引库的方式对基本块执行序列进行存储。

程序顺序执行的一段汇编语句序列，该序列是单入口单出口的，程序执行过程中仅从入口进入这段序列，仅从出口退出这段序列，则这段序列就称为基本块。程序执行一旦进入某个基本块，就一定会执行该基本块中所有指令直到退出该基本块。如果直接记录基本块执行序列，仍然需要较大的存储空间，因此采用基本块索引库的方式进行存储，将基本块与执行序列分别存储。在存储基本块时相同的基本块仅记录一次，为每个基本块分配唯一的编号，基本块执行序列中使用编号来代替基本块，从而大大降低存储空间。基本块粒度的软件动态指令流数据获取算法步骤如下：

步骤1 程序准备执行一个基本块，触发基本块插桩函数；

步骤2 在基本块索引库中查询该基本块对应编号，如果已经记录过该基本块，则转到步骤5；

步骤3 为该基本块分配执行编号；

步骤4 记录基本块相关信息并添加到索引库；

步骤5 将基本块的执行编号添加到基本块执行序列；

步骤6 程序执行基本块；

步骤7 判断程序是否执行完成，否则转到步骤1，是则退出。

2.2 基本块集合的处理与相似度分析

2.2.1 基本块集合预处理

直接提取得到的基本块集合存在功能无关指令噪声、可重排指令噪声、指令多样化等问题，会严重影响相似度计算结果，因此需要对基本块集合进行预处理。

（1）常用指令筛选

在预处理的过程中需要对指令格式进行统一处理。目前缺少能够统一汇编语言格式的中间语言，如果针对每个汇编指令一一进行格式规定，工作量过大，而且这些指令不都是经常使用的指令，没有全部处理的必要，只需要对常用的指令格式进行格式统一。因此需要筛选出常用指令。

本文从样本网站获取1 500 个二进制样本，提取了这些样本的动态指令流，并对其中属于x86指令集的指令进行统计。统计的内容包括指令符号、指令在样本集中出现的次数、指令在样本集中出现的频率、包含指令的样本占比，最后筛选出最常用的100个汇编指令。

（2）指令多样性去除

在汇编语言中有一些语句有相同的功能，例如xor eax，eax 和mov eax，0 都是将eax 寄存器清零本质上没有区别。为避免这种同义语句给基本块相似度计算带来干扰，需要将这些语句进行统一。

（3）指令格式标准化

x86 汇编指令格式多样，对参数的操作也不尽相同，给相似度计算带来麻烦，因此需要对指令格式进行标准化。

将指令语句标准化为三部分：一个指令码、一个返回值、三个参数。指令码即原来的指令码，结果存储变量为用于存储指令执行结果的变量，参数即原来的参数，个数不够的用null代替。

除指令格式外，指令参数也要进行标准化。汇编指令可以使用寄存器、栈地址、内存地址作为参数，这些参数的本质都是变量，因此将这些参数进行统一命名，并进行编号。

（4）基本块简化

进行上述处理后，能够得到格式统一的基本块集合，然后基于DAG 图（Directed Acyclic Graph，有向无环图）对基本块进行简化，包括删除无用赋值语句、合并串联赋值语句等局部优化处理，从而使基本块语句更加精简，进一步缩小基本块集合的规模。

以返回值和参数为顶点，将BBL（Basic Block，基本块）转化为DAG图。顶点划分为三种：返回值所在顶点为def顶点，初次使用的变量所在顶点为zero顶点，其他顶点为use顶点。

通过判断顶点的父节点和子节点的个数来判断该语句是否需要优化，并且通过顶点的合并、删除来完成优化。如果某个定义顶点无父节点，则说明该顶点定义后未被使用，可以被删除；如果定义顶点只有一个子节点，则说明该顶点对应的参数或返回值的值与子节点相同，可以将该顶点与子顶点合并。最后，将优化后的DAG图恢复成BBL的格式。

2.2.2 相似度计算

本文基于指令间的参数依赖提取基本块的def-use链，并基于基本块的def-use 链来计算基本块间的相似度，从而避免指令可重排问题给相似度计算带来的干扰。之后，根据基本块间的相似度构造集合的相似度矩阵来计算集合间的相似度。

（1）基本块相似度

def-use 链是编译原理中用来描述变量依赖关系的链表，在变量作用域内，以变量定义语句为起点，依次缀连变量的使用语句直到变量再次被定义或作用域结束。基本块的def-use链则以一个基本块作为变量的作用域，以变量定义语句或变量初次出现语句为起点，依次缀连变量使用语句，直到基本块结束或变量被重定义。

定义1（基本块常量集合）将基本块中汇编指令操作数中的立即数称为基本块常量，符号记为con，将常量con的个数记为connum，将基本块中常量集合符号记为con_set，则：

定义2（基本块变量集合）将基本块中除常量外的其余操作数称为变量，符号记为var，将变量var的个数记为varnum，将基本块中变量集合记为var_set，则：

定义3（def-use 链集合）将基本块中的def-use链记为chain，个数记为chanum，def-chain链集合记为cha_set，则

定义4（相似度）集合或数值之间相似的程度，数值范围在0～1，符号记为sim。基本块之间相似度记为simbbl，变量相似度记为simvar，常量相似度记为simcon，常量集合相似度记为simcon_set，def-chain链集合相似度记为simcha_set。

将基本块语义内容转化为基本块变量个数、常量个数、def-use链集合、常量集合四部分，并通过这四部分相似度的结合计算出基本块相似度。

对于基本块A，将其相关信息转化为{varnuma,connuma,cha_setchanuma,con_setconnuma}，其中基本块A的def-use链集合可以表示为：

同样，对于基本块B，将其转化为{varnumb,connumb,cha_setchanumb,con_setconnumb}。

基本块A与基本块B相似度计算公式如下：

其中simvar用varnum之间的距离来计算，simcon用connum之间的距离来计算，公式如下：

simcha_set用两个BBL的cha_set的Jaccard系数来计算，simcon_set用两个BBL 的con_set的Jaccard 系数来计算。其中，Jaccard系数定义为两个集合交集大小与并集大小的比值。对于集合S1和S2，其Jaccard系数计算公式如下：

比对A和B的cha_set，相同chain的个数记为Nsamechain，不同chain的个数记为Ndiffchain，则：

比对A和B的con_set，相同con的个数记为Nsamecon，不同con的个数记为Ndiffcon，则：

（2）基本块集合相似度

定义5（基本块集合）将基本块记为BBL，将基本块个数记为BBLnum，将基本块集合记为BBLSet，则对于程序P，其基本块集合表示为：

定义6（基本块集合相似度矩阵）计算两个基本块结合中任意两个基本块之间的相似度，并按照基本块顺序进行排列，构成相似度矩阵，记为SimMatrix。

将程序P和Q任意两个BBL之间的相似度简记为sij=simBBL(BBLi,BBLj)，其中i∈NBBLnumP,j∈NBBLnumQ。则P 和Q 的基本块集合相似度矩阵表示为：

使用KM 算法计算出s11,…,sBBLnumPBBLnumQ中最大的相似度匹配值。KM 算法是求最大权匹配的经典算法，能够获得结果最大化的情况下两组集合最优匹配顺序。则两个BBL集合的相似度公式为：

2.3 控制流图的生成与相似度计算

控制流图（Control Flow Graph，CFG）是Frances E Allen 于1970 年提出的一种抽象数据结构[18]，是对程序控制流图的简化，用于描述程序代码结构。图1所示是程序中最基本的三种结构：顺序结构、分支结构、循环结构。

图1 程序基本结构

基本块集合仅包含了程序动态指令流的组成，未包含程序的代码结构信息，因此引入控制流图相似度，从而使程序相似性的衡量更为全面和准确。

本文基于NetworkX模块来实现控制流图的生成和相似度计算。

2.3.1 控制流图的生成

本文基于基本块执行序列来生成基本块级别的控制流图，在使用PinFWSand沙箱提取程序动态指令流的同时记录基本块执行序列。在记录基本块时采用了基本块索引库的方式，为每一个基本块设置一个唯一的编号，在执行序列中使用编号表示基本块。基本块内容记录在基本块索引库中，基本块执行序列记录在基本块执行序列文件中。

如图2 所示，这是某个基本块索引库的一部分，包含5个基本块，编号分别为1、2、3、4、5，这5个基本块在执行序列文件中对应的执行序列为123435。

图2 基本块集合与执行序列示例

根据基本块执行序列文件中的编号序列来生成控制流图。将所有的编号作为图的节点，将编号的相邻关系作为边，边的方向由先出现的编号指向它后面的编号，以边重复出现的次数作为边的权重。用符号G表示生成的控制流图，G(V,E)表示包含节点集合V和有向带权边集合E的控制流图。

例如，基本块执行的编号序列为123435，则将1、2、3、4、5 作为控制流图的顶点，将执行序列中的5 种相邻关系作为连接顶点的有向边，分别为（1，2）（2，3）（3，4）（4，3）（3，5），每条边均只出现一次，因此边的权重均为1。由此，生成了带有循环结构控制流图，如图3所示。

图3 基本块序列转控制流图示例

2.3.2 相似度计算

图的相似度计算是一个非常复杂的问题，在实际应用过程中常常根据实际情况对图进行专门的处理，从而降低复杂度，提高计算效率。对于程序的动态控制流图来说，最关键的部分是其中的分支结构、循环结构，这两种结构包含了程序运行中的控制转移信息。而顺序结构对于控制流图来说是不重要的，而且在控制流图中大量存在，因此对控制流图中顺序结构的部分进行合并能够有效缩小图的规模，且不影响图的相似度计算。

通过检查顶点及其相邻顶点的出度和入度来识别垂直结构。如果一个顶点的入度大于1 或出度大于1，则该顶点在一个分支结构上，需要保留，例如图3 中的顶点3。由这种顶点指向的的顶点也需要保留，例如图3中的顶点4和顶点5，其余顶点可以合并。

例如，对于图3 中的示例，顶点123 之间是垂直结构，顶点345 之间是循环结构，则由123435 序列可以简化为3435。简化示意图如图4所示。

图4 控制流图简化示例

控制流图顺序结构合并算法伪代码如下所示：

input：控制流图节点集合V

控制流图边集合E

output：控制流图节点集合V′

控制流图节点集合E′

for v in V ：

get edge set e of v in E

if v out-degree＜2 and v in-degree＜2：

get (v′,v) in e

if v′ out-degree＞=2：

continue

get (v,v′)

add edge (v′,v′′) to E

del (v′,v) in E

del (v,v′) in E

del v in V

根据实验结果，经顺序结构合并处理，V和E的规模都下降到了原来的20%以内。

将两个控制流图的相似度定义为两个控制流图公共子图规模与原图规模的比值。基于VF2 算法[26]来获取G1与G2的公共子图，伪代码如下所示：

input：控制流图G1

控制流图G2

output：公共子图集合commonGraphSet

while G1not empty and G2not empty:

generate subgraph subG1of G1

while subG1subgraph isomorphism to G2：

while not used node n in G1：

if n not in subG1and connected to subG1and in G1：

add n to subG1

break

else:

add subG1to common Graph Set

goto next

get next node n

next：

del subG1in G1

del subG1in G2

根据以上步骤可以获得G1与G2的公共子图集合，该集合能够最大范围的覆盖G1和G2的公共部分，记为common Graph(G1,G2)。

将图的相似度记为simGraph，则simGraph(G1,G2)表示G1与G2的的相似度。

定义7（图的规模）将图G的规模定义为图中节点与边的总数，记为Scale(G)。

则G1与G2的相似度计算公式为：

例如，对于图5中的两个控制流图A和B，A中顶点3、4、5组成的图与B中顶点1、2、3组成的子图同构，则A与B的公共子图规模为6。图A的规模为6，图B的规模为10，则两个图的相似度为0.75。

图5 控制流图相似度计算示例

2.4 基于二维特征整合的相似度计算

基本块集合可以表征程序语义特征，控制流图可以表征程序结构特征，将这两种特征结合，从语义和结构两种维度来计算程序之间的相似度，能够使相似度计算结果更为准确、更可信。

定义8（程序相似度）将两个程序之间的相似度定义为两个程序动态基本块集合相似度与动态控制流图相似度的线性组合，记为simPro。

对于程序P和Q，其相似度记为simPro(P,Q)，则相似度计算公式为：

其中α为线性系数，值为0.5。若0.8 ≤simPro(P,Q)≤1.0，则判定程序P和Q相似；如果0.0 ≤simPro(P,Q)≤0.4，则判定程序P和Q不相似；否则无法判定程序P和Q是否相似。

3 实验评估

本文对提出的方法进行了可行性实验和可靠性实验，从可行性、可靠性两方面对实验结果进行评估。

实验在搭载有VM虚拟机的服务器上进行，实验环境包括Win7操作系统、pin工具和python环境。详细实验环境如表1所示。

表1 实验环境

3.1 可行性实验

可行性实验用于测试本方法能否正确识别程序的相似性。本文从恶意程序分析网站获取了7 组恶意程序，共120 个样本进行可行性测试实验，同组程序都是相同恶意程序的变种，程序组别与样本个数如表2所示。

表2 实验样本列表

计算每个程序与自身的相似度，均为1.0。

对同组程序两两之间进行相似度检测，实验结果统计如图6所示。

同组程序之间的相似度计算结果中约有99%大于0.8，说明本方法能够有效识别相似的恶意程序。

对不同组程序两两之间进行相似度检测，每组程序之间的平均相似度统计结果如表3所示。

表3 不同组程序间相似度平均值

图6 同组程序相似度取值范围分布图

不同组程序之间的相似度平均值在0.4 以内，说明本方法能够区分相似性较小的恶意程序。

由实验结果得知，本文方法既能识别相似性较大的程序又能区分相似性较小的程序，说明本方法在恶意程序的相似性分析上是可行的。

多次重复上述实验，得到相同的实验结果。由此可见，本文方法是稳定可行的。

3.2 可靠性实验

对120个样本程序进行加壳处理，分别计算其与原程序的相似度，加壳方法选择了常见的upx、ASPack、PECompact、ASProtect、EXECryptor 这5 种。相似度计算结果如表4所示。

表4 加壳后程序与原程序相似度部分数据

对相似度取值范围进行统计，结果如图7、8所示。

图7 加壳后程序与原程序相似度取值范围分布柱状图

图8 加壳后程序与原程序相似度取值范围百分比

从图7 和图8 的实验结果中可以看出，加壳变形后的程序中有大约83%与原程序的相似度达到0.9 以上，约94%达到0.8 以上，说明本文方法能够有效地对抗程序加壳变形手段，是可靠的。

4 结语

本文提出一种基于控制流图和指令基本块的恶意软件相似度分析方法，首先使用PinFWSand 沙箱建立程序指令流快照，并使用索引库的方式进行存储，然后对获取的指令流信息进行预处理，去除基本块集合和控制流图的干扰噪声，最后综合程序基本块集合和控制流图的相似度得出程序间的相似度。本文方法从程序结构和代码语义两个方面综合考虑程序的相似度，对程序相似度的衡量更全面更准确，能够有效的识别同源的恶意软件，并且能够对加壳等软件变形手段有较好的抗干扰效果。本文未对这两种相似度进行加权计算，在下一步的工作中需要对两者在软件相似中的权重进行研究。