4 自動(dòng)重現(xiàn)和分析嵌入式軟件中的Bug

4.1 引言

嵌入式軟件的重要性逐年增加。ISO26262標(biāo)準(zhǔn)的最高安全級(jí)別要求十個(gè)9小時(shí)內(nèi)無(wú)故障運(yùn)行。然而，歷史上的一些項(xiàng)目表明，即使進(jìn)行了全面的測(cè)試，多年來(lái)仍有許多錯(cuò)誤未被發(fā)現(xiàn)。航天飛機(jī)的控制計(jì)算機(jī)僅有50萬(wàn)行源代碼，卻經(jīng)過(guò)了長(zhǎng)達(dá)8年的測(cè)試，每行源代碼耗資1000美元，即總耗資5億美元。然而，在1990年最后一次發(fā)布時(shí)，預(yù)計(jì)每2000行代碼中會(huì)遺留一個(gè)錯(cuò)誤。這種錯(cuò)誤可能在極少數(shù)情況下出現(xiàn)，而且可能只有在實(shí)際運(yùn)行環(huán)境中測(cè)試嵌入式系統(tǒng)時(shí)才能發(fā)現(xiàn)。

靜態(tài)分析在早期測(cè)試（如單元測(cè)試）中得到了有效利用。然而，對(duì)于復(fù)雜軟件來(lái)說(shuō)，對(duì)錯(cuò)誤的靜態(tài)分析已接近極限。大型軟件的狀態(tài)空間或控制流很難被完全探索。因此，這種分析在性能或精度上都存在缺陷。此外，語(yǔ)義錯(cuò)誤具有很強(qiáng)的應(yīng)用特異性，即使使用優(yōu)化的靜態(tài)分析工具，也無(wú)法檢測(cè)到錯(cuò)誤的行為。如果沒(méi)有完整、正確的規(guī)范作為黃金參考，情況就會(huì)變得更加嚴(yán)重。

系統(tǒng)測(cè)試描述了在目標(biāo)平臺(tái)上部署和測(cè)試軟件的過(guò)程。與只測(cè)試單個(gè)模塊的單元測(cè)試或組件測(cè)試相比，系統(tǒng)測(cè)試是通過(guò)所有集成的軟件和硬件模塊來(lái)執(zhí)行和測(cè)試軟件。在系統(tǒng)測(cè)試之前，約有60%的錯(cuò)誤未被發(fā)現(xiàn)。不過(guò)，根據(jù)軟件開(kāi)發(fā)流程模式的不同，系統(tǒng)測(cè)試可能只在開(kāi)發(fā)流程的后期才進(jìn)行。在系統(tǒng)測(cè)試期間，真實(shí)的傳感器和設(shè)備被連接到嵌入式系統(tǒng)，以獲得真實(shí)的輸入。這樣，傳感器硬件與被測(cè)軟件之間的不兼容性就能被檢測(cè)出來(lái)。

研究表明，錯(cuò)誤發(fā)現(xiàn)得越晚，需要修復(fù)的工作量就越大。一些研究表明，在開(kāi)發(fā)過(guò)程中，錯(cuò)誤修復(fù)成本呈指數(shù)增長(zhǎng)。因此，與單元測(cè)試相比，在系統(tǒng)測(cè)試過(guò)程中發(fā)現(xiàn)的錯(cuò)誤需要付出更多努力，這是由于密切的硬件交互和認(rèn)證要求造成的。然而，一小部分錯(cuò)誤（20%）需要 60-80% 的修復(fù)工作。當(dāng)很大一部分復(fù)雜的錯(cuò)誤在開(kāi)發(fā)過(guò)程中很晚才被發(fā)現(xiàn)時(shí)，項(xiàng)目進(jìn)度和項(xiàng)目期限就會(huì)受到負(fù)面影響。因此，產(chǎn)品往往無(wú)法及時(shí)投放市場(chǎng)。

造成錯(cuò)誤修復(fù)工作量大的原因之一是錯(cuò)誤難以重現(xiàn)?，F(xiàn)場(chǎng)用戶或操作測(cè)試期間的開(kāi)發(fā)人員往往無(wú)法提供足夠的信息來(lái)在實(shí)驗(yàn)室重現(xiàn)錯(cuò)誤。不同的非確定性方面（如線程調(diào)度）可能使實(shí)驗(yàn)室中很難重現(xiàn)與運(yùn)行期間觀察到的相同的執(zhí)行情況。根據(jù)社區(qū)的錯(cuò)誤報(bào)告，開(kāi)源桌面和服務(wù)器應(yīng)用程序中約有17%的錯(cuò)誤甚至無(wú)法重現(xiàn)。對(duì)于具有傳感器驅(qū)動(dòng)輸入的嵌入式軟件，這一比例可能更高。

當(dāng)錯(cuò)誤可以通過(guò)測(cè)試用例重現(xiàn)時(shí)，還需要額外的工作來(lái)分析錯(cuò)誤。如果測(cè)試用例可用，在系統(tǒng)測(cè)試期間運(yùn)行測(cè)試用例和修復(fù)錯(cuò)誤大約需要8小時(shí)。Mozilla等開(kāi)源項(xiàng)目每天會(huì)收到300份錯(cuò)誤報(bào)告。在如此高的錯(cuò)誤修復(fù)工作量下，要處理如此高的錯(cuò)誤率是很困難的。動(dòng)態(tài)驗(yàn)證可以幫助開(kāi)發(fā)人員修復(fù)錯(cuò)誤。然而，大多數(shù)動(dòng)態(tài)分析工具都需要在運(yùn)行期間對(duì)軟件進(jìn)行監(jiān)控。這些監(jiān)控工具通常只適用于特定的平臺(tái)。
錯(cuò)誤分為內(nèi)存錯(cuò)誤、并發(fā)錯(cuò)誤和語(yǔ)義錯(cuò)誤。經(jīng)驗(yàn)研究表明，語(yǔ)義錯(cuò)誤是最主要的根源。最常見(jiàn)的語(yǔ)義錯(cuò)誤是實(shí)現(xiàn)不符合設(shè)計(jì)要求或行為與預(yù)期不符。我們需要自動(dòng)定位語(yǔ)義錯(cuò)誤根源的工具。內(nèi)存錯(cuò)誤并不難解決，因?yàn)橛性S多內(nèi)存剖析工具可用。并發(fā)錯(cuò)誤問(wèn)題較多，尤其難以重現(xiàn)。每十個(gè)并發(fā)錯(cuò)誤中就有一個(gè)無(wú)法重現(xiàn)。

我們自己開(kāi)發(fā)的基于可移植調(diào)試器的錯(cuò)誤重現(xiàn)和動(dòng)態(tài)驗(yàn)證方法為嵌入式軟件開(kāi)發(fā)領(lǐng)域的技術(shù)現(xiàn)狀做出了以下貢獻(xiàn)：

• 通過(guò)使用調(diào)試器工具自動(dòng)記錄和重現(xiàn)錯(cuò)誤，避免了在任何嵌入式平臺(tái)上進(jìn)行費(fèi)力的人工錯(cuò)誤重構(gòu)。
• 通過(guò)強(qiáng)制隨機(jī)線程切換來(lái)改進(jìn)多線程錯(cuò)誤檢測(cè)。
• 通過(guò)對(duì)重現(xiàn)的錯(cuò)誤進(jìn)行自動(dòng)根源分析，減少人工調(diào)試工作量。
• 通過(guò)使用低成本調(diào)試工具實(shí)施性能優(yōu)化和分層分析，避免了昂貴的監(jiān)控硬件。
• 通過(guò)在可擴(kuò)展和易調(diào)整的模塊中實(shí)施動(dòng)態(tài)驗(yàn)證工具，降低了動(dòng)態(tài)驗(yàn)證工具的移植成本。

我們的方法支持開(kāi)發(fā)人員更快地檢測(cè)和重建（主要是語(yǔ)義和并發(fā)）錯(cuò)誤。通過(guò)實(shí)施自動(dòng)根源分析，它還能幫助開(kāi)發(fā)人員更快地修復(fù)錯(cuò)誤。我們的工具可節(jié)省調(diào)試成本和硬件投資成本。它支持大多數(shù)嵌入式平臺(tái)。它能幫助開(kāi)發(fā)團(tuán)隊(duì)將軟件產(chǎn)品更早地投放市場(chǎng)。

第4.2節(jié)簡(jiǎn)要介紹了正常的手動(dòng)調(diào)試過(guò)程。第4.3節(jié)介紹了自動(dòng)重現(xiàn)錯(cuò)誤的方法，隨后介紹了我們自己基于調(diào)試器的方法。第4.4節(jié)展示了如何使用調(diào)試器工具實(shí)現(xiàn)基于斷言的驗(yàn)證。第4.5節(jié)介紹了在不使用斷言的情況下分析錯(cuò)誤根源的概念，以及使用廉價(jià)調(diào)試器接口加速監(jiān)控實(shí)現(xiàn)的概念。

4.2 概述

下圖中的工作流程介紹了手動(dòng)查找和修復(fù)錯(cuò)誤的過(guò)程。首先要在系統(tǒng)測(cè)試環(huán)境中測(cè)試嵌入式系統(tǒng)和運(yùn)行中的軟件。例如，導(dǎo)航軟件可在連接真實(shí)傳感器的測(cè)試驅(qū)動(dòng)器中執(zhí)行。在執(zhí)行過(guò)程中，對(duì)輸入進(jìn)行跟蹤并記錄到錯(cuò)誤報(bào)告（A.）中。該錯(cuò)誤報(bào)告將提交至錯(cuò)誤報(bào)告庫(kù)。在實(shí)驗(yàn)室中，開(kāi)發(fā)人員會(huì)根據(jù)錯(cuò)誤報(bào)告嘗試手動(dòng)重現(xiàn)錯(cuò)誤 (B.)。如果錯(cuò)誤可以重現(xiàn)，開(kāi)發(fā)人員必須手動(dòng)查找源代碼中的故障根源 (C.)。修復(fù)錯(cuò)誤后，可使用回歸測(cè)試套件執(zhí)行軟件 (D.)。這樣就可以確保在修復(fù)過(guò)程中不會(huì)增加新的錯(cuò)誤。

手動(dòng)調(diào)試概述：

4.3 基于調(diào)試器的錯(cuò)誤重現(xiàn)

本節(jié)介紹自動(dòng)支持錯(cuò)誤再現(xiàn)的工具方法。為了重現(xiàn)錯(cuò)誤，必須在運(yùn)行過(guò)程中捕獲傳感器輸入。在重放過(guò)程中，必須觸發(fā)或注入相同的傳感器輸入（如來(lái)自GPS或觸摸屏的輸入），以實(shí)現(xiàn)相同的執(zhí)行或指令序列。軟件的正常執(zhí)行是確定性的。當(dāng)軟件在相同輸入的情況下運(yùn)行時(shí)，會(huì)執(zhí)行相同的指令。然而，這些輸入是非確定的，在兩次執(zhí)行軟件時(shí)并不完全相同。例如，在兩次測(cè)試執(zhí)行中很難在觸摸屏上實(shí)現(xiàn)相同的動(dòng)作。兩次執(zhí)行之間的微小差異就可能決定是否觸發(fā)故障。圖4.2顯示了被測(cè)軟件（SUT）的不同輸入。非確定性輸入具體如下：傳感器是嵌入式軟件最常見(jiàn)的輸入源（如 GPS 傳感器）。用戶交互由人機(jī)界面設(shè)備（如觸摸屏）觸發(fā)。靜態(tài)數(shù)據(jù)可從磁盤(pán)或閃存（如XML配置文件）中存儲(chǔ)和讀取。訪問(wèn)硬件中的時(shí)間或隨機(jī)性功能可改變執(zhí)行情況，從而使復(fù)制變得困難。網(wǎng)絡(luò)交互可用于與嵌入式系統(tǒng)中的其他設(shè)備進(jìn)行通信（如 CAN 總線）。操作環(huán)境可由操作系統(tǒng)來(lái)表示，該系統(tǒng)控制日程安排和內(nèi)存管理。物理效應(yīng)可能會(huì)導(dǎo)致硬件變化，這也是最難處理的分歧。從SUT的角度來(lái)看，非確定性的來(lái)源可分為： 操作系統(tǒng) SDK 訪問(wèn)（如系統(tǒng)調(diào)用）、信號(hào)或中斷、特定處理器功能、調(diào)度或共享內(nèi)存訪問(wèn)順序以及內(nèi)存初始化和內(nèi)存分配（如圖4.2中SUT框周圍的方框所示）。

圖4.2嵌入式軟件的輸入類型

4.3.1 技術(shù)現(xiàn)狀

本節(jié)介紹了當(dāng)前最先進(jìn)的錯(cuò)誤自動(dòng)重現(xiàn)方法。對(duì)所介紹的非確定性源引起的不同事件的跟蹤和重放可在不同層面上實(shí)現(xiàn)。

圖4.3：重放模塊的不同層次

可以在硬件層面記錄/重放軟件的執(zhí)行（第 4.3.1.1 節(jié)）。因此，需要添加額外的特殊硬件來(lái)支持跟蹤和回放。另一種方法是模擬硬件。在仿真平臺(tái)中，可以集成捕獲模塊。操作系統(tǒng)可控制軟件和硬件，并可記錄/重放事件（第 4.3.1.2 節(jié)）?？梢孕薷牟僮飨到y(tǒng)并將其安裝到目標(biāo)平臺(tái)上。有些操作系統(tǒng)支持集成新模塊。此外，還可以修改軟件以記錄/重放應(yīng)用層面的事件（第 4.3.1.3 節(jié)）。因此，可以在源代碼或二進(jìn)制代碼層面修改應(yīng)用程序。調(diào)試器工具在軟件和操作系統(tǒng)之間提供了一個(gè)層級(jí)，因此可以記錄/重放事件，如第 4.3.2 節(jié)和第 4.3.1.3 節(jié)所述。4.3.2 和 4.3.3 節(jié)中介紹的那樣。以下各節(jié)將根據(jù)各個(gè)層面介紹不同的方法。

4.3.1.1 硬件級(jí)重放

我們研究了硬件級(jí)重放領(lǐng)域的三種方法：硬件支持重放、全電路重放和基于虛擬化的重放。大多數(shù)硬件支持的重放方法都考慮了多處理器平臺(tái)。為了實(shí)現(xiàn)相似的執(zhí)行，不同內(nèi)核之間對(duì)共享內(nèi)存的訪問(wèn)會(huì)被記錄下來(lái)，并在重放過(guò)程中納入相同的序列。共享內(nèi)存訪問(wèn)的跟蹤可通過(guò)附加硬件實(shí)現(xiàn)。與基于軟件的方法相比，這種方法的優(yōu)勢(shì)在于基于硬件的功能開(kāi)銷低。全電路重放方法在FPGA綜合電路中添加了調(diào)試工具。這樣，就可以實(shí)時(shí)記錄和重放FPGA電路的數(shù)據(jù)流。不過(guò)，只能實(shí)時(shí)捕獲程序執(zhí)行的一部分。其他方法實(shí)現(xiàn)了基于虛擬化的重放，對(duì)硬件進(jìn)行模擬。此外，還有虛擬原型平臺(tái) Quick Emulator（QEMU）。不過(guò)，虛擬原型平臺(tái)的基礎(chǔ)開(kāi)銷較大，可能會(huì)影響與所連接傳感器硬件的交互。

4.3.1.2 操作系統(tǒng)級(jí)重放

我們研究了操作系統(tǒng)級(jí)重放的三種不同方法：事件序列重放、同步事件重放和周期精確事件重放。為了重放相同的事件序列，一些方法使用操作系統(tǒng) SDK 特定命令來(lái)跟蹤底層事件，并在重放過(guò)程中觸發(fā)相同的序列。RERAN使用 Android SDK的getevent和自帶的sendevent函數(shù)在Android移動(dòng)平臺(tái)上進(jìn)行跟蹤和重放。RERAN無(wú)需修改即可記錄和重放排名前100位的Android應(yīng)用程序。記錄和重放觸摸屏上的復(fù)雜手勢(shì)輸入只需很低的開(kāi)銷（約 1%）。不過(guò)，操作系統(tǒng)中必須有支持事件跟蹤和發(fā)送的功能。在多個(gè)內(nèi)核上進(jìn)行不同的調(diào)度或并行執(zhí)行會(huì)導(dǎo)致另一種行為。并行執(zhí)行需要同步事件，以實(shí)現(xiàn)對(duì)共享資源的相同訪問(wèn)順序。SCRIBE是作為用于跟蹤和注入的Linux內(nèi)核模塊實(shí)現(xiàn)的。它支持多處理器執(zhí)行，并使用同步點(diǎn)實(shí)現(xiàn)并行訪問(wèn)的同步。利用這種同步，即使在多個(gè)內(nèi)核上運(yùn)行，系統(tǒng)調(diào)用也能在記錄和重放過(guò)程中保持一致的順序。然而，實(shí)時(shí)系統(tǒng)有嚴(yán)格的時(shí)間要求，需要對(duì)中斷等事件進(jìn)行精確的指令再現(xiàn)。RT-Replayer利用實(shí)時(shí)操作系統(tǒng)內(nèi)核跟蹤中斷。為了進(jìn)行重放，在發(fā)生中斷的內(nèi)存地址上使用陷阱指令（類似于調(diào)試器的斷點(diǎn)）。因此，在重放過(guò)程中，軟件會(huì)在陷阱處停止，并觸發(fā)相同的中斷功能。

4.3.1.3 應(yīng)用程序級(jí)回放

為了跟蹤和注入應(yīng)用層事件，我們研究了三種不同的應(yīng)用層回放方法：源代碼工具化回放、二進(jìn)制工具化回放和基于檢查點(diǎn)的回放。使用源代碼工具，可以修改源代碼以跟蹤控制流和變量賦值。Jalangi提出了一種方法，即在運(yùn)行時(shí)對(duì)變量的每次賦值進(jìn)行工具化，并將賦值寫(xiě)入跟蹤文件。在重放過(guò)程中，會(huì)注入跟蹤到的變量值。該方法是針對(duì)JavaScript提出的，但可移植到任何其他編程語(yǔ)言。Jalangi的缺點(diǎn)是：開(kāi)銷大、跟蹤文件大，而且可能產(chǎn)生副作用。動(dòng)態(tài)二進(jìn)制代碼工具在執(zhí)行過(guò)程中修改源代碼，例如記錄。它可在運(yùn)行時(shí)對(duì)加載的二進(jìn)制代碼進(jìn)行動(dòng)態(tài)檢測(cè)，并注入額外的跟蹤代碼。工具化代碼可以高度優(yōu)化，執(zhí)行代碼只需較低的開(kāi)銷。PinPlay利用 Pin工具框架對(duì)二進(jìn)制代碼進(jìn)行動(dòng)態(tài)工具化。它考慮了本節(jié)導(dǎo)言中介紹的幾種非確定性來(lái)源。不過(guò)Pin框架僅適用于特定指令集。檢查點(diǎn)方法能高頻捕捉當(dāng)前進(jìn)程狀態(tài)。從檢查點(diǎn)開(kāi)始，所有非確定性事件（如系統(tǒng)調(diào)用）都會(huì)被捕獲。檢查點(diǎn)通?；谂c平臺(tái)相關(guān)的操作系統(tǒng)SDK操作。

4.3.2 理論與算法

上一節(jié)介紹了最先進(jìn)的方法在不同系統(tǒng)級(jí)別記錄和重放錯(cuò)誤的方式。本節(jié)將介紹我們自己為調(diào)試器工具跟蹤和重放錯(cuò)誤的方法。它考慮了兩種非確定性輸入來(lái)源：傳感器輸入和線程調(diào)度。我們不考慮內(nèi)存違規(guī)，因?yàn)檫@類錯(cuò)誤可以通過(guò)許多可用的內(nèi)存剖析工具輕松檢測(cè)到。我們首先介紹傳感器訪問(wèn)的記錄/重放，然后介紹線程計(jì)劃的記錄/重放。
嵌入式軟件經(jīng)常在定時(shí)器或中斷的觸發(fā)下訪問(wèn)連接的設(shè)備。設(shè)備狀態(tài)以特定頻率被請(qǐng)求。例如，導(dǎo)航軟件可能以10Hz的頻率訪問(wèn) GPS 傳感器。圖 4.4顯示了如何通過(guò)定時(shí)器功能訪問(wèn)傳感器。

可以通過(guò)在設(shè)備訪問(wèn)結(jié)束的位置（我們定義為接收）暫停軟件執(zhí)行來(lái)實(shí)現(xiàn)跟蹤。讀取的數(shù)據(jù)將寫(xiě)入日志文件。圖 4.5 展示了這一概念。

圖 4.5 記錄序列

在重放過(guò)程中，執(zhí)行暫停在某個(gè)位置，在該位置中斷開(kāi)始訪問(wèn)設(shè)備（我們定義為請(qǐng)求）。跳過(guò)對(duì)傳感器的訪問(wèn)，跳轉(zhuǎn)到接收位置（定義為 Receive）。此時(shí)，將從日志文件中讀取數(shù)據(jù)。這些數(shù)據(jù)被注入到執(zhí)行過(guò)程中。這樣，記錄運(yùn)行中的傳感器數(shù)據(jù)就會(huì)被重放。這一概念可通過(guò)調(diào)試器工具實(shí)現(xiàn)，如第 4.3.3 節(jié)所述。4.3.3. 基于調(diào)試器的重放如圖 4.6 中的序列圖所示。

圖 4.6 重放序列圖

非確定性的其他來(lái)源可能是線程調(diào)度。線程計(jì)劃的記錄/重放基于線程事件和IO事件序列的重建。這樣，在線程操作（如 sem_wait和sem_post時(shí)的活動(dòng)線程就會(huì)受到監(jiān)控。在重放過(guò)程中，會(huì)觸發(fā)這些事件的相同調(diào)用序列。列表1和2顯示了行人識(shí)別軟件組件的兩個(gè)線程的示例：Proc線程用于識(shí)別圖片中的行人，GUI線程用于在檢測(cè)到行人的圖片中繪制矩形。如果交替執(zhí)行這兩個(gè)線程，不會(huì)出現(xiàn)故障。但是，當(dāng)Proc線程執(zhí)行兩次時(shí)，有一幅圖片沒(méi)有繪制。此外，當(dāng)Proc被執(zhí)行兩次時(shí)，semaphore的值為2，GUI線程也會(huì)被執(zhí)行兩次。因此，當(dāng)前圖片在第4行的 GUI 線程中被釋放，下一次調(diào)用drawRec時(shí)會(huì)觸發(fā)已釋放的圖片。這種情況在正常執(zhí)行中極少發(fā)生，因?yàn)樵诰€程 Proc（第 2 行）中對(duì)圖像進(jìn)行長(zhǎng)時(shí)間的行人識(shí)別后，通常會(huì)觸發(fā)線程切換到 GUI。

我們的方法實(shí)現(xiàn)了活動(dòng)線程的序列化，并在線程操作時(shí)隨機(jī)切換線程。因此，正常的線程調(diào)度器被鎖定，任何時(shí)候都只有一個(gè)線程處于活動(dòng)狀態(tài)。這樣，活動(dòng)線程就不會(huì)被其他線程搶占。在我們的概念中，線程切換由我們的工具在線程事件（如 sem_wait、sem_post）時(shí)觸發(fā)。腳本通過(guò)暫停相應(yīng)函數(shù)并觸發(fā)線程切換來(lái)監(jiān)控線程事件。在每個(gè)線程事件中，我們的工具都會(huì)觸發(fā)線程切換操作（見(jiàn)表 4.1）。
表 4.1 工具觸發(fā)的線程切換操作列表

我們的工具會(huì)為每個(gè)semaphore sem設(shè)置計(jì)數(shù)器。每當(dāng)出現(xiàn)sem_wait，算法都會(huì)檢查語(yǔ)義符號(hào)是否大于零，因此是否可以通過(guò)，并減少語(yǔ)義符號(hào)計(jì)數(shù)器sem。如果semaphore計(jì)數(shù)器為零，則線程被注冊(cè)為等待線程，并觸發(fā)切換到另一（非等待）線程。當(dāng)sem_post 發(fā)生時(shí)，post結(jié)束，并觸發(fā)切換到隨機(jī)線程。在重放過(guò)程中，與跟蹤過(guò)程一樣，通過(guò)為隨機(jī)函數(shù)設(shè)置相同的種子，調(diào)用相同的隨機(jī)線程切換。使用這種方法，線程切換總是由腳本觸發(fā)。因此，腳本可以完全控制線程調(diào)度。

4.3.3 執(zhí)行

調(diào)試器工具用于控制SUT的執(zhí)行。GNU調(diào)試器是一種流行的調(diào)試工具，可用于不同的嵌入式平臺(tái)。目前GDB主頁(yè)列出了GDB支持的80 個(gè)主機(jī)平臺(tái)。此外，不同的供應(yīng)商還將其適配到其他平臺(tái)。在正常使用過(guò)程中，GDB由開(kāi)發(fā)人員手動(dòng)控制，開(kāi)發(fā)人員在控制臺(tái)終端輸入命令。表 4.2 列出了最常用的 GDB 命令。

表 4.2 線程事件操作

GDB 提供了外部 API。通過(guò)該API，可以使用Python編程語(yǔ)言控制調(diào)試器的執(zhí)行和命令。清單3顯示了一個(gè)可與GDB一起加載的簡(jiǎn)單 Python腳本。它開(kāi)始加載要測(cè)試的程序（第2行），并在方法foo上設(shè)置斷點(diǎn)（第3行）。腳本開(kāi)始運(yùn)行程序（第4行）。程序在調(diào)用 foo時(shí)暫停。腳本對(duì)foo的調(diào)用進(jìn)行計(jì)數(shù)（第 6-8 行）。

這樣，調(diào)試器就由腳本邏輯控制了。其他調(diào)試器提供不同的 API 來(lái)控制被測(cè)軟件的執(zhí)行。即使調(diào)試器只提供終端命令接口，也可以通過(guò)腳本模擬這些終端命令，并對(duì)終端輸出進(jìn)行評(píng)估。我們基于調(diào)試器的方法就是利用這種調(diào)試器工具 API 來(lái)記錄和重放事件。清單4顯示了我們?yōu)?Navit 導(dǎo)航軟件實(shí)現(xiàn) GPS 傳感器數(shù)據(jù)重放的方法。

在開(kāi)始請(qǐng)求設(shè)備和結(jié)束訪問(wèn)設(shè)備的源代碼行（第1-2行）中設(shè)置斷點(diǎn)。在記錄時(shí)，執(zhí)行會(huì)在接收GPS數(shù)據(jù)的位置暫停。在這種情況下，將打印當(dāng)前的GPS值（第7-8行）并將其寫(xiě)入日志文件（第9行）。對(duì)于重放，執(zhí)行暫停在開(kāi)始訪問(wèn)GPS的位置。使用跳轉(zhuǎn)命令跳過(guò)訪問(wèn)（第12行），并注入日志中的數(shù)據(jù)（第13-14行）。如果使用斷點(diǎn)進(jìn)行基于調(diào)試器的記錄太慢，可以使用printf語(yǔ)句或跟蹤緩沖區(qū)來(lái)實(shí)現(xiàn)。

下一段將介紹如何控制被測(cè)程序以實(shí)現(xiàn)確定的線程調(diào)度。GDB為調(diào)試多線程程序提供了表4.3所列的命令。表4.3列出了用于調(diào)試多線程程序的命令，其中包括我們?cè)趯?shí)現(xiàn)過(guò)程中使用的三條命令。在每次斷點(diǎn)暫停時(shí)，開(kāi)發(fā)人員可以手動(dòng)檢查當(dāng)前線程，也可以切換到線程列表中的其他線程。

表 4.3 處理多線程的 GDB 命令列表

清單5介紹了行人識(shí)別重放的實(shí)現(xiàn)（與第 4.3.4 節(jié)中介紹的游戲案例研究類似）。

命令"set scheduler-locking on"可禁用當(dāng)前線程調(diào)度器（第5行）。激活該選項(xiàng)后，任何時(shí)候都只能執(zhí)行一個(gè)線程?？梢浦驳姆菗屨际骄€程庫(kù)也能達(dá)到類似效果。這樣，線程的并行執(zhí)行就被序列化了。為了實(shí)現(xiàn)所需的線程切換，我們的工具會(huì)在使用的線程操作處設(shè)置斷點(diǎn)（見(jiàn)第4-5行）。每經(jīng)過(guò)一個(gè)線程操作，我們的工具都會(huì)根據(jù)表4.1中的操作，用GDB的線程命令觸發(fā)線程開(kāi)關(guān)（清單5，第14-17行）。線程計(jì)劃的控制與傳感器重放集成在一起（清單5，第18行之后）。

與普通線程調(diào)度程序相比，在線程操作中使用隨機(jī)切換可實(shí)現(xiàn)更好的線程交錯(cuò)覆蓋率。這樣，并發(fā)錯(cuò)誤就能更快地顯現(xiàn)出來(lái)。

4.3.4 實(shí)驗(yàn)

圖4.7顯示了我們?cè)?X86 英特爾平臺(tái)的Ubuntu Linux上執(zhí)行單線程軟件Navit時(shí)跟蹤或記錄傳感器輸入數(shù)據(jù)的測(cè)量結(jié)果。測(cè)量考慮了一條有1200個(gè)GPS坐標(biāo)的路線。這些坐標(biāo)由Mockup GPS服務(wù)器從文件中讀取。測(cè)試GPS頻率為50、33、20和10 Hz，同時(shí)以100Hz 捕獲用戶光標(biāo)輸入（例如從觸摸屏）。正常執(zhí)行（標(biāo)記為"Normal"）和記錄執(zhí)行（標(biāo)記為"Rec"）之間的開(kāi)銷幾乎保持不變，因?yàn)樵跀帱c(diǎn)處暫停執(zhí)行所用的時(shí)間被輪詢定時(shí)器的調(diào)用所占用。這樣，我們針對(duì)基于定時(shí)器軟件的方法就能將開(kāi)銷降到最低。對(duì)于其他類型的軟件，還需要對(duì)跟蹤進(jìn)行優(yōu)化，例如將多個(gè)輸入分組，一次只跟蹤一組輸入。

圖 4.7 單線程 Navit 傳感器輸入記錄的性能測(cè)量。

我們用兩個(gè)使用 POSIX 線程實(shí)現(xiàn)的嵌入式軟件示例測(cè)試了我們的確定性調(diào)度和記錄方法。這些示例的性能測(cè)量結(jié)果如圖4.8所示。第一個(gè)是基于 ASCII 碼的飛行射擊游戲。該游戲使用兩個(gè)線程，一個(gè)用于繪制場(chǎng)景，另一個(gè)用于讀取鍵盤(pán)信息。第二個(gè)例子是在車載攝像頭的視頻數(shù)據(jù)中識(shí)別行人（見(jiàn)第 4.3.2 節(jié)）。在每個(gè)例子中，我們都使用了兩種場(chǎng)景進(jìn)行測(cè)量，一種是短場(chǎng)景，另一種是長(zhǎng)場(chǎng)景。我們對(duì)游戲進(jìn)行了測(cè)量，直到用戶在沒(méi)有互動(dòng)的情況下?lián)p失5或10條生命為止。我們使用一組60或165張圖片作為輸入，對(duì)行人識(shí)別進(jìn)行了測(cè)量。我們的實(shí)驗(yàn)在配備ARM CPU和Linux操作系統(tǒng)的NVIDIA Tegra K1上執(zhí)行了五次。

圖 4.8 確定性調(diào)度和錄制的性能測(cè)量結(jié)果

在記錄游戲場(chǎng)景時(shí)，短場(chǎng)景平均需要調(diào)度377次線程切換，長(zhǎng)場(chǎng)景平均需要調(diào)度642次線程切換。在行人識(shí)別示例中，平均需要安排186次（短）和475次（長(zhǎng)）線程切換。錄制行人軟件平均需要1.22倍和1.36倍的開(kāi)銷。記錄游戲的開(kāi)銷更高，平均為2.86倍和2.98倍，因?yàn)樾枰诟痰臅r(shí)間內(nèi)觸發(fā)更多的線程開(kāi)關(guān)。

我們觀察到，在兩個(gè)案例研究中，短時(shí)間和長(zhǎng)時(shí)間的開(kāi)銷都差不多。測(cè)量結(jié)果表明，只需極少的工作量就能實(shí)現(xiàn)高性能記錄。每個(gè)記錄和重放腳本的源代碼不到50行。此外，行人識(shí)別示例表明，如果使用我們的工具強(qiáng)制進(jìn)行隨機(jī)切換，并發(fā)錯(cuò)誤的檢測(cè)速度會(huì)更快。因此，在我們的測(cè)試中，使用我們的方法在幾秒鐘內(nèi)就能檢測(cè)到示例錯(cuò)誤，但在使用普通線程調(diào)度器進(jìn)行10次圖片輸入時(shí)卻不會(huì)觸發(fā)該錯(cuò)誤。為了測(cè)量性能，我們觸發(fā)了兩個(gè)線程的交替調(diào)用，以避免觸發(fā)錯(cuò)誤。

4.4 重放期間的動(dòng)態(tài)驗(yàn)證

即使可以重現(xiàn)錯(cuò)誤，也很難在重放過(guò)程中找到錯(cuò)誤的根本原因。手動(dòng)調(diào)試重放（如使用GDB）非常費(fèi)力。源代碼通常由其他開(kāi)發(fā)人員實(shí)現(xiàn)。因此，很難理解是哪一系列操作（如方法調(diào)用）導(dǎo)致了故障。此外，也很難理解錯(cuò)誤的操作序列是如何造成的。運(yùn)行時(shí)驗(yàn)證領(lǐng)域的方法提供了在運(yùn)行時(shí)通過(guò)將執(zhí)行與正式規(guī)范進(jìn)行比較來(lái)自動(dòng)分析執(zhí)行的概念。運(yùn)行時(shí)驗(yàn)證測(cè)試在執(zhí)行過(guò)程中是否保持了一組特定屬性。觀察執(zhí)行情況的組件稱為監(jiān)控器。

4.4.1 技術(shù)現(xiàn)狀

在線監(jiān)控器方法是在運(yùn)行過(guò)程中與執(zhí)行并行運(yùn)行監(jiān)控器。在線監(jiān)控器必須非常高效，因?yàn)檎?zhí)行不應(yīng)受到干擾。不過(guò)，在線監(jiān)控器可能會(huì)對(duì)執(zhí)行過(guò)程中觀察到的異常情況做出反應(yīng)。出現(xiàn)異常時(shí)，可在運(yùn)行過(guò)程中啟動(dòng)故障安全或恢復(fù)模式。日志監(jiān)控器檢查在軟件長(zhǎng)期運(yùn)行過(guò)程中捕獲的日志文件。跟蹤文件是在運(yùn)行過(guò)程中有效生成的。為了不影響正常執(zhí)行，跟蹤應(yīng)精簡(jiǎn)或使用快速的附加硬件來(lái)實(shí)現(xiàn)。離線時(shí)，會(huì)對(duì)跟蹤文件進(jìn)行詳細(xì)分析?？梢詸z測(cè)出跟蹤文件中的錯(cuò)誤事件序列，指出故障或甚至故障的根本原因。有些方法結(jié)合了軟件的記錄/重放和動(dòng)態(tài)分析 。但是，這些方法沒(méi)有使用實(shí)現(xiàn)復(fù)雜斷言的框架，也沒(méi)有在嵌入式平臺(tái)上進(jìn)行測(cè)試。
表4.4列出了每種模式的優(yōu)缺點(diǎn)。這兩種方法不支持檢查故障是否仍然發(fā)生（控制測(cè)試）。此外，這兩種方法都不能細(xì)粒度應(yīng)用（細(xì)粒度），因?yàn)樗鼈儠?huì)干擾與用戶或其他系統(tǒng)的正常交互。我們的重放方法符合前兩類要求（控制測(cè)試和細(xì)粒度）。不過(guò)，只有在表 4.4 中總結(jié)的在線模式下才能激活恢復(fù)功能。我們認(rèn)為，長(zhǎng)期跟蹤和監(jiān)控最好使用跟蹤日志。
表 4.4 監(jiān)控類型不同特性的比較

4.4.2 理論和工作流程

在重放過(guò)程中應(yīng)用動(dòng)態(tài)驗(yàn)證的概念是基于只跟蹤軟件的相關(guān)輸入并離線重放的概念。在重放過(guò)程中，可以執(zhí)行細(xì)粒度跟蹤。監(jiān)控或分析可檢查這些跟蹤是否存在異常。與正常運(yùn)行相比，重放期間對(duì)高效跟蹤和監(jiān)控的要求較低。此外，生成的重放還可在錯(cuò)誤修復(fù)后用作控制重放。我們認(rèn)為，重放概念是系統(tǒng)測(cè)試的最佳選擇，因?yàn)樯傻目刂浦胤趴捎米饕院蟮幕貧w測(cè)試用例。圖 4.9 顯示了自動(dòng)化工具如何支持或取代不同的人工步驟。4.3.3節(jié)中介紹的隨機(jī)調(diào)度概念優(yōu)化了多線程錯(cuò)誤（A.）的檢測(cè)。4.3.3. 錯(cuò)誤重放（B.）已實(shí)現(xiàn)自動(dòng)化（見(jiàn)第 4.3 節(jié)），并可用作回歸測(cè)試（D.）。重放（B.）過(guò)程中的自動(dòng)分析支持手動(dòng)錯(cuò)誤修復(fù)（C.）。下文將介紹這些分析工具。

圖4.9重放期間基于調(diào)試器的動(dòng)態(tài)驗(yàn)證工作流程

A. 系統(tǒng)錯(cuò)誤檢測(cè)： 在實(shí)際操作中測(cè)試軟件。在這些測(cè)試過(guò)程中，會(huì)捕捉到進(jìn)入軟件的事件。記錄機(jī)制通過(guò)符號(hào)調(diào)試器實(shí)現(xiàn)，以避免工具化并實(shí)現(xiàn)平臺(tái)兼容性。因此，調(diào)試器由腳本控制。開(kāi)發(fā)人員決定哪些事件是相關(guān)的，必須捕獲。因此，記錄可以保持精簡(jiǎn)。為有效檢測(cè)多線程錯(cuò)誤，線程調(diào)度器由腳本控制，在任何線程事件中觸發(fā)隨機(jī)開(kāi)關(guān)。

B. 自動(dòng)重放和分析： 故障序列可在實(shí)驗(yàn)室中加載并確定性地重放。重放機(jī)制是通過(guò)便攜式調(diào)試器工具實(shí)現(xiàn)的。軟件通過(guò)調(diào)試界面在與運(yùn)行期間相同的硬件上執(zhí)行，以安排與原始運(yùn)行期間相同的系統(tǒng)行為。在重放過(guò)程中，故障會(huì)根據(jù)確定性重放再次發(fā)生。手動(dòng)調(diào)試完整的執(zhí)行序列甚至是事件的多個(gè)處理路徑非常耗時(shí)。因此，我們?cè)谥胤胚^(guò)程中采用動(dòng)態(tài)驗(yàn)證來(lái)自動(dòng)檢測(cè)潛在的異常情況。這些信息可以為故障提供提示。在運(yùn)行過(guò)程中進(jìn)行的在線分析會(huì)干擾正常執(zhí)行，但在重放過(guò)程中不會(huì)造成弊端，因?yàn)橹胤诺膱?zhí)行不需要與用戶或外部組件進(jìn)行交互。

C. 手動(dòng)錯(cuò)誤修復(fù)： 根據(jù)動(dòng)態(tài)驗(yàn)證報(bào)告，開(kāi)發(fā)人員可以手動(dòng)修復(fù)故障。該步驟的結(jié)果是一個(gè)已打補(bǔ)丁的程序。

D. 回歸重放： 修改后的程序可通過(guò)控制回放進(jìn)行測(cè)試。使用記錄的故障輸入序列執(zhí)行程序，觀察故障行為是否再次發(fā)生。最后，錯(cuò)誤重放可作為回歸測(cè)試套件的測(cè)試用例存檔。

4.4.3 在回放過(guò)程中執(zhí)行斷言

在上一節(jié)介紹的工作流程中，動(dòng)態(tài)驗(yàn)證是在重放過(guò)程中應(yīng)用的，用于檢測(cè)錯(cuò)誤原因。本節(jié)將展示如何使用斷言來(lái)檢測(cè)錯(cuò)誤原因。這種斷言可以通過(guò)調(diào)試器輕松實(shí)現(xiàn)。因此，在基于調(diào)試器的重放過(guò)程中，也可以使用調(diào)試器監(jiān)控執(zhí)行情況。下文將討論行人識(shí)別軟件的多線程重放（如第4.3節(jié)所述）。在軟件重放過(guò)程中，可以使用基于斷言的驗(yàn)證對(duì)事件序列進(jìn)行分析。通過(guò)在相應(yīng)的方法上設(shè)置斷點(diǎn)來(lái)監(jiān)控方法調(diào)用的順序。在行人識(shí)別示例中，有三個(gè)相關(guān)事件：recogPed()、drawRec() 和 showImg()。在重放過(guò)程中，可以通過(guò)方法斷點(diǎn)或觀察點(diǎn)檢查時(shí)間條件。圖4.10中的自動(dòng)機(jī)會(huì)檢查加載和處理圖像的正確順序是否被調(diào)用。如果發(fā)生其他轉(zhuǎn)換，則會(huì)檢測(cè)到違反規(guī)范的情況。

圖 4.10 行人識(shí)別動(dòng)作序列自動(dòng)機(jī)

這種監(jiān)控器可以在GDB Python腳本中輕松實(shí)現(xiàn)（見(jiàn)清單 6）。第1-3行根據(jù)條件設(shè)置斷點(diǎn)和觀察點(diǎn)。第6-14行檢查達(dá)到的點(diǎn)和當(dāng)前狀態(tài)。

參考資料

• 軟件測(cè)試精品書(shū)籍文檔下載持續(xù)更新 https://github.com/china-testing/python-testing-examples 請(qǐng)點(diǎn)贊，謝謝！
• 本文涉及的python測(cè)試開(kāi)發(fā)庫(kù) 謝謝點(diǎn)贊！ https://github.com/china-testing/python_cn_resouce
• python精品書(shū)籍下載 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
• Linux精品書(shū)籍下載 https://www.cnblogs.com/testing-/p/17438558.html

4.4.4 實(shí)驗(yàn)

圖 4.11顯示了不同監(jiān)控場(chǎng)景下的性能測(cè)量結(jié)果與多線程記錄開(kāi)銷的比較。

我們測(cè)量了使用GDB監(jiān)控相應(yīng)軟件所有方法中的2%、5%和10%（代表在線監(jiān)控或日志監(jiān)控模式）時(shí)的運(yùn)行時(shí)間。受監(jiān)控的方法可與上一節(jié)中介紹的并行運(yùn)行狀態(tài)機(jī)進(jìn)行比較。我們隨機(jī)選取了一定比例（2%、5% 或 10%）的方法，并在這些方法上設(shè)置了斷點(diǎn)。我們還測(cè)量了執(zhí)行多線程記錄方法（標(biāo)記為 Record）的運(yùn)行時(shí)間。我們使用了與第4.3節(jié)中相同的四種場(chǎng)景："飛行"和"射擊"。我們使用了與第4.3節(jié)中相同的四個(gè)場(chǎng)景：有5或10條生命的飛行射擊游戲，以及有60或165張視頻圖片的行人識(shí)別。在所有場(chǎng)景中2%的監(jiān)測(cè)方法比記錄方法更快。5%的方法的監(jiān)控速度慢于記錄速度，尤其是在游戲場(chǎng)景中。在監(jiān)控10%的方法時(shí)，錄制場(chǎng)景的執(zhí)行時(shí)間平均比運(yùn)行時(shí)間快2.45 倍。不過(guò)，方法監(jiān)控的性能主要取決于每個(gè)方法在執(zhí)行過(guò)程中出現(xiàn)的頻率。表4.5顯示了記錄場(chǎng)景和每個(gè)方法監(jiān)控場(chǎng)景（2、5 和 10%）的 GDB 停頓次數(shù)。

表 4.5 記錄和方法監(jiān)控的GDB操作次數(shù)

暫停次數(shù)越多，記錄或監(jiān)控時(shí)間就越長(zhǎng)。然而，與監(jiān)控方案相比，記錄方案的暫停次數(shù)較少，運(yùn)行時(shí)開(kāi)銷比例卻較高。造成這一結(jié)果的原因是，為實(shí)現(xiàn)記錄，每次斷點(diǎn)暫停都需要更多的GDB命令。此外，我們還測(cè)試了對(duì)15%的行人識(shí)別方法進(jìn)行監(jiān)控，但第一張圖片的監(jiān)控在10分鐘后仍未完成。

4.5 根本原因分析

在上一節(jié)中，我們展示了如何通過(guò)將執(zhí)行的操作與規(guī)范屬性進(jìn)行比較來(lái)檢測(cè)錯(cuò)誤的操作序列。錯(cuò)誤序列觸發(fā)了錯(cuò)誤，導(dǎo)致程序崩潰。然而，在許多情況下，并不存在正確或完整的操作規(guī)范。通常就是這種情況，因?yàn)橐?guī)范屬性往往已經(jīng)指出了潛在的故障，可以手動(dòng)修復(fù)。在本節(jié)中，我們將考慮語(yǔ)義錯(cuò)誤（在沒(méi)有規(guī)范的軟件中），即錯(cuò)誤的根源在于數(shù)值處理或程序邏輯。我們將介紹一些概念，用于檢測(cè)處理過(guò)程中錯(cuò)誤或缺失的方法調(diào)用，并確定相應(yīng)錯(cuò)誤邏輯的根本原因。

4.5.1 技術(shù)現(xiàn)狀

本節(jié)介紹了非崩潰錯(cuò)誤定位和嵌入式軟件監(jiān)控領(lǐng)域的最新技術(shù)。

4.5.1.1 Delta調(diào)試

《程序?yàn)楹螘?huì)失敗》一書(shū)介紹了軟件故障定位的不同概念。書(shū)中介紹了幾個(gè)動(dòng)態(tài)分析概念，包括三角調(diào)試和異常檢測(cè)。其中一些概念在我們的工作中也有類似的考慮，例如我們的delta計(jì)算方法。后來(lái)Burger和Zeller的工作開(kāi)發(fā)了用于定位非崩潰錯(cuò)誤的動(dòng)態(tài)切片。他們采用了多個(gè)步驟，通過(guò)回溯執(zhí)行過(guò)程中的錯(cuò)誤來(lái)隔離故障位置。然而delta調(diào)試基于對(duì)程序的實(shí)驗(yàn)，以自動(dòng)生成通過(guò)運(yùn)行和失敗運(yùn)行，這在嵌入式環(huán)境下是困難的，且耗費(fèi)運(yùn)行時(shí)間。

4.5.1.2 非崩潰錯(cuò)誤的動(dòng)態(tài)驗(yàn)證

Zhang 等人提出了一種檢測(cè)錯(cuò)誤配置導(dǎo)致的非崩潰錯(cuò)誤的方法。它剖析了失敗配置和非失敗配置的執(zhí)行情況。許多嵌入式軟件甚至不需要配置，錯(cuò)誤可以在源代碼中找到。Liu等人應(yīng)用支持向量機(jī)對(duì)非崩潰錯(cuò)誤的通過(guò)運(yùn)行和失敗運(yùn)行進(jìn)行分類。他們的方法在方法級(jí)別上生成行為圖，以比較不同的運(yùn)行。為了進(jìn)行分類，需要大量的輸入運(yùn)行，而且只能檢測(cè)到可疑的方法（而不是相關(guān)的源代碼行）。Abreu使用基于頻譜的覆蓋率分析實(shí)現(xiàn)了嵌入式軟件的故障定位。他們應(yīng)用基于模型的診斷來(lái)改進(jìn)分析結(jié)果。與Tarantula類似，他們將每個(gè)失敗運(yùn)行的執(zhí)行語(yǔ)句覆蓋率與通過(guò)運(yùn)行的語(yǔ)句覆蓋率進(jìn)行比較。他們假定失敗運(yùn)行和通過(guò)運(yùn)行的測(cè)試用例集都是可用的。然而，所有方法都需要一組失敗運(yùn)行，用于分類。在我們的系統(tǒng)測(cè)試用例中，沒(méi)有大量的非失敗運(yùn)行和失敗運(yùn)行可用于分類。

4.5.1.3 監(jiān)控嵌入式軟件

為實(shí)現(xiàn)故障定位，必須對(duì)軟件進(jìn)行監(jiān)控。Amiar等人使用特殊的跟蹤硬件來(lái)監(jiān)控嵌入式軟件。他們?cè)趩蝹€(gè)跟蹤上應(yīng)用基于頻譜的覆蓋分析。當(dāng)檢測(cè)到一個(gè)故障周期時(shí)，將其與之前的類似周期進(jìn)行比較，以檢測(cè)基于頻譜的覆蓋范圍脫差。不過(guò)，它們假設(shè)有適用于特定嵌入式平臺(tái)的跟蹤硬件。這種硬件通常價(jià)格昂貴。有幾種運(yùn)行時(shí)驗(yàn)證方法使用 GNU 調(diào)試器 (GDB)的廉價(jià)調(diào)試器接口來(lái)實(shí)現(xiàn)平臺(tái)兼容性，但它們沒(méi)有提出在沒(méi)有規(guī)范的情況下檢測(cè)錯(cuò)誤的概念。FLOMA使用概率采樣對(duì)軟件進(jìn)行細(xì)粒度觀察，但并不監(jiān)控每一行源代碼。它會(huì)隨機(jī)決定是否監(jiān)控特定的執(zhí)行步驟。不過(guò)，概率采樣可能會(huì)遺漏重要步驟，而且FLOMA需要對(duì)源代碼進(jìn)行工具化。Zuo等人提出了一種分層監(jiān)控方法來(lái)加速監(jiān)控。他們的方法利用軟件來(lái)監(jiān)控和分析方法調(diào)用序列。之后，只在源代碼行級(jí)監(jiān)控可疑部分。通過(guò)這種方法，可以加快監(jiān)控速度。我們的方法擴(kuò)展了這一方法，并將其應(yīng)用于調(diào)試器工具。

4.5.2 理論和概念

我們對(duì)故障回放進(jìn)行根本原因分析，自動(dòng)檢測(cè)出可能是故障根本原因的可疑源代碼行。分析結(jié)果將形成一份報(bào)告，為開(kāi)發(fā)人員提示錯(cuò)誤在源代碼中的位置。下面，我們將介紹一個(gè)基于故障重放和非故障重放的工作流程。我們將軟件的執(zhí)行分成幾個(gè)部分（見(jiàn)第4.5.2.1節(jié)）。一個(gè)分區(qū)的多個(gè)執(zhí)行過(guò)程存在重疊，可以進(jìn)行比較。一個(gè)分區(qū)的每次執(zhí)行稱為一次運(yùn)行。之后，必須檢測(cè)重放中執(zhí)行故障的運(yùn)行（見(jiàn)第4.5.2.2節(jié)）。重放中的故障運(yùn)行將與重放中類似且未被歸類為故障運(yùn)行的多個(gè)運(yùn)行進(jìn)行比較（見(jiàn)第4.5.2.3節(jié)）。為了將失敗運(yùn)行與類似運(yùn)行進(jìn)行比較，我們對(duì)源代碼行進(jìn)行了細(xì)粒度分析，目的是檢測(cè)出存在錯(cuò)誤的源代碼行。我們展示了覆蓋率分析和不變量生成分析的指標(biāo)（見(jiàn)第 4.5.2.4節(jié)）。然而，使用廉價(jià)的調(diào)試器接口進(jìn)行細(xì)粒度監(jiān)控可能會(huì)非常緩慢。因此，我們?cè)诘?4.5.2.5 節(jié)中介紹了一種加速方法。4.5.2.5.我們用開(kāi)源導(dǎo)航軟件Navit中的一個(gè)非崩潰錯(cuò)誤來(lái)舉例說(shuō)明我們自己的方法。如果Navit接收到的GPS傳感器數(shù)據(jù)角度小于 -360，車輛指針將在短時(shí)間內(nèi)無(wú)法繪制。例如，在繁忙的街道上尋找正確的十字路口時(shí)，這個(gè)錯(cuò)誤可能會(huì)干擾駕駛員。這個(gè)錯(cuò)誤不會(huì)產(chǎn)生異常。只是在圖形用戶界面中可以短暫觀察到。這是由于處理了錯(cuò)誤的傳感器數(shù)據(jù)（傳感器發(fā)送的角度值為<-360造成的。當(dāng)軟件與傳感器硬件輸出不兼容時(shí)，就會(huì)出現(xiàn)這種情況。該錯(cuò)誤由Navit軟件中的錯(cuò)誤計(jì)算引起（見(jiàn)下文）。

4.5.2.1 分區(qū)重放

異常檢測(cè)領(lǐng)域的最新方法提供了通過(guò)比較被測(cè)軟件的非失敗運(yùn)行和失敗運(yùn)行來(lái)檢測(cè)根本原因的概念。然而，復(fù)雜嵌入式軟件的執(zhí)行可能包含執(zhí)行不同功能的部分。對(duì)不同功能進(jìn)行比較可能會(huì)導(dǎo)致許多誤報(bào)，尤其是在只有一小部分參考運(yùn)行時(shí)。在我們的方法中，我們將嵌入式軟件的執(zhí)行分成幾個(gè)可比較的部分（執(zhí)行類似的功能）。嵌入式軟件通常會(huì)處理傳感器數(shù)據(jù)以更新程序狀態(tài)。每次執(zhí)行時(shí)的處理過(guò)程通常非常相似。圖 4.12舉例說(shuō)明了Navit的重放概念。Navit重放包含不同類型的處理，例如GPS處理、觸摸屏輸入處理或交通數(shù)據(jù)處理。

從傳感器硬件（在第 4.3 節(jié)中定義為接收點(diǎn)）讀取數(shù)據(jù)后，即開(kāi)始處理傳感器數(shù)據(jù)。處理過(guò)程由以下元組表示：

Processing = (Start, Run, End)

Start和End表示執(zhí)行過(guò)程中傳遞的源代碼行數(shù)。Start是執(zhí)行過(guò)程中系統(tǒng)開(kāi)始處理傳感器數(shù)據(jù)的位置。End是執(zhí)行過(guò)程中傳感器數(shù)據(jù)處理結(jié)束的位置。處理運(yùn)行包括傳感器數(shù)據(jù)處理過(guò)程中的所有操作Ops和方法調(diào)用M的列表：

Run = (M,Ops)

和

在我們的方法中，執(zhí)行會(huì)在開(kāi)始時(shí)中斷。從這個(gè)斷點(diǎn)開(kāi)始，處理過(guò)程會(huì)在方法或源代碼行級(jí)別上被觀察到。

4.5.2.2 檢測(cè)故障運(yùn)行

軟件分區(qū)的每次執(zhí)行都被視為一次重放運(yùn)行。在運(yùn)行故障回放時(shí)，特定傳感器處理的一次或多次運(yùn)行會(huì)導(dǎo)致觀察到的故障。我們提出了一個(gè)輕量級(jí)概念，用于檢測(cè)回放中的故障運(yùn)行。它將與非故障重放中的運(yùn)行差異最大的運(yùn)行分類為故障運(yùn)行（如下所述）。重放的每個(gè)運(yùn)行都可以與其他運(yùn)行進(jìn)行比較，因?yàn)闀?huì)執(zhí)行類似的操作和方法。運(yùn)行中的差異可能指向故障。要檢測(cè)故障運(yùn)行，我們的方法需要進(jìn)行兩次重放。一個(gè)是導(dǎo)致故障的重放，另一個(gè)是不會(huì)導(dǎo)致故障的重放。出現(xiàn)故障的重放運(yùn)行可與未出現(xiàn)故障的重放運(yùn)行進(jìn)行比較?？梢酝ㄟ^(guò)檢查一次運(yùn)行覆蓋了哪些源代碼行或方法來(lái)比較兩次運(yùn)行。如第4.5.2.5節(jié)，在此階段考慮方法的覆蓋范圍更為有效。

表 4.6 顯示了示例矩陣（代表 Navit Bug），其中包含重放的每次運(yùn)行的方法覆蓋率（就像為跟蹤提出的那樣）。

可調(diào)用方法在行中表示。運(yùn)行用列表示。單元格中的值1表示該行中的方法由相應(yīng)列中的運(yùn)行執(zhí)行。可以使用漢明距離（hamming distance）比較兩個(gè)運(yùn)行的差異，即計(jì)算兩列運(yùn)行在行中的差異。在我們的例子中：distance(Run1,Run7)=2,distance(Run2,Run7)=3, distance(Run3,Run7)=3。為了簡(jiǎn)單明了，我們考慮了一些偽方法m1-m4和繪制方法。

利用上述矩陣和漢明距離，通過(guò)比較故障重放中的每個(gè)運(yùn)行和非故障重放中的每個(gè)運(yùn)行來(lái)檢測(cè)故障。故障重放中與非故障重放中所有運(yùn)行不相似（或差異最大）的運(yùn)行被視為故障運(yùn)行。圖4.13顯示了故障重放中的運(yùn)行7與非故障重放中的每個(gè)運(yùn)行的比較情況。Run7與非失敗運(yùn)行的差異最大，因?yàn)槿鄙倭藢?duì)車輛指針的繪制方法的調(diào)用。每種方法的出現(xiàn)次數(shù)也可以與漢明距離相結(jié)合。這樣，如果一個(gè)運(yùn)行比另一個(gè)運(yùn)行執(zhí)行了更多的方法，那么兩個(gè)運(yùn)行中的一個(gè)方法就可以被歸類為不同的方法。還可以考慮調(diào)用序列。不過(guò)，方法覆蓋率的監(jiān)控速度要快于源代碼行覆蓋率（見(jiàn)第4.5.4節(jié)）。此外，還可以將若干次運(yùn)行歸類為失敗運(yùn)行。例如，可以將與非失敗重放的運(yùn)行相比出現(xiàn)20%差異的運(yùn)行歸類為失敗運(yùn)行。不過(guò)，以下解釋以一次失敗運(yùn)行為基礎(chǔ)。注：如果多個(gè)運(yùn)行排序的距離相同，則選擇最近的運(yùn)行（因?yàn)轭A(yù)計(jì)錯(cuò)誤將出現(xiàn)在重放的末尾）。

圖 4.13 檢測(cè)故障運(yùn)行

在這里，故障重放中的運(yùn)行7與非故障重放中的所有其他運(yùn)行差別最大。這意味著Run5、Run6和Run8在非故障重放中都有相應(yīng)的運(yùn)行，其漢明距離小于 Run7 與非故障重放中各運(yùn)行的漢明距離。

4.5.2.3 檢測(cè)相似運(yùn)行

在上一節(jié)中，我們介紹了檢測(cè)故障運(yùn)行的概念。通過(guò)將故障運(yùn)行與無(wú)故障運(yùn)行進(jìn)行比較，可以檢測(cè)出異常。因此，我們的方法會(huì)在故障回放中檢測(cè)與故障運(yùn)行相似但未被歸類為故障運(yùn)行的若干運(yùn)行，即使用漢明距離檢測(cè)與故障運(yùn)行具有相似方法覆蓋范圍的運(yùn)行。圖4.14顯示了失敗重放。在本例中，與失敗運(yùn)行 Run7 最相似的運(yùn)行是 Run5。這樣，故障運(yùn)行就會(huì)與其最相似的運(yùn)行進(jìn)行詳細(xì)比較。這一概念基于近鄰模型，該模型同樣適用于跟蹤硬件的日志文件。我們的方法是在發(fā)生故障運(yùn)行的同一重放中檢測(cè)類似運(yùn)行，這些類似運(yùn)行是在與故障運(yùn)行相同的上下文（例如，考慮配置上下文）下執(zhí)行的。

圖 4.14 檢測(cè)類似運(yùn)行
在測(cè)試中，我們檢測(cè)到三個(gè)運(yùn)行與故障運(yùn)行相似。我們將使用delta分析法對(duì)這些運(yùn)行和故障運(yùn)行進(jìn)行詳細(xì)比較。

4.5.2.4 Delta計(jì)算

對(duì)故障運(yùn)行和類似運(yùn)行進(jìn)行詳細(xì)比較，以檢測(cè)可指向故障根源的Delta。將類似運(yùn)行與故障重放中的故障運(yùn)行進(jìn)行比較時(shí)，可采用不同的指標(biāo)來(lái)識(shí)別可疑源代碼行。我們以Navit Bug為例，介紹Delta分析的概念和指標(biāo)。
Navit bug基于GPS處理中的錯(cuò)誤計(jì)算（偽代碼見(jiàn)清單 7）。如果角度小于0，第2行中的角度值會(huì)加上360。但是，如果角度小于-360，則角度在第2行后保持負(fù)值，第5+6行被跳過(guò)，并且不會(huì)繪制車輛指針。在正確的執(zhí)行過(guò)程中，應(yīng)該對(duì)角度計(jì)算進(jìn)行數(shù)學(xué)調(diào)制運(yùn)算，以產(chǎn)生一個(gè)正值。第5行和參數(shù)變量lazy將在下一節(jié)中解釋。

在我們的示例中，以下對(duì)vehicle_update方法的GPS輸入序列觸發(fā)了錯(cuò)誤（...{42, 9, 40, 0}，{42, 9, 55, 0}，{42, 9, -370, 0}，{42, 9, 70, 0}）。這里第三輸入端發(fā)送錯(cuò)誤的角度數(shù)據(jù)，例如來(lái)自傳感器設(shè)備的數(shù)據(jù)。

我們采用故障定位度量來(lái)檢測(cè)故障重放中此類錯(cuò)誤的根本原因（在本例中，第2行中的錯(cuò)誤計(jì)算）。我們用三個(gè)系數(shù)來(lái)定義這些指標(biāo)，每個(gè)可執(zhí)行源代碼行都會(huì)生成這三個(gè)系數(shù)。這些系數(shù)用于計(jì)算滿足特定源代碼行op的特定特征的運(yùn)行次數(shù)。這些特征定義了導(dǎo)致故障或未導(dǎo)致故障的運(yùn)行次數(shù)。它們還定義了是否涵蓋特定源代碼行操作。

Tarantula、Jaccard 和 Occhiai 等人給出了常用的故障定位指標(biāo)。這些指標(biāo)定義如下：

Tarantula衡量失敗運(yùn)行主要執(zhí)行哪些行。這些行被認(rèn)為更有可能是失敗的根本原因。如果許多非故障運(yùn)行也執(zhí)行了該行，則其可疑程度會(huì)降低。Jaccard 系數(shù)也是基于e_f，但當(dāng)許多非失敗運(yùn)行執(zhí)行了該行或許多失敗運(yùn)行未執(zhí)行該行時(shí)，可疑排名會(huì)降低。Occhiai還對(duì) $$e_p$ 和 n_f之間的差值進(jìn)行了加權(quán)。因此，當(dāng)許多非失敗運(yùn)行同時(shí)執(zhí)行該行，而許多失敗運(yùn)行同時(shí)不執(zhí)行該行時(shí)，排名就會(huì)降低。前面介紹的指標(biāo)主要考慮的是哪些源代碼行經(jīng)常出現(xiàn)在失敗運(yùn)行中。然而，在嵌入式軟件出現(xiàn)非崩潰錯(cuò)誤時(shí)，錯(cuò)誤的原因可能是缺少對(duì)操作系統(tǒng) SDK 庫(kù)的調(diào)用。此外，失敗運(yùn)行中遺漏的源代碼行可能指向錯(cuò)誤的條件邏輯評(píng)估。將失敗運(yùn)行中的遺漏代碼與非失敗運(yùn)行中的遺漏代碼進(jìn)行比較，可以發(fā)現(xiàn)失敗的原因。因此，我們認(rèn)為有必要對(duì)失敗運(yùn)行中的缺失特征進(jìn)行排序。AMPLE 指標(biāo)（4.9）也考慮了失敗運(yùn)行中的缺失特征。

表 4.7顯示了Navit錯(cuò)誤示例（見(jiàn)清單 7）中三個(gè)相似運(yùn)行RunSim和一個(gè)失敗運(yùn)行RunFail的不同度量結(jié)果。得出的系數(shù)越高，相應(yīng)源代碼行的可疑度就越高。我們發(fā)現(xiàn)，每個(gè)指標(biāo)都將索引為2的操作列為可疑操作。然而，盡管AMPLE將另外指向錯(cuò)誤條件情況的操作5和6列為可疑操作，但卻未將其列為可疑操作。

表 4.7 按示例計(jì)算指標(biāo)

在大多數(shù)故障定位方法中，度量指標(biāo)會(huì)產(chǎn)生一個(gè)源代碼行列表，并根據(jù)其可疑程度進(jìn)行排序。然而，要根據(jù)該列表對(duì)源代碼進(jìn)行人工評(píng)估是很困難的。在我們的使用案例中，我們的工具會(huì)在重放過(guò)程中在最可疑的源代碼行上設(shè)置斷點(diǎn)。開(kāi)發(fā)人員可以在重放過(guò)程中逐步查看可疑行，并檢查哪些行在失敗運(yùn)行和非失敗運(yùn)行中被執(zhí)行。我們的工具只在AMPLE可疑度排名為1的源代碼行上設(shè)置斷點(diǎn)。此外，它還會(huì)在每一行可疑源代碼上注明，該行是否在故障運(yùn)行中被執(zhí)行（但未在任何類似運(yùn)行中執(zhí)行），或是否在每個(gè)類似運(yùn)行中被執(zhí)行（但未在故障運(yùn)行中執(zhí)行）。還有一些方法提出了可疑度量的組合，例如將AMPLE和Occhiai結(jié)合起來(lái)。這樣，機(jī)器學(xué)習(xí)算法就會(huì)生成不同指標(biāo)的加權(quán)組合。研究表明，使用組合指標(biāo)可以獲得更好的指標(biāo)結(jié)果。不過(guò)，這需要一個(gè)學(xué)習(xí)階段，而在我們的使用案例中這是不可能的。

之前，我們展示了delta計(jì)算如何能夠顯示故障重放中的故障運(yùn)行與重放中一些類似運(yùn)行之間的覆蓋率差異。然而，只有通過(guò)監(jiān)控每一行源代碼中的所有變量值，才能發(fā)現(xiàn)從錯(cuò)誤的變量賦值開(kāi)始傳播的根本原因。

在我們的示例中，GPS 輸入的另一個(gè)序列也可能觸發(fā)錯(cuò)誤：（{42, 9, 340, 0}，{42, 9, -355, 0}，{42, 9, -370, 0}，{42, 9, -355, 0}）。當(dāng)傳感器發(fā)送小于0的數(shù)據(jù)并逐步切換到小于-360的角度時(shí)，就會(huì)出現(xiàn)這種序列。在此序列的重放過(guò)程中應(yīng)用基于覆蓋率的分析，無(wú)法檢測(cè)到錯(cuò)誤的源代碼行（清單7中的第2行），因?yàn)榈?行在每次運(yùn)行中都會(huì)被執(zhí)行。但是，如果監(jiān)控每行源代碼中的所有變量值，就可以檢測(cè)到根本原因。

變量值中的異常情況可以使用不變量來(lái)檢測(cè)。不變式是為每次運(yùn)行存儲(chǔ)的變量/值對(duì)的特征。非故障運(yùn)行所持有的不變式可與故障運(yùn)行所存儲(chǔ)的不變式進(jìn)行比較。因此，我們會(huì)自動(dòng)為非失敗運(yùn)行和失敗運(yùn)行生成不變式。范圍不變式檢查在運(yùn)行期間觀察到的變量值的范圍。在我們的 Navit例子中，公式 (4.10) 中的不變式存儲(chǔ)在每次非失敗運(yùn)行中。該不變量可在失敗運(yùn)行中進(jìn)行檢查，因?yàn)樵谑∵\(yùn)行中該不變量被違反。在我們的實(shí)現(xiàn)中，我們?yōu)槊恳恍型ㄟ^(guò)的源代碼生成不變式。

然而，由于參考運(yùn)行較少，很難建立范圍不變式。變量/值對(duì)之間的關(guān)系不變式檢查兩個(gè)數(shù)值變量之間的關(guān)系。變量關(guān)系通常在條件分支中進(jìn)行檢查。這種關(guān)系可能是變量角度總是大于特定源行中的變量懶惰值（4.11）。

我們的分析將每個(gè)變量值與所有其他變量值進(jìn)行比較，以檢測(cè)變量之間的關(guān)系。在Navit示例中，調(diào)用vehicle_update方法時(shí)總是使用第四個(gè)變量lazy，它定義了繪制模式，在大多數(shù)情況下為0或1。將變量angle與變量lazy比較，可以發(fā)現(xiàn)在操作2之前，angle<lazy。在操作2 之后，每次非故障運(yùn)行都滿足 lazy<angle。但是，對(duì)于失敗運(yùn)行，angle<(lazy==0)仍然成立。圖 4.15 顯示了變量 angle 和 lazy 之間的變量關(guān)系序列。

圖4.15檢測(cè)兩個(gè) Navit GPS 處理之間的不變量Delta

在圖4.15中，故障運(yùn)行中第3行和第4行的錯(cuò)誤關(guān)系正好指向故障的根本原因。由此產(chǎn)生的分析報(bào)告包括通過(guò)比較故障運(yùn)行與類似運(yùn)行的覆蓋范圍而發(fā)現(xiàn)的異常。此外，報(bào)告還包括生成的關(guān)系不變式，這些關(guān)系不變式在故障運(yùn)行和類似運(yùn)行之間存在差異。

4.5.2.5 加速監(jiān)控

許多方法使用特殊硬件來(lái)監(jiān)控被測(cè)嵌入式軟件。然而，這種硬件可能很昂貴，甚至無(wú)法用于新平臺(tái)。因此，我們提出了一種如何優(yōu)化監(jiān)控以實(shí)現(xiàn)快速動(dòng)態(tài)驗(yàn)證結(jié)果的方法。大多數(shù)開(kāi)發(fā)人員已經(jīng)使用增量方法手動(dòng)調(diào)試軟件。他們首先在方法上設(shè)置斷點(diǎn)，開(kāi)始檢測(cè)方法調(diào)用序列中的異常。然后，他們檢查可疑方法，并逐步完善檢查。我們的工具通過(guò)自動(dòng)應(yīng)用這一概念，實(shí)現(xiàn)了對(duì)錯(cuò)誤根源分析的加速監(jiān)控。首先，我們定義了單級(jí)監(jiān)控（SL）的基本概念。

單級(jí)監(jiān)控-SL：在（處理）運(yùn)行過(guò)程中，對(duì)每行已執(zhí)行的源代碼進(jìn)行單步監(jiān)控。它監(jiān)控每個(gè)被監(jiān)控源代碼行的當(dāng)前變量值。
上一節(jié)介紹的分析可應(yīng)用于 SL 監(jiān)控生成的跟蹤。不過(guò)，運(yùn)行單級(jí)監(jiān)控可能會(huì)比較慢。軟件方法的執(zhí)行頻率通常遠(yuǎn)低于源代碼行。因此，監(jiān)控方法通常比監(jiān)控每一行源代碼更快。

多層次監(jiān)控 -ML：在第一次重放中，對(duì)方法調(diào)用進(jìn)行監(jiān)控。在此方法調(diào)用跟蹤中可應(yīng)用以下活動(dòng)： 檢測(cè)故障運(yùn)行和檢測(cè)類似運(yùn)行。在第二次重放中，通過(guò)單步監(jiān)控詳細(xì)監(jiān)控故障運(yùn)行和類似運(yùn)行。Delta計(jì)算可應(yīng)用于生成的跟蹤。這樣，所有運(yùn)行（盡管有故障）和類似運(yùn)行都無(wú)需詳細(xì)監(jiān)控。
圖 4.16舉例說(shuō)明了這一概念。圖中顯示了兩個(gè)重放：一個(gè)用于方法級(jí)監(jiān)控，另一個(gè)用于通過(guò)單步詳細(xì)監(jiān)控相關(guān)運(yùn)行。在方法層面，首先將故障運(yùn)行與非故障重放進(jìn)行比較，從而檢測(cè)到故障運(yùn)行 (A.)，如第 4.5.2.2節(jié)所述。圖 4.16 中的故障運(yùn)行是運(yùn)行7。然后，在方法層 (B.) 上識(shí)別出與失敗運(yùn)行類似的運(yùn)行，如第4.5.2.3節(jié)所述。里的相似運(yùn)行是Run5。不過(guò)，我們的方法可以檢測(cè)并處理多個(gè)類似運(yùn)行。失敗運(yùn)行與類似運(yùn)行（Run5和Run7）之間的區(qū)別是通過(guò)單步監(jiān)控（與SL相同）和分析每一行源代碼來(lái)實(shí)現(xiàn)的，如第4.5.2.4節(jié)所述。因此，在本示例中，不對(duì) Run6 和 Run8 進(jìn)行詳細(xì)監(jiān)控。

然而，每次方法通過(guò)時(shí)暫停也會(huì)導(dǎo)致較長(zhǎng)的監(jiān)控時(shí)間（如第4.5.4節(jié)所述），尤其是在高頻率調(diào)用短方法時(shí)。因此，在下文中，我們提出了一種基于調(diào)試器的高效監(jiān)控運(yùn)行方法覆蓋率的概念。

ML方法監(jiān)控-MLMethd： 方法覆蓋率監(jiān)控只跟蹤一次運(yùn)行中每個(gè)已執(zhí)行的方法。
算法1以偽代碼的形式展示了 MLMethd 的概念。通過(guò)這種方式，方法覆蓋率的監(jiān)控是高效的，因?yàn)楸O(jiān)控工具只需對(duì)每個(gè)方法跟蹤一次。

然而，在檢測(cè)到故障運(yùn)行并計(jì)算出類似運(yùn)行后，Delta計(jì)算步驟需要進(jìn)行細(xì)粒度跟蹤。對(duì)該軌跡的監(jiān)控可能非常緩慢。逐步細(xì)化可以加快監(jiān)控速度。MLMethd會(huì)產(chǎn)生一個(gè)可疑方法（relmethds）列表，這些方法會(huì)在失敗運(yùn)行或類似運(yùn)行中執(zhí)行。

ML 回溯監(jiān)控-MLBack： 識(shí)別 relmethds 中方法的回溯。首先對(duì)這些回溯中出現(xiàn)的每個(gè)方法進(jìn)行監(jiān)控，而不介入被調(diào)用的方法（邊步驟）。在類似運(yùn)行或失敗運(yùn)行中執(zhí)行的方法不會(huì)受到監(jiān)控（無(wú)法進(jìn)行比較）。MLBack 包括 MLMethd。
在 Navit 示例中，我們考慮了五種不同的方法：

• update：根據(jù) GPS 輸入數(shù)據(jù)更新當(dāng)前車輛狀態(tài)。
• route： 代表路線計(jì)算。
• vehi： 代表車輛繪制方法。
• set： 更改繪制模式。
• draw： 調(diào)用繪制車輛指針。
  圖 4.17 展示了 Navit bug 的 MLBack 概念。每條黑線（或?qū)嵕€）代表一個(gè)受監(jiān)控的方法。每條紅線（或虛線）代表一個(gè)未監(jiān)控的方法。
  

圖 4.17 多級(jí)回溯 (MLBack) 監(jiān)控

首先，重放會(huì)監(jiān)控方法覆蓋范圍，并檢測(cè)到失敗運(yùn)行中的繪制方法未命中。根據(jù)方法監(jiān)控，檢測(cè)出與失敗運(yùn)行類似的幾個(gè)運(yùn)行。在MLBack 期間，在非失敗運(yùn)行中調(diào)用 draw 的回溯中出現(xiàn)的方法被收集到relmethds中。在第二次重放過(guò)程中relmethds中的方法會(huì)在相似運(yùn)行和失敗運(yùn)行中受到監(jiān)控，但不會(huì)步入被調(diào)用（或側(cè)步）的方法。在步入這些方法的過(guò)程中，會(huì)對(duì)局部變量和方法參數(shù)變量的值進(jìn)行監(jiān)控。MLBack 的結(jié)果是包含異常suspectmethd 的方法列表。方法update和vehi.在不進(jìn)入邊步驟（此處為路由和設(shè)置）的情況下受到監(jiān)控。這樣，與我們考慮的錯(cuò)誤無(wú)關(guān)但需要大量操作的路由計(jì)算就不會(huì)受到監(jiān)控。此外，不監(jiān)控繪制，因?yàn)樗怀霈F(xiàn)在相似運(yùn)行中，而不出現(xiàn)在故障運(yùn)行中（無(wú)法比較）。在vehi中計(jì)算angle+=360后，可以檢測(cè)到變量值的第一次異常。

定義ML步驟監(jiān)控-MLStep： 此監(jiān)控概念將可疑方法列表suspectmethd作為輸入。這些方法會(huì)在額外的重放中受到監(jiān)控，并被稱為邊步驟。在類似運(yùn)行或失敗運(yùn)行中執(zhí)行的方法仍不會(huì)受到監(jiān)控。
在Navit示例中，執(zhí)行了第三次重放以額外監(jiān)控可疑方法中的邊步驟（見(jiàn)圖 4.18）。

圖 4.18 多級(jí)步驟 (MLStep) 監(jiān)控

在這里，還通過(guò)側(cè)步驟對(duì)方法車輛進(jìn)行監(jiān)控。這包括步入方法集（以及圖 4.18 中未顯示的一些其他方法）。在Navit的另一種實(shí)現(xiàn)中，方法集（或由 vehi.調(diào)用的另一個(gè)方法）可能包括 $$angle+=360$$ 的錯(cuò)誤源代碼行，之后角度和懶惰之間的錯(cuò)誤關(guān)系會(huì)被檢測(cè)到。

4.5.3 執(zhí)行

本節(jié)介紹如何通過(guò)單步跳過(guò)每一行源代碼來(lái)監(jiān)控回放中的一組運(yùn)行（單步監(jiān)控）。在源代碼層面，對(duì)運(yùn)行中執(zhí)行的每一行源代碼的變量值進(jìn)行監(jiān)控。在第二次重放中，SL和ML都需要這種實(shí)現(xiàn)方式。我們將展示如何實(shí)現(xiàn)方法級(jí)監(jiān)控（方法覆蓋監(jiān)控）。在方法層面，運(yùn)行中已執(zhí)行方法的覆蓋率受到監(jiān)控。此外，我們還展示了如何使用GDB Python腳本實(shí)現(xiàn)MLBack和MLStep。

4.5.3.1 單步監(jiān)控

清單8顯示了Navit示例的單步監(jiān)控實(shí)現(xiàn)（考慮到GPS處理）。第 1-2行在源代碼中GPS處理開(kāi)始和結(jié)束的位置設(shè)置斷點(diǎn)。如果到達(dá)處理開(kāi)始的位置（第7行），則激活監(jiān)控（第8行）。如果激活了監(jiān)控，則會(huì)通過(guò)打印局部變量和參數(shù)變量來(lái)監(jiān)控處理過(guò)程中的每一步（第13-14行）。通過(guò)執(zhí)行 GDB step命令（第16行）到達(dá)被測(cè)軟件的下一行源代碼。

4.5.3.2 方法覆蓋監(jiān)控

清單9顯示了 Navit示例方法覆蓋監(jiān)控的實(shí)現(xiàn)（考慮到GPS處理）。第 1-2行在源代碼中GPS處理開(kāi)始和結(jié)束的位置設(shè)置斷點(diǎn)。此外，在 Navit 軟件的每個(gè)方法上都設(shè)置了斷點(diǎn)（第5-6行）；它們?cè)趫?zhí)行開(kāi)始時(shí)被禁用（第7行）。如果到達(dá)處理開(kāi)始的位置（第10行），監(jiān)控將被激活（第11行），此外，Navit 軟件中每個(gè)方法的斷點(diǎn)也會(huì)被啟用（第12行）。如果只需監(jiān)控已執(zhí)行方法的覆蓋范圍，可在首次通過(guò)后禁用每個(gè)斷點(diǎn)（第 18-19 行）。

4.5.3.3 方法回溯監(jiān)控

清單10顯示了Navit示例（考慮到 GPS 處理）中方法回溯監(jiān)控的實(shí)現(xiàn)。第2-3行在先前方法監(jiān)控和分析報(bào)告的relmethds中的所有方法上設(shè)置斷點(diǎn)。使用GDB命令next（第14行）對(duì)這些方法進(jìn)行步進(jìn)，同時(shí)監(jiān)控變量值，而不步進(jìn)到被調(diào)用的方法（側(cè)步）。MLStep的實(shí)現(xiàn)與此類似，但它監(jiān)控的是MLBack分析所報(bào)告的方法。它使用GDB的命令步而不是命令下一步。

4.5.4 實(shí)驗(yàn)

前面幾節(jié)介紹了動(dòng)態(tài)驗(yàn)證如何幫助開(kāi)發(fā)人員分析錯(cuò)誤的根源。在第 4.5.2.5 節(jié)中，我們介紹了加速監(jiān)控這些分析的優(yōu)化技術(shù)。我們?cè)谖鏖T(mén)子測(cè)試套件的Replace工具中測(cè)試了多級(jí)監(jiān)控 (ML) 概念。Replace程序有32個(gè)不同版本，并包含多個(gè)測(cè)試用例。我們測(cè)試了前 20 個(gè)版本中的 19 個(gè)，它們都包含一個(gè)錯(cuò)誤（我們無(wú)法手動(dòng)檢測(cè)第 19 個(gè)版本中的錯(cuò)誤）。為了生成可能的隨機(jī)重放，我們實(shí)施了一個(gè)重放生成器，從西門(mén)子測(cè)試套件故障矩陣中的 5542 個(gè)測(cè)試用例中隨機(jī)選擇 99 個(gè)不會(huì)導(dǎo)致故障的測(cè)試用例。在重放的最后，我們添加了一個(gè)執(zhí)行錯(cuò)誤的失敗運(yùn)行作為運(yùn)行 100。為了隨機(jī)選擇測(cè)試用例，我們使用了 Python 隨機(jī)函數(shù)，每次生成的重放均使用 100 種子。我們生成了包含 200 個(gè)非失敗運(yùn)行的第二個(gè)重放，以模擬噪聲（使用相同的種子 100）。我們將此重放作為非故障重放，用于第 4.5.2.2 節(jié)中介紹的故障運(yùn)行檢測(cè)。4.5.2.2. 對(duì)于 SL，我們監(jiān)控了 100 次重放運(yùn)行的執(zhí)行情況，收集源代碼行覆蓋率以及局部變量和參數(shù)變量的數(shù)值。對(duì)于 ML，我們根據(jù)方法覆蓋率檢測(cè)失敗運(yùn)行。在此實(shí)施過(guò)程中，我們還使用了特定方法的出現(xiàn)次數(shù)來(lái)構(gòu)建 hamming 詞（如第 4.5.2.3 節(jié)所述，使用 threshold=5）。此外，還根據(jù)方法覆蓋率確定了與失敗運(yùn)行最相似的三個(gè)運(yùn)行。在第二次重放中，考慮到行覆蓋率和變量關(guān)系，對(duì)故障運(yùn)行和相似運(yùn)行進(jìn)行了監(jiān)測(cè)和比較。我們發(fā)現(xiàn)，ML 監(jiān)控比 SL 監(jiān)控要快得多。圖 4.19 顯示了單級(jí)（SL）監(jiān)控與多級(jí)（ML）監(jiān)控 Replace 的運(yùn)行時(shí)間對(duì)比（對(duì)于我們可以使用算法檢測(cè)到相應(yīng)錯(cuò)誤的版本）。

圖 4.19 對(duì)替換進(jìn)行多層次分析的監(jiān)控運(yùn)行時(shí)間
對(duì)于一般評(píng)估，只包括監(jiān)控運(yùn)行時(shí)間，因?yàn)榉治霰O(jiān)控結(jié)果的運(yùn)行時(shí)間取決于分析類型。ML包括方法級(jí)的第一次重放監(jiān)控和行級(jí)的第二次重放監(jiān)控。ML和SL監(jiān)控了失敗運(yùn)行和三個(gè)最相似運(yùn)行的delta計(jì)算的所有局部變量、參數(shù)和宏。我們發(fā)現(xiàn)，ML監(jiān)控比SL監(jiān)控快得多。對(duì)于Replace，監(jiān)控速度提高了varnothing 9.5倍。表4.8 顯示了SL和ML報(bào)告的可疑行數(shù)，以及不同Replace版本的失敗運(yùn)行與三個(gè)相似運(yùn)行之間的漢明距離。

delta-ML/SL示報(bào)告的可疑行計(jì)數(shù)。Fail Detect（失敗檢測(cè)）顯示是否能在方法層面上檢測(cè)到失敗運(yùn)行。Dist. Meth. Detect顯示是否通過(guò)覆蓋率delta計(jì)算或變量關(guān)系delta計(jì)算檢測(cè)到有問(wèn)題的線路。在6個(gè)版本（3、4、7、13、14、16）中，ML和SL檢測(cè)到的相似運(yùn)行是相同的。在這些情況下，報(bào)告的可疑行也是相同的。在15次實(shí)驗(yàn)中，SL和ML檢測(cè)到了該版本的所有錯(cuò)誤，這些錯(cuò)誤要么指向覆蓋率Delta (Cov)，要么指向變量關(guān)系Delta (Rel)。有四個(gè)錯(cuò)誤報(bào)告間接指向了失?。ǖ?12 版--關(guān)系三角中多次出現(xiàn) MAXPAT；第15版和第18版--錯(cuò)誤行中其他變量的關(guān)系差異；第14版--if-clause 封閉行中的關(guān)系差異）。我們用其他四個(gè)版本的Replace（2、9、10、11）測(cè)試了我們的工具，但在這些測(cè)試中，我們用ML和SL進(jìn)行的delta分析無(wú)法檢測(cè)到有錯(cuò)誤的源代碼行。在這里，錯(cuò)誤主要是由if子句中訪問(wèn)數(shù)組（僅在寄存器中可用）的謂詞引起的。Fail Detect一行顯示的是可以在方法級(jí)別檢測(cè)到失敗運(yùn)行的版本。在第4.5.2.2節(jié)中介紹的優(yōu)化輕量級(jí)分類中，第6、14 和18版無(wú)法檢測(cè)到失敗運(yùn)行。4.5.2.2節(jié)中介紹的優(yōu)化的輕量級(jí)分類方法無(wú)法檢測(cè)到第6、14 和18個(gè)版本的失敗運(yùn)行。因此，基于100次運(yùn)行的故障重放和200次運(yùn)行的非故障重放，63%的錯(cuò)誤可以通過(guò)ML自動(dòng)有效地定位。

在某些情況下，ML 的 delta 計(jì)算報(bào)告的誤報(bào)率較低，這是因?yàn)?SL 檢測(cè)到的相似運(yùn)行恰好造成了更多的變量關(guān)系差異?？偟膩?lái)說(shuō)，SL 和 ML 的報(bào)告質(zhì)量差異主要取決于重放中不同運(yùn)行的組成。注：SL 在失敗的運(yùn)行和重放中的每個(gè)運(yùn)行之間進(jìn)行Delta計(jì)算（cov+rel）會(huì)導(dǎo)致解析和比較監(jiān)控結(jié)果的運(yùn)行時(shí)間增加（Replace 在不監(jiān)控三個(gè)運(yùn)行的情況下進(jìn)行Delta計(jì)算的運(yùn)行時(shí)間為 $$\varnothing $$ 13.7 s）。
不過(guò)，對(duì)于指令密集型計(jì)算而言，ML 監(jiān)控仍然太慢。例如，對(duì) Navit 方法級(jí)路由計(jì)算（高頻率調(diào)用轉(zhuǎn)換方法）的監(jiān)控，在每次方法調(diào)用時(shí)暫停執(zhí)行，速度會(huì)非常慢。我們?cè)?NVIDIA Tegra K1 ARM 平臺(tái)上測(cè)量了包括路由計(jì)算在內(nèi)的 20 個(gè) GPS 坐標(biāo)處理的方法監(jiān)控，結(jié)果顯示需要 50 多小時(shí)。
圖
4.20顯示了我們使用 Navit 軟件（MLBack 和 MLStep）的細(xì)化功能加速監(jiān)控根源分析的實(shí)驗(yàn)。

我們測(cè)量了包含20個(gè)GPS坐標(biāo)的重放和包含30個(gè)GPS坐標(biāo)的重放，這兩個(gè)重放都包含前面章節(jié)中的Navit錯(cuò)誤。在這些實(shí)驗(yàn)中，每種分析（MLBack、MLStep 和 SL）都檢測(cè)到了錯(cuò)誤的根源。這些測(cè)量包括 Navit GPS 處理的路由計(jì)算。
在20個(gè)GPS的情況下，MLBack比SL快1354倍。在20GPS情景下，MLStep比SL快334倍。對(duì)于30GPS方案，加速系數(shù)為：MLBack1292倍，MLStep405倍。加速度并沒(méi)有隨著序列的延長(zhǎng)而增加，因?yàn)殚_(kāi)始時(shí)的一些GPS處理（重新計(jì)算和重新繪制航線）需要更長(zhǎng)的時(shí)間。Navit的測(cè)量結(jié)果表明，具有高監(jiān)控開(kāi)銷的分析可以通過(guò)分層細(xì)化加速，從而實(shí)現(xiàn)可行的動(dòng)態(tài)驗(yàn)證性能。

4.6 小結(jié)

本章介紹的方法展示了自動(dòng)化工具如何支持人工調(diào)試過(guò)程。我們介紹了最先進(jìn)的自動(dòng)錯(cuò)誤重現(xiàn)方法。然而，這些方法主要是針對(duì)特定平臺(tái)開(kāi)發(fā)的。因此，我們開(kāi)發(fā)了基于調(diào)試器的方法，可移植到不同的嵌入式平臺(tái)。它可以重現(xiàn)傳感器輸入，并實(shí)現(xiàn)隨機(jī)線程調(diào)度，以高效定位并發(fā)錯(cuò)誤。本章介紹了如何利用調(diào)試器工具實(shí)現(xiàn)斷言，以定位并發(fā)錯(cuò)誤的原因。隨后，我們展示了如何在不需要規(guī)范或斷言的情況下定位錯(cuò)誤的根本原因。根源可追溯到導(dǎo)致錯(cuò)誤的變量值變化?；谝粋€(gè)導(dǎo)航軟件，我們演示了如何加速這些根源定位技術(shù)。這樣，就可以優(yōu)化慢速監(jiān)控工具的應(yīng)用，使其適用于實(shí)際情況。

所介紹的方法幾乎不需要對(duì)其他調(diào)整。不過(guò)，實(shí)現(xiàn)的腳本都非常短（每個(gè)記錄/重放或監(jiān)控腳本都短于200LOC）。因此，該工具具有很強(qiáng)的可擴(kuò)展軟件進(jìn)行性。此外，大多數(shù)嵌入式平臺(tái)都支持GDB，我們的腳本實(shí)現(xiàn)也適用于大多數(shù)嵌入式平臺(tái)。只需稍加修改，我們就能在ARM Linux上運(yùn)行所有腳本，就像在X86Linux上一樣。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-710317.html

到了這里，關(guān)于嵌入式軟件調(diào)試與驗(yàn)證4自動(dòng)重現(xiàn)和分析嵌入式軟件中的Bug的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！