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

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

(2) 将改进后的相似哈希算法与 MD 5 算法进行对比,证实其能够覆盖 MD 5 方法 99%以上的匹配结果,比
使用 MD 5 的方法多获取到 40%以上的相似文件对,并进一步匹配到 44%以上的包含相似成分的工程对.
(3) 基于 Github 开源项目,构建了项目数量达 130 万、文件数量达 3.86 亿的大规模代码指纹库.通过索引
和分表,文件平均检测速度达到 0.43s/个,并抽取了 309 对工程对加以验证,结果表明改进后的算法能够在大数
据集上保持 97%以上精度的检测效果(实验结果可从 https://Github.com/Nica97/simhash_experimental_results
下载).
本文第 1 节介绍代码相似性检测领域研究背景,对比传统指纹与相似哈希在原理和应用上的不同,并回顾
相似哈希在代码相似性检测领域已有的研究成果.第 2 节介绍传统相似哈希方法及行粒度相似哈希筛选方法,
深入分析后者在大规模数据集下产生的行覆盖现象及其原因,并提出本文的分语言行筛选的相似哈希优化算
法.第 3 节提出 3 个研究问题(research question,简称为 RQ),对实验数据集、本文采用的评测指标以及整体的
实验流程进行介绍.第 4 节分别针对 3 个 RQ 的实验结果进行展示和分析.第 5 节总结本文工作并展望下一步
研究.

1 相关工作

1.1 代码相似性检测

在代码相似性检测流程中,如何选取合适的方法对代码进行特征提取和表达是最为关键的步骤,依照提取
[1]
特征层次的不同,可分为基于指标、基于文本、基于词法、基于树和基于图 5 这个层次 .早期的检测方法通常
[4]
[5]
基于指标或基于软件量测,如 Ottenstein 提出的基于霍尔斯特德复杂度测量指标 的检测方法中将源代码表
示为不同操作符个数、不同操作数个数、操作符出现总次数、操作数出现总次数构成的 4 维向量并进行比较,
虽然该类方法较其他类型方法实现简单但缺乏有效性.基于文本的检测方法只对源代码进行少量的简单处理,
[6]
主要将源代码看作文本来进行处理,如著名工具 NiCad 通过最长公共子序列(longest common subsequence)对
比两个从源代码中获取的字符串序列来获取相似代码.基于词法的检测方法则通常利用解析器将源代码分成
[7]
[8]
符号序列,并对符号序列进行比较和分析得出检测结果.比较著名的工具有 CCFinder 、CCAligner 、
[9]
SourcererCC 等.基于树的检测方法将源代码转化为抽象语法树(AST)来进行分析,如 CloneDR [10] 提取了 AST
的信息作为中间表示并通过树匹配技术对获得的有效信息进行克隆分析.基于图的检测方法可以捕捉程序的
语义信息,例如基于程序依赖图(PDG)的检测方法 Duplix [11] 等等.
在目前代码大数据的情境下,传统的代码相似性检测方法面临着新的挑战 [12] .采用基于树或图的检测方法
通常需要依赖于特定语言的语法分析器以生成抽象语法树、程序依赖图等代码特征信息,处理过程消耗了大量
计算资源且可扩展性有限,在大规模库上的应用较少.对于基于词法的检测方法,通常将代码转化为一组 token
序列,再通过各种相似度衡量方法,如后缀树(suffix tree)、Jaccard 相似度、字符串对齐等方法进行相似性度量.
相较于基于树和基于图的方法,其效率更高,适用于更大规模的数据集.这些方法中通过各种手段对检测的候选
[9]
[8]
结果进行筛选,如仅对 token 序列子集的每一位进行索引 、对 n-gram 的部分 token 建立倒排索引等 ,获得了
[9]
不错的效果,如 SourcererCC 可以检测的规模达到 250MLOC(lines of code).但是,随着规模的进一步扩大,候选
token 序列的规模亦将持续扩大,与 token 序列之间的对比会消耗大量时间.对此,本文主要采用文本层次的基于
相似哈希指纹的相似检测方法,将源代码转化为一串二进制字符串,两两比较效率更高.通过分段索引和按语言
分表的方法,将候选序列范围大幅度降低,以达到快速检索的效果.针对文本检测在代码相似性检测上出现的问
题,结合语言的特点进行了优化,语言迁移成本极低,在大规模库上构建的效率也比较高.
1.2 传统指纹与相似哈希

在大规模代码库中,为了快速获取相似的代码文件,可以将源代码降维为指纹(fingerprint),再通过指纹之间
的比较进行快速匹配.正如人的指纹能够代表个人身份,代码相似性检测中的指纹也常用来代表输入代码的独
有特性.指纹计算方法的输入对象可以是一个文件、一个方法,甚至某一行代码,对其进行一系列变换、降维后