基于API依赖关系的代码相似度分析

姚新磊，庞建民，岳 峰，余 勇

(信息工程大学信息工程学院，郑州 450002)

1 概述

代码相似度分析是检测源代码窃取和恶意代码变种的主要方式，其本质上依赖于对代码的描述和理解。现有对代码特征的描述有很多种，如特征码、指令序列、控制流图、API序列[1]、API依赖图[2-4]等，不同的描述方式代表着对代码实际逻辑的不同理解方式。但程序理解本身就是 NP问题[5]，各种理解在实现上只能更大程度地接近代码的实际逻辑，为此一般要在描述上采取一定的精简策略。

正如多态引擎[6]在指令级采用垃圾指令插入、等价指令替换、指令顺序重排、寄存器随机等方式实现指令级特征的混淆，针对目前较为流行的API级行为分析，一些API级特征的混淆方式开始大量使用，如API噪声[7]、API顺序重排和等价API替换等。

针对此类混淆，文献[8]提出一种基于行为依赖的恶意代码相似度比较方法，首先在依赖图的构建阶段采用虚拟节点消除API序列重排混淆；然后在依赖图的预处理阶段手工构建等价API序列集合，在分析中若发现其中一个序列则，在等价序列集合中寻找统一表示的序列将其替换；最后在污点传播中对产生了污点但没有进行传播，或进行了传播但在传播过程中没有引起系统状态改变的噪声API进行消除。该方法有效解决一些 API级特征的混淆方式对相似度分析的影响，但也存在如下改进空间:

(1)对 API噪声的处理依赖于改变系统状态的函数集合，若一个API调用使用了污点数据而且改变了系统状态，则不被认为是噪声API，就不会从依赖图中删除。然而，这样的 API调用也可能是噪声 API调用。

(2)对API重排问题的处理有待商榷:1)只处理了2个API的重排问题，没有考虑2个API序列之间的重排问题；2)对API重排的定义欠妥，其中的“有数据依赖但没有发生修改”定义扩大了API重排范围，实际上2个API之间在有数据依赖关系但没有修改污点数据的情况下并不能交换位置。

鉴于此，本文在分析这2类问题的基础上，提出基于API依赖关系的代码相似度分析方式，通过动态分析形成程序的SCDG，然后对SCDG进行预处理消除API噪声、API重排，最后采用子图同构算法计算可疑代码与原有代码的相似度。

2 问题的提出

2.1 污点源复用式噪声API

动态污点分析是获取API依赖关系的主要方式，污点源是污点追踪过程的开始，污点源的变化是必然引起追踪过程的变化，进而引起 API依赖关系的变化。污点源复用攻击就是一种将原有污点源复用到新污点源从而导致污点源变化的攻击方式。

在常见的远程线程注入代码中添加了 Create File和 SetFilePointer 2个噪声 API，根据本文对SetFilePointer参数的设置，FILE_BEGIN代表调整时起始参考点是文件的开头，hProcess作为参数是调整的字节数，当SetFilePointer调用成功后，其返回值就是一个与hProcess相等的DWORD值，将其赋给 hProcess2后就完成了污点源复用，后面的CreateRemoteThread函数的第 1个参数就是hProcess2，同样实现了向explorer进程注入一个线程的功能。

混淆后远程线程注入类C代码如下:

从图1中可以看出，混淆后的远程线程注入代码的函数依赖图发生了巨大变化，新增加的函数⑧与函数③产生输入依赖关系，与函数⑥产生流依赖关系；而且 SetFilePointer函数将“1.tmp”文件的读写头移动到hProcess值处，导致系统的完整性发生变化即系统状态发生变化，这是原有方法所不能消除的噪声API。

图1 混淆后的远程线程注入函数依赖图

2.2 API重排

将图1中的部分函数分为3组，分别是第1组函数①～函数③、第2组函数④、函数⑤、第3组函数⑥。通过对函数⑥的功能实现过程分析发现:

(1)前2组函数的调用顺序是可以互换的，即只要在函数⑥执行前完成前2组函数的功能即可，而不需关心这2组函数的调用顺序。

(2)在第 1组和第 2组函数内部，只要保持函数①～函数③和函数④、函数⑤的相对顺序即可，而不用关心它们之间是否有其他 API调用，因此，将2组函数混合放置也可以实现相同功能。

基于以上2点对前2组API的顺序进行重排，将有如图2所示的10种实现，也就是有10个不同的依赖图。在基于SCDG的代码相似性分析中必须先处理这类情况，将不同的依赖图归一化为同一个模型，才能进行后续的比较过程。

图2 远程线程注入API重排的10种情况

3 代码相似度分析

3.1 API依赖关系的构建

定义 1(依赖图) 依赖图是一个四元组(V, E, α,β)，其中，V是顶点集合，代表系统调用集合，每个顶点中包含2项:系统调用号和污点数据信息；E:V×V是边集合，说明2个系统调用之间存在依赖关系；α:V→S是系统调用号与系统调用名称之间的映射；β:E→D是边和依赖关系之间的映射，由于2个系统调用的依赖关系可能多于一个，该映射是一个边到所有依赖关系的映射。

污点数据信息是五元组＜Address, Length, Type,ParamType, Value＞，其中，Address是污点数据的地址；Length为污点数据的长度；Type表示污点数据的类型，分内存数据 Mem和寄存器 Reg 2类；ParamType表示污点数据作为系统调用的参数信息，分入参in、出参out、出入参in-out 3类。借鉴文献[9]中的方法设计一个双向链表记录污点信息，用于回溯污点数据的传播过程。

对于数据依赖关系，在执行过程中将系统调用的出参、出入参和返回值设置为污点源，然后跟踪数据操作指令和内存操作指令进行污点传播，当执行到新的系统调用时分析其入参是否为污点数据，若是则回溯分析该系统与前一个系统调用存在的数据依赖关系，若存在流依赖、反依赖、输入依赖和输出依赖中的任何一种，则记录两者之间的数据依赖关系然，并将该系统调用的出参、出入参和返回值设置为新的污点源。

对于控制依赖关系，借鉴文献[8]中的方法进行构建。以参数hProcess和hProcess2的污点传播过程为例，最终形成的SCDG的具体信息如图3所示。

图3 混淆后的SCDG部分具体信息

3.2 SCDG预处理

3.2.1 噪声API的识别消除

本文主要解决污点源复用式噪声API问题，通过对比分析发现，污点源复用式噪声 API有 3个主要特征:

(1)该类API的出参或返回值是新的污点源。

(2)为了保证后续调用的正确性，新污点源的值与原污点源的值必须是相等的。

(3)新污点源的值是接受原污点源为输入，并经过计算而形成的，所以，该API与产生或使用原污点源的API存在流依赖或输入依赖关系。

依据上述3个特征，可以设计出噪声API识别与消除过程:

(1)遍历 SCDG图，将 ParamType为out或 in-out类型的污点数据加入污点源信息集合。

(2)在污点源信息集合中找出Value相等的污点源对偶。

(3)对于每一对污点源对偶＜A, B＞，若 B对应的API与A对应的API或A所在污点信息双向链表的任一污点信息对应的API存在输入依赖或流依赖，则标记B对应的API调用为噪声API。

(4)对于噪声API，在SCDG中找出与其具有数据依赖关系和控制依赖关系的前驱节点 F和后继节点B，根据F和B的污点数据信息，建立相应的依赖关系，并去除噪声API与F、B节点之间的依赖关系。

3.2.2 噪声API的判定与消除

通过对API之间的4种数据依赖关系发现:流依赖和反依赖直接决定了两者的执行顺序不可改变，存在输出依赖关系的2个API顺序重排后，输出的值有可能不一样，所以也不能重排。只有输入依赖关系的2个API，两者的顺序重排后执行结果是一样的。

为了表示API重排消除后的控制依赖关系，本文设计了统一的控制依赖图。在该图中，控制依赖关系表示一个API的执行依赖于其他API的预先执行，如图4所示，A、B是可以重排的，前2种控制依赖图可以统一成后面的控制依赖图。

图4 统一的控制依赖图

根据上述分析可以设计出 API重排的判定和消除过程:

(1)按照控制依赖关系遍历 SCDG图，对于每一个节点与其他节点的控制依赖关系，检查相应的数据依赖关系，若两者不存在数据依赖或只存在输入依赖，则两者的顺序是可以重排的。

(2)对于可重排的2个节点，消除两者原有的控制依赖关系。然后根据前一个节点的数据依赖关系，建立该节点与其数据依赖关系上的后继节点的控制依赖关系。然后处理下一个节点。图5是图1经过预处理的效果。

图5 SCDG预处理后的函数依赖图

3.3 SCDG相似度分析

定义 2(公共子图) 给定图 G1、G2，C是 G1的子图，如果C子图同构于G2，则C是G1和G2的一个公共子图。

由于2个图的公共子图并不一定是连通的，此处称两者的公共子图并集为公共部分。实际中 2个SCDG的公共部分在各自 SCDG中所占比例是不同的，为了更加精确地描述2个SCDG的相似性，本文使用Jaccard系数表示2个SCDG的相似度。对于A、B 2个SCDG:

其中，A∩B是两者的公共子图并集；A∪B是两者合并图；|A∪B|表示图中节点的数量，也就是系统调用的个数，因此Jaccard系数就表示2个SCDG中相同功能部分占两者所有功能的比例。

计算J(A, B)的关键点就是获取|A∩B|，也就是获取公共子图并集。本文采用 VF2算法[10]计算2个图的公共子图，进而获取公共子图并集，由此设计如下的SCDG相似度分析算法:

算法 SCDG相似度分析算法

输入 恶意代码SCDG:A，可疑代码SCDG:B

输出 A、B的相似度

(1)对 A、B进行预处理，并对 A中的每一个子图设置Visited标志为False。

(2)若所有子图的 Visited标志为 True，则转步骤(3)，否则选择A中一个Visited标志为False的子图S，调用VF2算法检查它是否子图同构于 B，若是则将 S加入公共子图集合中。设置S的Visited标志为True，转步骤(2)。

(3)根据获取的公共子图集合，计算A、B的Jaccard系数并返回。

4 实验结果

本文选取常见的木马Downloader，它主要功能是向 IE进程注入一个线程，实现下载，并运行下载的程序；然后对源代码进行修改形成4个变种A、B、C和D。

在测试中，采用依赖相似度分析方法分别对Downloader和它的4个变种的相似度进行分析，同时采用序列相似度分析进行对比，实验结果如表1所示。

表1 Downloader变种相似度分析比较

从表1可以发现，API噪声和API重排使得原有恶意代码的API序列发生巨大变化，对基于序列相似度的分析有较大影响，而基于依赖关系的相似度分析则很好地解决了这个问题，分析结果显示两者的相似度达到90%以上。但是对于添加或删除部分功能的变种，公共功能部分的API序列是没有发生变化的，所以两者的分析效果基本相似的。

从该对比中可以发现，基于依赖关系的相似度分析更能有效解决API噪声、API重排等API级行为混淆的问题。

5 结束语

本文提出一种基于 API依赖关系的代码相似度分析方法对API噪声、API重排等混淆方式具有较好的抗干扰效果，但其分析过程与动态分析平台的效率息息相关，所以针对代码多路径分析的抗分析技术必然成为对抗动态分析的重要方向，这也是下一步研究的重点。

[1]Wang Xinran, Jhi Yoon-Chan, Zhu Sencun, et al.Detecting Software Theft via System Call Based Birthmarks[C]//Proc.of the 25th Annual Computer Security Applications Conference.Honolulu, USA∶ [s.n.], 2009∶ 149-158.

[2]Christodorescu M, Jha S, Kruegel C.Mining Specifications of Malicious Behavior[C]//Proc.of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering.New York, USA∶ACM Press, 2007∶ 5-14.

[3]Bayer U, Comparetti P M, Hlauscheck C, et al.Scalable,Behavior-based Malware Clustering[C]//Proc.of NDSS’09.San Diego, USA∶ [s.n.], 2009.

[4]Wang Xinran, Jhi Yoon-Chan, Zhu Sencun, et al.Behavior Based Software Theft Detection[C]//Proc.of the 16th ACM Conference on Computer and Communications Security.New York, USA∶ ACM Press, 2009.

[5]Woods S, Yang Qiang.The Program Understand Problem∶Analysis of Heuristic Approach[C]//Proc.of the 18th Int’l Conference on Software Engineering.Berlin, Germany∶[s.n.], 1996∶ 25-29.

[6]The Symantec Enterprise.Understanding and Managing Polymorphic Virus[EB/OL].(2012-03-20).http∶//www.symantec.com/avcenter/reference/striker.pdf.

[7]Kaze A.Stealth API-based Decryptor[EB/OL].(2012-03-20).http∶//vxheavens.com/lib/vkz00.html.

[8]杨 轶, 苏璞睿, 应凌云, 等.基于行为依赖特征的恶意代码相似性比较方法[J].软件学报, 2011, 22(10)∶2438-2453.

[9]Newsome J, Song D.Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software[C]//Proc.of the 12th Annual Network and Distributed System Security Symposium.[S.1.]∶ IEEE Press, 2005.

[10]Cordella L P, Foggia P, Sansone C, et al.A (Sub) Graph Isomorphism Algorithm for Matching Large Graphs[J].IEEE Trans.on Pattern Analysis and Machine Intelligence,2004, 26(10)∶ 1367-1372.