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

過去五年，基于深度學(xué)習(xí)的方法給大量應(yīng)用帶來了變革，如需要理解圖像、話語和自然語言的應(yīng)用。對(duì)于計(jì)算機(jī)科學(xué)家而言，一個(gè)自然出現(xiàn)的問題是：計(jì)算機(jī)是否能夠?qū)W會(huì)理解源代碼。乍一看這個(gè)問題似乎很簡(jiǎn)單，因?yàn)?a href="http://www.socialnewsupdate.com/v/tag/1315/" target="_blank">編程語言的設(shè)計(jì)初衷就是被計(jì)算機(jī)理解。但是，很多軟件 bug 的出現(xiàn)是因?yàn)槲蚁胱屲浖@么做，但是寫出來卻是另外一回事。也就是說，小的拼寫錯(cuò)誤可能導(dǎo)致嚴(yán)重后果。

看一下以下這個(gè)簡(jiǎn)單示例：

float getHeight { return this.width; }.

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

之前的程序分析主要關(guān)注程序的正式、機(jī)器可理解語義或?qū)⒊绦蚩醋鳎ㄓ悬c(diǎn)奇怪的）自然語言。前者的方法來自于數(shù)理邏輯，要求對(duì)每個(gè)需要處理的新案例進(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é)點(diǎn)包括程序的 token（即變量、運(yùn)算子、方法名等）及其抽象句法樹的節(jié)點(diǎn)（定義語言句法的語法元素，如 IfStatement）。程序圖包含兩種不同類型的邊：句法邊，表示代碼解析方式，如 while loop 和 if block；語義邊，即簡(jiǎn)單程序分析的結(jié)果。

圖 1：句法邊

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

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

圖 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ù)此計(jì)算的變量連接起來。

句法邊大概對(duì)應(yīng)程序員在閱讀源代碼時(shí)所看到的。語義邊對(duì)應(yīng)程序如何執(zhí)行。通過在一個(gè)圖中結(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)注。一個(gè)組織可以用圖的形式展現(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ò)展）。

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

搜索 bug

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

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

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

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

未來應(yīng)用

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