使用靜態(tài)分析查找并發(fā)錯誤

盡管幾十年來小型化的進步已經(jīng)為單處理器帶來了巨大的性能提升，但這個時代似乎即將結(jié)束。使用單芯片實現(xiàn)顯著額外性能的最佳選擇是通過多個內(nèi)核，但前提是軟件可以編程以利用它們。

不幸的是，并發(fā)編程很困難。即使是只熟悉單線程編程的專家級程序員也常常無法理解并發(fā)程序容易受到諸如競爭條件、死鎖和饑餓等全新類別的缺陷的影響。人類很難推理并發(fā)程序，并且編程語言本身的某些方面不適合并發(fā)。因此，專家們經(jīng)常偶然發(fā)現(xiàn)這些危害。以下討論描述了常見的并發(fā)缺陷，并解釋了靜態(tài)分析工具如何在不執(zhí)行程序的情況下發(fā)現(xiàn)此類缺陷。

競爭條件的后果

當(dāng)多個執(zhí)行線程訪問一個共享的數(shù)據(jù)并且其中至少一個線程在沒有顯式同步操作來分離訪問的情況下更改該數(shù)據(jù)的值時，就會出現(xiàn)競爭條件。根據(jù)兩個線程的交錯，系統(tǒng)可能會處于不一致的狀態(tài)。

種族條件特別陰險，因為它們可以無限期地潛伏而未被發(fā)現(xiàn)，并且只在極少數(shù)情況下出現(xiàn)，表現(xiàn)出難以診斷和重現(xiàn)的神秘癥狀。特別是，它們很可能通過對已部署軟件的測試而存活下來。充其量，這意味著增加開發(fā)時間；在最壞的情況下，后果可能是毀滅性的。

2003 年東北大停電如此普遍的一個原因是計算機化能源管理系統(tǒng)中的競爭條件導(dǎo)致向運營商傳達誤導(dǎo)性信息。正如 Kevin Poulsen 在 2004 年的一篇文章 （ www.securityfocus.com/news/8412 ） 中指出的那樣，“該漏洞有一個以毫秒為單位的機會窗口。” 在測試過程中出現(xiàn)此類問題的可能性微乎其微。在另一種情況下，iOS 4.0 到 4.1（現(xiàn)已修復(fù)）中的競爭條件意味著任何可以物理訪問 iPhone 3G 或更高版本的人都可以在某些條件下繞過其密碼鎖定。

圖 1 顯示了一個簡單競爭條件的示例。帶有入口和出口傳感器的制造裝配線維護當(dāng)前生產(chǎn)線上的項目的運行計數(shù)。每次項目進入行時，此計數(shù)都會增加，每次項目到達行尾并退出時，此計數(shù)就會減少。如果一個項目在另一個項目退出的同時進入該行，則計數(shù)應(yīng)該遞增然后遞減（或反之亦然），以使凈變化為零。但是，正常的遞增和遞減不是原子操作；它們由一系列單獨的指令組成，這些指令首先從內(nèi)存中加載值，然后在本地對其進行修改，最后將其存儲回內(nèi)存中。如果更新事務(wù)是在沒有足夠保護措施的多線程系統(tǒng)中處理的，由于傳感器讀取和寫入共享數(shù)據(jù)：計數(shù)，因此可能會出現(xiàn)競爭條件。圖 1 中的交錯導(dǎo)致錯誤計數(shù)為 69。也有可能導(dǎo)致錯誤計數(shù)為 71 的交錯，以及一些正確導(dǎo)致計數(shù)為 70 的交錯。

圖 1：競爭條件導(dǎo)致裝配線上的項目計數(shù)不正確。

對于這個例子和一般的競爭條件錯誤，標準調(diào)試技術(shù)可能由于幾個原因而無效。

很少發(fā)生意味著發(fā)現(xiàn)問題的機會減少。如果問題不經(jīng)常出現(xiàn)，它可能永遠不會在測試期間出現(xiàn)。這個問題是雙重的。首先，兩個線程中可能的指令交錯數(shù)量可能很大，并且隨著指令數(shù)量的增加而急劇增加。這種現(xiàn)象被稱為組合爆炸。如果線程 A 執(zhí)行M條指令，線程 B 執(zhí)行N條指令，則兩個線程的可能交錯為：

等式 1

例如，給定兩個普通線程，每個線程有 10 條指令，則指令有 184，756 種可能的交錯?，F(xiàn)實世界的軟件龐大而復(fù)雜；測試每一個交織是根本不可能的。其次，即使測試人員可以識別出一些值得檢查的交錯，也很難設(shè)置測試用例來確保它們確實發(fā)生，因為線程調(diào)度可能是高度不確定的。

如果詳盡的測試難以解決，那么開發(fā)人員可以做什么？一種非常有用的方法是靜態(tài)分析。CodeSonar 等高級靜態(tài)分析工具使用高度復(fù)雜的符號執(zhí)行技術(shù)同時考慮許多可能的執(zhí)行路徑和交錯。這些技術(shù)可以在不需要執(zhí)行程序的情況下找到競爭條件和其他并發(fā)錯誤。

有幾個因素使比賽狀況診斷變得困難。首先，癥狀可能令人困惑。在圖 1 示例中，運行計數(shù)通常是正確的，但有時太高，有時太低。其次，不習(xí)慣考慮多線程編程的特定缺陷的程序員可能會在可能出現(xiàn)競爭條件之前花費大量時間對代碼感到困惑。高級靜態(tài)分析工具在這方面特別有用。他們通過檢查共享內(nèi)存位置的訪問模式來識別競爭條件；也就是說，他們關(guān)注的是種族本身，而不是它的癥狀。當(dāng)識別出競爭條件時，高級靜態(tài)分析工具將報告它以及支持信息，以幫助用戶進行評估和調(diào)試。程序員的負擔(dān)大大減輕。

更復(fù)雜，更多錯誤

競爭條件通常通過使用鎖來保護共享資源來避免。但是，鎖可能會引入性能瓶頸，可能會阻止程序充分利用多核的潛力，因此程序員在使用它們時必須小心謹慎。編寫有效使用鎖的代碼可能很棘手，這種復(fù)雜性可能導(dǎo)致一組不同的問題，即死鎖和饑餓。

在死鎖中，兩個或多個線程相互阻止，因為每個線程都持有另一個線程需要的鎖。圖 2 顯示了如何使用用于保護兩個共享變量的兩個鎖出現(xiàn)死鎖。在此示例中，多條裝配線共享當(dāng)前正在裝配的項目總數(shù)，第二個 bad_items 值記錄有多少成品未通過質(zhì)量控制。一個線程在 count 上獲得鎖，另一個在 bad_items 上獲得鎖。兩個線程都無法獲得它需要的第二個鎖；因此既不能執(zhí)行它的操作，也不能到達釋放鎖的地步。由于兩個更新都無法完成，因此兩個線程都完全卡住了。

圖 2：在兩個線程之間的死鎖中，兩個線程都無法前進。

靜態(tài)分析工具可以通過標記不同線程可以以不同順序獲取相同鎖的情況來識別存在死鎖風(fēng)險的軟件，例如圖 2 中所示的線程。消除所有這些情況足以確保系統(tǒng)不會陷入死鎖。

饑餓是使用鎖的多線程程序中發(fā)生的另一個問題。如果一個線程正在等待另一個線程當(dāng)前持有的資源需要很長時間，它可能會餓死。例如，假設(shè)上述制造自動化系統(tǒng)包括一個定期審核線程，該線程檢查所有進入和退出記錄，以確保運行計數(shù)與進入的項目總數(shù)相匹配，而退出的項目總數(shù)更少。審計線程需要鎖定計數(shù)和所有傳感器，因此所有更新都必須等待審計完成。如果審核運行很長時間，更新可能會顯著延遲。如果運行時間過長，下一次審計可能會設(shè)法獲取所有鎖并在未完成的線程取得任何進展之前開始運行。在最壞的情況下，部分或全部更新可能永遠沒有機會運行。

靜態(tài)分析可以通過提出諸如“在持有鎖時是否調(diào)用長時間運行的庫函數(shù)？”之類的問題來提供重要的價值。CodeSonar 等工具還為用戶提供了添加自己檢查的機制。如果已知內(nèi)部函數(shù) f（） 具有較長的運行時間，工程師可以添加自定義檢查，每當(dāng)持有一個或多個鎖的線程調(diào)用 f（） 時觸發(fā)警告。

多線程為嵌入式開發(fā)人員必須考慮的潛在錯誤添加了全新的類別，使得查找各種錯誤變得更加困難。最新一代的靜態(tài)分析工具可以幫助解決這兩個問題。

審核編輯：郭婷