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

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

的匹配结果.改进后的相似哈希方法获取到的相似文件对数是 MD 5 方法的 2 倍,而改进前的相似哈希方法则获
取到远大于另外两种方法的文件对数.在改进前的相似哈希检测结果中出现了大量误报的文件对,主要原因是
改进前的相似哈希算法在实际工程上出现了大量的行覆盖现象,包括“returnfalse;”“}else{”“break;”等.在改进后
的相似哈希算法中,通过不同筛选器对不同语言的常见行进行了筛选,排除了此类行对结果的影响,使得最终匹
配的精确度得到了大幅度提升.为了进一步查看不同海明距离下的检测数量以及精确度的变化情况,对改进前
后两种相似哈希方法在海明距离阈值为 0~8 的情况下分别进行检测,结果如图 5 所示.

Fig.5 Experimental results of two methods under different Hamming distance thresholds
图 5 相似哈希改进前后算法在不同海明距离阈值上的检测情况

可以看到,在整体检测效果上使用不同语言筛选器对特征进行行筛选的相似哈希算法都显著优于改进前
算法,两种算法的检测文件数量均与海明距离阈值呈正相关,精确度与海明距离阈值呈负相关.改进后的相似哈
希方法在所测的各个海明距离阈值上都能保持 99%以上的精确度,而改进前的方法在最优情况下也不足 4%,
差距悬殊.
上述匹配结果均为文件级别的匹配结果,即匹配到的相似文件对中有多少是正确的.在工程级别的评测主
要衡量相似性匹配算法能否寻找到更多潜在相似的工程对,为后续的工程两两对比作铺垫.获取到的相似工程
对结果见表 5.改进后的相似哈希方法可以覆盖全部 MD 5 方法匹配到的工程对,并且能够额外发现新的相似工
程对,发现的新工程对的精确度也较高.改进前的方法比改进后的相似哈希方法能够匹配到更多的相似工程对,
主要是因为该方法在两两比对中匹配出大量相似文件对,因此关联到的工程对数目更多.

Table 5 Project pairs detected by simhash before enhancement, simhash after enhancement, and MD 5
表 5 改进前后的相似哈希方法与 MD 5 方法的匹配工程
指纹计算方法 检测出的工程对 筛选后的工程对
相似哈希-改进前 9 697 813
相似哈希-改进后 628 607

对改进后方法无法检测而改进前能够检测到的文件对作进一步漏报分析,发现主要由两种情况所致.
(1) 改进后的相似哈希方法筛除了一些常见行,因此在一定程度上放大了剩下行的差异对结果的影响,导
致本来海明距离小于等于 8 的结果在筛选之后大于 8.
(2) 对于某些行数较小的文件,由于其整个文件均包含在其对应语言常见行筛选的范围内,导致其所有内
容均被筛除,最后获取到的特征为空,即相似哈希指纹值为 0,不参与后续的指纹匹配过程.
其中,情况 1 为出现漏报的主要原因.关于改进后方法漏报情况的进一步详细分析见第 4.2 节.
在指纹计算效率方面,同样对 3 种方法进行了统计和比较.在 200 个工程中的近 30 万个代码文件上进行预
处理和 3 种不同指纹的计算,耗费的总时间见表 6.改进后的相似哈希方法指纹生成速度与 MD 5 算法的处理速
度相近,比改进前的相似哈希方法在速度上有所提升.其主要原因是,在对各种语言的常见行进行筛选后,一些
无意义行的特征被过滤,不需要再计算其哈希值并参与累加,因此节省了时间.