CN111324380A - Efficient multi-version cross-project software code clone detection method - Google Patents

Abstract

The invention belongs to the technical field of software code analysis, and particularly relates to an efficient multi-version cross-project software code clone detection method. The method comprises the steps of firstly obtaining version information of a software project containing a plurality of versions, then establishing a method version group by the same method with different versions and same or highly similar code contents based on method names and file paths, selecting the earliest version in each method version group as a sample method, wherein a set of the sample methods is called a history image, then carrying out clone detection on all the history images, and simultaneously establishing an index relation between the sample method and the method version group, which is called method index. And finally, recovering the original full-scale clone relation according to the clone detection result of the sample method and the method index. The invention considers that a plurality of versions of the project have a large amount of repeated codes, and shields the repeated codes during code clone detection, thereby improving the efficiency of multi-version cross-project code clone detection.

Description

An efficient multi-version cross-project software code clone detection method

technical field

The invention belongs to the technical field of software development, in particular to an efficient multi-version cross-project software code clone detection method.

Background technique

There are various reasons for the generation of cloned code. Software developers intentionally or unintentionally copy and paste the software code is the main reason for the generation of cloned code. Cloning is usually accompanied by some slight modifications, but cloning can improve the speed of code development. It also brings many hidden dangers. To understand the repeated codes in a complex software project and the relationship with other software projects, and to improve the stability of the key codes of the target software, it is necessary to use code clone detection technology and automated code analysis technology to achieve. And the code clone information can assist code reviewers and analysts to discover the key codes of the target software system and form a complete and comprehensive understanding, laying a data foundation for in-depth understanding of the software system, thereby improving the robustness and stability of the system.

At present, researchers at home and abroad have made many research results on code clone detection technology. Including but not limited to: Baker et al. proposed a text-based clone detection method, which treats the source code as text and compares it as a basic unit of text to detect clones. Kamiya et al.'s CCFinder uses a lexical analyzer to divide each line of source code into tokens, then converts the token sequences, and finally uses a suffix tree-based matching algorithm to perform clone detection on the converted token sequences. Baxter et al. proposed an abstract syntax tree detection method, which parses the source code into a syntax tree for clonal analysis, thereby preserving more syntactic structure. Ferrante et al. proposed a clone detection method based on program dependency graph, which converts the source code into a program dependency graph and then uses the similarity between graphs to detect clones.

The current clone detection technologies or tools in academia mainly focus on the clone detection algorithm itself. However, for some projects with multiple versions, due to the large amount of repetitive code between the versions, no matter which clone detection tool is used, it is unavoidable There is a large number of unnecessary duplicate detections. In order to detect clones more efficiently, considering the regularity of code duplication between versions, a clone detection method that is more suitable for multi-version projects than traditional code clone detection methods is proposed, which greatly improves the efficiency of multi-version project clone detection.

SUMMARY OF THE INVENTION

The purpose of the present invention is to consider that there are a large number of duplicate codes in multi-version projects, and the traditional clone detection method will have many unnecessary duplicate detections. Multi-version software project code clone detection method.

The main idea of the high-efficiency multi-version software project code clone detection method based on the code mapping relationship between versions provided by the present invention is: for a project with multiple versions, according to some heuristic rules Methods Establish method version groups, and then select a method from each method version group as a sample to participate in clone detection. Finally, the clone detection result of the sample method is restored to the complete clone detection result.

The concrete steps of the method of the present invention are as follows:

a. Obtain the historical version information of each software project to be analyzed, including version name and release time;

b. For each project, (1) establish a method version group: first, establish a method version group for the same method with different versions, the same or highly similar code content; (2) build a historical image: then select the earliest method from all method version groups The version of the sample method is used as the sample method, and the collection of these sample methods is called the historical image of the project; (3) Establish method index: Finally, establish the index relationship between the sample method and the method version group in which it belongs, which is called the method index. If the project has only one version, the version is the historical image of the project;

c. Use the code clone detection tool to perform clone detection on the historical images of each project, and obtain the clone detection results;

d. Use the obtained clone detection result in combination with the method index saved in step b to restore the original full clone relationship.

In step a, the items to be detected are the set of items specified by the user that need to be tested for code clones. This step requires the user to provide version information for these items.

Wherein, the version information of the software to be analyzed includes the names of all versions of the project and the corresponding release time. The version information is stored in a predetermined format. The acquisition of version information can be directly exported by version control tools such as SVN, Git, etc. If the project is not managed by the version control tool, version information can be added manually according to the specified format.

In step b, the establishment of a method version group is for a single project. If the project has multiple versions, there are likely to be a large number of the same methods between versions, and these methods generally exist in the same relative path. , and the method name is the same. According to this feature, the cost of establishing a method version group is very small, but the efficiency of subsequent clone detection is greatly improved. The specific process is to process each version of the project in turn as follows according to the release time sequence of the version: first extract all methods in the current version, and for each method, determine whether it already belongs to a method version group, and skip to Otherwise, create a new method version group, for this method, extract the relative path between its method name and the file where it is located, find all subsequent versions of the method with the same relative path, method name and highly similar text, and put these The method is added to this new method version group. Next, the earliest version in all method version groups is selected as the sample method, and the set of all sample methods in a project is called the historical image of the project. Finally, the index relationship between the sample method and the method version group is established, and the index is called the method index.

Wherein, the determination criterion of the same method is based on the edit distance between the method texts, specifically: for methods A and B, if the edit distance between the methods A and B texts is smaller than the length of the methods A and B texts If the ratio is less than 0.05, that is, the text similarity between methods A and B exceeds 95%, then methods A and B are considered to be the same method.

In step c, the clone detection is to detect the historical images of each project, the detection scope includes both intra-project and inter-project clones, and the detection result is a clone group. Moreover, the detection tool is configurable, and it can be developed by using the existing detection tool.

In step d, the restoration of the original full clone relationship refers to mapping from the partial clone relationship to the complete clone relationship based on the clone detection result of the historical image of the project, combined with the method index.

The full clone relationship refers to the result detected by the clone detection tool without additional processing of the multi-version project.

Compared with the prior art, the present invention has the following advantages and positive effects: the present invention provides an effective means for software maintainers and software developers to understand the clone relationship within a multi-version software system and other projects. Different from the traditional code clone detection technology or tool that mainly focuses on the algorithm itself, the present invention starts from the structural characteristics of the multi-version project itself, reduces the amount of code to be detected in the multi-version project, and can greatly improve the detection of multi-version cross-project code clones. efficiency.

Description of drawings

FIG. 1 is a schematic diagram of the basic process of the present invention. It includes several processes of extracting project version information, establishing method version group, historical image and method index, clone detection and clone recovery.

FIG. 2 is a schematic diagram of an exemplary implementation process, showing a specific process of clone detection for multiple release versions of a software project set.

Detailed ways

The objectives, specific structural features and advantages of the present invention can be further understood through the following description of the embodiments of the present invention in conjunction with the accompanying drawings. FIG. 2 is a schematic diagram of an example implementation process.

In this embodiment, a total of 251 Java open source projects with more than 50 stars, at least two release versions, and from different fields are selected from GitHub as clone detection target codes. The following is an example of a specific implementation manner of the multi-version cross-project code clone detection for the software project collection.

The main process based on this embodiment is:

(1) According to the target project set path, version information file path, etc. specified by the user, parse out the target project set to be detected and its version information; with the help of the version management tool Git, extract and save all the source code of its released version, and at the same time Save all its version information to the database; considering that this embodiment is only for Java code, only the Java code file (.java file) in the source code is retained; there are a total of 3234 released versions, and the total number of lines of code is about 300 million Row;

(2) Constructing historical images and establishing method indexes; it took 1129 seconds to construct historical images for the selected 3234 released versions and save method indexes using this method (to ensure the credibility of the results, the average value was obtained after multiple construction operations, The same below); the generated historical images of 251 projects total about 40 million lines of code and 788,120 sample methods;

(3) Clone detection; we used an existing code clone detection tool to perform cross-project clone detection on the historical image generated in step (2), and obtained 82,595 clone groups with a total of 644,653 clone instances, which took a total of 96 seconds;

(4) Restore the full clone relationship; according to the detected clone group and the established method index, restore the full clone relationship, with a total of 3,821,507 instances.

Analysis of the results: The amount of historical image code generated in the second step is about 40 million lines, which is reduced by about 87% compared with the code amount of all the original releases (300 million lines). In the third step, clone detection of historical images takes 96 seconds. As a comparison, we also used the same code clone detection tool to perform code clone detection on the same code set (3234 original 300 million lines of code in 3234 releases), which took about 5800 seconds in total. It can be seen that after using this method, the overall clone detection time is greatly reduced, and the efficiency of multi-version cross-project code clone detection is improved.

Claims (6)

1. An efficient multi-version cross-project software code clone detection method is characterized by comprising the following specific steps:

a. acquiring historical version information of each software project to be analyzed;

b. for each project, a method version set is first established: establishing a method version group for the same method with different versions and same or highly similar code content; then, a history map is built: selecting the earliest version from all the method version groups as a sample method, wherein the set of the sample methods is called a history image of the item; and finally establishing a method index: establishing an index relation between a sample method and a method version group where the sample method is located, wherein the index is called a method index;

c. performing clone detection on the historical images of all the projects by adopting a code clone detection tool to obtain a clone detection result;

d. and (c) restoring the original full-scale clone relation by combining the obtained clone detection result with the method index stored in the step b.

2. The method according to claim 1, wherein in step a, the version information of the software to be analyzed includes names of all versions of the project and corresponding release times; the version information is stored in a predetermined format.

3. The method according to claim 1, wherein in step b, the specific process of establishing the method version group is to sequentially perform the following processing on each version of the project according to the release time sequence of the versions: firstly, extracting all methods in the current version, judging whether each method belongs to a certain method version group or not for each method, and skipping if the method belongs to the certain method version group; otherwise, establishing a new method version group, extracting the relative path between the method name and the file where the method is located, searching methods which are the same as the relative path and the method name and have highly similar texts in all subsequent versions, and adding the methods into the new method version group; then, selecting the earliest version in all method version groups as a sample method, wherein the set of all sample methods in a project is called a history image of the project; finally, an index relationship between the sample methods and the groups of method versions is established, and the index is called a method index.

4. The method according to claim 3, wherein in step b, the criterion of the same method is an edit distance between method texts, specifically: for method a and method B, if the ratio of the edit distance between the texts of method a and method B to the smaller of the text lengths of method a and method B is less than 0.05, i.e., the text similarity between method a and method B exceeds 95%, then method a and method B are considered to be the same method.

5. The method according to claim 3, wherein in step c, the clone detection is performed on the history map of each item, the detection range includes the clone within the item and among the items, and the detection result is a clone group; also, the detection tool is configurable.

6. The method according to any one of claims 1 to 5, wherein in step d, the restoring of the original full-scale clonal relationship refers to mapping from a partial clonal relationship to a full clonal relationship in combination with a method index based on a clonal detection result of a history map of an item;

wherein, the full-scale clone relation refers to the result detected by a clone detection tool under the condition that the multi-version project is not additionally processed.

Images