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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(7):22422259 [doi: 10.13328/j.cnki.jos.006271] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563


面向代码相似性检测的相似哈希改进方法

1,2
1,2
1,2
4
1,2
李 玫 1,2,3 , 高 庆 , 马 森 , 张世琨 , 胡文蕙 , 张兴明
1
(高可信软件技术教育部重点实验室(北京大学),北京 100871)
2
(北京大学 软件工程国家工程研究中心,北京 100871)
3 (北京大学 软件与微电子学院,北京 102600)
4 (之江实验室,浙江 杭州 311121)
通讯作者: 高庆, E-mail: gaoqing@pku.edu.cn, 马森, E-mail: masen@pku.edu.cn

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

中文引用格式: 李玫,高庆,马森,张世琨,胡文蕙,张兴明.面向代码相似性检测的相似哈希改进方法.软件学报,2021,32(7):
22422259. http://www.jos.org.cn/1000-9825/6271.htm
英文引用格式: Li M, Gao Q, Ma S, Zhang SK, Hu WH, Zhang XM. Enhanced simhash algorithm for code similarity detection.
Ruan Jian Xue Bao/Journal of Software, 2021,32(7):22422259 (in Chinese). http://www.jos.org.cn/1000-9825/6271.htm
Enhanced Simhash Algorithm for Code Similarity Detection

1,2
1,2
1,2
1,2
LI Mei 1,2,3 , GAO Qing , MA Sen , ZHANG Shi-Kun , HU Wen-Hui , ZHANG Xing-Ming 4
1
(Key Laboratory of High Confidence Software Technologies of Ministry of Education (Peking University), Beijing 100871, China)
2
(National Engineering Research Center for Software Engineering, Peking University, Beijing 100871, China)

 基金项目: 2019 年工业互联网创新发展工程-工业软件源代码安全检测工具项目; 之江实验室“先进工业互联网安全平台”项
目(2018FD0ZX01)
Foundation item: 2019 Industrial Internet Innovation Development Project-industrial Software Source Code Security Detection Tool
Project; “Advanced Industrial Internet Security Platform” Project of Zhijiang Laborator (2018FD0ZX01)
本文由“面向非确定性的软件质量保障方法与技术”专题特约编辑陈俊洁副教授、汤恩义副教授、何啸副教授以及马晓星教
授推荐.
收稿时间: 2020-09-16; 修改时间: 2020-10-26; 采用时间: 2020-12-14; jos 在线出版时间: 2021-01-22