《电子技术应用》
您所在的位置：首页 > 其他 > 设计应用 > 基于改进WL图核的代码克隆检测方法
基于改进WL图核的代码克隆检测方法
网络安全与数据治理 3期
班必奂1，2，徐 云2，3
(1.中国科学技术大学 大数据学院，安徽 合肥230026； 2.安徽省高性能计算重点实验室，安徽 合肥230026； 3.中国科学技术大学 计算机科学与技术学院，安徽 合肥230026)
摘要： 基于程序依赖图(Program Dependency Graph，PDG)的代码克隆检测方法是检测代码克隆的重要方法之一，近年来提出的基于Weisfeiler-Lehman(WL)图核迭代的近似图匹配方法在克隆检测中取得了较好的效果，但PDG中少量顶点的差异会随着图核迭代传播到越来越多的顶点，从而导致算法召回率的下降。为此，针对WL图核在克隆检测应用中存在的问题，提出了一种基于改进WL图核的代码克隆检测方法，将WL图核迭代过程中采用的普通哈希算法替换为局部敏感哈希，同时引入向量的相似性度量方法，进一步提升了对PDG近似子结构的识别能力。实验结果表明，改进后的方法不仅可以检测出更多的差异克隆对，同时还保持了良好的精度和时间性能。
中图分类号： TP311.5
文献标识码： A
DOI： 10.20044/j.csdg.2097-1788.2022.03.010
引用格式： 班必奂，徐云. 基于改进WL图核的代码克隆检测方法[J].网络安全与数据治理，2022，41(3)：60-66.
An improved WL graph kernel-based code clone detection method
Ban Bihuan1，2，Xu Yun2，3
(1.School of Data Science，University of Science and Technology of China，Hefei 230026，China； 2.Key Laboratory of High Performance Computing of Anhui Province，Hefei 230026，China； 3.School of Computer Science and Technology，University of Science and Technology of China，Hefei 230026，China)
Abstract： Code clone detection based on Program Dependency Graph(PDG) is one of the important methods in code clone detection domain. In recent years, a code clone detector that based on Weisfeiler-Lehman(WL) graph kernel has achieved success in detecting code clones. However, several different vertices in the PDG will ″spread″ to the whole PDG with iterations and finally results in a decline in recall rate. Therefore, an improved WL kernel-based clone detector is proposed to address the problem of the WL kernel when applied in clone detections. The ordinary hash algorithm used in the iterations of WL kernel is replaced with the local sensitive hash algorithm, and the vector similarity measure approach is employed, which enhances the ability to identify the similar PDG sub-structures. The experimental results show that compared to the original WL graph kernel-based detector, the improved method can not only detect more clones but also keep good accuracy and a low computing time.
Key words : code clone detection；program dependency graph；Weisfeiler-Lehman kernel

0 引言

在实际的软件系统开发过程中，开发人员出于提高开发效率或者降低软件错误风险的原因，通常会将其他模块中功能相同或者相近的代码片段通过复制—修改(或不修改)—粘贴的模式引入到当前正在开发的模块中，这些粘贴而来的功能相同或相似的代码片段在学术界通常被称为克隆代码[1]。大量的研究表明，过多的克隆代码会给软件系统带来维护成本提高[2]和Bug蔓延[3]等问题。例如，假设某一段代码中存在Bug并且这段代码被复制粘贴在不同的位置，那么这个Bug将会随着这些克隆代码在整个软件中传播，进而增加了维护的难度。因此，检测出软件系统中的克隆代码并对其进行统一管理是非常有必要的。

随着代码克隆检测技术的不断发展，高级别代码克隆(即Type-3和Type-4克隆)的检测成为当前的研究热点之一。由于高级别克隆代码往往在复制粘贴之后还进行了一些修改，因此也更有可能存在Bug[4]。另外，修改所导致的差异性也使得这一类型的克隆更加难以被检测。

得益于程序依赖图(Program Dependency Graph，PDG)中所包含的大量语法结构信息和语义信息，基于PDG的克隆检测方法在检测高级别克隆上更具优势，能够检测出更多的结构相似但文本差异较大的高级别克隆代码。但在已有的方法中，采用精确图匹配算法的CCSharp[5]、GPLAG[6]等克隆检测方法存在时间性能差和召回率低的缺点，而采用Weisfeiler-Lehman(WL)图核进行近似图匹配计算的CCGraph[7]，受限于节点初始标签的单一性和WL图核迭代过程中对近似子结构识别能力的缺失，召回率也相对较低。为此，本文针对WL图核算法在PDG克隆检测应用中存在的缺陷，提出了一种改进思路：首先利用语法分析技术将PDG节点所包含的源代码信息解析为特征向量的形式来作为该节点的初始标签，使其能够保留更多的语义信息；然后通过引入局部敏感哈希技术提升PDG中近似子结构的识别能力，进而提升高级别克隆的召回率。





本文详细内容请下载：http://www.chinaaet.com/resource/share/2000004907





作者信息：

班必奂1，2，徐  云2，3

(1.中国科学技术大学 大数据学院，安徽 合肥230026；

2.安徽省高性能计算重点实验室，安徽 合肥230026；

3.中国科学技术大学 计算机科学与技术学院，安徽 合肥230026)


微信图片_20210517164139.jpg

此内容为AET网站原创，未经授权禁止转载。

相关内容