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

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个部分:建立控制流图邻接矩阵、基本块签名匹配和基本块边匹配。