基于基本块签名和跳转关系的二进制文件比对技术

ISSN 1000-0054

CN 11-2223/N

清华大学学报(自然科学版)J T sing hua Un iv (Sci &Tech),2011年第51卷第10期

2011,V o l.51,N o.1022/251351-1356

基于基本块签名和跳转关系的二进制文件比对技术

崔宝江1,2

, 马 丁1

, 郝永乐2

, 王建新

3

(1.北京邮电大学计算机学院,北京100876; 2.中国信息安全测评中心,北京100085; 3.北京林业大学信息学院,北京100083)

收稿日期:2011-08-30

基金项目:国家自然科学基金资助项目(61170268;90818021)作者简介:崔宝江(1973 ),男(汉),山东,副教授。

E -mail:cuib j@

摘 要:基于基本块签名和跳转关系的二进制文件结构化比对技术,对已有的二进制结构化比对算法进一步改进,提出一种基于基本块签名和基本块之间跳转关系的函数控制流图比对算法。即首先提取二进制文件反汇编后的函数控制流图信息,然后对图中的基本块进行签名匹配,在签名匹配的基础上再进一步利用邻接矩阵进行边匹配,最后利用匹配的基本块计算函数相似度和文件相似度,并开发出比对工具BinCompae 。研究结果表明:相对于源码比对工具和几个常用的二进制补丁比对工具,针对常见的代码抄袭方式,BinCompae 均能检测出99%以上的相似度;此外,BinCompare 还能检测出语义不变,代码形式改变的抄袭方式。因此,基于基本块签名和跳转关系的结构化比对算法针对二进制文件比对具有很高的准确性和实用性。

关键词:二进制文件同源性检测;基本块签名;基本块跳转

关系;函数控制流图

中图分类号:T P 309

文献标志码:A

文章编号:1000-0054(2011)10-1351-06

C omparison of executable objects based on block signatures and jump relations

CUI Baojian g 1,2,MA Din g 1,H AO Yongle 2,WA NG Jianxin 3(1.Sch ool of Computer Science and T echnology,Beijing University of Posts and Telecommunications,Beijing 100876,China;2.China I nformation Technology S ecurity Evaluation Center,

Beijin g 100085,China;

3.School of I nformation Science and Technology,Beijing Forestry University,B eijing 100083,China)

Abstract:Th e pap er describes graph -based com paris on of executable ob jects bas ed on block signatures and ju mp relations.This pap er d escribes an algorithm combining basic b lock signatures and basic b lock jum p r elations.Th e algor ith m develops th e fu nction control flow graph after disass embly,then match es the block signatures and furth er matches the block s using an adjacency m atrix.The algorithm finally calcu lates the function an d file s imilarity usin g a comparison tool.T ests dem onstrate that th e algorithm can d etect m ore than 99%of commonly us ed s ou rce code plagiarisms an d similarities,b etter than s ource code comparison tools and several executable patch comparison tools.The algorithm can also detect cases w ith th e sam e seman tics,but different expressions.T hus,the graph -bas ed

comparis on algorithm based on the block sign atures and jum p relations is accu rate and effective in comparing executable objects.Key words:ex ecu table objects h om ology comparison;block

signature;block jum p relation ;function control flow

graph

随着计算机技术的飞速发展和互联网的广泛应用,软件抄袭现象愈演愈烈;因此抄袭检测和版权保护对软件同源性鉴别提出了迫切的要求。目前,针对软件同源性的静态检测手段主要有源码检测[1-2]和二进制文件检测。前者已经有相对比较成熟的技术和工具,其优点是程序的全程信息比较完整、检测技术难度较低、检测结果准确性较高。缺点是很多软件的源代码难以获得,这种情况限制了基于源码的同源性检测技术的广泛应用。在不能获得源代码的情况下,基于二进制的软件同源性检测技术就显得尤为重要。二进制代码作为软件的最终表现形式,软件的发布必定是带有二进制的可执行程序,即使是以源代码的形式发布也可以编译为二进制可执行程序,因此基于二进制的软件同源性检测技术具有广泛的实用性。

目前常用的二进制文件比较方法有:二进制字节的比较、基于反汇编后文本的比较、基于汇编指令的比较和基于结构化的比较。二进制字节的比较和基于反汇编后文本的比较只适用于文件有少量变化的情况,没有语义分析,缺乏对程序逻辑的理解;基于汇编指令的比较[3]受编译器编译优化的影响。H alv ar Flake 首次提出基于结构化比较的方法[4]

,即通过比对文件中函数的控制流图来判断函数是否同构,进而建立函数之间的一一对应关系。

1352 清华大学学报(自然科学版)2011,51(10)

之后,很多研究机构对此算法做了一系列改进。例如Dullien 等[5]引入了基本块属性的概念,并增加了属性的划分。魏强等[6]改进图的重构方法,提出了增加启发式匹配方法来发现在固定点初始化和传播过程中可能出现的错误匹配关系。基于可信基点的结构化签名比较算法[7]增加了函数新属性的划分,进而更细致的刻画函数以提高准确性;同时还提出了采用父子关系启发式策略对匹配过程的中的错误进行校验,但只是提示人工进行校验,并未提出相应的算法。一种层次化的安全补丁比较技术[8]对函数引入了函数控制结构签名。一种基于签名和属性的可执行文件比较[9]

在函数、基本块和指令级别上设计了一系列的签名,并提出了融合签名和属性的函数匹配算法、基本块匹配算法;提出了邻接矩阵的概念,但邻接矩阵的应用仍受指令顺序的影响。

函数控制流图以基本块为节点,以基本块之间的跳转关系为边。因此,在比对过程中需要综合考虑这2方面因素。由上可知,目前国内外的二进制文件比对相关的理论中,很少有能有效的结合这2方面的研究;同时,由于应用于软件抄袭检测的二进制文件比对技术特有的困难性和复杂性,目前更是少有相关的检测工具。

本文针对二进制文件同源性检测,提出基于基本块和基本块之间的跳转关系的理论来检测相同基本块,即先比对2组基本块的签名;在此基础上,通过邻接矩阵判定基本块的跳转关系。根据基本块之间的跳转关系,以得出函数相似度和文件相似度。

1 基于基本块签名和跳转关系的二进制文

件同源性比对算法

1.1 算法概述

对w indo ws 系统中PE 格式的二进制可执行程序进行同源性比对技术研究,在没有源代码的条件下分析出二进制文件的同源性。

为了对二进制文件进行同源性比对分析,首先对二进制文件进行反汇编,提取二进制文件反汇编信息,然后对反汇编信息进行基于基本块签名和基本块跳转关系的函数控制流图比对以计算函数相似度,进而得到文件相似度。上述算法总体上包括提取二进制文件反汇编信息、函数控制流图比对、函数相似度计算以及文件相似度计算等几个主要部分,如图1所示。具体算法细节将在下面各小节中展开

描述。

图1 算法流程图

1.2 提取二进制文件反汇编信息

基于二进制的软件同源性检测虽然以二进制文件为检测分析对象,但是直接在二进制机器码上进行分析检测显然是不现实的,必须将二进制机器码转变成对人们更加友好的形式才能更好的加以分析。在IDA 等反汇编工具软件的基础上,对输入的二进制可执行程序进行反汇编;并利用自主研发的IDA 插件导出基本块-函数对应表、函数基本信息表、基本块信息表、基本块跳转关系表等反汇编信息存储到数据库中。二进制文件经过反汇编后,可执行代码会按区块划分为多个子函数,一般情况下,每一个子函数都能完成一项独立功能。也就是说,2个文件之间的子函数相同则可以反映出2个文件的部分功能相同,从而对其同源性做出有效判断。

1.3 函数控制流图比对

经过反汇编、信息提取后,二进制文件转变为一系列的函数控制流图。每一个函数对应一个控制流图,图中每个节点对应函数中的基本块,节点之间的连线对应基本块之间的跳转关系。传统的二进制分析算法往往只针对基本块进行比较而忽略基本块之间的跳转关系。事实上,单个基本块信息量非常少,单纯的对比基本块很容易造成误判。因此,本文提出了基于基本块签名和基本块之间的跳转关系的函数控制流图比对方法。整个比对过程分为以下3个部分:建立控制流图邻接矩阵、基本块签名匹配和基本块边匹配。

崔宝江,等: 基于基本块签名和跳转关系的二进制文件比对技术1353

1)建立控制流图邻接矩阵

这一步目的是将函数内部基本块之间虚的跳转

关系转化为实的数据,使用邻接矩阵来记录基本块

之间的跳转关系。所谓邻接矩阵,就是根据函数内

部的基本块而创建的矩阵,矩阵内部每一个元素代

表着其横纵坐标所对应的基本块之间的跳转关系。

邻接矩阵的具体建立步骤如下:

a)设有函数A,其内部包含有n个基本块,那

么首先建立一个n n的矩阵M atrix(A),并将其中

所有的分量初始化为0,即

M atrix(A)=0

0 0n n

.(1)

b)遍历基本块跳转关系表,假设第i个基本块到第j个基本块存在跳转关系(0<i n;0<j n;

i j),则将矩阵Matrix(A)中第i行、第j列的元素a ij的值置为1,即

a ij=1,基本块i到基本块j有跳转0,基本块i到基本块j无跳转

(0<i n;0<j n;i j).

遍历完毕后的矩阵Matrix(A)就是函数A的邻接矩阵

M atrix(A)=

0a12a13 a1n

a21

a n1 n n

. (2)

邻接矩阵很好地反映了函数中基本块之间的跳转关系,可以根据矩阵中的分量来判断函数中任意2个基本块之间是否存在跳转关系。

2)基本块签名匹配

采用基本块的H ash值作为基本块的签名。基本块的H ash的计算基于基本块内部反汇编后的汇编指令,采用小素数乘积法来计算基本块H ash。

对每一个基本块中的每一条汇编指令的助记符分配一个小素数,然后对整个基本块中的所有的素数求乘积。因为其乘积的唯一性,所以如果2个基本块的乘积相同,则其指令集合是相同的,而不管其指令顺序如何改变。将这个乘积作为基本块的Hash,就可以忽略因编译器优化而带来的指令顺序改变。素数乘法是高开销的,乘积增长的非常快,对于大的基本块,可能会发生溢出,因此将乘积与264取模。2个Hash相同的基本块标记为基本H ash值匹配。

3)基本块边匹配

在基本块H ash相同的基础之上,进一步对其跳转关系进行判断,如果2组H ash相同的基本块存在一致的跳转关系,则说明这2组基本块满足边匹配判定,属于相同基本块。边匹配的具体实现过程如下:

a)假设源函数A,基本块数为n;目标函数B,基本块数m。对A、B基本块中H ash匹配相同的基本块对进行双重遍历。

b)对基本块对进行边判定,方法为利用邻接矩阵判定两组H ash相同的基本块之间是否存在一致的跳转关系,如存在则判定为边相同。

假设任意一次循环中,H ash匹配的基本块对分别是(A i1,B j1)和(A i2,B j2)(A i1、A i2、B j1、B j2分别是A、B内部的基本块)。则分别在A、B的邻接矩阵Matrix(A)、Matrix(B)中查看其分量a i1,i2和b j1,j2的值,如果两者都等于1,则说明A i1到A i2,B j1到B j2之间都存在跳转关系。也就是说这2组基本块在H ash值相同的基础上还存在一致的跳转关系,因此可以认为这2组基本块对满足控制流图匹配。

c)统计满足控制流图匹配的基本块对数,用于计算函数相似度。

1.4 函数相似度计算

确定了匹配的基本块后,进行函数相似度计算。具体计算公式如下:

S func=

N same

N sample

.(3)

其中:S func是函数的相似度;N same和N sample分别是样本文件和目标文件中相同的基本块数量和样本文件总的基本块数量。

1.5 文件相似度计算

遍历比对双方的全部函数,计算所有函数间的相似度;然后再次遍历样本函数,选出每个样本函数所对应的所有目标函数相似度中的最大值。

假设样本文件和目标文件中各有N1、N2个函数。那么对于样本函数中的任意一个函数F,理论上该函数和目标文件中所有函数依次进行比

对后会产生N2个结果:[F1,F2, ,F N

2

],其中F i(0 i N2)表示函数F和目标文件中函数F i 的相似度。事实上,并不需要所有结果,而只需关注这些结果中的最大值,所有最终函数F最大相似度为:

F sim=M AX[F1,F2, ,F N

2

] 100%.(4) 在得到样本文件中所有函数的相似度后,计算文件整体相似度,即

1354

清华大学学报(自然科学版)2011,51(10)

S file= (F sim[i] F val[i])

F val[i] 100%

(0 i N1).(5)

其中:F sim[i]是样本文件中每个函数的最大相似度,F val[i]是该函数的权重,S file为文件整体相似度。

早期的二进制比对算法大多数忽视函数之间的个体性差异,将所有的函数无差别处理,仅仅对函数个数进行统计。这种做法存在很大的偏差,不同的基本块、函数之间差异很大。为了体现不同函数之间的差异,引入函数权重这一概念,用于表示函数在当前文件中所占的 比重 。函数权重计算公式如下:

F val=F2nod+F2edg+F2call,(6)其中:F2nod、F2edg、F2call分别是函数的内部基本块数量,内部基本块跳转数量和内部子调用数量。

2 试验结果及分析

由于应用于软件抄袭检测的二进制文件同源性比对工具的稀缺,本文把自主研发的BinCompar e 工具与文[1]中的针对源码检测的CodeCom pare工具以及Patchdiff2、BinDiff2等二进制补丁比对工具进行比较。

2.1 BinCompare与源码比对工具比较

1)针对源码常见抄袭情况的检测

针对源代码中语句顺序变换、变量名变换、变量顺序变换、变量类型变换、函数名变换等情况,各构建一组测试用例。然后用源码比对工具CodeCom pare得出每组测试用例的源码语法比对相似度、源码文本比对相似度;用BinCompare得出每组测试用例编译生成的二进制文件比对的相似度。例如针对源代码中语句顺序变化的情况部分测试用例如图2。

lo ng f1,f2; int i;

int i;long f1,f2;

f1=f2=1;f1=f2=1;

图2 源代码中语句顺序变化情况的部分测试用例

针对上述常见抄袭情况,采用源码比对工具CodeCom pare的语法比对和文本比对技术以及采用二进制比对工具BinCom pare,对文件的相似度测试结果如表1所示。

表1 针对不同测试用例的文件相似度比对结果

测试用例源码语法比对/%源码文本比对/%二进制文件比对/%语句顺序变化10085.7100

变量名变换10065.8100

变量顺序变换10094.199.7

变量类型变换10095.3100

函数名变换10080.899.7

表1的测试结果表明:针对上述源码常见抄袭情况,二进制比对工具BinCompare与源码比对工具CodeCompare的源码语法比对技术相比,两者检测的文件相似度基本相同。与Co deCompar e的源码文本比对技术相比,二进制比对工具BinCompar e 的准确度更高。

2)针对语义不变,源码表现形式变化的检测

软件抄袭行为中,包括一些通过改变源代码的语句形式,从而实现语义不变的抄袭手段。例如,将for循环用w hile循环替换;又如,在源码for 循环中增加冗余代码,从而改变语法和文本特征,但不改变语义。针对语义不变,源码表现形式变化的情况,源码比对工具从语法和文本的相似性匹配角度进行分析,因此难以进行准确的检测。而由于编译器优化原理,针对语义不变、源码表现形式变化的情况,二进制文件比对技术可以进行准确的比对。本文以for-w hile替换以及在源码for 循环中增加冗余代码为例,对二进制文件比对技术进行检测。

Whiletest.cpp和fortest.cpp是2个具有相同功能的源码文件;不同之处在于,在w hiletest.cpp 中,w hile循环代替了fortest.cpp中的具有相同功能的for循环,如图3所示,采用源码比对工具CodeCom pare和二进制文件比对工具BinCompare 进行文件相似度测试,其相似度测试结果如表2所示。

崔宝江,等: 基于基本块签名和跳转关系的二进制文件比对技术1355

fo r(i=1;i<=20;i++)i=1;

{printf("%12ld%12ld",f1,f2);while(i<=20)

if(i%2==0)printf("\n");{printf("%12ld%12ld",f1,f2);

f1=f1+f2;if(i%2==0)pr int f("\n");

f2=f1+f2;f1=f1+f2;

}f2=f1+f2;

i++;

}

图3 f ortest.cpp中的for循环代码和whiletest.cpp中的while代码

表2 针对f or-while替换、for循环中增加冗余代码的相似度比对结果

测试用例源码语法比对/%源码文本比对/%二进制文件比对/%

for-w hile替换14.2968.899.22 for循环中增加冗余代码5096.9100

Addcomm ent.cpp和addco mment2.cpp同样是具有相同功能的2个源码文件;不同之处在于, addcomm ent2.cpp在addco mment.cpp的for循环中增加了一行不影响文件功能的冗余代码,如图4 所示。采用源码比对工具CodeCom pare和二进制文件比对工具BinCompar e进行文件相似度测试,其测试结果如表2。

综上可知,与源码比对技术相比,针对for-w hile

fo r(i=0;i<5;i++)for(i=0;i<5;i++)

{pr intf("\n please input N o.%d scor e:\n",i);{printf("\n please input No.%d sco re:\n",i); printf("stuN o:");flo at a,b,c;

scanf("%s",stu[i].num);pr intf("stuN o:");

scanf("%s",stu[i].num);

图4 addcomment.cpp和addcomment2.cpp中的部分代码

替换以及在源码for循环中增加冗余代码等语义不变,而源代码表现形式变化的抄袭情况,二进制比对技术的相似度检测准确度更高。

2.2 BinCompare与二进制补丁比对工具比较

Patchdiff2和BinDiff2是常见的2种二进制补丁比对工具。其中,Patchdiff2主要采用指令循环冗余校验和块地址信息技术;BinDiff2主要采用基本块结构化签名技术。为了检测本文提出的基于基本块签名和基本块之间跳转关系的二进制文件同源性检测技术的优略性,下面把BinCpmpar e与Patchdiff2、BinDiff2等几个二进制补丁比对工具进行比对。

为了进行更广泛的比较,本文构建了针对源代码中语句顺序变换、变量名变换、变量顺序变换、参数顺序变换、参数名变换、变量类型变换、函数名变换等情况的测试用例;然后把每组测试用例编译生成二进制文件,用以上二进制文件比对的工具分别进行文件相似度的比对实验,测试结果如表3所示。

表3 针对不同类型的测试用例BinC ompare与

二进制补丁比对工具的相似度比对结果/%

测试用例Patchdiff2BinDiff2BinCo mpar e 参数顺序变换86.3695.65100

变量名变换86.7695.74100

变量顺序变换86.7695.7499.7

参数顺序变换86.7695.7499.5

参数名变换73.38736.18100

函数名变换86.7690.4399.7

变量类型变换87.1495.83100

for-w hile替换86.3695.6599.22 for循环中增加冗余代码86.3695.65100

由表3可知,与几个常用的二进制补丁比对工具比较,基于基本块签名和基本块之间跳转关系技术的BinCompare对上述测试用例进行二进制文件同源性比对得出的相似度准确性更高。

3 结 论

为了研究应用于软件抄袭检测的二进制文件同

1356

清华大学学报(自然科学版)2011,51(10)

源性比对技术,本文提出了基于基本块签名和基本块之间的跳转关系的二进制文件同源性比对算法,在检测基本块签名和基本块之间跳转关系的基础上,分析函数、文件的整体相似度,并开发了二进制文件同源性比对工具BinCo mpar e。针对常见的软件源码抄袭情况,二进制文件同源性比对技术与基于语法树的源码比对技术相比,具有基本相同的准确性;但针对语义不变、代码形式变化的抄袭情况,二进制文件同源性比对技术与源码比对技术相比,具有更高的准确性。与Patchdiff2和BinDiff2等二进制补丁比对的工具相比,基于基本块签名和基本块之间跳转关系的二进制文件同源性比对技术具有更高的检测准确性。

为了进一步优化和提升二进制文件同源性比对技术的准确性,本文后续将在理论和技术方面继续改进,增加更多合理要素以更准确标记一个基本块的签名以及考虑多阶的跳转关系以更准确地反映控制流图信息等。

参考文献 (References)

[1]CU I Baojiang,LI Jians ong,GUO T ao,WANG Jianxin,M A

Ding.Code comparison system bas ed on ab stract syntax tree

[C]//Proceedings of4th IEEE International Conference on

Broadband Netw ork&M ultim edia T echnology.Beijing,

C hina:IEEE Pres s,2010,668-673.

[2]T oshihiro Kamiya,S hinji Kusum oto,Katsuro Inoue.

CC Fin der:A m ultilinguistic tok en-based code clone detection

s ystem for large s cale source code[J].IE EE T ransactions on

S of tw ar e Eng inee ring,2002,28(7):654-670.[3]Sabin paring bin aries w ith grap h isomorphis m

[Z/OL].(2011-06-20),/publish/ papers/comparig-binaries.html.

[4]H alvar Flake.Structu ral comparison of executable ofobjects

[Z/OL].(2011-06-20),h ttp://w w w.s ab /

files/dimva_paper2pdf.

[5]T homas Dullien,Rolf Rolles.Graph-based com paris on of

ex ecu table objects[Z/OL].(2011-06-20),http://w w w.

sabre-s ecu /files/BinDiffSS TIC05.pdf.

[6]魏强.结构化签名和签名结构化[Z/OL].(2011-06-20),

http://w w w.xfocus.n et.

WE I Qian g.S tructured signature and sign ature structu ralized.[Z/OL].(2011-06-20),http://ww w.xfocus.

net.(in Chinese)

[7]魏强,金然,王清贤.基于可信基点的结构化签名比较算法.

计算机工程与设计[J].2007,28(24),5850-5853.

WE I Qiang,JIN Ran,W ANG Qin gxian.Stru ctural signature com paris on algorithm based on credible nodes[J].

Comp ute r Eng ine ering and Design,2007,28(24),5850-

5853.(in Ch ines e)

[8]刘光宏,吴刚,章文,朱明,帅建梅.一种层次化的安全补丁

比较技术[J].小型微型计算机系统,2008,29(11),2065-

2069.

LIU Guangh on g,WU Gan g,ZHANG W en,et al.A k ind of hierar chical patch technology[J].Mini-M icro Comp uter S ystem,29(11),2008.(in Chines e)

[9]傅建明,乔伟,高德斌.一种基于签名和属性的可执行文件

比较[J].计算机研究与发展,2009,46(11):l868-

1876,2009.

FU Jianming,QIAO W ei,GAO Deb paris on of ex ecu table codes based on signatu re and property[J].

Comp ute r Resear ch and Dev e lop ment,2009,46(11):l868-

1876.(in Ch ines e)

本文来源：https://www.bwwdw.com/article/azl4.html