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

李玫 等:面向代码相似性检测的相似哈希改进方法 2247

将源代码文件以行为粒度进行切分,并对得到的行序列进行筛选和预处理.然后,对每一行进行传统哈希值计算
并映射为一串由 1、–1 组成的序列.接着,对每一行的映射结果进行逐位累加,得到一个有符号数的序列.最后,
对序列进行降维,得到改进后的相似哈希指纹结果.

Fig.2 Simhash algorithm with line granularity
图 2 行粒度相似哈希方法
2.2 大规模数据集下行覆盖现象及分析
[2]
本文对上述提到的行粒度相似哈希检测方法 进行了复现,并在实际工程代码上进行了一系列的实验.尽
管行粒度的代码特征提取算法在理论上一定程度地解决了词粒度特征提取算法中的词覆盖问题,但在实际的
检测与实验中发现,行粒度提取方法仍会出现一些特殊的高频次特征对低频次特征的覆盖情况.经过实验分析
和统计,行覆盖现象主要出现在以下两种情况中.
 在代码中频繁出现的一些包含关键字的代码行,例如“break”“return;”“try{”.在某些情境下,这些行出现的
频率非常高,以至于它对结果的影响覆盖了所有其他行的影响.
 由于代码功能的特殊性(如一些表示信息提示的工具类或测试类),在代码中会频繁出现一些功能性行内
容,例如对某一种方法的频繁调用、在多个方法里实现传递同一信息的功能等.
在以上两种情况中,后者的覆盖现象可以视作是文件代码功能单一性的体现,所以本实验中具有大量重复
相同方法的两个相似代码文件对不算作在代码相似度量过程中的误报.第 1 种情况中这些代码行的大量出现
不能特征性地代表代码文件的功能,因此会对结果的准确性带来较大影响.
针对行覆盖现象,如果单纯地将文件里频繁出现的行的权重降低,可能会将第 2 种情况中重复调用方法的
行对指纹的影响减弱,无法体现文件的特殊功能,造成此类文件的漏报,因此本文选择从不同语言常见行的消除
这一角度出发来降低行覆盖问题对结果的影响.

2.3 针对语言的行筛选优化方法
[3]
TF-IDF 是一种广泛应用于数据挖掘和信息检索的加权算法,其中,TF(term frequency)是指词频即单词在
文档中出现的频次,IDF(inverse document frequency)是指逆向文档频率.其主要思想为一个词在一篇文章中出
现的频率越高,且其在其他文章中出现的次数越低,说明这个词具有较好的区分能力,应该赋予它更高的权重.
第 2.2 节中提到的第 1 种行覆盖现象通常出现在一些由于代码的特殊语法结构而频繁出现的行上,这些行在大
量的代码文件中广泛存在,但包含的语义信息有限,且对代码文件之间的区分起到的作用极小.在现有的相似哈
希方法中,高频行在计算特征时以出现的频次为权重,即体现了 TF 的信息,但是对于行的 IDF 信息并没有相应
的体现.对此,我们对代码中出现的常见重复行进行了统计与分析,并结合统计结果创新性地提出了分语言行筛
选优化方法.
为了排除由于代码的特殊语法结构而频繁出现的一些代码行对结果的影响,本文收集了 Github 上面按星
数排行 Top 300 的工程项目作为统计来源,这些排名靠前的项目具有规模较大、影响范围较广、结构较规范等
特点.根据后缀名筛选出其中的代码文件,并进行去空行、去行内空格、去注释等预处理步骤,对得到的结果中
的代码行进行了统计,获取到常见重复行列表,部分结果见表 1.