楊騰　趙逢禹　劉亞

摘 要： 代碼復用可以有效縮短軟件開發(fā)的時間，而代碼搜索是代碼復用的主要途徑。提出了一種基于程序切片和BiGRU的代碼搜索方法，該方法通過構建源代碼的程序依賴圖，以程序依賴圖中出度最大的節(jié)點作為興趣點構建前向切片。將程序切片與源代碼的其他相關特征一起構成代碼特征。把代碼特征和代碼的功能描述通過嵌入模塊輸入到BiGRU網絡中，結合注意力機制訓練BiGRU模型。用戶輸入功能查詢語句，模型返回向量值最接近的代碼。為了驗證該模型的可行性和有效性，從開源代碼庫下載了Java項目，構建了數(shù)據集并進行實驗。實驗結果表明，提出的基于程序切片和BiGRU的方法在代碼搜索的準確率和相關性排名等方面都有所改進。

關鍵詞： 代碼搜索; 程序切片; BiGRU; 注意力機制

Code search based on program slicing and BiGRU

YANG Teng， ZHAO Fengyu， LIU Ya

（School of Optical-Electrical & Computer Engineering， University of Shanghai for Science & Technology，

Shanghai 200093， China）

【Abstract】Code reuse can effectively shorten the time of software development， and code search is the main way of code reuse. This paper proposes a code search method based on program slicing and BiGRU. The method builds a program dependency graph of source code， and takes the node with the highest degree in the program dependency graph as the point of interest to construct program slices. The features of source code are formed by combining program slices with other relevant method features. Code features and code function descriptions are input into the BiGRU network through an embedding module， and BiGRU network model is generated by combining attention mechanism. Users enter the function query statement， and the model returns the code with the closest vector value. In order to verify the feasibility and effectiveness of the model， several Java projects are downloaded from the open source library to build the data set and conduct experiments. Experimental results show that the proposed method based on program slicing and BiGRU has some improvements in code search accuracy and relevance ranking.

【Key words】code search; program slice; BiGRU; attention

0 引 言

重用現(xiàn)有的代碼片段可以有效縮短軟件開發(fā)的時間，開發(fā)人員可以通過代碼搜索重用已有的方法，提高開發(fā)效率。研究表明，代碼搜索是軟件開發(fā)人員使用最頻繁的活動之一[1]。近年來，隨著開源理念的加強，開源項目的質量和數(shù)量在不斷地增加，開源代碼庫為人們提供了豐富的資源，但如何快速準確地搜索到需要的代碼成為了一個新的問題。

早期的代碼搜索方法通常采用全文檢索技術，通過全文檢索獲得與查詢關鍵詞匹配的代碼段?；谛畔z索的方法通常將源代碼視為純文本，并利用信息檢索模型來檢索與給定查詢關鍵字匹配的相關代碼段。Sindhgatta[2]提出了基于Lucene的JSearch，該工具通過結構化查詢語言搜索Java文件。 Hill等人[3]提出了基于詞組的搜索技術，該技術基于關鍵字搜索，并且還引入了基于短語概念的評分機制，通過查詢單詞的位置、語義角色、頭部距離和使用信息對程序的相關性進行評分。Bajracharya等人[4]提出了Sourcerer，Sourcerer以查詢語句為輸入，通過分析代碼中API調用情況，搜索相似的代碼實體，根據這些實體的名稱進行擴展，在此基礎上使用TF-IDF技術搜索流行的類。Raghothaman等人[5]提出了SWIM，與之前的信息檢索技術不同，該方法使用詞袋模型，根據查詢找到相應的API，再把API組合成代碼段返回給用戶。

近年來，研究人員開始將機器學習和深度學習技術應用于代碼搜索領域。Gu等人[6]提出一個基于LSTM的代碼搜索模型DeepCS，該模型利用了代碼的注釋信息，通過深度神經網絡得到代碼和注釋的向量表示，模型訓練時通過相似度計算，使得匹配的代碼和注釋生成相似的向量。與基于信息檢索的代碼搜索技術相比，運用深度神經網絡通過對比代碼和查詢語句的向量之間的空間距離能夠挖掘到更高層次的特征，更充分地理解代碼語義。

利用深度學習進行代碼搜索，通常需要先從源代碼中提取代碼特征，以便更充分地理解代碼語義。比如Aroma[7]從簡化的抽象語法樹中提取了下文關系作為代碼特征、DeepCS通過遍歷抽象語法樹提取了由代碼調用的API組成的序列作為代碼特征。本文認為基于抽象語法樹的特征提取方法提取的主要是代碼的結構特征，沒有考慮到代碼中變量的定義、判斷、使用的數(shù)據流信息，不能夠很好地反映出代碼的語義特征。而程序切片通過分析程序語句之間的控制依賴和數(shù)據依賴關系，移除了程序中與興趣點無關的部分，能夠更好地反映出源代碼的結構和功能信息。

基于這一思想，本文構建了基于程序切片和BiGRU[8]的代碼搜索模型。首先從開源代碼庫獲取數(shù)據集，提取出方法代碼-功能描述對。建立方法代碼的程序依賴圖，將出度最大的節(jié)點作為興趣點，在程序依賴圖上利用圖形可達性算法獲得程序切片。然后使用BiGRU神經網絡模型，結合注意力機制，構建一個注釋-代碼聯(lián)合嵌入模型，將方法代碼和功能描述當作輸入，訓練模型學習二者的相關性。在搜索階段，用戶將需要的功能描述作為輸入，該模型會返回與輸入信息匹配的方法代碼。

1 基于程序切片和BiGRU的代碼搜索

為了更加準確高效地搜索具有某些功能的代碼，本文提出了一個基于程序切片和BiGRU的代碼搜索方法。該方法首先從開源代碼庫GitHub上獲取數(shù)據集，從中選取部分具有清晰完善注釋的方法代碼，構建出方法代碼-注釋對。然后為方法代碼建立程序依賴圖，在程序依賴圖上利用可達性算法獲得程序切片，從程序切片中提取代碼的結構特征。最后將提取到的特征和相應的注釋輸入進BiGRU網絡模型，通過相似度計算訓練模型。

本文構建了一個基于程序切片和BiGRU的代碼搜索模型。其中，程序切片是通過在程序依賴圖上做可達性分析得到的，具體包含了對源代碼的控制依賴信息和數(shù)據依賴信息的分析，能夠更加準確地表達代碼語義。由于在數(shù)據量不是特別大的時候，GRU能夠達到和LSTM[9]相似的性能，但參數(shù)量比LSTM減少了三分之一，收斂速度更快，因此本文選擇使用BiGRU神經網絡模型。此外，該模型還增加了注意力機制，通過加權處理，突出重點，使模型表現(xiàn)出更好的性能。與DeepCS相比，在性能相當?shù)那疤嵯拢疚奶岢龅哪Ｐ褪諗克俣雀?。代碼搜索模型的構建流程如圖1所示。由圖1可知，對其中主要部分的功能解析可做闡釋分述如下。

（1）功能描述提取。首先從Github上下載Java項目，從中提取方法和注釋對構建代碼庫，然后對方法注釋進行解析，只保留其中對方法的功能的描述。

（2）方法特征提取。由圖1可知，在特征提取階段，該模型生成了源代碼的程序依賴圖PDG，從中選取出度最大的語句作為興趣點，利用可達性算法構建程序切片。此外，該模型還生成了抽象語法樹AST，從中提取了方法名、返回值類型、參數(shù)等特征，這些特征也與方法的功能有著密切的關系，將其與程序切片一同作為方法特征。通過完全連接層將這4個特征融合到一個向量中，即：

C=tanhWcm;r;p;s（1）

其中，向量C為融合后的向量;Wc是可訓練參數(shù)的矩陣;m;r;p;s是方法名、返回值類型、方法參數(shù)和程序切片四個特征對應向量的串聯(lián)。

（3）模型訓練。在模型訓練階段，將上個階段提取的方法代碼特征和功能描述嵌入到高維向量空間，得到兩者各自的向量表示。通過訓練學習二者的相關性，如果功能描述和方法代碼具有相似的語義，那么對應的向量表示就應該互相接近。

在查詢階段，由用戶輸入一句對代碼功能的自然語言描述，模型把該描述嵌入到向量空間中，在代碼庫中搜索與其相似度最高的5個方法的向量表示，然后從源代碼庫中取出具有相應功能的方法代碼作為結果返回。

2 程序切片和代碼搜索模型關鍵技術

本文用到的關鍵技術主要有獲取源代碼的程序切片、BiGRU和Attention機制。這里擬對此展開研究論述如下。

2.1 程序切片

程序切片的概念由Weiser[10]首次提出，研究發(fā)現(xiàn)某個輸出只與部分語句相關，將不相關的語句刪除不影響該輸出的結果，將這種只與某個輸出相關的語句構成的程序稱為程序切片。

目前研究程序切片的主要方法是基于程序依賴圖來做的，Ottenstein等人[11]引入了程序依賴圖的圖可達性算法，用來計算程序切片。李潤清等人[12]通過提取源代碼的切片摘要，把切片摘要作為搜索引擎中的關鍵字進行搜索，證明了運用程序切片的代碼搜索引擎的性能要優(yōu)于傳統(tǒng)的代碼搜索方法。本文以Java代碼為例，給出了構建程序切片的方法。

要獲取程序切片，需要為Java方法生成相應的程序依賴圖PDG（Program Dependence Graph），PDG中的節(jié)點表示語句或者謂詞表達式，邊表示節(jié)點之間的數(shù)據依賴、控制依賴關系?？刂埔蕾囍傅氖且蚩刂屏饕鸬哪K之間的依賴關系。數(shù)據依賴指的是由數(shù)據流引起的變量之間的依賴關系。PDG圖是一個有向圖，本文選擇程序依賴圖中除入口節(jié)點以外出度最大的節(jié)點對應的語句N作為興趣點，因為出度代表受其影響的語句數(shù)量，出度越大則說明受到該節(jié)點影響的語句數(shù)量越多，意味著該節(jié)點對應的語句蘊含的結構信息越豐富。因此選擇這樣的語句作為興趣點N，遞歸遍歷數(shù)據依賴或控制依賴于N的結點、即PDG中以N為源節(jié)點的鄰接節(jié)點，將其加入到切片集合，生成節(jié)點N的前向切片。

對于PDG中的每個節(jié)點，文中使用集合S.out代表以節(jié)點S為源節(jié)點的鄰接節(jié)點的集合。算法1給出了獲取PDG中出度最大的結點max的過程，算法2描述了以max為興趣點構建程序切片的步驟。算法流程詳見如下。

2.2 雙向門控循環(huán)單元

雙向門控循環(huán)單元（GRU）[13]是長短期記憶LSTM模型的一個變體， 只有2個門函數(shù)：更新門和重置門。其中，更新門用于控制前一時刻的狀態(tài)信息被帶入到當前狀態(tài)中的程度，更新門的值越大說明前一時刻的狀態(tài)信息帶入越多。重置門控制前一狀態(tài)有多少信息被寫入到當前的候選集上，重置門越小，前一狀態(tài)的信息被寫入得越少。

GRU模型結構圖如圖2所示。圖2中，rt為控制重置的門控（reset gate），zt為控制更新的門控（update gate），ht-1為前一時刻的狀態(tài)信息，ht為當前時刻的狀態(tài)信息，σ為sigmoid函數(shù)，通過這個函數(shù)可以將數(shù)據變換為0～1范圍內的數(shù)值，從而來充當門控信號。具體計算如下：

其中，Wr、Wz、W[AKh～]t是通過訓練學習的參數(shù)，[AKh～]t是候選隱藏層狀態(tài)，并只與輸入xt、上一層的隱藏狀態(tài)ht-1有關。

BiGRU由2個方向相反的GRU構成。一個正向的GRU，利用歷史信息;一個反向的GRU，利用未來的信息。這樣在時刻t，既能夠利用到t-1時刻的信息，又能利用t+1時刻的信息。在每一時刻，把輸入同時給2個GRU，輸出由2個GRU的狀態(tài)同時決定。BiGRU的結構如圖3所示。

2.3 Attention機制

注意力機制 （attention mechanism）源自人類大腦對新事物認知的特點，即對于重要的內容分配較多注意力，而對于不重要的部分分配較少的注意力。借助注意力機制為神經網絡隱層單元分配不同的概率權重，能夠關注到更有利的特征，同時降低對一些冗余信息的關注[14]。Attention通過對數(shù)據自動加權變換，把2個不同的部分聯(lián)系起來，突出重點，以表現(xiàn)出更好的性能。引入Attention機制的重要原因就是減少文本序列中關鍵信息的丟失。由于注意力機制在自然語言處理中對強化關鍵信息的有效性， 所以本文在雙向 GRU 神經網絡的基礎上添加了Attention機制來提高模型的準確率。Attention機制注意力分布的計算通常分2步：

（1）給定一個查詢向量q，通過其與輸入向量[X1，X2……Xn]的相關性，使用打分函數(shù)計算得到n個score，相關性越高，則值越大。

（2）通過softmax函數(shù)計算得到注意力分布，計算方法如公式（6）所示：

注意力分布αi可以解釋為在上下文查詢q時，第i個信息受關注的程度。sxi，q為注意力打分函數(shù)，計算方法如公式（7）所示：

其中，xTi表示輸入向量;q表示查詢向量;d表示輸入向量的維度?？s放點積模型解決了點積模型在d較大的時候的結果方差會比較大，softmax的梯度會變小的問題。

3 實驗與分析

本節(jié)給出了該模型的實現(xiàn)步驟，并通過搜索結果的準確率和檢索排名等指標來檢驗該模型的性能。

3.1 實驗數(shù)據集

本文通過從開源網站Github上下載Java項目來構建訓練代碼庫和搜索代碼庫，從中選擇了268個Java項目。在這些Java代碼中選取了11 893個方法-注釋對作為正樣本，然后構建了10 224個負樣本一同作為訓練代碼庫。正樣本就是數(shù)據集里匹配的方法-注釋對，負樣本則是隨機選取的注釋與當前方法構成的方法-注釋對。搜索代碼庫是由數(shù)據集中的所有方法代碼構成的，其中包括沒有注釋信息的方法，共有35 533個方法代碼。數(shù)據集80%作為訓練集，20%作為測試集，使用BiGRU模型在訓練集上進行訓練并在驗證集上對模型進行調參，最后在測試集上測試。

3.2 參數(shù)設置

本文將詞向量維度設置為100，BiGRU每個方向上的隱藏層節(jié)點數(shù)設置為50，batch_size設置為64，dropout_rate為0.5，以防止模型發(fā)生過擬合現(xiàn)象。

3.3 實驗過程

（1） 在對注釋信息進行抽取時，去除@author、@see、@link、@since等注解后面的信息，只保留注釋中對方法的功能描述。本文從Github獲取了停用詞列表，然后使用NLTK分詞對功能描述進行分詞，根據停用詞列表去除分詞后的文本中的停用詞。

（2）取出數(shù)據集中的方法代碼，通過2.1節(jié)的算法1和算法2構建方法代碼的程序切片。

（3）使用Eclipse的JDT工具生成方法代碼的抽象語法樹，遍歷抽象語法樹提取返回值類型、方法名、參數(shù)類型，將其與程序切片一同作為方法特征。

（4）分別按順序存儲方法特征和功能描述，通過按順序分別讀取方法特征和功能描述的方式輸入數(shù)據，使用word2vec[15]獲得方法代碼特征和功能描述各自的詞向量表達，使用H5格式的文件存儲這些數(shù)據。

（5）本文使用torch.nn.gru構建了BiGRU模型，將方法特征和功能描述的詞向量表達作為 BiGRU的輸入，提取深層局部特征和長距離特征。將BiGRU提取的特征作為Attention層的輸入，并在Attention分配詞向量權重。在完全連接層使用Keras的Concatenate函數(shù)對方法代碼的4個特征進行融合，得到嵌入向量。訓練時使正樣本中的功能描述在向量空間中不斷地向方法代碼靠近，負樣本中的功能描述在向量空間中不斷地遠離方法代碼。在訓練到340個迭代周期左右，發(fā)現(xiàn)loss不再繼續(xù)減小，停止訓練。

3.4 實驗結果與分析

本小節(jié)將在搜索代碼庫上對本文提出的方法進行評估，為了評估提出的代碼搜索方法的有效性，本文從準確率和檢索排名等方面將該方法與其他方法作對比。

本文選擇了Precision和MRR（Mean reciprocal rank）對搜索結果進行評價，這2個指標都是信息檢索領域常用的評價指標?？偟卣f來，Precision計算的是正確預測為正樣本的數(shù)量占所有預測為正樣本的數(shù)量的比例。MRR通過正確檢索結果在全部檢索結果中的排名來評估檢索系統(tǒng)的性能。

本文在同一實驗環(huán)境下，使用相同的數(shù)據集將本文模型與Sourcerer、SWIM以及DeepCS做對比，用來評估該模型的性能。Sourcerer是基于Lucene的代碼搜索工具，能夠代表傳統(tǒng)的基于全文檢索技術的搜索引擎。SWIM利用詞袋技術將查詢翻譯成API，考慮到了代碼的結構信息。對比結果見表1。

為了驗證本文提取特征的有效性以及模型對結果的影響，增加了特征提取方式與模型組合的對照實驗。實驗以方法名、返回值類型以及方法參數(shù)等特征結合LSTM的模型作為基線模型，在此基礎上分別驗證了使用了程序切片作為代碼特征的效果以及使用BiGRU替換LSTM的效果。模型對比效果見表2。

由表1可知，對于Precision，本文模型的表現(xiàn)與DeepCS相當，比Sourcerer和SWIM要好。MRR的值也表明，本文模型正確的查詢結果更加靠前。由表2可知，提取程序切片作為代碼特征提高了搜索結果的精度，BiGRU + Program Slice的模型達到了與LSTM + Program Slice模型相當?shù)男阅?，但在實驗過程中發(fā)現(xiàn)該模型的收斂速度比LSTM + Program Slice模型快。LSTM + Program Slice在420個迭代周期后loss不再發(fā)生明顯下降，BiGRU + Program Slice則在340個迭代周期以后loss不再下降。雖然本文模型在整體性能上比SWIM和Sourcerer表現(xiàn)得好，但是研究發(fā)現(xiàn)在個別查詢語句的結果中，Sourcerer的準確率超過了本文模型。在分析后，研究發(fā)現(xiàn)這是因為這些查詢語句中包含了較多與代碼中變量名相同的關鍵詞，在這種情況下，基于全文檢索技術的方法的優(yōu)勢就體現(xiàn)了出來。這說明本文的模型還有需要繼續(xù)改進的地方，在后續(xù)工作中會改進這些問題。

4 結束語

本文提出了基于程序切片和BiGRU的代碼搜索模型，該模型通過構建代碼的程序切片與代碼功能特征一同作為方法特征，然后計算方法特征和注釋的向量表示的余弦相似度，使得匹配的功能描述和方法生成相似度較高的向量，在查詢時將在向量空間中與查詢語句的向量表示最接近的方法返回給用戶。實驗結果表明，跟傳統(tǒng)的代碼搜索方法相比，該模型通過構建程序切片，有效地利用了代碼的控制依賴和數(shù)據依賴關系，更加準確地提取了代碼的語義信息，在一定程度上提高了搜索結果的準確率。下一步研究工作將是對構建程序切片的方法進行改進，比如選擇多個興趣點構建多個切片，以挖掘更準確的代碼語義信息。

參考文獻

[1]黎宣，王千祥，金芝. 基于增強描述的代碼搜索方法[J]. 軟件學報，2017，28（6）：1405-1417.

[2]SINDHGATTA R. Using an information retrieval system to retrieve source code samples[C]// International Conference on Software Engineering. Shanghai，China： dblp， 2006：905-908.

[3]HILL E，POLLOCK L L，VIJAY-SHANKER K. Improving source code search with natural language phrasal representations of method signatures [C]// IEEE/ACM International Conference on Automated Software Engineering. Lawrence， KS， USA： ACM， 2011：524-527.

[4]BAJRACHARYA S K ， OSSHER J ， LOPES C V. Leveraging usage similarity for effective retrieval of examples in code repositories[C]//ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York，NY，USA：ACM，2010：157-166.

[5]RAGHOTHAMAN M， WEI Y， HAMADI Y. SWIM： Synthesizing what I mean - code search and idiomatic Snippet synthesis [C]// 2016 IEEE/ACM 38th International Conference on Software Engineering （ICSE）. Austin， TX：IEEE， 2016：357-367.

[6]GU X， ZHANG H， KIM S. Deep code search [C]// IEEE/ACM 40th International Conference on Software Engineering （ICSE）. Gothenburg：IEEE， 2018：933-944.

[7]LUAN Sifei， YANG Di， BARNABY C， et al. Aroma： code recommendation via structural code search[C]//Proceedings of the ACM on Programming Languages. Athens： ACM，2019：1-28.

[8]ZHANG Liujie， ZHOU Yanquan， DUAN Xiuyu，et al. A hierarchical multi-input and output Bi-GRU model for sentiment analysis on customer reviews[J]. Iop Conference， 2018， 322（6）：062007.

[9]劉丹，葉茂. 回復式神經網絡及其應用研究綜述[J]. 小型微型計算機系統(tǒng)，2020，41（10）：2024-2029.

[10]WEISER M . Program slicing[J]. The IEEE Transactions on Software Engineering， 1984， 10（4）：352-357.

[11]OTTENSTEIN K J， OTTENSTEIN L M.The program dependence graph in a software development environment[J]. ACM Sigplan Notices，1984，19（5）：177-184.

[12]李潤青， 曾國蓀. 程序源代碼中的切片摘要提取及在搜索中的應用[J]. 信息技術與網絡安全， 2018， 37 （3） ：122-125，130.

[13]DEY R，SALEMT F M. Gate-variants of Gated Recurrent Unit （GRU） neural networks [C]// IEEE International Midwest Symposium on Circuits & Systems. Boston，MA，USA： IEEE， 2017：1597-1600.

[14]司念文，王衡軍，李偉，等. 基于注意力長短時記憶網絡的中文詞性標注模型[J]. 計算機科學，2018，45（4）：66-70，82.

[15]MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space[J].arXiv preprint arXiv：1301.3781，2013.

文章編號： 2095-2163（2021）07-0216-06中圖分類號：TP311文獻標志碼： A

基金項目： “十三五”密碼發(fā)展基金理論課題（MMJJ20180202）。

作者簡介： 楊 騰（1996-） ，男，碩士研究生，主要研究方向：軟件工程、代碼搜索; 趙逢禹（1963-），男，博士，教授，CCF會員，主要研究方向：計算機軟件與軟件系統(tǒng)安全、軟件工程與軟件質量控制、軟件可靠性; 劉 亞（1983-），女，博士，副教授，CCF會員，主要研究方向：信息安全、密碼學。

收稿日期： 2021-03-24