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

时间：2025-04-21

崔宝江,等: 基于基本块签名和跳转关系的二进制文件比对技术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