通過消息重排自動檢測 Go 程序中的并發(fā)缺陷

大家好，我是 polarisxu。

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

賓州州立大學系統(tǒng)安全實驗室^[1]依靠模糊測試的思想設計了檢測工具GFuzz，能自動檢測Go程序中的并發(fā)缺陷。GFuzz在著名的開源軟件（如Docker，Kubernetes）中發(fā)現(xiàn)了184個此前未知的并發(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è)級編程語言，當時Google設計Go的目的是編寫安全高效的并發(fā)程序。最近幾年來，Go 快速普及，已經(jīng)成為世界上最受開發(fā)者喜愛的編程語言之一。開發(fā)者們用 Go 編寫了很多工業(yè)界的基礎架構軟件，比如 Docker，Kubernetes，和 gRPC等。

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

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

現(xiàn)有的檢測技術

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

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

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

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

在這里展示一個來自Docker的信道相關并發(fā)缺陷，來更清楚地說明為什么現(xiàn)有的檢測技術無法有效地發(fā)現(xiàn)Go程序中的并發(fā)缺陷。

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

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

如果Fire（）的消息先到達，父goroutine會選擇第一個case，記錄超時信息并從當前函數(shù)返回。在這之后，除了子goroutine，沒有其他的goroutine可以訪問ch或者errCh，因為沒有其他的goroutine可以在這兩個信道中收取信息。

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

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

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

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

此外，在測試中，我們發(fā)現(xiàn)來自Fire（）的消息從來沒有先到達過，所以動態(tài)監(jiān)測技術也會漏報這個缺陷（無法滿足條件1）。

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

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

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

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

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

我們再來看這段Docker中的并發(fā)缺陷和修復補丁。

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

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

Gfuzz設計過程中的挑戰(zhàn)

盡管GFuzz的設計思路聽起來非常直截了當，但要構建一個在實際操作中可順暢使用的工具，我們依然要應對一系列的挑戰(zhàn)。

第1個問題：GFuzz如何辨識并發(fā)消息？

如果沒有識別并發(fā)消息，GFuzz可能會強制一個和已有的happens-before消息順序相沖突的順序，從而導致在現(xiàn)實中不可能發(fā)生的死鎖。

在這里，我們采用了一個簡單的方法來識別并發(fā)消息。

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

為了強制測試程序按照具體的順序來處理消息，GFuzz會把每個select都轉換成一種特別的形式，以保證某一個case被優(yōu)先處理。同時，GFuzz還提供了一個超時機制去避免死鎖。

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

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

我們設計了一個公式來評價每個消息處理順序的可疑程度，然后根據(jù)公式的計算結果來確定順序的優(yōu)先級。

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

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

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

Gfuzz系統(tǒng)概述和實驗評估

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

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

我們對GFuzz進行了實驗和評估，評估結果如圖所示。其中LoC是源代碼行數(shù)，Test是用于我們實驗的單元測試數(shù)量。

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

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

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

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

結論

總的來說，我們做出了以下3個貢獻。

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

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

? 我們進行了詳細的實驗來評估GFuzz。GFuzz 在大型開源Go軟件中檢測到 184 個以前從未被發(fā)現(xiàn)過的與信道相關的錯誤。

參考資料