Scalable and accurate detection of code clones

Abstract

A detailed description of a method for detection of code clones is described. This method is based on the semantic analysis of programs and on new algorithms that make it scalable without affecting its accuracy. The proposed method involves two phases. In the first phase, the program dependence graph (PDG) is constructed while the program is compiled. LLVM is used as the compilation infrastructure. In the second phase, similar subgraphs of maximum size that represent code clones are detected. Before starting the search for similar subgraphs, the PDG is divided into subgraphs that will be considered as potential clones of each other. To ensure scalability of the search for similar subgraphs, the composition of algorithms is used. The first algorithm checks that a pair of graphs cannot have similar subgraphs of the desired size; this is done in a linear amount of time. If this algorithm fails, another (approximate) algorithm is executed to find similar subgraphs of maximum size. After similar subgraphs have been found, the program code is additionally checked for the position of the code lines corresponding to the detected clone candidates. Tests showed that the developed tool is more accurate than similar tools, such as MOSS, CCFinder, and CloneDR. Results obtained for the projects Linux-2.6, Firefox Mozilla, LLVM/Clang, and OpenSSL are presented.