基于Token编辑距离检测克隆代码

doi:10.11772/j.issn.1001-9081.2015.12.3536

计算机应用 ›› 2015, Vol. 35 ›› Issue (12): 3536-3543.DOI: 10.11772/j.issn.1001-9081.2015.12.3536

基于Token编辑距离检测克隆代码

张久杰, 王春晖, 张丽萍, 侯敏, 刘东升

内蒙古师范大学计算机与信息工程学院, 呼和浩特 010022

收稿日期:2015-06-12 修回日期:2015-09-06 出版日期:2015-12-10 发布日期:2015-12-10
通讯作者: 刘东升(1956-),男,内蒙古呼和浩特人,教授,CCF会员,主要研究方向:软件工程、计算机教育
作者简介:张久杰(1990-),男,内蒙古赤峰人,硕士研究生,主要研究方向:软件分析;王春晖(1979-),女(蒙古族),内蒙古通辽人,讲师,硕士,CCF会员,主要研究方向:软件分析、多媒体、计算机辅助教学;张丽萍(1974-),女,内蒙古呼和浩特人,教授,硕士,主要研究方向:软件工程、软件分析;侯敏(1979-),女,内蒙古呼和浩特人,讲师,硕士,主要研究方向:软件分析、计算机教育。
基金资助:
国家自然科学基金资助项目(61363017,61462071);内蒙古自然科学基金资助项目(2014MS0613);内蒙古自治区硕士研究生科研创新基金资助项目(S20141013524);内蒙古师范大学研究生科研创新基金资助项目(CXJJS14077)。

Clone code detection based on Levenshtein distance of token

ZHANG Jiujie, WANG Chunhui, ZHANG Liping, HOU Min, LIU Dongsheng

College of Computer and Information Engineering, Inner Mongolia Normal University, Hohhot Nei Mongol 010022, China

Received:2015-06-12 Revised:2015-09-06 Online:2015-12-10 Published:2015-12-10

摘要/Abstract

摘要： 针对当前Type-3克隆代码检测工具较少、效率偏低等问题,提出了一种基于Token的能有效检测Type-3克隆代码的检测方法。该方法同时能有效检测Type-1和Type-2克隆代码。首先将源代码Token化得到特定代码粒度的Token串,其次将所有Token串的定长子串进行映射,在对映射信息进行查询的基础上,利用编辑距离算法确定克隆对,然后通过并查集算法快速构建克隆群,最终反馈克隆代码信息。实现了原型工具FClones,利用基于代码突变的框架对工具进行了评价,并与领域内较优秀的两款工具NiCad及SimCad进行了对比。实验结果表明,FClones在检测三类克隆代码时查全率均不低于95%,查准率均不低于98%,能更好地检测Type-3克隆代码。

关键词: 克隆代码, 克隆检测, 编辑距离, Type-3, token

Abstract: Aiming at the problems of less clone code detection tools and low efficiency for the current Type-3, an effective clone code detection method for Type-3 based on the levenshtein distance of token was proposed. Type-1, Type-2 and Type-3 clone codes could be detected by the proposed method in an efficient way. Firstly, the source codes of a subject system were tokenized into some token sequences with specified code size. Secondly, each definite-sized substring of the token sequences was mapped with corresponding index. Thirdly, the clone pairs were built by the levenshtein distance algorithm and the clone groups were built by the disjoint-set algorithm on the basis of the mapping information query. Finally, the feedback information of clone codes were given. A prototype tool named FClones was implemented. It was evaluated by the code mutation-based framework and compared with two state-of-the-art tools SimCad and NiCad. The experimental results show that the recall of FCloens is equal to or greater than 95% and its precision is not lower than 98% in detecting all of these three types of clone codes. FClones can do better in detecting Type-3 clones than others.

Key words: clone code, clone detection, Levenshtein distance, Type-3, token

中图分类号:

TP311.5

张久杰, 王春晖, 张丽萍, 侯敏, 刘东升. 基于Token编辑距离检测克隆代码[J]. 计算机应用, 2015, 35(12): 3536-3543.

ZHANG Jiujie, WANG Chunhui, ZHANG Liping, HOU Min, LIU Dongsheng. Clone code detection based on Levenshtein distance of token[J]. Journal of Computer Applications, 2015, 35(12): 3536-3543.

参考文献

[1] ROY C K, ZIBRAN M F, KOSCHKE R. The vision of software clone management:past, present, and future (keynote paper)[C]//Proceedings of the 2014 IEEE Conference on Software Maintenance, Reengineering and Reverse Engineering. Piscataway:IEEE, 2014:18-33.
[2] BELLON S, KOSCHKE R, ANTONIOL G, et al. Comparison and evaluation of clone detection tools[J]. IEEE Transactions on Software Engineering, 2007, 33(9):577-591.
[3] ROY C K, CORDY J R. NICAD:Accurate detection of near-miss intentional clones using flexible pretty-printing and code normalization[C]//Proceedings of the 16th IEEE Conference on Program Comprehension. Piscataway:IEEE, 2008:172-181.
[4] SHI Q, ZHANG L,YIN L, et al. Clone detection based on suffix array[J]. Computer Engineering, 2013, 39(9):123-127. (史庆庆,张丽萍,尹丽丽,等.基于后缀数组的克隆检测[J].计算机工程,2013,39(9):123-127.)
[5] KAMIYA T, KUSUMOTO S, INOUE K. CCFinder:a multilinguistic token-based code clone detection system for large scale source code[J]. IEEE Transactions on Software Engineering, 2002, 28(7):654-670.
[6] TOOMEY W. Ctcompare:code clone detection using hashed token sequences[C]//Proceedings of the 6th IEEE International Workshop on Software Clones. Piscataway:IEEE, 2012:92-93.
[7] LAVOIE T, MERLO E. Automated type-3 clone oracle using Levenshtein metric[C]//Proceedings of the 5th International Workshop on Software Clones. New York:ACM, 2011:34-40.
[8] WAHLER V, SEIPEL D, GUDENBERG J, et al. Clone detection in source code by frequent itemset techniques[C]//Proceedings of the 4th International Workshop on Source Code Analysis and Manipulation. Piscataway:IEEE, 2004:128-135.
[9] DAVEY N, BARSON P, FIELD S, et al. The development of a software clone detector[J]. International Journal of Applied Software Technology, 1995, 1(3/4):219-236.
[10] LAVOIE T, MERLO E. About metrics for clone detection[J/OL]//Electronic Communications of the EASST, 2014, 63. http://journal.ub.tu-berlin.de/eceasst/article/viewFile/923/915.
[11] KRINKE J. Identifying similar code with program dependence graphs[C]//Proceedings of the 8th Working Conference on Reverse Engineering. Piscataway:IEEE, 2001:301-309.
[12] KHAN M A A, ROY C K, SCHNEIDER K A. Active clones:source code clones at runtime[J/OL]//Electronic Communications of the EASST, 2014:63. http://www.cs.usask.ca/~croy/papers/2014/KhanIWSC2014ActiveClones.pdf.
[13] SAJNANI H, SAINI V, LOPES C. A parallel and efficient approach to large scale clone detection[J]. Journal of Software Evolution & Process, 2015, 7(6):402-429.
[14] LIN Y, XING Z, XUE Y, et al. Detecting differences across multiple instances of code clones[C]//Proceedings of the 36th International Conference on Software Engineering. New York:ACM, 2014:164-174.
[15] LIN Y, XING Z, PENG X, et al. Clonepedia:summarizing code clones by common syntactic context for software maintenance[C]//Proceedings of the 2014 IEEE International Conference on Software Maintenance and Evolution. Piscataway:IEEE, 2014:341-350.
[16] SVAJLENKO J, ROY C K, CORDY J R. A mutation analysis based benchmarking framework for clone detectors[C]//Proceedings of the 7th International Workshop on Software Clones. Piscataway:IEEE, 2013:8-9.
[17] ROY C K, SCHNEIDER K. SimCad:an extensible and faster clone detection tool for large scale software systems[C]//Proceedings of the 21st International Conference on Program Comprehension. Piscataway:IEEE, 2013:236-238.
[18] ROY C K, CORDY J R, KOSCHKE R. Comparison and evaluation of code clone detection techniques and tools:a qualitative approach[J]. Science of Computer Programming, 2009, 74(7):470-495.
[19] SVAJLENKO J, ROY C K. Evaluating modern clone detection tools[C]//Proceedings of the 2014 IEEE International Conference on Software Maintenance and Evolution. Piscataway:IEEE, 2014:321-330.

基于Token编辑距离检测克隆代码

Clone code detection based on Levenshtein distance of token

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	朱怡, 宁振虎, 周艺华. 基于视觉特征的仿冒域名轻量级检测技术[J]. 计算机应用, 2020, 40(8): 2279-2285.
[2]	王亚芳, 刘东升, 侯敏. 基于图像相似度检测代码克隆[J]. 计算机应用, 2019, 39(7): 2074-2080.
[3]	赵宏, 常兆斌, 王乐. 基于词法特征的恶意域名快速检测算法[J]. 计算机应用, 2019, 39(1): 227-231.
[4]	折蓉蓉, 张丽萍, 侯敏, 闫盛. 基于决策树推荐克隆重构的方法[J]. 计算机应用, 2018, 38(7): 2037-2043.
[5]	徐林, 范昕炜. 基于改进遗传算法的餐厅服务机器人路径规划[J]. 计算机应用, 2017, 37(7): 1967-1971.
[6]	王欢, 张丽萍, 闫盛, 刘东升. 克隆代码有害性预测中的特征选择模型[J]. 计算机应用, 2017, 37(4): 1135-1142.
[7]	韩建栋, 邓一凡. 结合纹理与轮廓特征的多通道行人检测算法[J]. 计算机应用, 2017, 37(10): 3012-3016.
[8]	张久杰, 翟晔, 王春晖, 张丽萍, 刘东升. 基于版本间克隆映射的演化模式识别及谱系构建[J]. 计算机应用, 2016, 36(7): 2021-2030.
[9]	陈桌, 张丽萍, 王欢, 张久杰, 王春晖. 基于改进向量空间模型的克隆群映射方法[J]. 计算机应用, 2016, 36(7): 2031-2037.
[10]	陈桌, 张丽萍, 王春晖. 基于软件代码演化信息的克隆谱系提取方法[J]. 计算机应用, 2016, 36(12): 3461-3467.
[11]	王欢, 张丽萍, 闫盛. 克隆代码有害性预测中分类不平衡问题的解决方法[J]. 计算机应用, 2016, 36(12): 3468-3475.
[12]	张丽萍, 张瑞霞, 王欢, 闫盛. 基于贝叶斯网络的克隆代码有害性预测[J]. 计算机应用, 2016, 36(1): 260-265.
[13]	涂颖, 张丽萍, 王春晖, 侯敏, 刘东升. 基于软件多版本演化提取克隆谱系[J]. 计算机应用, 2015, 35(4): 1169-1173.
[14]	刘丽霞张志强. 基于Trie树的相似字符串查找算法[J]. 计算机应用, 2013, 33(08): 2375-2378.
[15]	周典瑞周莲英. 海量数据的相似重复记录检测算法[J]. 计算机应用, 2013, 33(08): 2208-2211.