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

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

节和第 4.2 节相关部分.
3.3 实验流程
如第 3.1 节所述,在本文的实验中将分别在一大一小两个数据集上对所提出的算法进行验证.
在 RQ1 和 RQ2 的实验中,我们随机选取了 Github 星数排名前 7 万个项目中的 200 个工程,对这些工程进
行筛选,仅仅保留代码文件.对于每一个工程,将其所有代码文件进行去空行、去注释、去空白符、全部转换为
小写处理后,分别计算 MD 5 值(将所有文件压缩到一行视作一个字符串进行计算)和改进前、改进后相似哈希
的值并连同代码文件的文件名、相对路径、所属工程名称和版本号以及文件的行数存储在一个文件中作为该
项目的信息文件,信息文件的每一行代表该项目中的一个代码文件.在相似性检测过程中,我们对前述 200 个工
程中的近 30 万个代码文件的 MD 5 值、改进前后的相似哈希值进行两两比对.对于 MD 5 的比对标准为,若两
个文件的 MD 5 相等,则判断两个文件相似;对改进前后两种相似哈希方法的比对标准为,若两个文件的海明距
离在阈值以内,则判断为相似.我们对相似哈希海明距离阈值为 0~8 的情况均进行了实验,结果如第 4.1 节所示.
在 RQ3 的实验中,为了验证改进后的相似哈希算法在实际大规模代码库上的检测效果,本文构建了大规模
开源代码指纹库.对 Github 上按星数降序排列的前 130 万个开源项目的不同版本进行了指纹计算和入库,根据
文件的 MD 5 值筛除同一项目不同版本之间的内容完全一致的冗余文件.构建的大规模库包含共计 6 244 310
个版本的开源项目,386 486 112 个项目文件,在数据存储上选用面向大数据的 Mongodb 分布式数据库.
由于文件数目巨大,为了加速检测速率,对所有文件进行索引和分表.
(1) 借鉴谷歌公司 Manku 等人 [17] 基于抽屉原理提出的索引优化方法,将每个文件的指纹值分为 5 段,长度
分别为 13、13、13、13、12,任意每两段进行组合作为一个字段存储到文件文档中,共有 10 个相应字段(1&2,1&3,
1&4,1&5,2&3,2&4,2&5,3&4,3&5,4&5),对每个字段建立索引以便快速检测到与待测指纹值距离 3 位以内的指
纹结果.
(2) 不同语言之间几乎不存在相似文件,为了进一步减少每次需要检测的候选匹配对,将获取到的文件信
息按文件语言进行分表,每次查询时按照待测文件的语言查询对应表.
在大规模库上的文件匹配同样分为通过 MD 5 匹配和通过相似哈希进行匹配.通过 MD 5 匹配时利用 MD 5
字段建立的索引搜索 MD 5 完全相同的文件,在通过相似哈希进行匹配时,先根据文件语言获取对应的表,再通
过分段索引的方法找到潜在的候选文件对,对候选文件对进行两两海明距离计算,距离在阈值内的视作相似.实
验结果如第 4.2 节所示.

4 实验结果与分析

4.1 对研究问题1的分析
随机选取 Github 星数排名前 7 万个项目中的 200 个工程并两两之间进行比较,相似哈希海明距离 [16] 阈值
取 8(即海明距离小于等于 8 的文件对视作相似文件对),实验数据以及各个指纹计算方法获取到的相似文件对
结果见表 4,其中,改进前的相似哈希方法是指仅筛选纯符号行且以行为特征粒度的相似哈希方法,改进后的相
似哈希方法是指根据文件所属语言筛除指定常见行且以行为特征粒度的相似哈希方法,错误匹配对数是指所
有检测出的文件对中根据第 3.2 节给出的判别方法判别实际为不相似的文件对数,精确度是指通过该判别方法
判别为相似的文件对数占检测出文件对总数的百分比.
Table 4 Experimental results of RQ1
表 4 RQ1 的实验结果
相似文件对 与 MD 5 的交集文件对数 错误匹配对数 精确度(%)
MD 5 21 879  0 100
相似哈希-改进前 8 923 644 21 858 8 816 731 1.20
相似哈希-改进后 40 082 21 862 67 99.83

从实验结果可以看出,无论是改进前还是改进后的相似哈希算法,其匹配结果都能够基本上完全覆盖 MD 5