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

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]

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