一種基于功能的程序表示研究

陳功

（四川大學計算機學院，成都 610065）

0 引言

隨著軟件技術的迅速發展，軟件倉庫的規模變得越來越龐大，軟件倉庫中大量的軟件工件為軟件開發人員從中挖掘出有用的信息，并應用于軟件工程活動提供了可能。軟件倉庫中的源程序就是軟件工程的重要研究對象之一。為了有效地挖掘出程序中隱含的信息，關鍵在于找到一種合適的程序的中間表示方法。

為了解決軟件工程中的實際問題，國內外研究者們對于程序的表示方法也進行了許多嘗試。2006年Koschke[1]在研究中使用基于抽象語法樹的方法來進行代碼克隆檢測。2013年Wu[2]等人采用基于程序依賴圖的方法來分析程序中的克隆。2015年White[3]等人將循環神經網絡應用于程序語言中，獲取token的詞向量表示，并應用于代碼推薦系統中。

深度學習[4]作為當前的研究熱點之一，在自然語言處理、語音識別以及圖像處理等領域都取得了突破性的進展。近年來，軟件工程領域的研究者們也開始嘗試將深度學習應用于軟件工件中[5-6]。本文利用深度學習自動提取特征的特點，提出了一種基于功能的程序表示方法，得到可以反映程序特征的矩陣表示。

1 算法思想

我們的核心問題是將程序在一個固定維度的實數值空間表示出來，進而才可以將其作為典型的有監督學習算法的輸入。盡管程序可能包含了很多特征，如代碼風格、時空間復雜度等，在這里我們將首要關注程序最基本的方面——功能。給定一個程序A，以及它的前置條件P，我們希望能夠通過學習A的特征從而預測當P成立時，運行A得到的結果，即程序A的后置條件Q。一般地，我們將P和Q表示成一個實值向量，該向量包含了程序在某個特定時刻的狀態（即程序中變量的值），這里的（P,A,Q）被稱為霍爾三元組。我們提出以霍爾三元組集合作為深度網絡的輸入來學習程序的特征，采用的主要方法是同時找到程序的狀態和程序在特征空間的對應的點，在這個空間上，程序可以視作是程序的前置條件到后置條件的一個線性映射。

更具體地說，給定一個三元組（P，A，Q），如果fP和fQ分別是前置條件P和后置條件Q的m維的特征表示，那么它們的關系可以通過等式1聯系起來：

于是，我們得到了一個m維的矩陣MA作為程序A的特征表示，我們希望通過學習得到的P，Q到特征空間f的映射以及fP到fQ的線性映射MA具備較好的泛化能力，即對于給定的程序A以及前置條件P，可以預測其后置條件Q。

2 網絡結構

本文方法的網絡結構如圖1所示。

圖1

我們的網絡總體上可以分為四層，輸入層、輸出層以及兩個隱含層，輸入層到第一個隱含層對應圖中的編碼器（Encoder），第二個隱含層到輸出層對應圖中的解碼器（Decoder），分別完成了程序的前置條件P和后置條件Q到特征空間f的映射，隱含層之間的權重系數就是程序特征的矩陣表示。對于給定的程序A，我們多次記錄程序中變量的值以及運行之后的值，得到大量的三元組（P,A,Q），以此作為數據集來訓練我們的模型。

3 模型訓練

假設提取到的程序的前置條件P和后置條件Q均是d維的向量，利用自編碼器思想，我們建立一個從前置條件P到m維的特征表示fP的非線性映射，這種映射被稱為編碼器。如傳統的自編碼網絡一樣，我們使用如下的非線性特征映射：

式中的We∈Rm×d,be∈Rm，Φ是一種非線性函數。之后，同傳統的自編碼器做法一樣，我們可利用fP重構出原始的輸入P：

式中的Wd∈Rd×m,bd∈Rd，ψ是一種非線性函數。到這一步，我們可以利用等式（1）得到后置條件Q在特征空間的表示fQ，進而重構出由模型得到的后置條件Q：

為了訓練模型中的參數，我們建立這樣一個損失函數L()

θ：

該損失函數由三個部分組成，其中lpred表示了在給定前置條件的情況，我們預測出程序的后置條件的準確程度，lauto反映了我們的自編碼器將輸入P編碼再解碼后重構得到的P?與原始輸入P之間的誤差，R是正則項，λ是正則化參數。我們的訓練目標就是使得取得最小值。

4 結語

本文介紹了一種基于功能的程序的表示方法。該方法從程序的功能出發，通過收集運行程序得到的霍爾三元組（P，A，Q）作為深度網絡的輸入，經過訓練同時得到程序的前置條件和后置條件在新特征空間的表示，使得程序的執行可以視作一個線性的映射過程。同時我們還獲得了程序的矩陣表示，該矩陣可以應用于很多的軟件工程任務中，如代碼克隆檢測、代碼自動評分、測試用例自動生成等。該方法同其他方法相比最大的優勢在于利用深度網絡自動提取程序的特征。在下一步的研究工作中，我們將從實際的軟件工程任務出發，來驗證該方法的有效性。

參考文獻：

[1]Koschke R,Falke R,Frenzel P.Clone Detection Using Abstract Syntax Suffix Trees[C].Reverse Engineering,2006.Wcre'06.Working Conference on.IEEE,2006:253-262.

[2]吳軍華,王佳利.基于依賴圖的程序克隆分析及近似解求解方法[J].南京工業大學學報(自科版),2013,35(5):52-56.

[3]White M,Vendome C,Linares M,Poshyvanyk D.Toward Deep Learning Software Repositories.MSR'15.

[4]Bengio Y,Courville A,Vincent P.Unsupervised Feature Learning and Deep Learning:A Review and New Perspectives[J]，2012.

[5]Hindle A,Barr E T,Su Z,et al.On the Naturalness of Software[J].Communications of the Acm,2016,59(5):122-131.

[6]Allamanis M,Sutton C.Mining Source Code Repositories at Massive Scale Using Language Modeling[J]，2013:207-216.