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

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

其他情况均视作不相似.
上述两个条件均用于判断两个文件是否相似,其主要针对实际文件引用中的两个场景.其中,条件 1 针对的
引用场景为开发者对引用文件进行了多次修改,但该引用文件的整体结构不变,因此两个文件的共同行数均占
两个文件的一半以上.条件 2 针对的场景为开发者在原有引用文件的基础上额外增加或删除了一些方法和功
能,因此两个文件的行数有一定差距,对其中的大文件来说增加的内容可能超过了 50%,因此无法满足条件 1,但
是两个文件在实际功能上仍然是相似的.因此,条件 2 保证,当大文件与小文件的共同行数占小文件 70%以上(即
大文件保留了小文件 70%以上的行)时将两个文件视作相似文件.
上述指标中,50%和 70%是我们根据实际开源项目中引用文件的一般修改情况选取的经验性取值,根据实
际应用场景的不同,可以对指标进行调整和修改.为了验证该评测指标的合理性与正确性,在 RQ1 和 RQ3 的检
测结果中,随机抽取各个海明距离在该标准下判断为正确的相似文件对各 10 对,共计 180 对结果并进行人工核
验.主要针对的问题是判断为相似的文件对是否真正结构相似,是否会出现大量行相同但相同行所处的位置不
同导致整体代码功能结构上并不相似的情况.核验结果表明,所有参与人工核验的文件对抽样都是结构相似、
功能相关的文件对,在同源检测上有显著的相关性.具体人工核验结果统计情况见表 3.
Table 3 Manual validation of the evaluation metric
表 3 评测标准人工核验结果
验证结果(文件对之间的关系) 数量 百分比(%)
预处理后完全一致 17 9.44
修改个别行,其他均一致,整体语义几乎不影响 46 25.56
修改或增删部分行,其他部分一致 79 43.89
多处修改或增删,整体结构一致 26 14.44
一个比另一个增加了一些部分,即一个是另一个的子集 12 6.67

在本次实验的相似性匹配过程中,涉及到对以下两个名词的定义.
(1) 相似文件对:这是指两个不同工程内部发现的一对相似的代码文件,可能产生于一个工程对另一个工
程内文件的复制和复用.引用的文件可能经过了后期的增删和修改,因此与源文件有所差别.在实验过程中,主
要通过 MD 5 指纹和相似哈希指纹值的匹配来发现相似文件对.
(2) 相似工程对:对于一个工程,只要其包含的所有代码文件中有任意一个文件与另一个工程中的文件被
匹配为相似文件对,就将这两个工程认定为相似工程对.
在实际应用过程中,两个相似工程对的确认有助于我们发现随着代码复用而进行传播的漏洞和缺陷,发现
抄袭或许可证违反现象.我们也可以使用文件相似性检测来进行粗粒度的代码搜索.
在验证过程中,相似文件对的验证方法为:通过本节提出的评测指标来评判两个文件是否的确相似.对相似
工程的验证方法为:使用本节提出的评测指标对两个工程之间的所有文件对进行两两评判,只要存在一对真实
相似的文件对,即判定两个工程对的确相似.
在实验分析过程中,本文选用了精确度、漏报、匹配对数、检测时间等指标来分析算法的有效性和效率.TP
表示真正例(即判断为相似且真实相似的文件对),TN 表示真负例(未检测出相似且确实不相似的文件对),FP 表
示假正例(检测出的相似文件对中实际上不相似的),FN 表示假负例(未检测出相似但实际为相似的工程对).
第 4 节中的漏报对应 FN,即假负例.精确度(precision)的计算方法为
TP
精确度(precision)= ,
TP  FP
FP
误报率 (FNR)  ,
FP TN
FN
漏报率 (FNR)  .
FN  TP
由于该实验数据规模较大,对海量数据文件进行依次两两对比将消耗大量的时间和计算资源,因此我们没
有从误报率和漏报率的角度对算法进行分析(因为难以获得 TN 与 FN),关于本文算法的详细漏报分析见第 4.1