Page 328 - 《软件学报》2021年第7期

2246 Journal of Software 软件学报 Vol.32, No.7, July 2021

码段的行数进行索引,第 2 层中根据二进制哈希值中 1 的位数进行索引.通过这样的索引方式,加速聚类过程中
获取相邻节点的速度.Qiao 等人 [23] 也将相似哈希用于二进制同源检测中,他们将二进制文件进行反编译,以汇编
代码中的函数为单位,计算出每个函数标准化后的 simhash 指纹值,并建立两类优化索引.郭颖等人 [24] 认为,以词
的频率为特征在代码克隆检测领域的效果不尽人意,于是结合数据消重中的基于内容可变长度分块(content-
defined chunking,简称 CDC)思想和 simhash 算法思想,把源代码转换为词法单元序列,并采用 CDC 分块将词法
单元序列分块并计算出指纹值.在这一方法中,并未直接采用 simhash 算法计算指纹,而是借鉴了 simhash 算法的
思想,将所有代码文件的哈希值序列从大到小进行排序,并依次检查两个序列中每一个哈希值是否相同,如果两
[2]
个文件的哈希序列有超过某个百分比以上的哈希值是相等的,则聚为一类.Zhu 等人 指出,由于代码中经常会
出现重复词,以词粒度来获取代码相似哈希特征容易出现高频的特征把低频的特征覆盖掉的现象,于是提出以
代码行为粒度进行特征累加,并且在预处理中筛除了纯符号行和空行,对相似哈希在代码检测方面的应用作了
进一步改进.
2 一种改进的相似哈希代码克隆检测方法

2.1 传统相似哈希方法与行粒度相似哈希方法的提出
相似哈希算法能够将一个文档转换成一个指定长度的二进制数,即当前文档的指纹.指纹的长度通常取决
于计算过程中采用的哈希算法输出值的长度.
相似哈希算法主要分为 5 个基本步骤.
(1) 特征提取:根据数据的特点进行特征提取,对于文本类数据常采用分词结果、文档关键字、文档标签等
作为特征,对于视频类数据可以提取时空特征,对于网页可以提取超链接作为特征等.在提取特征的同时给每个
[3]
特征赋予一个权重,在文本数据集中常用词频或 TF-IDF 方法来获取权重,亦可结合不同数据集的特征设计不
同类型的权重值.
(2) 哈希:这一过程通常采用各种传统哈希算法将上一过程中的各个特征转化为哈希值.
(3) 加权:结合步骤 2 生成的各个特征的哈希结果与其权重生成加权字符串,哈希值每一位的 0 或者 1 决定
了其与权重值是正相乘还是负相乘.
(4) 累加:将上一步骤中所有特征的加权结果按位累加,得到结果序列串.
(5) 降维:对加权求和获得的结果序列串进行变换.序列串中,每一位的值若为正数,则变换为 1,否则,变换为
0,得到了最终的相似哈希指纹值.
我们主要通过海明距离(Hamming distance) [16] 对指纹的相似性进行比较.两个指纹值对应的二进制数(01
串)取值不同的位的数量称为这两个指纹的海明距离.对于二进制字符串 a 和 b,海明距离等于 a XOR b 运算结
果中 1 的个数.
在 Uddin 等人 [21,22] 提出的 SimCad 工具中,大规模软件系统的源代码被拆分为多个小代码块,每个代码块采
用空格分割的方法计算出对应的相似哈希指纹值,通过聚类算法获取到大规模软件系统中相似的代码块簇.虽
然该工具仅用于单个软件系统内部的相似代码发现,无法应用于大规模代码相似性检测,但其通过实验验证了
相似哈希在软件代码相似性检测中应用的可行性.
在将相似哈希应用到基于大规模代码库的同源分析过程中时,由于数据规模的庞大有时采用单个代码文
[2]
件作为生成指纹的单位.Zhu 等人 发现,若以词为特征粒度来获取源代码文件的相似哈希指纹值,则会出现词
频较高的词将词频较低的词覆盖的现象.由于代码数据集的特殊性,某一个词在代码文件中可能会频繁出现,若
采用传统的分词方法直接对源文件进行分词,高词频词对结果的影响将会非常显著,甚至出现指纹结果完全等
同于某一个词的哈希值的情况,显然这样的问题会带来很高的误报率.尽管源代码文件中可能会出现大量相同
的词,但行与行之间的语义是较为独立的,同一个文件内不容易出现大量相同内容的行.因此,他们开始尝试以
行作为特征提取的粒度.为了避免一些大量而无意义的行对算法结果的影响,该方法使用正则表达式对每行的
字符串进行筛选,筛除不包含任何字母或数字的纯符号行或空行.最后得到改进后的相似算法,如图 2 所示.算法