Efficient token based clone detection with flexible tokenization

ABSTRACT

Code clones are similar code fragments that occur at multiple locations in a software system. Detection of code clones provides useful information for maintenance, reengineering, program understanding and reuse. Several techniques have been proposed to detect code clones. These techniques differ in the code representation used for analysis of clones, ranging from plain text to parse trees and program dependence graphs. Clone detection based on lexical tokens involves minimal code transformation and gives good results, but is computationally expensive because of the large number of tokens that need to be compared. We explored string algorithms to find suitable data structures and algorithms for efficient token based clone detection and implemented them in our tool Repeated Tokens Finder (RTF). Instead of using suffix tree for string matching, we use more memory efficient suffix array. RTF incorporates a suffix array based linear time algorithm to detect string matches. It also provides a simple and customizable tokenization mechanism. Initial analysis and experiments show that our clone detection is simple, scalable, and performs better than the previous well-known tools.

REFERENCES

• 1: Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, v.2 n.1, p.53-86, March 2004 [doi>10.1016/S1570-8667(03)00065-0]
• 2: Baker, B. S., "A Program for Identifying Duplicated Code", Computing Science and Statistics, vol. 24, 1992, pp. 49--57.
• 3: Hamid Abdul Basit , Damith C. Rajapakse , Stan Jarzabek, Beyond templates: a study of clones in the STL and some general implications, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062537]
• 4: Hamid Abdul Basit , Stan Jarzabek, Detecting higher-level similarity patterns in programs, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 5: Ira D. Baxter , Andrew Yahin , Leonardo Moura , Marcelo Sant'Anna , Lorraine Bier, Clone Detection Using Abstract Syntax Trees, Proceedings of the International Conference on Software Maintenance, p.368, March 16-19, 1998
• 6: Bellon, S., "Vergleich von Techniken zur Erkennung duplizierten Quellcodes", Master's Thesis, Institut fur Softwaretechnologie, Universitat Stuttgart, Stuttgart, Germany, 2002.
• 7: Elizabeth Burd , John Bailey, Evaluating Clone Detection Tools for Use during Preventative Maintenance, Proceedings of the Second IEEE International Workshop on Source Code Analysis and Manipulation (SCAM'02), p.36, October 01-01, 2002
• 8: Stéphane Ducasse , Matthias Rieger , Serge Demeyer, A Language Independent Approach for Detecting Duplicated Code, Proceedings of the IEEE International Conference on Software Maintenance, p.109, August 30-September 03, 1999
• 9: Stan Jarzabek , Li Shubiao, Eliminating redundancies with a "composition with adaptation" meta-programming technique, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 10: J. Howard Johnson, Identifying redundancy in source code using fingerprints, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
• 11: Toshihiro Kamiya , Shinji Kusumoto , Katsuro Inoue, CCFinder: a multilinguistic token-based code clone detection system for large scale source code, IEEE Transactions on Software Engineering, v.28 n.7, p.654-670, July 2002 [doi>10.1109/TSE.2002.1019480]
• 12: Kolpakov, R., Bana, G., and Kucherov, G., "mreps: efficient and flexible detection of tandem repeats in DNA", Nucleic Acids Research, vol. 31(13), Oxford University Press, 2003, 3672--3678.
• 13: Raghavan Komondoor , Susan Horwitz, Using Slicing to Identify Duplication in Source Code, Proceedings of the 8th International Symposium on Static Analysis, p.40-56, July 16-18, 2001
• 14: Jens Krinke, Identifying Similar Code with Program Dependence Graphs, Proceedings of the Eighth Working Conference on Reverse Engineering (WCRE'01), p.301, October 02-05, 2001
• 15: Rainer Koschke , Raimar Falke , Pierre Frenzel, Clone Detection Using Abstract Syntax Suffix Trees, Proceedings of the 13th Working Conference on Reverse Engineering, p.253-262, October 23-27, 2006 [doi>10.1109/WCRE.2006.18]
• 16: Bruno Lague , Daniel Proulx , Jean Mayrand , Ettore M. Merlo , John Hudepohl, Assessing the Benefits of Incorporating Function Clone Detection in a Development Process, Proceedings of the International Conference on Software Maintenance, p.314, October 01-03, 1997
• 17: Zhenmin Li , Shan Lu , Suvda Myagmar , Yuanyuan Zhou, CP-Miner: Finding Copy-Paste and Related Bugs in Large-Scale Software Code, IEEE Transactions on Software Engineering, v.32 n.3, p.176-192, March 2006 [doi>10.1109/TSE.2006.28]
• 18: Linux Online, http://www.linux.org/, 2006.
• 19: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 20: Jean Mayrand , Claude Leblanc , Ettore Merlo, Experiment on the Automatic Detection of Function Clones in a Software System Using Metrics, Proceedings of the 1996 International Conference on Software Maintenance, p.244, November 04-08, 1996
• 21: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 22: XML-Based Variant Configuration Language- Technology for Reuse, http://xvcl.comp.nus.edu.sg, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

General Terms:
Algorithms

Keywords:
clone detection, reverse engineering, software maintenance, token-based clone detection