微軟研究院：基於圖模型表示程序，通過深度學習自動找出bug
來源：微軟研究院
編譯：weakish
最近有一些研究將深度學習應用到源代碼這樣的形式語言上，不過大部分的工作只是嘗試將自然語言方法遷移到形式化語言上，而沒有很好地利用代碼語法的特性。比如，大部分的工作都沒有考慮變數和函數引入的長距離依賴關係。最近的ICLR 2018上，微軟研究院的研究人員提交的論文Learning to Represent Programs with Graphs（地址：https://www.microsoft.com/en-us/research/wp-content/uploads/2017/11/programGraphs.pdf）用圖模型表示代碼的語法語義結構，並使用基於圖的深度學習方法學習理解程序結構，成功找到了知名開源項目中的bug。在ICLR 2018的評審中，本論文名列十佳。
圖模型背後的直覺
如前所述，當前應用於源代碼的深度學習模型，絕大部分僅僅刻畫了代碼膚淺的文本結構，包括：
這些模型忽略了代碼明確定義的、豐富語義，僅僅遷移了自然語言處理方法。
當然，也有研究注意到了這些模型的缺陷，嘗試利用代碼的語義改善模型的表現。
比如，當前大部分模型基於變數的扁平依賴網路，這樣的模型顯然沒有充分利用代碼中變數的特性。代碼中的變數有哪些特性呢？
首先，變數是有作用域的。只有在相應的作用域中，才能使用變數。在作用域之外，變數是不可見的。因此，在理解作用域的基礎上，統計變數的所有用例，可以更精確地建模。
其次，在靜態類型語言中，變數的類型經常是顯式聲明的，有時則是由編譯器自動推斷得出。無論哪種情況，變數的類型都是確定的，否則編譯器會報編譯錯誤。那麼這個類型信息，也是可以供模型利用的。
Allamanis等在2015年提出了學習變數的分散式表示的方法，就利用了變數的所有用例來預測變數的名稱。而Raychev等在2015年和Bichsel等在2016年的研究，建模了變數、AST元素和類型之間的關係來預測變數名和類型，就利用了變數的類型信息。
最後，變數不是孤立的，而是處於flow（流）之中。實際上，一些現代程序語言的類型系統，已經利用flow提供的信息來推斷變數的類型。這一技術被稱為flow-sensitive typing或flow typing。
比如，在支持flow-sensitive typing的Whiley語言中，編譯器可以成功推斷x的類型：
如果y大於1，則x的類型為int，否則為real。
Whiley於2009年引入flow-sensitive typing，是最早使用此特性的語言。之後，Ceylon、Kotlin和TypeScript等語言也引入了此特性。
同理，深度學習也可以利用flow，來改善模型的表現。微軟研究院的本項工作，就在建模時利用了flow信息。
最終得到的模型效果不錯。比如，模型能發現下面的代碼中第4行Assert.NotNull(clazz);中的clazz應該是first。目前的IDE難以發現這樣的錯誤，因為first在之後的語句中使用了。
GGNN
本工作的模型基於GGNN（Gated Graph Neural Networks）。這裡簡單介紹一下GGNN。
GGNN可以用下式表示：
上式中，V表示節點。
E表示由離散的邊的集合組成的列表：
k表示邊的類型數。
其中，X表示節點的特徵，我們用一個實數組成的向量x(v)表示節點x的特徵。我們給每個節點分配了一個狀態向量h(v)，該向量基於x(v)初始化。
然後，為了在圖中傳播信息，我們使用m(v)k表示節點v傳遞給相鄰節點的類型為k的「消息」。「消息」的內容，基於當前狀態向量計算，即m(v)k = fk(hv)，這裡，fk可以是任意的函數。通過同時計算所有邊的消息，可以同時更新所有的狀態。具體來說，聚合所有收到的信息可以計算出節點v的新狀態。
消息集合的條件是節點u和節點v之間存在類型為k的邊
上式中，g是聚合函數。基於聚合消息和當前的狀態向量h(v)，下一時刻的狀態h"(v)可以通過下式計算：
程序圖
我們將程序的源代碼表示為圖，骨架為程序的AST。
想一想，在AST層面，模型需要包含哪些與語義相關的信息。
首先，順序是重要的。顯然x / y和y / x的語義完全不同。因此，圖模型使用NextToken類型的邊表示這一語義。
其次，AST既然是抽象語法樹，顧名思義，存在層次關係。因此，圖模型使用Child類型的邊表示這一語義。
比如，以下語句
表示為
上圖中，黑色的方框表示語法token，而藍色的圓角框表示語法節點。黑色的NextToken邊將語法token與它的後繼節點連接起來，藍色的Child邊表示語法node間的關係。
如前所述，模型需要利用flow信息。那麼flow能提供哪些語義相關的信息呢？
最容易想到的就是變數的讀和寫。變數在什麼時候使用了，變數的值在什麼時候發生了改變，顯然，這是非常重要的信息。模型分別使用LastUse和LastWrite兩種類型的邊來表示這兩類信息。
其次，在像x = y + z這樣的語句中，x的值由y和z決定，因此x和y、z之間事實上存在依賴關係。因此，模型使用ComputedFrom類型的邊來表示這一信息。
比如，以下代碼段：
可以表示為：
為了清晰性，上圖給變數標上了序號。由下往上看，x4 = x5 + y6語句中，x4的值由x5和y6計算得到，因此，x4節點與x5、y6兩個節點間有ComputedFrom邊相連（圖中紫色的點劃線）。類似的，圖中紅色的點線表示LastUse邊，綠色的劃線表示LastWrite邊。
還有一些和flow無關的信息，也值得考慮。比如，在以下代碼結構中：
基於flow模型，兩個變數v之間並不存在LastUse關係，但它們仍屬於同一變數，為了建模這一關係，模型使用LastLexicalUse邊將同一變數的所有用例連接起來。
此外，方法名和return語句中的變數常常存在一定的聯繫。比如，考慮下面一段代碼：
顯然，IsDisposed和_isDisposed之間存在某種聯繫。
因此，模型使用ReturnsTo類型的邊連接兩者。
類似地，方法聲明時使用的參數名和方法調用時使用的變數名之間也常常存在聯繫。因此，模型使用FormalArgName類型的邊連接兩者。這一做法受到了Rice等《Detecting argument selection defects》的啟發。
最後，為了加快GGNN的傳播速率，使模型更具表達力，所有類型的邊都引入了相應的反向邊，使邊的數量和類型翻倍了。
變數的類型信息
模型假定面向的是靜態類型語言，且源代碼可以編譯。因此，每個變數都有一個（已知的）類型T(v)。我們定義了一個可學習嵌入函數r(T)來表示已知類型，用UnkType表示未知或未表示的類型。為了利用很多面向對象語言的類型層次，我們將一個變數的類型T(v)映射到它的超類：
通過計算元素最大值得出類型表示r*(v)。
節點表示初始化
將節點名稱切分為子token（例如，camelCase切分為camel和case，pascal_case切分為pascal和case），對所有子token的詞嵌入取平均，得到節點名稱的嵌入，與r*(v)連接，所得用0補齊，以便和GNNN的隱藏層尺寸保持一致。
VarNaming的程序圖
給定一個程序和一個現有的變數v，按照前述方法構建一個圖模型，然後將變數名替換為一個特殊的 token。使用上一節介紹的方法初始化節點表示，接著運行GGNN共8時步（經過測試發現，更少的次數不夠用，更多的次數表現並不更好），然後通過對所有 token的表示取平均以計算變數用例的表示。該表示進一步作為單層GRU的初始狀態，用於預測目標名稱（以子token序列表示，例如，inputStreamBuffer表示為[input, stream, buffer]）。我們以最大似然為目標，訓練graph2seq架構。
VarMisuse的程序圖
為了建模VarMisuse，需要修改圖。
首先，對於給定的slot t，插入一個新節點vSLOT，然後使用所有不依賴於選定的變數的邊（也就是LastUse、LastWrite、LastLexicalUse之外所有的邊）將其與圖的剩餘部分連接起來。通過這樣的方法，我們計算出t的上下文表示c(t)。
類似地，對於目標slot而言，插入一個候選節點vt,v，使用LastUse、LastWrite、LastLexicalUse三種類型的邊將其與圖的剩餘部分連接起來。拖過這樣的方法，我們計算出t處的候選變數v的用例表示u(t, v)。對所有的候選變數都進行類似的操作。
同樣，運行GGNN共8時步。將上下文表示和用例表示作為節點的這種狀態。正確的變數用例通過arg maxvc(t)Tu(t, v)計算得出。和VarNaming一樣，基於最大似然進行訓練。
實現
由於實際項目的源代碼規模較大，結構比較複雜。因此轉換成的圖模型也很大，也比較多樣化。在這樣的圖上應用GGNN是一個挑戰，一方面是規模大，另一方面是多樣化的形狀很難進行高效的batching。一個重要的洞見是，巨大的圖通常而言比較稀疏，因此將邊表示為鄰接表通常有助於降低內存使用。研究人員基於稀疏張量表示實現了這一點，從而使batch尺寸較大，可以高效地利用現代GPU的並行特性。另一個關鍵的洞見是，將圖batch表示為由許多孤立的部分組成的大型圖。這隻需要進行適當的預處理，保證節點標識唯一。由於這會讓batch構建給CPU更多的壓力，因此研究人員使用獨立的線程預備minibatch。在單張Nvidia GeForce GTX Titan X上，對於平均有2228（中位數 936）個節點、8350（中位數3274）條邊、8 GGNN展開迭代、16個邊類型（原本有8類，加上反向版本後共16類）、隱藏層尺寸為8的圖，研究人員基於TensorFlow的實現可以在訓練和測試時分別達到每秒55圖和每秒219圖的速率。
評估
評估的數據取自GitHub上的開源C#項目。選擇了GitHub上收藏數最多的一些項目，然後剔除難以使用Roslyn編譯的項目。Roslyn是微軟開發的.Net編譯器，提供了豐富的代碼分析API。由於模型需要編譯器能提取代碼的準確類型信息（包括由外部庫提供的類型），因此剔除了難以使用Roslyn編譯的項目。最終得到的數據集包括29個項目，290萬行代碼，覆蓋編譯器、資料庫等多個領域。
最終的測試結果表明，無論是在類型和結構已知的項目（SeenProject）還是在類型和結構未知的項目（UnseenProject）上，GGNN的表現都比基準模型要好。
為了驗證模型的設計上的一些選擇，研究人員也進行了消融研究。
同時，基於這個模型，研究人員在一個收藏數1500以上、測試齊全的GitHub項目中找到了3個bug。文章開頭的例子就是其中一例bug。
TAG:全球大搜羅 |