approximate code cloning detection method adopting GPU acceleration

Abstract

The invention belongs to the technical field of software code analysis, and particularly relates to an approximate code cloning detection method accelerated by a GPU. According to the invention, source codes of a plurality of software projects are labeled; converting into a string consisting of a tag sequence; constructing the string into a suffix array sorted according to suffix character stringsby adopting a GPU (Graphics Processing Unit) parallel method; and finally, the code cloning fragments which are smaller than the code cloning length threshold but not smaller than the candidate cloning length threshold are sequenced through a GPU parallel acceleration method according to the position in the code file, and whether the cloned fragments can meet the similarity threshold requirementof approximate cloning or not after being merged is calculated. And if the code similarity meets the threshold requirement, recording the code similarity as approximate code cloning. According to themethod, the approximate code clone can be rapidly detected on the code fragment granularity in mass codes.

Description

technical field [0001] The invention belongs to the technical field of software code analysis, and in particular relates to an approximate code clone detection method accelerated by GPU. Background technique [0002] Code clone detection is a technique to find duplicate identical or similar code fragments from software source code. As early as the 1990s, researchers noticed the repetitive nature of software code. Code duplication or code cloning generally falls into four types. Type I (Type-1) clone refers to the exact same code fragment. Type II (Type-2) clones are parameterized similar codes that are identical except for identifiers, constants, and types. Type III (Type-3) clones refer to similar codes that have additions, deletions, or other modifications beyond Type II clones. Type IV (Type-4) cloning refers to codes with similar semantics, that is, the grammatical structure may be completely different, but the codes have similar semantics. Among the code clone dete...

AI Technical Summary

Problems solved by technology

In 2016, researchers in the United States and Canada developed the SourcererCC[3] clone detection tool, which uses code word bagging technology and heuristic rules to detect approximate clones of codes with a given boundary in hundreds of millions of lines of code. An approximate clone of instrumented method granularity in 250 million lines of code still takes 4.5 days

In 2017, researchers developed CloneWorks[4], which uses a variety of strategies to improve the detection efficiency of large-scale codes. It is currently the fastest approximate clone detection tool. However, this tool provides two different operating strategies: conservative and aggressive. It is difficult to maintain a high level of detection accuracy and performance at the same time

However, this method is mainly used in biological fields such as gene sequence analysis, and has not been used in the field of code analysis for clone detection of source code.

Images