摘要:代码相似性检测（code similarity detection）是软件工程领域的基本任务之一，其在剽窃检测、许可证违反检测、软件复用分析以及漏洞发现等方向均起着重要作用.随着软件开源化的普及以及开源代码量的高速增长，开源代码在各个领域的应用日益频繁，给传统的代码相似性检测方法带来了新的挑战.现有的一些基于词法、语法、语义的检测方法存在算法较为复杂、对解析工具有依赖性、消耗资源高、可移植性差、候选对比项数量较多等问题，在大规模代码库上有一定的局限性.基于相似哈希（simhash）指纹的代码相似性检测算法将代码降维至1个指纹，能够在数据集规模较大的情况下实现快速相似文件检索，并通过海明距离阈值控制匹配结果的相似度范围.通过实验对现有的基于代码行粒度的相似哈希算法进行验证，发现其在大规模数据集下存在行覆盖问题，即高频行特征对低频行特征的覆盖现象，导致结果精确度较低.受TF-IDF算法思想启发，针对上述问题创新性地提出了分语言行筛选优化方法，通过各种语言的行筛选器对代码文件行序列进行筛选，从而消除高频出现但语义信息包含较少的行对结果的影响.对改进前后方法进行一系列对比实验，结果表明，改进后的方法在海明距离阈值为0~8的情况下都能够实现高精确度的相似文件对检索，当阈值为8时在两个数据集下的精确度较改进前的方法分别提升了98.6%和52.2%.在所建立的130万个开源项目、386 486 112个项目文件的大规模代码库上进行了实验，结果表明所提方法能够快速检测出待测文件的相似文件结果，平均单个文件检测时间为0.43s，并取得了97%以上的检测精度.



Abstract:Code similarity detection is one of the basic tasks in software engineering. It plays an effective and fundamental role in plagiarism, software licensing violation, software reuse analysis, and vulnerability discovery. With the popularization of open source software, open source code has been frequently applied to multiple areas, bringing new challenges to traditional code similarity detection methods.Some existing detection methods based on lexical, grammar, and semantics have problems such as high computational complexity, dependence on analytical tools, high resource consumption, poor portability, having a large number of comparison candidates, and so on. Simhash-based code similarity detection algorithm reduces the dimension of the code to a fingerprint, which can realize fast near-duplicate file retrieval on a large dataset. It controls the similarity of matched results through the Hamming distance threshold. This study verifies existed simhash algorithm with line granularity through experiments, and discovers the line coverage problem in large-scale datasets. Inspired by the idea of TF-IDF algorithm, a language-based line-filtering optimization method is proposed to deal with it. Line sequences of code files is filtered through line filters in various languages to eliminate the impact of lines that appear frequently but contain less semantic information on the results. After a series of comparative experiments, this study verifies that the enhanced method always achieves high precision with Hamming distance threshold set from 0 to 8. Compared to the method before enhancement, the proposed method improves the precision by 98.6% and 52.2% on two different datasets with threshold set to 8. Based on the large-scale code database built from 386 486 112 files in 1.3 million open source projects, it is verified that the proposed method can, keeping the high precision of 97%, efficiently detect similar files with an average speed of 0.43s per file.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/6271