# US 2023/0418578 A1 · Systems and methods for detection of code clones

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0418578 A1
- Document ID: US20230418578A1
- Status: Published application
- Kind: A1
- Application number: 18/463,956
- Filed: 2023-09-08
- Published: 2023-12-28
- Earliest claimed: 2021-08-28
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Jinfu CHEN; Yuan WANG; Dong QIU; Xin XIA
- Web page: https://patentgrep.com/patent/US20230418578A1

## CPC

- G06F 8/443: {Optimisation}
- G06F 8/751: {Code clone detection}
- G06F 8/73: Program documentation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and devices are described for detecting code clones in a software program. The source code of the software program is processed into a group of n-gram representations. A clone index is generated for each respective code portion defined in the normalized source code, where each clone index includes a feature vector encoding features of the respective code portion based on the n-gram representations corresponding to the respective code portion. Comparison of the clone indexes is used to detect a code clone, based on matching the feature vectors of the clone indexes.

## Claims

### Claim 1

A method comprising:
obtaining a software program comprising source code;
processing the source code into groups of n-gram representations, each group of n-gram representation corresponding to a respective line of code in the source code;
generating a clone index for each respective code portion defined in the source code, each respective code portion comprising a defined number of lines of code, wherein each clone index includes a feature vector encoding features of the respective code portion based on the n-gram representations corresponding to the respective code portion; and
detecting a code clone based on matching the feature vectors of the clone indexes by comparing the clone indexes.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
outputting a code clone report including an entry indicating the detected code clone.

### Claim 3 (depends on 1)

The method of claim 1, wherein processing the source code into the groups of n-gram representations comprises:
processing the source code into formatted source code having a common format;
converting the formatted source code into abstracted source code according to an abstraction level;
normalizing the abstracted source code into normalized source code comprising token sequences, wherein each token sequence corresponds to a respective line of code in the normalized source code and wherein each line of code in the normalized source code corresponds to a respective line of code in the source code; and
generating, for each token sequence, the group of n-gram representations corresponding to the respective line of code.

### Claim 4 (depends on 3)

The method of claim 3, wherein converting the formatting source code into the abstracted source code comprises:
obtaining a selection of the abstraction level, wherein the abstraction level defines one or more types of identifiers in the formatted source code to be replaced with respective generic labels; and
replacing the defined one or more types of identifiers in the formatted source code with the respective generic labels, to obtain the abstracted source code.

### Claim 5 (depends on 4)

The method of claim 4, wherein the abstraction level is selectable by user input.

### Claim 6 (depends on 1)

The method of claim 1, wherein the defined number of lines of code is selectable by user input.

### Claim 7 (depends on 1)

The method of claim 1, wherein generating the clone index for a given code portion comprises generating the feature vector encoding features of the given code portion, wherein generating the feature vector comprises:
extracting features from the given code portion based on the n-gram representations corresponding to the given code portion;
for each feature, generating a respective weighted hash vector; and
combining the weighted hash vectors into a combined vector for use as the feature vector.

### Claim 8 (depends on 7)

The method of claim 7, wherein extracting features from the given code portion comprises:
obtaining a collection of n-gram representations corresponding to the given code portion by collecting the group of n-gram representations corresponding to each line of code belonging to the given code portion; and
extracting the features from the given code portion, wherein each n-gram representation in the collection of n-gram representations is a feature of the given code portion, and wherein a count of each feature within the collection of n-gram representations is a respective weight.

### Claim 9 (depends on 7)

The method of claim 7, wherein generating the respective weighted hash vector for each feature comprises:
for each feature, generating a respective hash vector using a hash algorithm; and
for each hash vector corresponding to a respective feature, applying the respective weight to obtain the respective weighted hash vector.

### Claim 10 (depends on 7)

The method of claim 7, wherein the combined vector is further converted to a binary combined vector for use as the feature vector.

### Claim 11 (depends on 1)

The method of claim 1, wherein the clone index for a given code portion comprises an identifier of the source code, an indicator of a location of the given code portion in the source code, and the feature vector encoding features of the given code portion.

### Claim 12 (depends on 1)

The method of claim 1, wherein each code portion defined in the source code is defined by using a sliding window, the defined number of lines of code in each code portion being defined by a size of the sliding window.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
storing the clone indexes in a clone index database.

### Claim 14 (depends on 1)

The method of claim 1, wherein detecting the code clone comprises comparing the clone indexes associated with the software program with clone indexes associated with another software program.

### Claim 15

A device comprising:
a processing unit configured to execute instructions to cause the device to:
process a source code into groups of n-gram representations, each group of n-gram representation corresponding to a respective line of code in the source code;
generate a clone index for each respective code portion defined in the source code, each respective code portion comprising a defined number of lines of code, wherein each clone index includes a feature vector encoding features of the respective code portion based on the n-gram representations corresponding to the respective code portion; and
detect a code clone based on matching the feature vectors of the clone indexes by comparing the clone indexes.

### Claim 16 (depends on 15)

The device of claim 15, wherein the processing unit is configured to execute the instructions to further cause the device to:
output a code clone report including an entry indicating the detected code clone.

### Claim 17 (depends on 15)

The device of claim 15, wherein the processing unit is configured to execute the instructions to further cause the device to process the source code into the groups of n-gram representations by:
processing the source code into formatted source code having a common format;
converting the formatted source code into abstracted source code according to an abstraction level;
normalizing the abstracted source code into normalized source code comprising token sequences, wherein each token sequence corresponds to a respective line of code in the normalized source code and wherein each line of code in the normalized source code corresponds to a respective line of code in the source code; and
generating, for each token sequence, the group of n-gram representations corresponding to the respective line of code.

### Claim 18 (depends on 17)

The device of claim 17, wherein the processing unit is configured to execute the instructions to further cause the device to convert the formatting source code into the abstracted source code by:
obtaining a selection of the abstraction level, wherein the abstraction level defines one or more types of identifiers in the formatted source code to be replaced with respective generic labels; and
replacing the defined one or more types of identifiers in the formatted source code with the respective generic labels, to obtain the abstracted source code.

### Claim 19 (depends on 15)

The device of claim 15, wherein the processing unit is configured to execute the instructions to further cause the device to generate the clone index for a given code portion by generating the feature vector encoding features of the given code portion, wherein generating the feature vector comprises:
extracting features from the given code portion, based on the n-gram representations corresponding to the given code portion, by:
obtaining a collection of n-gram representations corresponding to the given code portion by collecting the group of n-gram representations corresponding to each line of code belonging to the given code portion; and
extracting the features from the given code portion, wherein each n-gram representation in the collection of n-gram representations is a feature of the given code portion, and wherein a count of each feature within the collection of n-gram representations is a respective weight;
for each feature, generating a respective weighted hash vector; and
combining the weighted hash vectors into a combined vector for use as the feature vector.

### Claim 20

A non-transitory computer readable medium having instructions encoded thereon, wherein the instructions, when executed by a processing unit of a device, cause the device to:
process a source code into groups of n-gram representations, each group of n-gram representation corresponding to a respective line of code in the source code;
generate a clone index for each respective code portion defined in the source code, each respective code portion comprising a defined number of lines of code, wherein each clone index includes a feature vector encoding features of the respective code portion based on the n-gram representations corresponding to the respective code portion; and
detect a code clone based on matching the feature vectors of the clone indexes by comparing the clone indexes.
