主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2022年专刊出版计划 微信服务介绍 最新一期:2021年第2期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李玫,高庆,马森,张世琨,胡文蕙,张兴明.面向代码相似性检测的相似哈希改进方法.软件学报,2021,32(7):26-0
面向代码相似性检测的相似哈希改进方法
Enhanced Simhash Algorithm for Code Similarity Detection
投稿时间:2020-09-16  修订日期:2020-10-26
DOI:10.13328/j.cnki.jos.006271
中文关键词:  代码相似性检测  代码同源分析  大数据  相似哈希  代码指纹生成
英文关键词:code similarity detection  code homology analyze  big data  simhash  code fingerprint generation
基金项目:2019年工业互联网创新发展工程——工业软件源代码安全检测工具项目;之江实验室“先进工业互联网安全平台”(2018FD0ZX01)
作者单位E-mail
李玫 高可信软件技术教育部重点实验室(北京大学), 北京 100871
北京大学 软件工程国家工程研究中心, 北京 100871
北京大学 软件与微电子学院, 北京 102600 
 
高庆 高可信软件技术教育部重点实验室(北京大学), 北京 100871
北京大学 软件工程国家工程研究中心, 北京 100871 
gaoqing@pku.edu.cn 
马森 高可信软件技术教育部重点实验室(北京大学), 北京 100871
北京大学 软件工程国家工程研究中心, 北京 100871 
masen@pku.edu.cn 
张世琨 高可信软件技术教育部重点实验室(北京大学), 北京 100871
北京大学 软件工程国家工程研究中心, 北京 100871 
 
胡文蕙 高可信软件技术教育部重点实验室(北京大学), 北京 100871
北京大学 软件工程国家工程研究中心, 北京 100871 
 
张兴明 之江实验室, 浙江 311121  
摘要点击次数: 166
全文下载次数: 95
中文摘要:
      代码相似性检测(Code Similarity Detection)是软件工程领域的基本任务之一,其在剽窃检测、许可证违反检测、软件复用分析以及漏洞发现等方向均有重要作用.随着软件开源化的普及以及开源代码量的高速增长,开源代码在各个领域的应用日益频繁,给传统的代码相似性检测方法带来了新的挑战.现有的一些基于词法、语法、语义的检测方法存在算法较为复杂,对解析工具有依赖性,消耗资源高,可移植性差,候选对比项数量较多等问题,在大规模代码库上有一定局限性.基于相似哈希(simhash)指纹的代码相似性检测算法将代码降维至一个指纹,能够在数据集规模较大的情况下实现快速相似文件检索,并通过海明距离阈值控制匹配结果的相似度范围.通过实验对现有的基于代码行粒度的相似哈希算法进行验证,发现其在大规模数据集下存在行覆盖问题,即高频行特征对低频行特征的覆盖现象,导致结果精确度较低.受TF-IDF算法思想启发,针对上述问题创新性地提出了分语言行筛选优化方法,通过各种语言的行筛选器对代码文件行序列进行筛选,从而消除高频出现但语义信息包含较少的行对结果的影响.对改进前后方法进行一系列对比实验,结果表明改进后的方法在海明距离阈值为0至8的情况下均能够实现高精确度的相似文件对检索,阈值为8时在两个数据集下的精确度较改进前的方法分别提升了98.6%和52.2%.在本文建立的130万个开源项目,386486112个项目文件的大规模代码库上进行实验,验证了本文的方法能够快速检测出待测文件的相似文件结果,平均单个文件检测时间为0.43s,并取得了97%以上的检测精度.
英文摘要:
      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 paper verifies existed simhash algorithm with line granularity through experiments, and discovered the line coverage problem in large-scale datasets. Inspired by the idea of TF-IDF algorithm, we propose a language-based line-filtering optimization method to deal with it. We filter line sequences of code files 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 paper verifies that the enhanced method always achieves high precision with Hamming distance threshold set from 0 to 8. Compared to the method before enhancement, our 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 we build from 386,486,112 files in 1.3 million open source projects, we verify that our method can, keeping the high precision of 97%, efficiently detect similar files with an average speed of 0.43s per file.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利