面向代码相似性检测的相似哈希改进方法
作者:
作者单位:

作者简介:

李玫(1997-),女,硕士,主要研究领域为软件工程.
张世琨(1969-),男,博士,研究员,博士生导师,CCF高级会员,主要研究领域为软件工程,网络安全,知识计算.
高庆(1989-),男,博士,助理研究员,主要研究领域为软件工程.
胡文蕙(1977-),女,博士,副研究员,主要研究领域为软件工程,大数据技术,知识图谱.
马森(1980-),男,博士,副研究员,主要研究领域为软件安全.
张兴明(1963-),男,教授,主要研究领域为网络安全.

通讯作者:

高庆,E-mail:gaoqing@pku.edu.cn,马森,E-mail:masen@pku.edu.cn

中图分类号:

基金项目:

2019年工业互联网创新发展工程-工业软件源代码安全检测工具项目;之江实验室“先进工业互联网安全平台”项目(2018FD0ZX01)


Enhanced Simhash Algorithm for Code Similarity Detection
Author:
Affiliation:

Fund Project:

2019 Industrial Internet Innovation Development Project-industrial Software Source Code Security Detection Tool Project; "Advanced Industrial Internet Security Platform" Project of Zhijiang Laborator (2018FD0ZX01)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    代码相似性检测(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.

    参考文献
    相似文献
    引证文献
引用本文

李玫,高庆,马森,张世琨,胡文蕙,张兴明.面向代码相似性检测的相似哈希改进方法.软件学报,2021,32(7):2242-2259

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-09-16
  • 最后修改日期:2020-10-26
  • 录用日期:
  • 在线发布日期: 2021-01-22
  • 出版日期: 2021-07-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号