基于后缀数组的克隆检测

doi:10.3969/j.issn.1000-3428.2013.09.026

计算机工程

基于后缀数组的克隆检测

史庆庆，张丽萍，尹丽丽，刘东升

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

收稿日期:2012-09-14 出版日期:2013-09-15 发布日期:2013-09-13
作者简介:史庆庆(1987－)，男，硕士研究生，主研方向：软件工程，软件测试；张丽萍，副教授、硕士；尹丽丽，硕士研究生；刘东升，教授
基金资助:
内蒙古自然科学基金资助项目(2011MS0906)

Clone Detection Based on Suffix Array

SHI Qing-qing, ZHANG Li-ping, YIN Li-li, LIU Dong-sheng

(Computer & Information Engineering College, Inner Mongolia Normal University, Hohhot 010022, China)

Received:2012-09-14 Online:2013-09-15 Published:2013-09-13

摘要/Abstract

摘要： 程序员对源代码的拷贝、粘贴及修改活动会导致软件中出现大量克隆代码，增加软件开发和维护的成本。为解决该问题，提出一种新的克隆检测方法。利用基于后缀数组的算法查找重复的Token子串，进而检测出克隆代码，开发相应的克隆检测工具SaCD，用其检测29款C语言开源软件。实验结果表明，SaCD能快速有效地检测软件中的Type-1和Type-2语句克隆，其检测速度比传统的克隆检测工具CCFinderx快了近20倍。

关键词: 克隆代码, 克隆检测, Token串, 后缀数组, 重复子串, DC3算法

Abstract: The activities of the programmers for copying, pasting and modifying result in a lot of code clones in the software systems, and increase the cost of software development and maintenance. Aiming at this problem, this paper presents a new clone detection method which uses algorithm based on suffix array to efficiently search repeated token substrings and to detect code clones at last. It develops a clone detection tool SaCD and detects twenty-nine open source software systems of C language. Experimental results show that the SaCD can fastly and efficiently detect Type-1 and Type-2 statement clones in the software. The detection speed of SaCD is twenty times than that of CCFinderx.

Key words: clone code, clone detection, Token string, suffix array, repeated substring, DC3 algorithm

中图分类号:

TP311

史庆庆，张丽萍，尹丽丽，刘东升. 基于后缀数组的克隆检测[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.09.026.

SHI Qing-qing, ZHANG Li-ping, YIN Li-li, LIU Dong-sheng. Clone Detection Based on Suffix Array[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.09.026.

http://www.ecice06.com/CN/Y2013/V39/I9/123

参考文献

[1] Kamiya T, Kusumoto S, Inoue K. CCFinder: A Multi-linguistic Token-based Code Clone Detection System for Large Scale Source Code[J]. IEEE Transactions on Software Engineering, 2002, 28(7): 654-670. [2] Deissenboeck F, Hummel B, Juergens E. Code Clone De- tection in Practice[C]//Proc. of the 32nd ACM/IEEE Inter- national Conference on Software Engineering. Cape Town, South Africa: ACM Press, 2010. [3] 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. [4] Johnson J H. Identifying Redundancy in Source Code Using Fingerprints[C]//Proc. of Centre for Advanced Studies on Collaborative Research: Software Engineering. [S. l.]: IBM Press, 1993. [5] Baker B S. On Finding Duplication and Near-duplication in Large Software Systems[C]//Proc. of the 2nd Working Conference on Reverse Engineering. Toronto, Canada: IEEE Press, 1995. [6] Li Zhenmin, Lu Shan, Myagmar S, et al. CP-Miner: Finding Copy-paste and Related Bugs in Large Scale Software Code[J]. IEEE Transactions on Software Engineering, 2006, 32(3): 176-192. [7] Baxter I, Andrew Y, Moura L, et al. Clone Detection Using Abstract Syntax Trees[C]//Proc. of International Conference on Software Maintenance. Bethesda, USA: IEEE Press, 1998. [8] 郭婧, 吴军华. 基于程序依赖图的克隆检测及改进[J]. 计算机工程与设计, 2012, 33(2): 595-600. [9] Mayrand J, Leblanc C, Merlo E. Experiment on the Automatic Detection of Function Clones in a Software System Using Metrics[C]//Proc. of International Conference on Software Maintenance. Monterey, USA: IEEE Press, 1996. [10] Davis I, Godfrey M. From Whence It Came: Detecting Source Code Clones by Analyzing Assembler[C]//Proc. of the 17th Working Conference on Reverse Engineering. Beverly, USA: IEEE Press, 2010. [11] Keivanloo I, Roy C K, Rilling J. Java Bytecode Clone Detection via Relaxation on Code Fingerprint and Semantic Web Reasoning[C]//Proc. of the 6th International Workshop on Software Clones. Zurich, Switzerland: [s. n.], 2012. [12] Bulychev P, Minea M. An Evaluation of Duplicate Code Detection Using Anti-unification[C]//Proc. the 3rd Inter- national Workshop on Software Clones. Kaiserslautern, Germany: [s. n.], 2009. [13] Kim H, Jung Y, Kim S, et al. Mecc: Memory Comparison- based Clone Detector[C]//Proc. of the 33rd International Conference on Software Engineering. Honolulu, USA: ACM Press, 2011. [14] 于冬琦, 吴毅坚, 彭鑫, 等. 基于相似性度量的面向对象程序方法级克隆侦测[J]. 电子学报, 2010, 38(2A): 174-181. [15] Mohamed I A, Stefan K, Enno O. Replacing Suffix Trees with Enhanced Suffix Arrays[J]. Journal of Discrete Algorithms, 2004, 2(1): 53-86. [16] Manber U, Myers G. Suffix Arrays: A New Method for On-line String Searches[J]. SIAM Journal on Computing, 1993, 22(5): 935-948. [17] Karkainen J, Sanders P, Burkhardt S. Linear Work Suffix Array Construction[J]. Journal of the ACM, 2006, 53(6): 918-936. [18] Kasai T, Lee G, Arimura T, et al. Linear-time Longest- common-prefix Computation in Suffix Arrays and Its Applications[C]//Proc. of the 12th Annual Symposium on Combinatorial Pattern Matching. Jerusalem, Palestine: Springer-Verlag, 2001. [19] Zibran M F, Saha R K, Asaduzzaman M, et al. Analyzing and Forecasting Near-miss Clones in Evolving Software: An Empirical Study[C]//Proc. of the 16th IEEE International Conference on Engineering of Complex Computer Systems. Las Vegas, USA: IEEE Press, 2011. 编辑刘冰

选择文件类型/文献管理软件名称

选择包含的内容

基于后缀数组的克隆检测

Clone Detection Based on Suffix Array

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	张冬梅, 陈永乐, 杨玉丽. 基于分层特征的代码克隆检测方法[J]. 计算机工程, 2021, 47(10): 125-131.
[2]	葛广帅,刘东升,张丽萍,侯敏. 基于图模型的克隆代码演化痕迹构建及模式识别[J]. 计算机工程, 2017, 43(5): 47-54，59.
[3]	金国平，余宗桥，郭延文，蒋和. 基于GPU加速的音频检索技术[J]. 计算机工程, 2014, 40(5): 266-269.
[4]	廖豪, 陈洁, 谭建龙. 大规模语料中频繁模式增量发现算法[J]. 计算机工程, 2011, 37(23): 27-29,32.
[5]	姚全珠;张楠;杨增辉;田元. 基于压缩后缀数组技术的搜索引擎[J]. 计算机工程, 2008, 34(10): 83-85.
[6]	杨笑天;陶晓鹏. 后缀数组创建算法的分析和比较[J]. 计算机工程, 2007, 33(03): 186-188.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于后缀数组的克隆检测

Clone Detection Based on Suffix Array

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价