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

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

行对结果的影响被覆盖.因此,假如有 n 个文件内部多次出现“returnfalse;”,则这些文件两两之间均会被识别为
相似文件对,总计 n(n–1)/2 对假克隆对.误报文件对个数与出现行覆盖的文件个数的平方成正比,因此数据规
模越大,越容易出现大规模的误报,精确度也随之越低.而本文通过常见行筛选改进后的相似哈希方法则能够很
好地解决这一问题,在大规模数据集上也能够保持较优的效果.
在本文的实验中,测试了不同海明距离下相似哈希算法结果的精确度,整体趋势均为随着海明距离阈值的
逐渐增加,精确度逐渐降低.在两个文件指纹值进行比较的过程中,海明距离越大,意味着两个指纹不同位数越
多,两个文件也就越不相似.当阈值较小时,只有非常相近的指纹才被视作相似,因此精确度比较高,但是会将一
些海明距离较大的相似文件对遗漏,导致漏报增多;当阈值逐渐增大、相似性判断的条件更加宽松时,更多的文
件会被判断为相似,因此可能出现一些本来不相关的文件被判断成相似的情况,导致精确度降低.在不同的实
际应用场景下,对误报、漏报的容忍度各不相同,需要对误报和漏报加以权衡,结合具体需求选择合适的海明
距离阈值.
5 总结与展望

目前,日益庞大的软件系统规模和高速增长的开源代码数量对代码克隆检测工具的高效性和可扩展性带
来了更高的挑战.对软件代码的相似性分析可以帮助开发者识别和管理软件系统中的开源代码组件,提高软件
质量,降低开发和维护的成本.本文对基于行粒度相似哈希的代码相似性检测算法进行了实验验证和分析,通过
分语言常见行筛选的方法对出现的行覆盖现象进行了优化.本文提出的改进后的相似性检测方法将源代码文
件降维成一个 64 位二进制字符串,能够实现代码特征的快速生成以及匹配,不需要额外的基于词法、语法的代
码分析工具辅助,且在不同语言上的迁移成本极低,可移植性强.
通过一系列的实验,对比了改进前后的相似哈希方法、普通 MD 5 方法以及仅靠文件名匹配的方法在相似
代码文件检测上的效果.无论是改进前还是改进后的相似哈希算法,其匹配结果都能够基本上完全覆盖 MD 5
的匹配结果,改进后的相似哈希方法在各个海明距离 [16] 阈值上都能保持 99%以上的精确度,而改进前的方法在
最优情况下也不足 4%,改进效果非常明显.仅靠文件名匹配的相似文件对的方法,其精确度仅为 12.65%,因此在
实际同源检测过程中,仅靠文件名匹配会误报出大量不正确的结果.在组建的 130 万个开源工程、3.86 亿个项
目文件的大规模代码指纹库上进行文件检测,平均单文件检测时间为 0.43s,通过索引和分表大幅度降低了候选
文件数量.从库中选取通过 MD 5 能够匹配出相似文件的 13 886 对工程对进行实验分析,证明了改进后的相似
哈希方法在大规模数据集上仍能够保持较高的精确度,较改进前方法在精确度上有大幅度提升,较 MD 5 方法
能够获取将近两倍的相似文件对结果.
在实验过程中也暴露出目前方法的一些漏报现象,主要分为下几种情况:文件本身较小或包含的语义信息
较少;两文件总行数差距较大,导致指纹的差异较大;某些小文件经过常见行筛选后文件特征为空;常见行的筛
选一定程度上放大了其他行的差异对结果指纹值的影响,导致海明距离超出阈值.虽然本文仅在由 Github 开源
项目组成的两个数据集上进行了实验(分别为 RQ1、RQ2 中 200 个项目的数据集和 RQ3 中 130 万个开源项目
组成的大规模库),但是这些项目均来自于 Github 上星数排名的前列,具有应用范围广泛、影响项目众多的特点.
本文中提及的许多算法适用的场景,如漏洞传播发现、抄袭检测等都以这些项目作为研究重点,因此本文的数
据集具有一定的代表性.在数据规模上达到了 3.8 亿这一量级,能够覆盖到多种语言和不同结构的实际项目,得
出的实验结果较为可靠.
在未来的工作中,我们将综合考虑实验中分析出的各种漏报情况对本文的相似哈希方法作进一步的改进.
具体来说,包括:通过启发式分析对当前通过统计得到的各种行作进一步取舍,保证更新后的行筛选器只筛除对
代码文件语义影响不大的行,而不过多筛除一些有用行以致剩余行差异被放大;对相似哈希方法在小文件上的
检测能力作进一步的实验和优化;在海明距离阈值方面,在更大范围内对精确度和漏报率作评估和权衡.