一種結(jié)合二者的新方法，展示如何查找已發(fā)布軟件中的bug

程序分析通常有兩種方法，分別基于數(shù)理邏輯和自然語言理解。通過將程序表示成圖結(jié)構(gòu)，來自微軟研究院和西門菲莎大學(xué)的研究者展示了一種結(jié)合二者的新方法，可以直接從源代碼中學(xué)習(xí)，且更準(zhǔn)確地查找已發(fā)布軟件中的 bug。

過去五年，基于深度學(xué)習(xí)的方法給大量應(yīng)用帶來了變革，如需要理解圖像、話語和自然語言的應(yīng)用。對于計算機(jī)科學(xué)家而言，一個自然出現(xiàn)的問題是：計算機(jī)是否能夠?qū)W會理解源代碼。乍一看這個問題似乎很簡單，因為編程語言的設(shè)計初衷就是被計算機(jī)理解。但是，很多軟件 bug 的出現(xiàn)是因為我想讓軟件這么做，但是寫出來卻是另外一回事。也就是說，小的拼寫錯誤可能導(dǎo)致嚴(yán)重后果。

看一下以下這個簡單示例：

float getHeight { return this.width; }.

該示例中，人類或者理解「height」和「width」意思的系統(tǒng)可以很快發(fā)現(xiàn)問題所在。源代碼具備兩種功能。首先，它與計算機(jī)進(jìn)行準(zhǔn)確交流，以執(zhí)行硬件指令。其次，它與其他程序員（或源代碼作者）針對程序的運行情況進(jìn)行交流。后者通過選擇代號、代碼布局和代碼注釋來實現(xiàn)。在發(fā)現(xiàn)兩種交流渠道似乎可以分離后，一個自動發(fā)現(xiàn)軟件 bug 的系統(tǒng)出現(xiàn)了。

之前的程序分析主要關(guān)注程序的正式、機(jī)器可理解語義或?qū)⒊绦蚩醋鳎ㄓ悬c奇怪的）自然語言。前者的方法來自于數(shù)理邏輯，要求對每個需要處理的新案例進(jìn)行大量的工程工作。而自然語言方法需要在純句法任務(wù)上性能優(yōu)越但尚無法學(xué)習(xí)程序語義的自然語言處理工具。

在 ICLR 2018 的一篇論文《Learning to Represent Programs with Graphs》中，來自微軟研究院和西門菲莎大學(xué)的研究者展示了一種結(jié)合二者的新方法，并展示了如何查找已發(fā)布軟件中的 bug。

程序圖

為了學(xué)習(xí)源代碼中的大量結(jié)構(gòu)，研究者首先把源代碼轉(zhuǎn)換成程序圖（program graph）。圖中的節(jié)點包括程序的 token（即變量、運算子、方法名等）及其抽象句法樹的節(jié)點（定義語言句法的語法元素，如 IfStatement）。程序圖包含兩種不同類型的邊：句法邊，表示代碼解析方式，如 while loop 和 if block；語義邊，即簡單程序分析的結(jié)果。

圖 1：句法邊

句法邊包括簡單的「NextToken」邊、用于表示抽象句法樹的「Child」邊，以及連接一個 token 和源代碼中它最后一次出現(xiàn)的「LastLexicalUse」邊。圖 1 展示了此類邊用于 statement Assert.NotNull(clazz) 的部分示例，其中對應(yīng) token 的節(jié)點是灰色框，對應(yīng)程序語法的非終端的節(jié)點是藍(lán)色橢圓形框。Child 邊是藍(lán)色的實線邊，而 NextToken 邊是黑色的雙線邊。

語義邊包括連接一個變量和它在程序執(zhí)行中最后一次使用的「LastUse」邊（如果是循環(huán)案例，則變量在程序執(zhí)行中最后一次使用的情況出現(xiàn)得更晚一些）、連接一個變量和它最后一次寫入的「LastWrite」邊，以及連接一個變量和它據(jù)此計算的值的「ComputedFrom」邊。也可能有更多語義邊，利用程序分析工具箱的其他工具，如 aliasing、points-to 分析，以及程序條件。圖 2 是在一個小代碼段（黑色）上形成的一些語義邊。

圖 2：語義邊

LastUse 關(guān)系用綠色邊表示，y 與循環(huán)前 y 最后一次使用的情況連接。類似地，LastWrite 關(guān)系用紅色邊表示，while 條件中的 x 的使用與循環(huán)前 x 的分配和循環(huán)中 x 的分配連接起來。最后，ComputedFrom 關(guān)系用藍(lán)色邊表示，變量與其據(jù)此計算的變量連接起來。

句法邊大概對應(yīng)程序員在閱讀源代碼時所看到的。語義邊對應(yīng)程序如何執(zhí)行。通過在一個圖中結(jié)合二者，該系統(tǒng)可以比單一方法學(xué)習(xí)到更多的信息。

從圖中學(xué)習(xí)

由于圖通常作為表征數(shù)據(jù)和數(shù)據(jù)關(guān)系的標(biāo)準(zhǔn)方式，從圖結(jié)構(gòu)數(shù)據(jù)中學(xué)習(xí)的方法近期受到了一定程度的關(guān)注。一個組織可以用圖的形式展現(xiàn)出來，正如藥物分子可以看成是原子構(gòu)成的圖。近期成功的應(yīng)用深度學(xué)習(xí)的圖方法是圖卷積網(wǎng)絡(luò)（卷積神經(jīng)網(wǎng)絡(luò)的一種擴(kuò)展）和門控圖神經(jīng)網(wǎng)絡(luò)（循環(huán)神經(jīng)網(wǎng)絡(luò)的一種擴(kuò)展）。

這兩種方法都是首先獨立地處理每個節(jié)點，以獲取節(jié)點本身的內(nèi)部表征（即低維空間中的一個向量），然后將互相連接的節(jié)點的表征進(jìn)行重復(fù)連接（兩種方法的組合方式不同）。因此，經(jīng)過一個步驟之后，每個節(jié)點擁有自身的信息和它的直接近鄰節(jié)點的信息；經(jīng)過兩個步驟之后，每個節(jié)點將獲得距離兩個節(jié)點的信息，以此類推。由于所有的步驟都使用（小型）神經(jīng)網(wǎng)絡(luò)，因此這些方法可以被訓(xùn)練用于從數(shù)據(jù)中提取整個任務(wù)相關(guān)的信息。

搜索 bug

在程序圖上學(xué)習(xí)可以用于搜索 bug，例如本文開頭描述的那個例子。給定一個程序、程序中的某個位置以及在該位置上可以使用的一系列變量。然后模型被詢問應(yīng)該使用哪些變量。為了執(zhí)行這項任務(wù)，程序被變換為程序圖，某個特定節(jié)點對應(yīng)所考慮的位置。通過考慮該特定節(jié)點的計算表征，以及對應(yīng)可用變量的節(jié)點表征，網(wǎng)絡(luò)可以計算每個變量的可能性。這樣的模型可以很容易地通過幾百萬行已有代碼來訓(xùn)練，并且不需要專門標(biāo)注的數(shù)據(jù)集。

當(dāng)模型在新代碼上運行，并以很高的概率預(yù)測出 var1，然而程序員選擇的是 var2，這可能就是一個 bug。通過標(biāo)記這些問題讓人類專家審核，可以發(fā)現(xiàn)真正的 bug。例如，以下來自 Roslyn（微軟 C# 編譯器）的例子：

注意參數(shù) filepath 和字段_filePath 的使用，二者很容易被混淆。然而，_filePath 只是一個打字錯誤，開發(fā)者在研究員報告這個問題和類似問題之后將其修改了。相似的 bug 在很多其它 C# 項目中也被找到、報告和修改。

在一個更大規(guī)模的定量評估中，新方法遠(yuǎn)遠(yuǎn)超越了傳統(tǒng)的機(jī)器學(xué)習(xí)技術(shù)。作為基線方法，雙向循環(huán)神經(jīng)網(wǎng)絡(luò)（BiRNN）直接在源代碼上執(zhí)行，BiRNN 的簡單擴(kuò)展可以訪問數(shù)據(jù)流的某些信息。為了評估不同的模型，微軟分析了包含 290 萬行源代碼的開源 C# 項目。在測試時，源代碼的某個變量被遮蓋，然后讓模型找出原始使用的變量（假定源代碼是準(zhǔn)確并經(jīng)過良好測試的）。在第一個實驗中，模型在項目的留出文件上進(jìn)行測試（其他文件用于訓(xùn)練）。在第二個實驗中，模型在全新項目的數(shù)據(jù)上測試。結(jié)果如下表所示，在新的程序圖上學(xué)習(xí)的模型得到了明顯更好的結(jié)果。

未來應(yīng)用

程序圖對于在程序上應(yīng)用深度學(xué)習(xí)方法是很通用的工具，微軟將繼續(xù)朝這個方向探索。