檢測(cè) Go 程序中并發(fā) Bug 的新方法

大家好，我是 polarisxu。

本文是網(wǎng)友「charlesxsh」投稿。

賓州州立大學(xué)系統(tǒng)安全實(shí)驗(yàn)室^[1]依靠模糊測(cè)試的思想設(shè)計(jì)了檢測(cè)工具GFuzz，能自動(dòng)檢測(cè)Go程序中的并發(fā)缺陷。GFuzz在著名的開(kāi)源軟件（如Docker，Kubernetes）中發(fā)現(xiàn)了184個(gè)此前未知的并發(fā)缺陷。?

工具：https://github.com/system-pclub/GFuzz^[2]

英文論文：https://songlh.github.io/paper/gfuzz.pdf

演講視頻：https://www.bilibili.com/video/BV1TF411b7nN?spm_id_from=333.999.0.0

背景

Go 是由 Google 發(fā)明的工業(yè)級(jí)編程語(yǔ)言，當(dāng)時(shí)Google設(shè)計(jì)Go的目的是編寫(xiě)安全高效的并發(fā)程序。最近幾年來(lái)，Go 快速普及，已經(jīng)成為世界上最受開(kāi)發(fā)者喜愛(ài)的編程語(yǔ)言之一。開(kāi)發(fā)者們用 Go 編寫(xiě)了很多工業(yè)界的基礎(chǔ)架構(gòu)軟件，比如 Docker，Kubernetes，和 gRPC等。

為了更加方便地編寫(xiě)并發(fā)程序，Go 有許多內(nèi)置特性，比如輕量級(jí)的線程（ goroutines）和 信道（channels），并且推薦開(kāi)發(fā)者使用信道發(fā)送消息的方式進(jìn)行g(shù)oroutines之間的通信。

但遺憾的是，用Go來(lái)編寫(xiě)正確的并發(fā)程序依然很困難，并發(fā)缺陷（concurrency bugs）仍然在Go程序中廣泛存在。而且最近的一項(xiàng)研究還表明，錯(cuò)誤地使用信道也會(huì)導(dǎo)致并發(fā)缺陷。在某些情況下，使用信道可能比使用鎖（mutexes）更容易出錯(cuò)。

現(xiàn)有的檢測(cè)技術(shù)

由于目前已有的檢測(cè)方法大多是為傳統(tǒng)的編程語(yǔ)言（例如C/C++，Java）而設(shè)計(jì)建造的，只能監(jiān)控鎖和共享內(nèi)存使用，并不能監(jiān)控信道，也無(wú)法檢測(cè)錯(cuò)誤使用信道而導(dǎo)致的缺陷，因此現(xiàn)有的缺陷檢測(cè)技術(shù)并不能有效發(fā)現(xiàn)Go程序中的并發(fā)缺陷，尤其是那些由于錯(cuò)誤的消息傳遞而導(dǎo)致的缺陷。

此外，現(xiàn)有的model checking技術(shù)雖然可以系統(tǒng)地檢查所有可能的消息順序，從而發(fā)現(xiàn)分布式系統(tǒng)中的并發(fā)缺陷。但因?yàn)橹挥袠O少數(shù)的消息順序能夠觸發(fā)并發(fā)缺陷，因此通過(guò)窮舉所有消息順序來(lái)找缺陷是非常低效的。

目前為Go設(shè)計(jì)的靜態(tài)檢測(cè)器，只能檢測(cè)有限類(lèi)型的缺陷，不能分析大規(guī)模代碼，而且會(huì)產(chǎn)生大量的誤報(bào)和漏報(bào)。而為Go設(shè)計(jì)的動(dòng)態(tài)檢測(cè)器，則只能檢測(cè)已經(jīng)觸發(fā)的缺陷。它們既無(wú)法改變程序的運(yùn)行狀態(tài)，也不能增加觸發(fā)缺陷發(fā)生的可能性，因此會(huì)漏報(bào)許多并發(fā)缺陷。

Go的并發(fā)缺陷案例

在這里展示一個(gè)來(lái)自Docker的信道相關(guān)并發(fā)缺陷，來(lái)更清楚地說(shuō)明為什么現(xiàn)有的檢測(cè)技術(shù)無(wú)法有效地發(fā)現(xiàn)Go程序中的并發(fā)缺陷。

在如圖所示的案例中，父goroutine在第4行調(diào)用了一個(gè)類(lèi)方法。被調(diào)用的函數(shù)是在17-31行的方法Watch（）。方法Watch（）在18，19行創(chuàng)建了兩個(gè)沒(méi)有緩沖區(qū)的信道 ch 和 errCh，然后在22行創(chuàng)建了一個(gè)子goroutine，最后在30行返回了這兩個(gè)新創(chuàng)建的信道。

子goroutine在23行調(diào)用了s.fetch()，檢查了返回值，根據(jù)檢查結(jié)果向errCh（25行）或者ch（27行）中發(fā)送一條消息。同時(shí)，父goroutine阻塞在了select語(yǔ)句（5-14行），來(lái)等待在Fire（），errCh，或者ch中傳來(lái)的消息。其中來(lái)自Fire（）消息會(huì)在1秒鐘之后收到。

如果Fire（）的消息先到達(dá)，父goroutine會(huì)選擇第一個(gè)case，記錄超時(shí)信息并從當(dāng)前函數(shù)返回。在這之后，除了子goroutine，沒(méi)有其他的goroutine可以訪問(wèn)ch或者errCh，因?yàn)闆](méi)有其他的goroutine可以在這兩個(gè)信道中收取信息。

由于errCh和ch都是沒(méi)有緩沖區(qū)的信道，在它們上執(zhí)行的發(fā)送操作會(huì)阻塞發(fā)送goroutine，一直到另外的goroutine在它們上執(zhí)行接收操作。所以子goroutine會(huì)永遠(yuǎn)卡在25行或者27行的發(fā)送操作，導(dǎo)致goroutine泄漏。

這個(gè)例子展示了在Go程序中成功檢測(cè)到信道相關(guān)并發(fā)缺陷的難度。在這個(gè)案例中，檢測(cè)器必須同時(shí)滿足2個(gè)條件，才能成功地檢測(cè)到這個(gè)并發(fā)缺陷。

首先，這個(gè)缺陷只有當(dāng)來(lái)自Fire（）的消息比其他兩個(gè)信道的消息先一步到達(dá)才會(huì)觸發(fā)（條件1）。與此同時(shí)，檢測(cè)器還需要有能力推斷，沒(méi)有別的goroutine可以訪問(wèn)ch或者errCh，因此沒(méi)有別的goroutine可以解鎖發(fā)送操作（條件2）。

在現(xiàn)有的檢測(cè)技術(shù)中，靜態(tài)技術(shù)無(wú)法推斷第4行調(diào)用的是17行的Watch（）函數(shù)，所以它們無(wú)法判斷是不是還有其他的goroutine可以解鎖子goroutine（無(wú)法滿足條件2）。

此外，在測(cè)試中，我們發(fā)現(xiàn)來(lái)自Fire（）的消息從來(lái)沒(méi)有先到達(dá)過(guò)，所以動(dòng)態(tài)監(jiān)測(cè)技術(shù)也會(huì)漏報(bào)這個(gè)缺陷（無(wú)法滿足條件1）。

新的動(dòng)態(tài)分析工具Gfuzz

為此，我們提出了一個(gè)新的動(dòng)態(tài)分析工具GFuzz，用來(lái)快速地檢測(cè)Go程序中信道相關(guān)的并發(fā)缺陷。

GFuzz可以檢測(cè)阻塞缺陷（blocking bugs：一個(gè)或多個(gè)goroutine在執(zhí)行中發(fā)生阻塞無(wú)法繼續(xù)進(jìn)行）和非阻塞缺陷（non-blocking bugs：所有g(shù)oroutine都可以結(jié)束但是產(chǎn)生了一些非期望的結(jié)果，比如panic）。

GFuzz的設(shè)計(jì)圍繞著Go程序中的并發(fā)消息。在Go程序中，并發(fā)消息的處理順序是不確定的，開(kāi)發(fā)者必須保證Go程序在所有可能的順序下都能正確執(zhí)行。但是，考慮到可能的處理順序數(shù)量龐大，開(kāi)發(fā)者在有限的時(shí)間和精力里，非常容易忽略一些順序，從而導(dǎo)致并發(fā)缺陷。

GFuzz通過(guò)改變測(cè)試程序中并發(fā)消息的處理順序，來(lái)增加阻塞缺陷和非阻塞缺陷的觸發(fā)幾率。同時(shí)，它也會(huì)監(jiān)控程序的執(zhí)行狀態(tài)來(lái)捕捉觸發(fā)的阻塞缺陷。

我們?cè)賮?lái)看這段Docker中的并發(fā)缺陷和修復(fù)補(bǔ)丁。

從理論上來(lái)說(shuō)，第6行、第8行和第12行的并發(fā)消息，到達(dá)的順序是不確定的。第6行的消息可以比第8行的、或者比第12行的更快或更慢到達(dá)。不管是哪一種情況，這段代碼都應(yīng)該能正確運(yùn)行。

然而開(kāi)發(fā)者沒(méi)有考慮到第6行Fire（）消息先到達(dá)的情況，導(dǎo)致前文提到的阻塞缺陷。通過(guò)改變并發(fā)消息的處理順序，GFuzz能分析這兩種情況并且檢測(cè)出缺陷。

Gfuzz設(shè)計(jì)過(guò)程中的挑戰(zhàn)

盡管GFuzz的設(shè)計(jì)思路聽(tīng)起來(lái)非常直截了當(dāng)，但要構(gòu)建一個(gè)在實(shí)際操作中可順暢使用的工具，我們依然要應(yīng)對(duì)一系列的挑戰(zhàn)。

第1個(gè)問(wèn)題：GFuzz如何辨識(shí)并發(fā)消息？

如果沒(méi)有識(shí)別并發(fā)消息，GFuzz可能會(huì)強(qiáng)制一個(gè)和已有的happens-before消息順序相沖突的順序，從而導(dǎo)致在現(xiàn)實(shí)中不可能發(fā)生的死鎖。

在這里，我們采用了一個(gè)簡(jiǎn)單的方法來(lái)識(shí)別并發(fā)消息。

在同一個(gè)select下，所有的信道操作是可以同時(shí)發(fā)生的，因此這些信道操作處理的消息是并發(fā)的。改變這些消息的處理順序，可以在保持程序原意不變的基礎(chǔ)上，保證程序執(zhí)行路徑的改變。

為了強(qiáng)制測(cè)試程序按照具體的順序來(lái)處理消息，GFuzz會(huì)把每個(gè)select都轉(zhuǎn)換成一種特別的形式，以保證某一個(gè)case被優(yōu)先處理。同時(shí)，GFuzz還提供了一個(gè)超時(shí)機(jī)制去避免死鎖。

第2個(gè)問(wèn)題，如何發(fā)現(xiàn)哪種消息順序更容易觸發(fā)缺陷，并且提高它們的分析優(yōu)先級(jí)？

消息的處理順序可能有無(wú)限多個(gè)，窮舉這些消息是不現(xiàn)實(shí)的。我們使用了模糊測(cè)試（fuzzing）的思路，從已經(jīng)分析過(guò)的消息順序出發(fā)，去生成新的消息處理順序，并且根據(jù)強(qiáng)制消息順序時(shí)測(cè)試程序的執(zhí)行反饋，來(lái)發(fā)現(xiàn)更可疑和更容易觸發(fā)缺陷的順序。

我們?cè)O(shè)計(jì)了一個(gè)公式來(lái)評(píng)價(jià)每個(gè)消息處理順序的可疑程度，然后根據(jù)公式的計(jì)算結(jié)果來(lái)確定順序的優(yōu)先級(jí)。

第3個(gè)問(wèn)題：如何確定一個(gè)與信道相關(guān)的阻塞缺陷已經(jīng)觸發(fā)了？

當(dāng)一個(gè)goroutine阻塞在信道操作上時(shí)，其他任何可以使用這個(gè)信道的goroutine都能對(duì)其解鎖。如果沒(méi)有小心地對(duì)測(cè)試程序的執(zhí)行狀態(tài)進(jìn)行檢查，很容易產(chǎn)生漏報(bào)或者誤報(bào)。

為了解決這個(gè)問(wèn)題，在GFuzz動(dòng)態(tài)監(jiān)控測(cè)試程序執(zhí)行時(shí)，信道引用在goroutine之間的傳遞。Gfuzz會(huì)根據(jù)這些信息來(lái)確定一個(gè)阻塞在信道操作的goroutine是不是能被其他goroutine解鎖，從而進(jìn)行阻塞缺陷的檢測(cè)。

Gfuzz系統(tǒng)概述和實(shí)驗(yàn)評(píng)估

GFuzz會(huì)用完整的Go程序或者單元測(cè)試作為入口，來(lái)檢測(cè)那些誤用channel而導(dǎo)致的并發(fā)錯(cuò)誤。在這個(gè)過(guò)程中，GFuzz通過(guò)持續(xù)生成新的消息順序，來(lái)監(jiān)測(cè)程序執(zhí)行狀態(tài)，同時(shí)篩選可疑順序來(lái)加速尋找錯(cuò)誤的過(guò)程。下圖展示了GFuzz的系統(tǒng)概述。

GFuzz可以作為線下的測(cè)試工具，和已有的程序輸入或者單元測(cè)試配合使用。啟動(dòng)GFuzz之后，它可以自動(dòng)探索測(cè)試程序的執(zhí)行狀態(tài)，來(lái)發(fā)現(xiàn)之前未知的與信道相關(guān)的并發(fā)缺陷。

我們對(duì)GFuzz進(jìn)行了實(shí)驗(yàn)和評(píng)估，評(píng)估結(jié)果如圖所示。其中LoC是源代碼行數(shù)，Test是用于我們實(shí)驗(yàn)的單元測(cè)試數(shù)量。

在“Detected New Bugs（發(fā)現(xiàn)新的缺陷）”下面的各列中，下角標(biāo)b代表阻塞錯(cuò)誤，NBK代表非阻塞錯(cuò)誤；“-”代表沒(méi)有錯(cuò)誤；GFuzz3代表在前三個(gè)小時(shí)里找到的錯(cuò)誤數(shù)量。“Overheads”這一列代表sanitizer的額外開(kāi)銷(xiāo)，“/”代表并不適用。

我們用了包括 Docker、Kubernetes 和 gRPC在內(nèi)的7個(gè)流行的Go開(kāi)源軟件對(duì)GFuzz進(jìn)行了評(píng)估。GFuzz 總共發(fā)現(xiàn)了 184 個(gè)以前未知的缺陷，包括 170 個(gè)阻塞錯(cuò)誤和 14 個(gè)非阻塞錯(cuò)誤，并產(chǎn)生12 個(gè)誤報(bào)。

我們已經(jīng)向軟件開(kāi)發(fā)者報(bào)告了所有錯(cuò)誤。到目前為止，根據(jù)我們的報(bào)告，開(kāi)發(fā)者已經(jīng)確認(rèn)了 124 個(gè)錯(cuò)誤并修復(fù)了其中的 67 個(gè)。

此外，我們系統(tǒng)地將 GFuzz 與最先進(jìn)的靜態(tài) Go 并發(fā)缺陷檢測(cè)器 GCatch 進(jìn)行了比較。GFuzz 在三個(gè)小時(shí)內(nèi)發(fā)現(xiàn)的缺陷數(shù)量要顯著地多于 GCatch發(fā)現(xiàn)的全部缺陷，這確認(rèn)了 GFuzz 確實(shí)推進(jìn)了 Go 并發(fā)缺陷檢測(cè)的進(jìn)展。

結(jié)論

總的來(lái)說(shuō)，我們做出了以下3個(gè)貢獻(xiàn)。

? 我們提出了利用消息重排來(lái)提高 Go 程序中并發(fā)缺陷的觸發(fā)概率。?

? 我們實(shí)現(xiàn)了GFuzz，它可以通過(guò)消息重排、順序優(yōu)先級(jí)的指定和對(duì)測(cè)試程序的動(dòng)態(tài)檢測(cè)，來(lái)有效地檢測(cè)和發(fā)現(xiàn)與信道相關(guān)的并發(fā)錯(cuò)誤。?

? 我們進(jìn)行了詳細(xì)的實(shí)驗(yàn)來(lái)評(píng)估GFuzz。GFuzz 在大型開(kāi)源Go軟件中檢測(cè)到 184 個(gè)以前從未被發(fā)現(xiàn)過(guò)的與信道相關(guān)的錯(cuò)誤。

參考資料