Publication Type
Conference Proceeding Article
Version
submittedVersion
Publication Date
5-2008
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.
Keywords
program dependence graph, refactoring, software maintenance, clone detection
Discipline
Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
ICSE '08: ACM/IEEE 30th International Conference on Software Engineering: 10-18 May 2008, Leipzig, Germany
First Page
321
Last Page
330
ISBN
9781605580791
Identifier
10.1145/1368088.1368132
Publisher
ACM
City or Country
New York
Citation
GABEL, Mark; JIANG, Lingxiao; and SU, Zhendong.
Scalable detection of semantic clones. (2008). ICSE '08: ACM/IEEE 30th International Conference on Software Engineering: 10-18 May 2008, Leipzig, Germany. 321-330.
Available at: https://ink.library.smu.edu.sg/sis_research/934
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://doi.org/10.1145/1368088.1368132