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

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

综上所述,本文针对行粒度相似哈希算法在实际工程上暴露的问题对相似哈希计算过程中的特征提取功
能进行优化,通过对 Github 上著名开源项目的统计,构建不同语言的相应常见行列表并组成常见行列表库.在获
取相似哈希特征时使用对应语言的常见行列表进行特征筛选,以消除常见重复行对其他行的覆盖.

3 实验设计

为了全面评价改进后的相似哈希方法是否在真实数据集上有较好的检测效果,本文设置了以下 3 个研究
问题,对改进前的相似哈希方法、改进后的相似哈希方法、MD 5 方法以及文件名匹配的方法进行了对比和分
[2]
析.其中,改进前的相似哈希方法是指 Zhu 等人 提出的基于行粒度提取特征且仅筛选纯符号行的相似哈希方
法,改进后的相似哈希方法是指本文提出的基于行粒度提取特征并根据语言筛选常见行的相似哈希方法.
 RQ1:在真实工程构成的数据集上,改进后的相似哈希检测方法与改进前相比能否展现出更佳的效果?
 RQ2:简单匹配同名文件能否达到与本文方法相近的效果?
 RQ3:改进后的相似哈希方法在大规模数据集上的表现如何?
[9]
在本文的实验设计中,未与现有其他大规模代码相似性检测工具,如 SourcererCC 进行比较.其主要原因
如下.
(1) 目前的相似性检测工具多以方法、函数为检测粒度,本文算法的检测粒度为文件级别.在 Sourcerer
[8]
[9]
CC 、CCAligner 等工具上广泛采用的数据集 BigCloneBench [26] 同样是基于函数粒度的,因此无法将本文的算
法直接运用于该数据集上.
(2) 本文提出的算法与其他相关工具的目标有所不同.本文的算法目标是在更大规模的数据量场景下实现
粗粒度、高效率、高精度的文件相似检索,现有方法大多在小规模数据上获取更加细粒度、深层次的相似检测.
现有的能够适应大规模数据的工具大多采用基于 token 的方法,采用的数据集量级最大为 BigCloneBench 的
IJaDataset,包含 25 000 个开源工程,共计 300 万文件.而本文的数据集包含 130 万个开源工程,共计约 3.8 亿代码
文件,远大于现有数据集量级.

3.1 实验数据集
为了验证改进后的相似哈希方法在实际工程同源检测中的有效性,本文按照 Github 星数排名的顺序选取
了较前位置的若干开源项目作为本文实验的数据集.这些评测对象是 Github 上比较著名的开源项目,代码规模
较大,项目活跃时间较长,影响范围较为广泛,且覆盖了不同类型的应用领域,如比特币 bitcoin、文本编辑器 vim、
图片处理工具 ImageMagick 等,因此具有一定的代表性.
在 RQ1 和 RQ2 的实验中随机选取了 Github 星数排名前 7 万个项目中的 200 个,并获取它们最新版本的源
代码作为数据集,共计约 100 万个文件.将这些文件按照后缀名进行筛选,仅保留第 2.3 节中统计过的相关常见
行的 10 种语言的源代码文件作为本次实验的研究对象,筛选后共计 297 210 个.
在 RQ3 的实验中构建了大规模的代码知识指纹库,按照星数排名的降序将 Github 上的项目进行入库,目前
共入库 1 320 663 个项目的共计 6 244 310 个版本,预处理的方法与上述一致.由于空文件和极小的代码文件包
含的语义信息较少,在同源分析中的重要性较低,本次实验对可执行行数小于 15 行和相似哈希指纹值等于 0 的
文件进行了筛除.
3.2 评测指标
为了论证相似哈希改进前后的检测精确程度,本次实验设计了与代码文件行成分相关的精确度度量指标,
以用于实验中对几种方法的精确度度量.首先对匹配文件对进行去空行、去空格、去注释的预处理,然后分别
获取两个文件的行序列,并根据两文件行序列匹配的结果判定文件是否相似,判定标准如下.
任意满足以下两个条件之一即可判断两个文件相似.
(1) 两文件行序列共同行数/文件 1 文件行数≥50%且两文件行序列共同行数/文件 2 文件行数≥50%.
(2) 两文件行序列共同行数/文件 1 文件行数≥70%或两文件行序列共同行数/文件 2 文件行数≥70%.