CN112215013B - A deep learning-based clone code semantic detection method - Google Patents

Abstract

The invention discloses a semantic clone detection method based on deep learning, for a given code block pair, firstly preprocessing the code block into a sequence of TPE basic units, then performing word embedding operation on the code block and the TPE basic units, and using the code block and the TPE basic units to a BilSTM module with context characteristic combination; secondly, intensively extracting useful information related to the clone codes learned by the neural network by using a self-attention mechanism; each code segment is converted into a vector representation, the Euclidean distances between the vectors are calculated as the characteristics of classification, and the vectors are classified into two classes: if two code blocks are similar, the vectors they generate over the neural network should be similar, i.e. predictive cloned/uncloned. Compared with the prior art, the invention saves more time and can capture rich grammar and semantic information; TPE can also avoid the problem of insufficient vocabulary (OOV).

Description

A deep learning-based clone code semantic detection method

technical field

The present invention relates to the field of program analysis and machine learning, in particular to a source code representation and semantic clone detection method.

Background technique

Clone code is duplicate code, similar code. It is common to divide code clones into four types: 1) Type 1 clones are two code fragments that are identical except for spaces, formats and comments; 2) Type 2 clones are two code fragments except for identifiers, constants , two code fragments that are exactly the same except for different variable types; 3) Type 3 clone is two code fragments that modify a small number of statements in the copied code fragment, such as changing, adding or deleting a small number of statements; 4) Type 4 Cloning is mainly concerned with functional similarity. The first three types are mainly related to text similarity. The existence of code clones unnecessarily increases program size, changes to code segments also require modifications to their clones, increasing maintenance effort, and duplicating code segments that contain errors can cause errors to propagate. Detecting code clones can help reduce software maintenance costs and prevent bugs.

Among the various methods for detecting code clones, few can detect semantic clones, because semantic clones are the most difficult to detect, they include clones that are syntactically different but still perform the same function, therefore, an efficient method to detect code semantic clones is proposed. is very necessary.

A key issue in semantic clone detection is how to efficiently learn the representation of source code to capture its semantics efficiently. Tokens and Abstract Syntax Trees (ASTs) are often used to detect code clones. However, Token cannot learn the semantic information contained in the code structure well, which is not enough for the task of semantic clone detection. Recent work on semantic clone detection mostly utilizes Abstract Syntax Trees (ASTs) to combine syntactic information to represent codes. These methods are proven to be effective, but the detection efficiency is lower, because the Abstract Syntax Trees (ASTs) of codes are usually more efficient than text parsing. Trees are more complex. Code clone detection considers not only accuracy but also efficiency.

In the code clone detection task, it is very common to use Token as the basic segmentation method to represent the program source code. The normalized token vocabulary size is very small (usually no more than 300 different normalized tokens), and the small vocabulary size leads to the limited capacity of the learned vocabulary (a kind of external knowledge obtained by pre-training), making external pre-training invalid for neural models . Therefore semantic clone detection tasks usually employ unnormalized tokens. But tokens may still fail to capture rich semantic information, especially when meaningless variables are used in programs.

To extract more information from pre-training, a straightforward approach is to expand the input vocabulary. Sentence-level segmentation may be a natural choice, however, due to the diversity of sentences, its vocabulary can be infinitely large. It is impossible to train a vocabulary containing all possible sentence representations. Therefore, it is possible to encounter input sentences for which the vector representation cannot be found in the vocabulary, which is called the OOV (out-of-vocabulary) problem. The OOV problem severely limits the usefulness of code representation.

SUMMARY OF THE INVENTION

The invention aims to solve the problem of detection of semantic code clones in programs, and proposes a semantic clone detection method based on deep learning. A source code representation unit TPE is proposed to represent the program source code, and then a supervised classifier is used to realize the focus Detection of code clone pairs for semantic clone detection.

A deep learning-based clone code semantic detection method of the present invention specifically includes the following processes:

Step 1. Determine the basic unit of the TPE represented by the code in the semantic clone detection task. The generation process of the TPE is as follows: first, each code in the input corpus is truncated into a Token sequence, and the obtained Token is used to initialize the vocabulary vocab, including the The two-tuple tokens in the corpus are merged, then all the token two-tuples in the current corpus are counted, the two-tuple tokens are sorted and marked, and then the token with the highest iteration combination frequency in the corpus is used to identify the new basic unit, and add the newly obtained unit to the vocabulary, the newly generated corpus consists of the newly added two-tuple Token, TPE regards the two-tuple Token as a new Token, the above process is performed iteratively, by continuously iterating Find the combination of tokens with higher frequency to update the vocabulary; after obtaining the final vocabulary, use the backward maximum matching method to divide the code statement into TPEs according to the obtained vocabulary;

According to the selected corpus, the basic unit of TPE in different languages is obtained by using the TPE algorithm;

Step 2, establish a neural network model suitable for code clone detection, use the Skip-Gram model to pre-train the basic unit of the TPE obtained in step 1, and generate a corresponding TPE unit-word vector representation format vocabulary; This series of discrete sequences is converted into a continuous vector representation, and a standard BiLSTM model is implemented and trained; the vector representation of the basic unit of TPE learned by the BiLSTM model is put into a matrix, and multiplied by a weight matrix to obtain a For a fixed-dimensional vector, by continuously learning and updating the weight matrix to grasp the weight of the basic unit vector of each TPE in the entire sentence, the vector representation of the entire code method is obtained; the specific formula is as follows:

表示BiLSTM的隐层输出，s_t表示

的显著性，a_t表示注意力权重t位置元素在整个序列的权重参数，h^CODE表示最终的代码向量表示；j表示迭代参数，t表示当前位置；where v represents the vector parameter, T represents the transpose of the matrix, and each element in the vector represents the importance of each sequence node,

Represents the hidden layer output of BiLSTM, s _t represents

The significance of , a _t represents the weight parameter of the attention weight t position element in the whole sequence, h ^CODE represents the final code vector representation; j represents the iteration parameter, t represents the current position;

Step 3. Design the Siamese architecture to classify and detect clone pairs/non-clone pairs, which specifically includes: giving two vectors converted from two code blocks as input, and pre-training by using the Skip-Gram model to obtain the value of each code block. Vector representation, and then use the calculation method of Euclidean distance between vectors to calculate the difference between the distances of the two output vectors as a feature of classification. The Euclidean distance between vectors is similar to the clone pair, thus obtaining the final clone/non-clone pair. Clone prediction.

Compared with the prior art, the beneficial effects of the present invention are as follows:

(1) Compared with the AST-based representation, the new source code representation basic unit TPE is more time-saving and can capture rich syntactic and semantic information at the same time;

(2) TPE can also avoid the problem of insufficient vocabulary (OOV).

Description of drawings

1 is an overall flow chart of a deep learning-based semantic clone detection method according to the present invention;

Fig. 2 is the example diagram that utilizes TPE to generate TPE unit;

Figure 3 is a diagram of the BiLSTM network structure.

Detailed ways

The present invention will be described in detail below with reference to the accompanying drawings and embodiments.

As shown in FIG. 1 , it is an overall flow chart of a deep learning-based semantic clone detection method of the present invention. The process specifically includes the following processing:

Step 1. Determine the basic unit of TPE represented by the code in the clone code detection task. Through the pre-trained embedding, the potential syntactic/semantic information can be learned from the large-scale original code corpus. Based on the vocabulary generated by the TPE, the expression ability can be improved by pre-training. Strong embedding matrix;

The basic unit generation process of TPE is: firstly truncate each code in the input corpus into a Token sequence, use the obtained Token to initialize the vocabulary vocab including merging all the two-tuple Tokens that appear in the corpus, and then use the obtained Token to initialize the vocabulary vocab. All Token binary groups are counted, the binary Tokens are sorted and marked, and then the Token with the highest frequency of iterative combination in the corpus is used to identify the new basic unit, and the newly obtained unit is added to the vocabulary, and the newly generated The corpus of is composed of newly added two-tuple Tokens. TPE regards the two-tuple Token as a new Token. The above process is performed iteratively, and the vocabulary is updated by iteratively searching for more frequent token combinations. After obtaining the final vocabulary, use the backward maximum matching method to divide the code statement into TPE units according to the obtained vocabulary (for example, a code statement is ABC, and two pointers are set to point to the first character A and the last character of the statement respectively. For a character C, first check whether the vocabulary has the basic unit ABC, if so, treat the entire program statement ABC as a TPE unit; if not, move the first pointer backward to find out whether BC is in the vocabulary. If Continue this process if it does not exist, and finally represent the entire code statement as a TPE unit in the vocabulary. Based on the new TPE vocabulary, a vocabulary with more information can be obtained through pre-training, and then applied in this process;

As shown in Figure 2, it is an example diagram of using TPE to generate a TPE unit, which is used to demonstrate the TPE algorithm of two iterations. The dashed arrows marked ④⑤ are the process of counting tokens in the segmented corpus. The dashed arrows marked ⑥ indicate that after the statistics are obtained, that is, the frequency of each token symbol, the vocabulary is then updated to incorporate the newly identified token combinations. shown. The dashed arrows marked ⑦ indicate that the last step of the iteration is to update the corpus with the newly obtained bigram token units. _V0 shows the vocabulary obtained from the original code snippet.

As an innovative segmentation method, TPE (Token Pair Encoding) uses Token as a basic component to construct a new code representation. TPE carries rich code information, which helps to better utilize the advantages of deep learning-based clone detection. At the same time, TPE can also avoid the problem of insufficient vocabulary (OOV).

Step 2. Establish a neural network model suitable for code clone detection and train it:

Before training, use the Skip-Gram model for pre-training: first, use the TPE algorithm to obtain TPE basic units in different languages according to the selected corpus; then use the Skip-Gram model to pre-train these TPE units to get a TPE unit — The vocabulary of the word vector representation format.

The principle of the Skip-Gram model is to give the center word model to predict the context, and use the prediction results of the surrounding words to adjust the word vector of the center word. In Skip-Gram, each word is affected by the surrounding words, and each word needs to be predicted and adjusted when it is used as a central word. This repeated adjustment and prediction makes the learned word vector more precise. Therefore, the Skip-Gram model is selected as the training model of the TPE unit vector. Use the tool fastText to implement the Skip-Gram model for training, and generate a vocabulary of code basic units-vectors. (Supplement: In the fastText command, set the parameter learning rate to 0.025, the training word vector dimension dim is selected as 100, the context window size ws defaults to 5, epoch and the lowest word frequency minCount both use the default value of 5, negative sampling The number of neg is set to 5, the loss function loss is set to ns, the number of subwords that can be accommodated in bucket is set to 2,000,000, the maximum and minimum character lengths maxn and minn are set to default values of 3 and 6, the number of threads is set to 4, and the learning rate is set to 4. Select the default value of 100. FastText finally generates two files with the suffix vec and bin. bin is a binary file that contains model parameters and all hyperparameters. The vec file is the final vocabulary required, and the format is one word per line (TPE unit) corresponds to a 100-dimensional vector representation.

Using the idea of the BPE algorithm to learn the basic units of TPE in different languages from the selected initial corpus, and then use the Skip-Gram model to pre-train these TPE units to obtain a TPE unit-word vector representation format vocabulary. Combined with the vocabulary, the code sequence represented by the TPE unit is converted into the corresponding vector representation.

Do preprocessing: remove blank lines and comments from the source code, and represent the source code as a sequence of TPE units combined according to a backward maximum matching algorithm. The pre-processed source code should refer to the pre-trained vocabulary to obtain the specific vector representation of each TPE unit. After a preprocessing step, the source code has been transformed into a sequence of TPE units. Next, we need to convert this series of discrete sequences into continuous vector representations, implement and train a standard BiLSTM model, and enhance the clone detection function of TPE embedding. LSTM is a widely utilized network for encoding sequence inputs to TPE units, and BiLSTM is a bidirectional extension of LSTM with a right-to-left extension. The hyperparameters of the model are determined through preliminary experiments, and the hidden layer dimension is set to 100. Dropou is applied on the input embedding layer, and the scale of the BiLSTM hidden layer is 0.33. Adam algorithm is used for parameter optimization, the initial learning rate is 5×10 ^-4 , the gradient clipping threshold is 5, and the minimum batch-size is 32. The semantic information of each element in the sequence is learned through a bidirectional long-short-term memory neural network, and the forward and reverse sequence information is also recorded in the learned vector. On this basis, the hidden layer vector generated by the bidirectional long short-term memory neural network is extracted through a global pooling layer height, where self-attention pooling is used to achieve the goal. A weighted summation with a layer of self-attention neural network converts each Java method into a vector that is comparable to each other.

The self-attention mechanism is used to put the vector representation of the TPE unit learned by BiLSTM into a matrix, and multiply it by a weight matrix to obtain a fixed-dimensional vector. By continuously learning and updating the weight matrix, each TPE unit vector can be grasped in the entire sentence. The weight occupied by the method, thereby obtaining the vector representation of the entire code method. The specific calculation formula is as follows:

表示是BiLSTM的隐层输出，s_t表示

的显著性，代表着每个位置的序列结点向量在整个句子中所占的权重，注意力权重a_t根据h_t本身计算并且进行归一化之后得到，并且在模型不断训练、学习的过程中不断更新，h^CODE表示最终的代码向量表示。Among them, v represents a vector parameter, T represents the transpose of the matrix, and each element in the matrix represents the importance of each sequence node, which is expressed in the form of a numerical vector,

Indicates that it is the hidden layer output of BiLSTM, and s _t represents

The significance of , represents the weight of the sequence node vector at each position in the entire sentence. The attention weight at _{is calculated and normalized according to h t itself} , and the model is continuously trained and learned. Constantly updated in , h ^CODE represents the final code vector representation.

表示BiLSTM的隐层输出，s_t表示

的显著性，代表着每个位置的序列结点向量在整个句子中所占的权重，a_t表示注意力权重t位置元素在整个序列的权重参数，根据h_t本身计算并且进行归一化之后得到，并且在模型不断训练、学习的过程中不断更新，h^CODE表示最终的代码向量表示；j表示迭代参数，t表示当前位置；where v represents the vector parameter, T represents the transpose of the matrix, and each element in the vector represents the importance of each sequence node,

Represents the hidden layer output of BiLSTM, s _t represents

The significance of , represents the weight of the sequence node vector at each position in the entire sentence, a _t represents the weight parameter of the attention weight t position element in the entire sequence, calculated and normalized according to h _t itself Obtained, and continuously updated in the process of continuous training and learning of the model, h ^CODE represents the final code vector representation; j represents the iteration parameter, and t represents the current position;

The bidirectional long-short-term memory neural network learns all the information of the forward sequence and the reverse sequence, which can capture the semantic and timing information of the sequence more powerfully, and can learn more fully and predict more accurately than the ordinary long-short-term memory neural network.

As shown in Figure 3, it is the structure diagram of BiLSTM network. Bi-directional long short-term memory network (BiLSTM) consists of two ordinary long short-term memory networks (LSTM), the forward LSTM uses the information of the past moment, and the reverse LSTM uses the information of the future moment. BiLSTM recursively calculates the hidden output vector by the following formula:

f _t =σ(W _f [h _t-1 ,x _t ]+b _f )

i _t =σ(W _i [h _t-1 ,x _t ]+b _i )

o _t =σ(W _o [h _t-1 ,x _t ]+b _o )

h _t =o _t ⊙tanh(c _t )

Among them, x ₁ , x ₂ ,…, x _n are inputs, h ₁ , h ₂ ,…, h _n are outputs, and other variables such as W and b are model parameters. The right-to-left direction just rehearsed the same calculation in reverse.

Step 3. Design a Siamese architecture for the classification detection of clone/non-clone pairs, including: comparing the code representations of the input fragment pairs, then calculating their differences as classification features, and finally performing the final cloning/non-cloning based on the classification features. Clone prediction; formalize the code clone detection problem as a supervised binary classification task, that is, given two vectors converted from two code blocks as input, and then use the Euclidean distance between the vectors to calculate the two output vectors The difference is used as the classification feature, and the Euclidean distance between vectors is close to the clone pair. If they are clone pairs, set their labels to 1, and if they are not clone pairs, set their labels to 0; also finally get the probability that a given input pair is clone and non-clone.

The main idea of Siamese network is to map the input to the target space through a function, and use a simple distance to compare the similarity in the target space. Converting code clone detection into a binary classification problem, we propose a simple and effective BiLSTM model that converts discrete code fragments into low-dimensional, continuous vector representations via BiLSTM. A Siamese architecture is designed, where the two BiLSTM sub-networks have the same structure and share weights.

The present invention adopts the Siamese architecture and the standard BiLSTM classification model for code clone detection, which improves the efficiency while ensuring the effectiveness of the code clone detection. Through the TPE unit, rich syntactic and semantic information can be obtained, which can effectively detect semantic clones.

The embodiments of the present invention are described as follows:

Step 1, data selection and preprocessing:

1-1. Prepare a data set, the data set includes:

(1) BigCloneBench is one of the widely used evaluation benchmarks for detecting clones, and many code clone detection tools use this dataset as the evaluation benchmark. The BigCloneBench dataset was created for the cloned code in the Java language. The older version of BigCloneBench only contains 6 million labeled true clone pairs and 260 thousand labeled fake clone pairs, covering 10 features. The new release includes more than 8 million pairs of Java code marked as clones (most of which are type III and type four clones) and 279,032 code pairs marked as non-clones. For the BigCloneBench dataset, 20,000 pairs of functions are selected from each type for experimentation, and all of those less than 20,000 are selected.

(2) Another code clone evaluation benchmark OJClone is created for C language programs. OJClone is based on the Open Judge System of online programming, often referred to as the OJ system [8]. Its construction method is to select 104 programming topics in the OJ system. For the same programming topic, different people will submit Code snippets are considered clone pairs. The OJClone dataset does not explicitly state the type of clones, but it is generally believed that most clone pairs in OJClone are either tri- or tetra-clones]. Choose 500 programs from OJClone's top 15 programming questions. The same programming problem can form 124,750 clone pairs. Different programming problems can be combined into more than 28 million non-clone pairs. 50,000 function pairs were randomly selected, and the ratio of clone pairs to non-clone pairs was 1:14.

(3) Google Code Jam (GCJ) is an online international programming competition held by Google every year. The competition consists of a series of algorithmic problems that must be solved within a specified time. Participants can answer questions using any programming language and development environment of their choice. Each project for the same problem was implemented by a different programmer, and Google verified its correctness. Therefore, the processing of the same problem should be functionally similar. A total of 1665 Java functions were selected from 12 questions from the 2016 version, which respectively formed about 270,000 clone pairs and 1 million non-clone pairs. Finally, 50,000 function pairs were randomly selected, among which the ratio of clone pairs to non-clone pairs is 1:4.

1-2. For the data selected in step 1-1, use the TPE algorithm mentioned above to represent the function with the TPE basic unit. Different TPE vocabularies are trained for Java and C languages.

Step 2, training set, test set division: For each data set, it is randomly divided into three parts, 60%, 20%, and 20% are used for training, validation and testing.

Step 3, use the model for training

Input the preprocessed TPE basic unit vector representation to the first layer LSTM unit to obtain the characteristics of the influence of the previous unit of this basic unit on it, and then input it to the second layer LSTM unit to obtain the next character of the character. The effect of characters on it. Then the output of the first layer LSTM and the output of the second layer LSTM are spliced and combined. After training, the output feature vector contains the context information of this code unit and its sequence information.

The semantic information of each element in the sequence is learned through a bidirectional long-short-term memory neural network, and the forward and reverse sequence information is also recorded in the learned vector. On this basis, the hidden layer vector generated by the bidirectional long-short-term memory neural network is extracted through a global pooling layer height. Here, the self-attention pooling mechanism is used to achieve the goal. A weighted summation with a layer of self-attention neural network converts each Java method into a vector that is comparable to each other. So far, the original plain code text has been converted into a digitized vector, and then the difference between the two vectors is calculated using the Euclidean distance between vectors.

Compare the present invention with two state-of-the-art clone detection methods TBCCD and ASTNN in terms of precision (P), recall (R), F1 score (F1), data-time (data-time) and test-time (test-time) Compare to compare. .

As shown in Table 1, the detection results of the prior art ASTNN model, the TBCCD model and the TPE model of the present invention on the BigCloneBench data set.

Table 1

It can be seen that on the BigCloneBench dataset, the model of the present invention has a higher F value than the other two latest tools for detecting semantic clones. Especially in terms of detection efficiency, the TPE basic unit code representation method of the present invention is nearly 2.5 times higher in data-time than the other two tools using AST to represent codes.

In terms of model detection speed, the standard BiLstm model of the present invention is nearly 3 times more efficient than the other two models. This is because TBCCD uses tree-based convolution model and max-pooling, ASTNN uses RvNN and RNN models for sentence and code encoding, and only uses a simple BiLSTM model, BiLSTM can learn all the forward and reverse sequences information, which can more powerfully capture the semantic and timing information of the sequence.

Table 2 lists the model of the present invention and the detection results of ASTNN and TBCCD on the OJClone dataset.

On the OJClone data set, the detection effect of the present invention is still better than that of TBCCD, and the model performance is not as good as that of ASTNN. This is because ASTNN first constructs an AST for each code fragment when representing the code, and decomposes the entire AST into small statement trees ( A tree consisting of the AST nodes of the statement, rooted at the statement node). Then, a recursive encoder on a multi-way sentence tree is used to capture sentence-level lexical and syntactic information to obtain sentence vectors. Finally, the code representation is obtained through the recurrent neural network. The code information captured in this way is more comprehensive, but it also consumes a lot of time.

As shown in Table 3, the detection results of the TPE model, the ASTNN model, and the TBCCD model on the GCJ dataset are shown.

table 3

On the GCJ data set, the model of the present invention still performs better than TBCCD, and can achieve an effect close to that of ASTNN, while having obvious advantages in time. Regardless of the dataset, the processing time of ASTNN and TBCCD is longer than that of TPE, because both ASTNN and TBCCD express code based on AST.

Claims (1)

1. a semantic clone detection method based on deep learning, is characterized in that, this method specifically comprises following process: Step 1. Determine the basic unit of the TPE represented by the code in the semantic clone detection task. The generation process of the TPE is as follows: first, each code in the input corpus is truncated into a Token sequence, and the obtained Token is used to initialize the vocabulary vocab, including the The two-tuple tokens in the corpus are merged, then all the token two-tuples in the current corpus are counted, the two-tuple tokens are sorted and marked, and then the token with the highest iteration combination frequency in the corpus is used to identify the new basic unit, and add the newly obtained unit to the vocabulary, the newly generated corpus consists of the newly added two-tuple Token, TPE regards the two-tuple Token as a new Token, the above process is performed iteratively, by continuously iterating Find the combination of tokens with higher frequency to update the vocabulary; after obtaining the final vocabulary, use the backward maximum matching method to divide the code statement into TPEs according to the obtained vocabulary; According to the selected corpus, the basic unit of TPE in different languages is obtained by using the TPE algorithm; Step 2, establish a neural network model suitable for code clone detection, use the Skip-Gram model to pre-train the basic unit of the TPE obtained in step 1, and generate a corresponding TPE unit-word vector representation format vocabulary; This series of discrete sequences is converted into a continuous vector representation, and a standard BiLSTM model is implemented and trained; the vector representation of the basic unit of TPE learned by the BiLSTM model is put into a matrix, and multiplied by a weight matrix to obtain a For a fixed-dimensional vector, by continuously learning and updating the weight matrix to grasp the weight of the basic unit vector of each TPE in the entire sentence, the vector representation of the entire code method is obtained; the specific formula is as follows:

where v represents the vector parameter, T represents the transpose of the matrix, and each element in the vector represents the importance of each sequence node,

Represents the hidden layer output of BiLSTM, s _t represents

The significance of , a _t represents the weight parameter of the attention weight t position element in the whole sequence, h ^CODE represents the final code vector representation; j represents the iteration parameter, t represents the current position; Step 3. Design the Siamese architecture to classify and detect clone pairs/non-clone pairs, which specifically includes: giving two vectors converted from two code blocks as input, and pre-training by using the Skip-Gram model to obtain the value of each code block. Vector representation, and then use the calculation method of Euclidean distance between vectors to calculate the difference between the distances of the two output vectors as a feature of classification. The Euclidean distance between vectors is similar to the clone pair, thus obtaining the final clone/non-clone pair. Clone prediction.

Images