Detection of Code Clone Based on Source Fragment Alignment

MATERIALS AND METHODS

Definitions
Definition 1: A token is a minimum meaningful element in source code, such as identifier, constant, symbol and delimiter, denoted by T.

Definition 2: A token sequence is a sequence of tokens generated after the normalization of source code. For a given source file f, its token sequence can be represented as: TS_f = (T₁, T₂, T₃,…,T_i,…,T_t), where, T_i is a token in f and t indicates the number of tokens in f.

Definition 3: A source hash sequence is defined as a sequence of values, each representing the hash value of the token sequence of one single line in a source file f, denoted by SHS_f = (h₁, h₂, h₃,…,h_i,…,h_k), where, k is the number of hash values (or lines) in f. In the method, the MD5 hash value is calculated for the token sequence of each line in the source file.

Definition 4: An i-th left prefix is the sub sequence consisting of the first i elements of a source hash sequence. For a given source hash sequence SHS_f = (h₁, h₂, h₃,…,h_i,…,h_k) of file f, its i-th left prefix is = (h₁, h₂, h₃,…,h_i,) where, 1<i<k.

Definition 5: An alignment matrix SSM^p,q represents the alignment of two source hash sequences for source files p and q, in which the cell locates at the i-th row and the j-th column indicates the alignment score of hash sequences values of the first i lines from file p and the first j lines from file q. More specifically, given two source hash sequences SHS_p and SHS_q for files p and q, respectively, in the alignment score matrix SSM^p,q represents the alignment score between and

Fig. 1:	Example of alignment matrix using the original Smith-Waterman algorithm

Figure 1 gives an example of alignment matrix for sequences "tabbcemnqsxyz" and "tabbcefoptxyz". For instance, indicates the alignment score between the first 6 lines of SHS_p and the first 6 lines of file SHS_q.

Mosaic problem refers to the mismatched fragment existed in the alignment of source hash sequences. When the mismatched fragments are long, the mosaic problem would decrease the accuracy of alignment.

Given two sequences SHS_p = "tabbcefoptxyz" and SHS_q = "tabbcemnqsxyz". Figure 1 shows the alignment matrix of SHS_p and SHS_q using the original Smith-Waterman algorithm. The final alignment would be:

SHS_p: t a b b c e f o p t -- -- -- -- x y z
SHS_q: t a b b c e -- -- -- -- m n q s x y z

Figure 1 shows that A and C are high similar areas and B is the low similarity area due to the so called mosaic problem. However, in the proposed method, the alignment would be broken into two more similar alignments:

SHS_p: t a b b c e x y z
SHS_q: t a b b c e x y z

Figure 2 shows that the improved Smith-Waterman algorithm will cut off the low similarity area B and only reserves the areas A and C which have high similarity. Obviously, the alignment A and C can reflect the similarity of p and q in a more accurate way.

Proposed method: The process of the proposed code clone detection approach can be divided into the following two phases: Code preprocessing and code clone detection. The phase of code preprocessing involves parsing, normalizing and sequencing the source files and persisting the intermediate results, whereas the phase of code clone detection deals with the source hash sequence alignment and identification of candidate code clones.

Code preprocessing
Parse and normalize source code: During this step, the source files are lexically analyzed for the normalization. More specifically, white spaces and comments are removed, whereas the user defined keywords, literals and identifiers are transformed into specific tokens. In this way, the source files are converted into token sequences. Meanwhile, the line numbers are recorded for locating code clones in source files later.

Sequence the source code: The MD5 (Message digest) algorithm is adopted to calculate the hash value of each line in the transformed token sequences. In this way, source files are converted into source hash sequences which are the inputs of the next phase of code clone detection.

Persist the intermediate results: In order to realize the incremental update and fast search, two indexes, i.e., GlobalIndex and TimestampIndex are created.

Fig. 2:	Example of alignment matrix using the proposed algorithm

GlobalIndex is the global index which maps names of source files with their source hash sequences. Meanwhile, TimestampIndex saves the time stamps of latest source file normalization. When initiating the code clone detection process, TimestampIndex is compared with file modification time. Only the file that has been changed since the latest normalization needs to be re-normalized.

Code clone detection: This phase can be further divided into the following two steps.

Alignment of hash sequences: During this step, an alignment matrix is constructed to represent the alignment between two hash sequences. The key to this step is how to calculate the alignment scores, which is given by Eq. 1, where CT represents the predefined cutting threshold. The SSM_i,j is the score of cell(i, j), whereas cell(i, j) is the cell corresponding to the i-th row and j-th column in the matrix. Additional, to calculate the alignment scores, the maxScore of each cell which refers to the max score along the closed trace back path, also needs to be set, as Eq. 3 shows, where, (m, n)∈{α|α∈{(i-1, j), (i, j-1), (i-1, j-1)}}, i>1, j>1:

(1)

Where:

(2)

(3)

Here, an acceleration penalty strategy is introduced to avoid the so-called mosaic problem. The main idea of acceleration penalty strategy can be summarized as follows. A cutting threshold is predefined in the process of calculating the score of each cell. If the difference of a cell’s maxScore and Score is equal or exceeds than the cutting threshold, the maxScore and Score are reset. In this way, the matched sequences can be broken into two pairs of more-matched ones if some middle fragments are not so matched.

As algorithm 1 illustrates, an initial score matrix for SHS_p and SHS_q (Lines 2-8) is created first. Afterwards, the Score and maxScore of each cell are calculated (Lines 10-18). In particular, if the difference of a cell’s maxScore and Score is greater or equal than a predefined cutting threshold, its Score and maxScore are reset to 0 (Lines 19-21). Finally, if a cell’s Score is above a predefined cutting threshold and it’s Score is greater than it’s maxScore and the i-th hash value of SHS_p and the j-th hash value of SHS_q corresponding to the cell are exactly matched, cell(i, j) is regarded as the start point of a closed trace back path (Lines 22-24).

Algorithm 1:	Code sequence alignment

Identification of code clones: After the alignment matrix is calculated, the closed trace back paths are then determined to find the matching subsequences, or code clones.

Definition 6: The preCell of a cell in the alignment matrix refers to the cell which its score is calculated from. The preCell of cell (i, j) can be obtained as follows:

(4)

Definition 7: A closed trace back path is the path which starts at a cell in the alignment matrix and follows its preCell until reaching the cell with 0 score. It represents the alignment of the given hash sequences.

The examples of preCell and closed trace back path are presented in Fig. 1. Algorithm 2 introduces how to find closed trace back paths that correspond to code clones. Firstly, the status of each cell is initialized to be unvisited (Lines 1-3). Afterward, the cell with maximum score among all unvisited ones is set to visited. Starting from this cell, the pre-cells are continuously traced back until reaching the cell with 0 score. In this way, a trace back path is obtained. Furthermore, the status of each cells in the obtained trace back path is set to visited and add their row numbers and column numbers to stack1 and stack2, respectively. This process is repeated until all cells are visited (Lines 5-12). Finally, the track back paths are mapped to the code clone pairs according to the records in stack1 and stack2 (Lines 13-14).

Algorithm 2:	Detection of closed trace back paths

RESULTS

To evaluate the effectiveness of the proposed method, 8 open source systems were selected and the results are compared with Bellon’s benchmark. The benchmark was constructed through the manually verification of the 2% code clone results of all the tools. The characteristic of 8 systems being tested in the experiment are shown in Table 1. The last column (No. of references) indicates the number of code clones in systems. The experiments were ran on Ubuntu with Intel Core2 Duo CPU E7500 and Redis, an open source, key-value database, is used to persistent the intermediate results.

The values of match, mismatch, insert and delete are set to 2, -2, -1 and -1, respectively according to the study performed by Murakami et al.⁶. Since the minimum lines of code clones detected in Bellon’s benchmark is 6, the Cutting Threshold is set to 12. Recall, precision and F-measure are used to evaluate the performance of the approach, which can be calculated as follows:

Fig. 3(a-c):	Recall, precision and F-measure of the proposed method and Murakami’s method

Table 1:	Characteristic of the systems

(5)

where, TC is true clones, RC is reference clones and CC is candidate clones.

The results are compared with Murakami’s method. The reason why choosing this method for comparison is that it employs Smith-Waterman algorithm, a similar approach as ours. The detail information of results are given in Fig. 3.

Figure 3a shows that compared with Murakami’s method, the proposed method achieves the higher recalls for all systems. In the best case, the recall is increased by almost 40% (weltab), whereas in the worst case, the recall is enhanced by 3% (jdtcore). However, the precisions are not always increased. Figure 3b shows that the precisions of the proposed method are higher than those of Murakami’s method for ant, jdtcore, swing, weltab and postgresql but lower for netbeans, cook and snns. By combining the precision and recall, however, the F-measure values of the proposed method outperform those of the Murakami’s method for all systems except for netbeans as shown in Fig. 3c. In other words, the method proposed in this study performs significant better than Murakami’s method.

Threats to validity: This study discusses the main threats to validity, a key challenge for researchers and practitioners in empirical research work. Generally speaking, several aspects need to be considered, such as construct validity, internal validity and external validity.

Construct validity generally refers to the validity of inferences that observations or measurement tools actually represent or measure the construct being investigated. In the context of study, this is mainly in relation to how the precision and recall are measured. During the experiments, the proposed code clone detection results is evaluated by using Bellon’s benchmark which only validates 2% of their code clone detection results. In other words, there are a lot of code clones that are not validated. However, the precisions and recalls are considered to be consistent if all the code clones of the systems had been used to evaluate the methods, simply because of Bellon et al.⁴ 2% detected clones are evenly distributed in the systems.

Threats to internal validity refers to experimental factors that could influence the results. During the code clone detection process, four parameters, i.e., match, mismatch, insert, delete and cutting threshold are introduced. The four parameters are set to the fixed values for all 8 systems according to the experience. If the parameters are changed to other values, the results of code clone detection may be different. Therefore, it is necessary to try different parameters to obtain the optimal ones.

As for the external validity, which concerns the extent to which the (internally valid) results of a study can be held to be true for other cases, the proposed method chooses eight systems for code clone detection. Although these systems are often used in code clone researches, they are all programmed in Java or C. It could be worthwhile to replicate the evaluation on other systems programmed in different languages, such as C# and JavaScript.

DISCUSSION

Code clone detection has been one of the main research focuses in the field of software analysis during the past decade. There are quite a few methods proposed for code clone detection at present, which are mainly based on text, token, AST, PDG, metric and some other approach.

Text-based approaches detect code clone after simply preprocessing the source code: remove white space and comments. Cordy’s NICAD is a text-based code clone detection tool which can detect type-3 clone effectively⁸. It converts the source code in a specific form of texts and then detects code clone by comparing similarity of texts. Simcad is another code clone detection tool developed by Uddin et al.⁹, Simcad transforms the source code to hash values through simhash algorithm and applies a three level index to speed up code clone detection. The SDD developed by Lee and Jeong¹⁰ is a tool which can detect code clone for large scale systems, SDD used inverted index to detect both exact and inexact code clones.

Token-based approach firstly converts the source code to token sequence through lexical analysis and detects code clones according to the similarity of token sequences. Finder¹¹ is a classical code clone detection tool, which transforms the source code into token sequences through normalization at first and then employs suffix tree to detect code clone based on the token sequences. Murakami et al.⁶ proposed a gapped code clone detection method which applies Smith-Waterman algorithm to clone detection, meanwhile, they rebuild Bellon’s benchmark according to add some gap information. Sajnani et al.¹² introduced a code clone detection tool SourcererCC, which uses the inverted index to speed up the code clone detection process and decrease the time used for index creating, token comparison times through heuristic filter. The source code is converted to abstract syntax tree according to syntax analysis. If the similarity of two sub trees is above the threshold, the code fragments corresponding to the sub trees are code clone. Baxter et al.¹³ proposed an AST-based method. They transform the source code into an abstract syntax tree with marked nodes and then calculate the hash values of sub-trees in the syntax tree. Code clones are finally detected through the comparison of hash values of sub-trees. Deckard, developed by Jiang et al.¹⁴ calculates the feature vectors base on code fragment’s abstract syntax tree, and then it uses LSH algorithm to detect code clones through clustering analysis for the feature vectors. Koschke et al.¹⁵ firstly converted the source to abstract syntax tree and serialized the abstract syntax tree to token sequences; code clones are finally detected based on the token sequences through suffix tree algorithm.

The PDG-based approach need to convert the source to PDG, if two sub graphs are similar enough, the code fragments corresponding to the two sub graph are code clone. Higo and Kusumoto¹⁶ presented a heuristic PDG-based clone detection strategy which can reduce the computation complexity. Krinke¹⁷ presented an approach to identify similar code in programs based on finding maximal similar sub graphs in fine grained program dependence graphs. Sargsyan et al.¹⁸ introduced a code clone detection method which consisted of two steps: Construct the program dependence graph and find the similar sub graphs. The PDGs were divided into sub graph units to make the method scalable.

Metric-based approach firstly calculates the metric of code fragments and detect code clone through the comparison of metrics. Mayrand et al.¹⁹ proposed a method to automatically identify clone functions in source code. The method used datrix to extract 21 metrics which are focused on the control flow metrics and data flow metrics and code clones are detected based on the comparison of metrics. Singh and Sharma²⁰ combined text based and metric based method to detect file level clones, their method can also detect high level clones in terms of file clones in different or same directories.

Smith-Waterman algorithm is a dynamic programming algorithm which is used to identify the local alignment between gene sequences⁵. As for a very successful approach of gene sequence alignment, there are still a number of methods proposed to improve the efficiency of Smith-Waterman algorithm. Liu et al.²¹ introduced a parallel version of Smith-Waterman algorithm, which utilizes the emerging Xeon Phis to speed up the implementation of long DNA sequences comparison. According to Sandes and de Melo²², a high performance computing platform is employed to the parallel implementation of Smith-Waterman algorithm in linear space. With the ability of sequence alignment, Smith-Waterman algorithm can also be used to detect code clone. For example, Murakami et al.⁶ applied Smith-Waterman algorithm to detect gapped code cloned.

Mosaic problem appears when the Smith-Waterman algorithm is applied to long sequence alignment. Here, mosaic problem refers to the region with low similarity in the optimal local alignment of sequences. It is necessary to eliminate mosaic problem since it decreases the accuracy of alignment. Huang, Zhang et al.²³ tried to solve the mosaic problem during the post process phase. However, their approaches may miss some local alignment with high similarity. Arslan et al.²⁴ introduced a length correction coefficient to avoid the mosaic problem. Nevertheless, it brings new problem of no fixed model to follow if the coefficient is relevant with the data used.

Different from the above code clone detection methods, the proposed one can detect the gapped type-3 clones effectively. In addition, it does not need to transform the source code into a complex intermediate representation (e.g., AST and PDG). Instead, it only needs to convert code into token sequence, which is straightforward.

CONCLUSION AND RECOMMENDATIONS

In this study, a new code clone detection method inspired by the Smith-Waterman algorithm is proposed. In order to resolve the mosaic problem when the Smith-Waterman algorithm is applied to the detection of code clone among the long token sequences, an acceleration penalty strategy is designed to enhance the accuracy of code clone detection. Additional, the trace back mechanism is employed to identify the closed trace back path, which further help identify code clone effectively. Finally, an experiment is demonstrated to validate the proposed method. The results show that the proposed method can detect code clone more effectively.

In the future, the reasons leading to some false positives and improve the precision of the proposed method needs to be investigated. Furthermore, the proposed method will be realized as a tool that can be used in the real software development process. Finally, in order to reduce the threats of validity, we plan to construct a complete benchmark with all clones in the systems (including the systems programmed with C# and JavaScript) and different parameters to further evaluate our method.

SIGNIFICANT STATEMENTS

Sequences of duplicate code with or without modification are known as code clones or just clones. They occur either within a program or across different programs owned or maintained by the same entity. Code clones are generally considered undesirable although they do bring about some convenience for developers. A new method for detecting code clones based on the alignment of two source code fragments is proposed. The acceleration penalty strategy and the closed trace-back paths helps improve the accuracy of code clone detection. An extensive experiment on 8 open source systems is conducted to measure the precisions and recalls. The results show that the proposed method can detect code clone more effectively than the current methods.

ACKNOWLEDGMENT

This study is supported by Natural Science Foundation of China (No. 61100043), Zhejiang Provincial Natural Science Foundation (No. LY12F02003) and the Key Science and Technology Project of Zhejiang (No. 2016F50014 and No. 2017C01010).