代码相似度检测【基于API依赖关系的代码相似度分析】

代码相似度检测【基于API依赖关系的代码相似度分析】 计 算 机 工 程 第卷 第1期 39 V ol.39 No.1 Computer Engineering ：10003428(xx)01008005?软件技术与数据库? xx年1月 January xx ：A ：TP311 基于API依赖关系的代码相似度分析 姚新磊，庞建民，岳 峰，余 勇 (工程大学信息工程学院，郑州 450002) 摘 要：针对传统系统调用依赖图(SCDG)不能很好地消除API噪声、API重排等API特征混淆的问题，提出一种基于API依赖关系的恶意代码相似度分析方法。采用由API控制依赖关系和4类数据依赖关系组成的SCDG程序行为描述方式，通过数据依赖关系分析和控制依赖关系归一化，消除SCDG中的API噪声和API重排。实验结果表明，与API序列相似度分析方式相比，该方法能提高恶意代码相似度分析的准确性。 关键词：恶意代码；相似度分析；数据依赖；控制依赖；系统调用依赖图；Jaard系数 Code Similarity Analysis Based on API Dependence Relation YAO Xin-lei, PANG Jian-min, YUE Feng, YU Yong (Institute of Information Engineering, Information Engineering University, Zhengzhou 450002, China) 【Abstract】Aiming at the problem of API feature obfuscation caused by API noise and API rearrangement which traditional System Call Dependence Graph(SCDG) can not eliminate, this paper presents a malicious code similarity analysis method based on API dependence. The method uses a program behavior description based on SCDG posed of control dependence and four types of data dependence between APIs. API noise and API rearrangement are eliminated through data dependence analysis and control dependence normalization. Experimental results show that, pared with API sequence similarity analysis method, this method significantly improves the auracy of the similarity analysis of malicious code. 【Key words】malicious code; similarity analysis; data dependence; control dependence; System Call Dependence Graph(SCDG); Jaard index DOI: 10.3969/j.issn.1000-3428.xx.01.017 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 基金项目：国家“863”计划基金资助重点项目(xxAA012201)；河南省重大科技攻关计划基金资助项目(1*1) 作者简介：姚新磊(1986)，男，硕士研究生，主研方向：软件逆向工程，信息安全；庞建民，教授、博士、博士生导师；岳 峰，博士研究生；余 勇，硕士研究生 ：xx-04-06 修回日期：xx-05-07 E-mail：trirocksyaogmail. API第39卷 第1期 姚新磊，庞建民，岳 峰，等：基于 依赖关系的代码相似度分析 81 调用。 (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 /功能：远程线程注入 2 /输入：目标进程explorer.exe的ID：PID，DLL名称：1.dll 3 /输出：TRUE：成功，FALSE：失败 4 ThreadInject() 5 6 HANDLE hKernel = GetModuleHandle(TEXT(Kernel32); 7 if(hKernel = NULL) 8 return FALSE; 9 10 PTHREAD_START_ROUTINE Pfn = (PTHREAD_ START_ROUTINE)GetProcAddress (hKernel, 11 LoadLiparyA); 12 if(pfn = NULL) 13 return FALSE; 14 15 HANDLE hProcess = OpenProcess (PROCESS_ALL_ACCESS, FALSE, PID); 16 if(hProcess=NULL) 17 return FALSE; 18 19 LPVOID RemoteMemory = VirtualAllocEx (hProcess, NULL, Strlen(1.dll)+1, 20 MEM_MIT,PAGE_READWRITE); 21 If(RemoteMemory=NULL) 22 Return FALSE; 23 24 if(!WriteProcessMemory(hProcess,Remote Memory, (void *)(LPCTSTR)1.dll, 25 Strlen(1.dll),NULL) 26 return FALSE; 27 28 29 FILE_SHARE_READ, NULL, 30 CREATE_ALWAYS, FILE_ ATTRIBUTE_NORMAL, NULL); 31 HANDLE hProcess2 = (HANDLE) 32 33 HANDLE hThread = CreateRemoteThread (hProcess2,NULL,0,pfn,RemoteMemory,0,NULL); 34 retrun TRUE; 35 从图1中可以看出，混淆后的远程线程注入代码 的函数依赖图发生了巨大变化，新增加的函数与函数产生输入依赖关系，与函数产生流依赖关系；而且SetFilePointer函数将“1.tmp”文件的读写头移动到hProcess值处，导致系统的完整性发生变化即系统状态发生变化，这是原有方法所不能消除的噪声API。 图1 混淆后的远程线程注入函数依赖图 2.2 API重排 将图1中的部分函数分为3组，分别是第1组函数函数、第2组函数、函数、第3组函数 82 计 算 机 工 程 xx年1月15日 。通过对函数的功能实现过程分析发现： (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：VV是边集合，说明2个系统调用之间存在依赖关系；：VS是系统调用号与系统调用名称之间的映射；：ED是边和依赖关系之间的映射，由于2个系统调用的依赖关系可能多于一个，该映射是一个边到所有依赖关系的映射。 污点数据信息是五元组，其中，Address是污点数据的地址；Length为污点数据的长度；Type表示污点数据的类型，分内存数据Mem和寄存器Reg 2类；ParamType表示污点数据作为系统调用的参数信息，分入参in、出参out、出入参in-out 3类。借鉴文献9中的方法设计一个双向链表记录污点信息，用于回溯污点数据的传播过程。 对于数据依赖关系，在执行过程中将系统调用的出参、出入参和返回值设置为污点源，然后跟踪数据操作指令和内存操作指令进行污点传播，当执行到新的系统调用时分析其入参是否为污点数据，若是则回溯分析该系统与前一个系统调用存在的数据依赖关系，若存在流依赖、反依赖、输入依赖和输出依赖中的任何一种，则记录两者之间的数据依赖关系然，并将该系统调用的出参、出入参和返回值设置为新的污点源。 对于控制依赖关系，借鉴文献8中的方法进行构建。以参数hProcess和hProcess2的污点传播过程为例，最终形成的SCDG的具体信息如图3所示。 图3 混淆后的SCDG部分具体信息 API第39卷 第1期 姚新磊，庞建民，岳 峰，等：基于 依赖关系的代码相似度分析 83 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)对于每一对污点源对偶，若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的相似性，本文使用Jaard系数表示2个SCDG的相似度。对于A、B 2个SCDG： J(A, B)=|AB|/|AB| 其中，AB是两者的公共子图并集；AB是两者合并图；|AB|表示图中节点的数量，也就是系统调用的个数，因此Jaard系数就表示2个SCDG中相同功能部分占两者所有功能的比例。 计算J(A, B)的关键点就是获取|AB|，也就是获取公共子图并集。本文采用VF2算法10计算2个图的公共子图，进而获取公共子图并集，由此设计如下的SCDG相似度分析算法： 算法 SCDG相似度分析算法 输入 恶意代码SCDG：A，可疑代码SCDG：B 输出 A、B的相似度 (1)对A、B进行预处理，并对A中的每一个子图设置 84 计 算 机 工 程 xx年1月15日 Visited标志为False。 (2)若所有子图的Visited标志为True，则转步骤(3)，否则选择A中一个Visited标志为False的子图S，调用VF2算法检查它是否子图同构于B，若是则将S加入公共子图集合中。设置S的Visited标志为True，转步骤(2)。 (3)根据获取的公共子图集合，计算A、B的Jaard系数并返回。 4 实验结果 本文选取常见的木马Downloader，它主要功能是向IE进程注入一个线程，实现下载，并运行下载的程序；然后对源代码进行修改形成4个变种A、B、C和D。 在测试中，采用依赖相似度分析方法分别对Downloader和它的4个变种的相似度进行分析，同时采用序列相似度分析进行对比，实验结果如表1所示。 表1 Downloader变种相似度分析比较 变种 混淆方式 序列相似度 依赖关系相似度 /(%) /(%) A API噪声 50.1 92.1 B API重排 60.4 93.4 C API噪声和API重排 42.7 90.5 D 添加删除部分功能 80.2 82.2 从表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 BirthmarksC/ Proc. of the 25th Annual Computer Security Applications Conference. Honolulu, USA: s. n., xx: 149-158. 2 Christodorescu M, Jha S, Kruegel C. Mining Specifications of Malicious BehaviorC/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, xx: 5-14. 3 Bayer U, Comparetti P M, Hlauscheck C, et al. Scalable, Behavior-based Malware ClusteringC/Proc. of NDSS09. San Diego, USA: s. n., xx. 4 Wang Xinran, Jhi Yoon-Chan, Zhu Sencun, et al. Behavior Based Software Theft DetectionC/Proc. of the 16th ACM Conference on Computer and Communications Security. New York, USA: ACM Press,