公开/公告号CN106126235A
专利类型发明专利
公开/公告日2016-11-16
原文格式PDF
申请/专利权人 中国科学院信息工程研究所;
申请/专利号CN201610474461.1
申请日2016-06-24
分类号G06F9/44(20060101);G06F9/45(20060101);
代理机构北京君尚知识产权代理事务所(普通合伙);
代理人司立彬
地址 100093 北京市海淀区闵庄路甲89号
入库时间 2023-06-19 00:53:35
法律状态公告日
法律状态信息
法律状态
2019-05-07
授权
授权
2016-12-14
实质审查的生效 IPC(主分类):G06F9/44 申请日:20160624
实质审查的生效
2016-11-16
公开
公开
技术领域
本发明涉及逆向分析与恶意代码分析领域,具体涉及一种基于simhash与倒排索引的复用代码库构建方法、快速溯源方法及系统。
背景技术
代码复用通常以函数为基本单位,即使被编译器高度优化仍然保留大量函数整体,所以本文以函数为单位进行溯源与相似判定更加符合复用场景。恶意代码同源判定的主要依据是恶意代码作者在不同恶意代码中对个人编写代码的复用,如Sasser与Netsky、Flame与Gauss等的同源判定均依据它们共享的特殊函数。但是,为提高开发速度,恶意代码作者经常复用他人编写的公开或半公开代码,如Chthonic是一款在Zeus源码基础上修改开发的恶意代码。同时据报告,Equation APT(Advanced Persistent Threat,高级持续性威胁)攻击中使用的一个样本,被判定属于Zlob家族,说明APT攻击组织也会复用开源代码。为执行需要,编译器在编译时通常插入大量代码。经测试,当编译仅有一个函数的C语言代码时,Windows下的VC6.0编译器插入了103个函数,Linux下的GCC4.7.2编译器插入了18个函数。不同的编译器插入的函数与函数的插入位置均不同,需要大量经验与技巧才能识别这些函数。复用函数对恶意代码分析与同源判定工作造成了很大干扰,目前主要依靠恶意代码分析人员的经验识别,导致同源判定效率不高。快速识复用函数将大大提高效率,并提升同源判定结论的可信度。
复用函数溯源的基础是相似函数判定,若在某二进制样本中存在一个函数的相似函数,则说明该函数为复用函数。目前相似函数判定技术,具有很高的准确率与召回率,但是判定效率较低,不适应海量代码的复用函数溯源。一个函数源码的少量修改,编译选项、所在位置的不同都会造成逆向后汇编代码中指令顺序、寄存器、跳转位置等的差异,因此若使用哈希等方法进行溯源将导致非常低的召回率。函数中,代码块的跳转结构是相似判定的重要特征,而跳转关系提取、结构图的比对要耗费大量时间,是导致目前相似判定准确率、召回率与速度难以兼得的一个重要原因。
发明内容
针对现有技术存在的技术问题,为了实现复用代码的快速溯源与判定,本发明公开了一种基于simhash与倒排索引的复用代码库构建方法、快速溯源方法及系统。
本发明以函数为单位,基于simhash与倒排索引技术,能在海量代码中快速溯源相似函数。首先逆向已有未加壳与已脱壳样本获取汇编代码,将其中的函数依据跳转指令划分为多个代码块并计算代码块的simhash值,构建simhash值与代码块、代码块与函数、函数与样本间的三级倒排索引。溯源函数,依据代码块的simhash值快速发现相似代码块,继而倒排索引潜在相似函数,并溯源至所在样本。
本发明公开了一种基于simhash与倒排索引的用于复用代码溯源的代码库构建方法,基于该代码库,使用本发明公开的溯源方法能快速溯源定位相似函数及其所在的样本。具体包括4个步骤:
(1)逆向获取每一可执行程序样本的汇编代码;
(2)依据调用指令call与调用地址,提取汇编代码中的函数,并依据每一函数中的跳转指令与跳转地址将该函数拆分为多个代码块;
(3)使用simhash算法(2002年提出《Similarity estimation techniques from rounding algorithms》)计算每个代码块的simhash值;
(4)构建三级倒排索引:simhash值索引对应的代码块,代码块索引包含该代码块的函数,函数索引包含该函数的样本。
本发明公开了一种基于simhash与倒排索引的复用代码快速溯源方法,对于待溯源函数,使用该方法能快速在海量代码库中溯源到与该函数相似的函数及其所在样本,若未溯源到相似函数,在代码库基础上可认为该函数为非复用函数。具体包括5个步骤:
(1)将待溯源函数依据跳转指令与跳转地址拆分为多个代码块,并计算代码块的simhash值;
(2)在代码库中搜索与代码块simhash值的汉明距离在3以内的simhash值,继而通过倒排索引搜索出汉明距离在3以内的每一simhash值对应的代码块作为相似代码块;
(3)通过相似代码块与倒排索引搜索出潜在相似函数,然后依据潜在相似函数与该待溯源函数的相似代码块的数量为每个潜在相似函数赋予一个权值,筛选出权值超过一定阈值的函数;比如通过函数A的3个相似代码块,检索出了两个与函数A相似的潜在相似函数B、C,假如函数B与函数A有一个代码块相似,那么函数B的权值就是1/3,函数C与函数A有两个代码块相似,那么函数C的权值是2/3;假如阈值是1/2,那么只会认为函数C与函数A相似;
(4)通过比对(3)中筛选出的相似函数的相似代码块间的跳转关系最终确定是否相似;本发明中设定只有当代码块间的跳转关系完全相似时,才认为函数相似。比如函数A与函数B有2个代码块(1、2)相似,假如在函数A中两代码块间跳转关系是1跳转到2,但是在函数B中是2跳转到1,那么函数A、B是不相似的,只有代码块间的跳转关系相同时,才认为函数A、B相似。
(5)通过倒排索引溯源定位到相似函数所在的样本。
本发明同时公开了一种基于simhash与倒排索引的复用代码快速溯源系统,主要由预处理模块、代码库构建模块、函数溯源模块3个模块组成。
与现有技术相比,本发明的积极效果为:
本发明能在大量样本中快速溯源与某函数相似的函数代码及其所在样本,且具有较高的准确率与召回率。基于该方法可以开发代码搜索引擎等工具,帮助逆向分析人员提高效率,提升同源判定工作的自动化程度。
通过实验表明,本发明具有很高的准确率、召回率与很快的溯源速度:
(1)使用32位WinXP系统中“Program Files”与“Windows”文件夹下的所有PE文件构建了一个代码库;
(2)使用VC6.0编译仅包含一个main函数,且仅有一条printf语句的C语言源代码,编译为Release版可执行文件,逆向获取该文件的汇编代码,IDA Pro能自动识别并剔除库函数,所以最终会被代码中除main函数外还有19个编译器插入函数;
(3)由于WinXP系统中存在大量VC6.0编译的文件,据此推测19个编译器插入函数有一定概率在WinXP文件构建的代码库中溯源到相似函数,因此对19个编译器插入函数进行溯源,发现其中16个存在相似函数,另外三个sub_401010、sub_4057BC与sub_402AD1未溯源到相似函数,在配有16核Intel(R)Xeon(R)CPU E562与16G内存的DellPower Edge R410服务器上进行该实验,每个函数的平均溯源时间约为0.149秒。
下表列出了部分溯源到的相似函数:
附图说明
图1为基于simhash与倒排索引的代码库构建方法流程图;
图2为三级倒排索引结构图;
图3为函数溯源流程图;
图4为基于simhash与倒排索引的复用代码快速溯源系统架构图.
具体实施方式
下面,结合具体的实施实例对本发明进行详细说明。
图1给出了本发明提供的代码库构建方法的流程,具体实施步骤如下:
(1)对加壳的样本进行脱壳处理
1)使用PeiD查壳工具判定样本所使用的壳;
2)针对不同的壳使用不同的脱壳工具进行脱壳处理;
3)舍弃其他使用特殊壳导致无法脱壳的样本。
最终的样本均为已脱壳样本。
(2)使用逆向工具获取各样本的汇编代码
本发明以IDA Pro为例。
(3)提取汇编代码中的函数
逆向获取的汇编代码中,“proc near”标识一个函数的开始,而“endp”标识一个函数的结束,依据这两个标识从汇编代码中提取函数。
(4)提取函数中的代码块
依据函数中的jnz、jz等跳转指令与跳转指令指向的地址,将函数代码划分为多个代码块,每个代码块或者没有跳转指令,或者最后一条为跳转指令。
(5)代码标准化处理
对源代码的轻微改动将造成汇编代码中寄存器、立即数、内存地址的大幅变动,为了忽略这种差异对代码造成的影响,依据以下规则对汇编代码进行标准化处理:
●寄存器如eax、ax、al等依据所占位数分别标准化为REG32、REG16、REG18;
●内存如[eax]、[edi+4]等均表示为MEM;
●立即数如0、5A4Dh表示为VAL;
●call指令调用外部的系统库函数时指令不做处理,调用内部函数如“call sub_105A8”时规范化为“call INNER”;
●跳转指令如“jz short loc_4023E7”规范化为“jz loc”。
(6)计算代码块的simhash值
simhash是一种模糊哈希,常常用于有轻微差异的相似文本、网页的判定工作。
1)创建一个64位的向量,并初始化为0;
2)对标准化的代码块进行分词处理,分词为2-gram标准化的指令序列;
3)为每个分词赋予权值,将分词的频率做为基础权值,由于调用的API在很大程度上决定了函数的功能,所以调用指令在代码块中具有重要作用,因此对包含调用指令分词的权值加倍;
4)对每个分词使用MD5哈希算法做哈希处理,取MD5值中的64位做为该分词的哈希值;
5)加权合并,对分词哈希的每一位,如果该位为1,则向量相应位的值加上该分词的权值,否则减去该分词的权值;
6)降维,对向量的每一位,若该位大于0,则设为1,否则设为0,形成一个64位的simhash值。
(7)构建三级倒排索引
经过前6步,提取了海量样本包含的函数、函数中包含的代码块,并计算了每个代码块的simhash值,为这些元素构建三级倒排索引,如图2所示:
1)由simhash值索引具有该simhash值的代码块,simhash碰撞概率较大,所以存在几个代码块具有同一个simhash值的情况;
2)由代码块索引代码块所在的函数,代码块标准化后,增大了相似的概率,不相似的函数也有可能存在相同的标准化代码块;
3)由函数索引函数所在的样本。
最终基于simhash与倒排索引在海量样本的基础上构建了用于函数溯源的代码库。
图3给出了在构建的代码库上快速溯源函数的流程,具体实施步骤如下:
(1)待溯源函数代码P,依据跳转指令拆分为多个代码块,假设共有n个,之后计算每个代码块的simhash值:
P→{sh1,sh2,…,shn}>
(2)使用simhash多表索引方法,为shi|i∈[1,n]快速检索海明距离在3以内的相似simhash,构成相似simhash集合:
shSeti={sh:d(shi,sh)≤3}|i∈[1,n]>
d(shi,sh)表示shi与sh的海明距离,若所有的相似simhash集合均为空集,说明不存在与该函数具有相似代码块的函数,否则,继续下一步;
(3)依据已构建的simhash与代码块的倒排索引,检索simhash值属于shSeti的代码块L,构成相似代码块集合:
LSeti={L:simhash(L)∈shSeti}|i∈[1,n]>
simhash(L)表示代码块L的simhash值;
(4)依据已构建的代码块与所在函数的倒排索引,检索相似代码块所在的函数P’,构成函数集合:
(5)对每个检索到的函数,计算该函数P’在待溯源函数P中的代码重合度,即该P’与P的相似代码在P中的占比,表示为iSim(P,P’),公式如下:
其中len(P)表示函数P的总指令数,len(Li)表示代码块Li的指令数,通过实验验证发现当函数的代码重合度不小于0.5时最有可能与待溯源函数代码相似,因此最终得出潜在相似函数集合为:
PSet={P’:iSim(P,P’)≥0.5} 【公式6】
若潜在相似函数集合PSet为空集,说明不存在与待溯源函数具有足够相似代码的函数,难以认定它们相似,待溯源函数在已有代码集上可认为是原创函数。
(6)若潜在相似函数与待溯源函数均仅有一个相似代码块,则判定为相似函数,若存在多个相似代码块时,只有当跳转关系相同时判定为相似函数。
本发明公开的基于simhash与倒排索引的复用代码快速溯源系统可用于快速溯源相似函数,判定是否为复用函数以及复用的样本,有助于提升恶意代码分析效率、复用关系的检测以及恶意代码同源判定。基于simhash与倒排索引的复用代码快速溯源系统主要由预处理模块、代码库构建模块与函数溯源模块3个模块组成。
系统结构如图4所示。系统具体实施步骤如下:
(1)预处理
1)对每个样本,做脱壳逆向反汇编处理获取汇编代码;
2)对每个汇编代码,依据特殊标识提取汇编代码中的所有函数;
3)对每个函数,依据跳转指令与跳转关系划分为多个代码块;
4)对每个代码块,做代码标准化处理并计算代码库的simhash值。
(2)代码库构建
基于海量样本,以及预处理后获取的函数、代码块、simhash值,构建包含三级倒排索引的代码库,由simhash值索引具有该simhash值的代码块,由代码块索引代码块所在的函数,由函数索引函数所在的样本。
(3)函数溯源
经过预处理模块,待溯源函数被划分为多个代码块,并获取了代码块的simhash值,首先基于代码库的simhash值检索代码库中的相似代码块,其次经相似代码库倒排索引到潜在相似函数,最后基于代码重合度与相似代码块间的跳转关系判定是否为相似函数。
机译: 用于在共享控制信道上对控制信号进行代码复用并与多个移动台共享控制信道的方法,以及用于对与多个移动台相关联的共享控制信道进行控制信号复用的代码复用方法
机译: 使用天线阵列的波束形成的cdma无线通信系统中的代码复用装置及其代码复用方法
机译: 使用天线阵列的波束形成的cdma无线通信系统中的代码复用装置及其代码复用方法