Scalable detection of semantic clones

ABSTRACT

Several techniques have been developed for identifying similar code fragments in programs. These similar fragments, referred to as code clones, can be used to identify redundant code, locate bugs, or gain insight into program design. Existing scalable approaches to clone detection are limited to finding program fragments that are similar only in their contiguous syntax. Other, semantics-based approaches are more resilient to differences in syntax, such as reordered statements, related statements interleaved with other unrelated statements, or the use of semantically equivalent control structures. However, none of these techniques have scaled to real world code bases. These approaches capture semantic information from Program Dependence Graphs (PDGs), program representations that encode data and control dependencies between statements and predicates. Our definition of a code clone is also based on this representation: we consider program fragments with isomorphic PDGs to be clones.

In this paper, we present the first scalable clone detection algorithm based on this definition of semantic clones. Our insight is the reduction of the difficult graph similarity problem to a simpler tree similarity problem by mapping carefully selected PDG subgraphs to their related structured syntax. We efficiently solve the tree similarity problem to create a scalable analysis. We have implemented this algorithm in a practical tool and performed evaluations on several million-line open source projects, including the Linux kernel. Compared with previous approaches, our tool locates significantly more clones, which are often more semantically interesting than simple copied and pasted code fragments.

REFERENCES

• 1: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 2: 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
• 3: 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
• 4: Stefan Bellon , Rainer Koschke , Giulio Antoniol , Jens Krinke , Ettore Merlo, Comparison and Evaluation of Clone Detection Tools, IEEE Transactions on Software Engineering, v.33 n.9, p.577-591, September 2007 [doi>10.1109/TSE.2007.70725]
• 5: Magiel Bruntink , Arie van Deursen , Tom Tourwe , Remco van Engelen, An Evaluation of Clone Detection Techniques for Identifying Crosscutting Concerns, Proceedings of the 20th IEEE International Conference on Software Maintenance, p.200-209, September 11-14, 2004
• 6: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 7: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 8: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 9: Lingxiao Jiang , Ghassan Misherghi , Zhendong Su , Stephane Glondu, DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones, Proceedings of the 29th international conference on Software Engineering, p.96-105, May 20-26, 2007 [doi>10.1109/ICSE.2007.30]
• 10: 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]
• 11: Raghavan Komondoor , Susan Horwitz, Semantics-preserving procedure extraction, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.155-169, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325713]
• 12: 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
• 13: K. Kontogiannis, R. de Mori, E. Merlo, M. Galler, and M. Bernstein. Pattern matching for clone and concept detection. Automated Soft. Eng., 3(1/2), 1996.
• 14: Zhenmin Li , Shan Lu , Suvda Myagmar , Yuanyuan Zhou, CP-Miner: a tool for finding copy-paste and related bugs in operating system code, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.20-20, December 06-08, 2004, San Francisco, CA
• 15: Zhenmin Li , Yuanyuan Zhou, PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code, 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
• 16: Chao Liu , Chen Chen , Jiawei Han , Philip S. Yu, GPLAG: detection of software plagiarism by program dependence graph analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150522]
• 17: 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
• 18: Saul Schleimer , Daniel S. Wilkerson , Alex Aiken, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872770]
• 19: Vera Wahler , Dietmar Seipel , Jurgen Wolff v. Gudenberg , Gregor Fischer, Clone Detection in Source Code by Frequent Itemset Techniques, Proceedings of the Source Code Analysis and Manipulation, Fourth IEEE International Workshop, p.128-135, September 15-16, 2004 [doi>10.1109/SCAM.2004.5]
• 20: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States
• 21: Rui Yang , Panos Kalnis , Anthony K. H. Tung, Similarity evaluation on tree-structured data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066243]

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, Experimentation, Languages

Keywords:
clone detection, program dependence graph, refactoring, software maintenance