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

Additional URL

http://doi.org/10.1145/1368088.1368132

Share

COinS