4 自動重現和分析嵌入式軟體中的Bug

4.1 引言

嵌入式軟體的重要性逐年增加。ISO26262標準的最高安全級別要求十個9小時內無故障運行。然而，歷史上的一些項目表明，即使進行了全面的測試，多年來仍有許多錯誤未被髮現。太空梭的控制電腦僅有50萬行源代碼，卻經過了長達8年的測試，每行源代碼耗資1000美元，即總耗資5億美元。然而，在1990年最後一次發佈時，預計每2000行代碼中會遺留一個錯誤。這種錯誤可能在極少數情況下出現，而且可能只有在實際運行環境中測試嵌入式系統時才能發現。

靜態分析在早期測試（如單元測試）中得到了有效利用。然而，對於複雜軟體來說，對錯誤的靜態分析已接近極限。大型軟體的狀態空間或控制流很難被完全探索。因此，這種分析在性能或精度上都存在缺陷。此外，語義錯誤具有很強的應用特異性，即使使用優化的靜態分析工具，也無法檢測到錯誤的行為。如果沒有完整、正確的規範作為黃金參考，情況就會變得更加嚴重。

系統測試描述了在目標平臺上部署和測試軟體的過程。與只測試單個模塊的單元測試或組件測試相比，系統測試是通過所有集成的軟體和硬體模塊來執行和測試軟體。在系統測試之前，約有60%的錯誤未被髮現。不過，根據軟體開發流程模式的不同，系統測試可能只在開發流程的後期才進行。在系統測試期間，真實的感測器和設備被連接到嵌入式系統，以獲得真實的輸入。這樣，感測器硬體與被測軟體之間的不相容性就能被檢測出來。

研究表明，錯誤發現得越晚，需要修複的工作量就越大。一些研究表明，在開發過程中，錯誤修複成本呈指數增長。因此，與單元測試相比，在系統測試過程中發現的錯誤需要付出更多努力，這是由於密切的硬體交互和認證要求造成的。然而，一小部分錯誤（20%）需要 60-80% 的修複工作。當很大一部分複雜的錯誤在開發過程中很晚才被髮現時，項目進度和項目期限就會受到負面影響。因此，產品往往無法及時投放市場。

造成錯誤修複工作量大的原因之一是錯誤難以重現。現場用戶或操作測試期間的開發人員往往無法提供足夠的信息來在實驗室重現錯誤。不同的非確定性方面（如線程調度）可能使實驗室中很難重現與運行期間觀察到的相同的執行情況。根據社區的錯誤報告，開源桌面和伺服器應用程式中約有17%的錯誤甚至無法重現。對於具有感測器驅動輸入的嵌入式軟體，這一比例可能更高。

當錯誤可以通過測試用例重現時，還需要額外的工作來分析錯誤。如果測試用例可用，在系統測試期間運行測試用例和修複錯誤大約需要8小時。Mozilla等開源項目每天會收到300份錯誤報告。在如此高的錯誤修複工作量下，要處理如此高的錯誤率是很困難的。動態驗證可以幫助開發人員修複錯誤。然而，大多數動態分析工具都需要在運行期間對軟體進行監控。這些監控工具通常只適用於特定的平臺。
錯誤分為記憶體錯誤、併發錯誤和語義錯誤。經驗研究表明，語義錯誤是最主要的根源。最常見的語義錯誤是實現不符合設計要求或行為與預期不符。我們需要自動定位語義錯誤根源的工具。記憶體錯誤並不難解決，因為有許多記憶體剖析工具可用。併發錯誤問題較多，尤其難以重現。每十個併發錯誤中就有一個無法重現。

我們自己開發的基於可移植調試器的錯誤重現和動態驗證方法為嵌入式軟體開發領域的技術現狀做出了以下貢獻：

• 通過使用調試器工具自動記錄和重現錯誤，避免了在任何嵌入式平臺上進行費力的人工錯誤重構。
• 通過強制隨機線程切換來改進多線程錯誤檢測。
• 通過對重現的錯誤進行自動根源分析，減少人工調試工作量。
• 通過使用低成本調試工具實施性能優化和分層分析，避免了昂貴的監控硬體。
• 通過在可擴展和易調整的模塊中實施動態驗證工具，降低了動態驗證工具的移植成本。

我們的方法支持開發人員更快地檢測和重建（主要是語義和併發）錯誤。通過實施自動根源分析，它還能幫助開發人員更快地修複錯誤。我們的工具可節省調試成本和硬體投資成本。它支持大多數嵌入式平臺。它能幫助開發團隊將軟體產品更早地投放市場。

第4.2節簡要介紹了正常的手動調試過程。第4.3節介紹了自動重現錯誤的方法，隨後介紹了我們自己基於調試器的方法。第4.4節展示瞭如何使用調試器工具實現基於斷言的驗證。第4.5節介紹了在不使用斷言的情況下分析錯誤根源的概念，以及使用廉價調試器介面加速監控實現的概念。

4.2 概述

下圖中的工作流程介紹了手動查找和修複錯誤的過程。首先要在系統測試環境中測試嵌入式系統和運行中的軟體。例如，導航軟體可在連接真實感測器的測試驅動器中執行。在執行過程中，對輸入進行跟蹤並記錄到錯誤報告（A.）中。該錯誤報告將提交至錯誤報告庫。在實驗室中，開發人員會根據錯誤報告嘗試手動重現錯誤 (B.)。如果錯誤可以重現，開發人員必須手動查找源代碼中的故障根源 (C.)。修複錯誤後，可使用回歸測試套件執行軟體 (D.)。這樣就可以確保在修複過程中不會增加新的錯誤。

手動調試概述：

4.3 基於調試器的錯誤重現

本節介紹自動支持錯誤再現的工具方法。為了重現錯誤，必須在運行過程中捕獲感測器輸入。在重放過程中，必須觸發或註入相同的感測器輸入（如來自GPS或觸摸屏的輸入），以實現相同的執行或指令序列。軟體的正常執行是確定性的。當軟體在相同輸入的情況下運行時，會執行相同的指令。然而，這些輸入是非確定的，在兩次執行軟體時並不完全相同。例如，在兩次測試執行中很難在觸摸屏上實現相同的動作。兩次執行之間的微小差異就可能決定是否觸發故障。圖4.2顯示了被測軟體（SUT）的不同輸入。非確定性輸入具體如下：感測器是嵌入式軟體最常見的輸入源（如 GPS 感測器）。用戶交互由人機界面設備（如觸摸屏）觸發。靜態數據可從磁碟或快閃記憶體（如XML配置文件）中存儲和讀取。訪問硬體中的時間或隨機性功能可改變執行情況，從而使複製變得困難。網路交互可用於與嵌入式系統中的其他設備進行通信（如 CAN 匯流排）。操作環境可由操作系統來表示，該系統控制日程安排和記憶體管理。物理效應可能會導致硬體變化，這也是最難處理的分歧。從SUT的角度來看，非確定性的來源可分為： 操作系統 SDK 訪問（如系統調用）、信號或中斷、特定處理器功能、調度或共用記憶體訪問順序以及記憶體初始化和記憶體分配（如圖4.2中SUT框周圍的方框所示）。

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

4.3.1 技術現狀

本節介紹了當前最先進的錯誤自動重現方法。對所介紹的非確定性源引起的不同事件的跟蹤和重放可在不同層面上實現。

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

可以在硬體層面記錄/重放軟體的執行（第 4.3.1.1 節）。因此，需要添加額外的特殊硬體來支持跟蹤和回放。另一種方法是模擬硬體。在模擬平臺中，可以集成捕獲模塊。操作系統可控制軟體和硬體，並可記錄/重放事件（第 4.3.1.2 節）。可以修改操作系統並將其安裝到目標平臺上。有些操作系統支持集成新模塊。此外，還可以修改軟體以記錄/重放應用層面的事件（第 4.3.1.3 節）。因此，可以在源代碼或二進位代碼層面修改應用程式。調試器工具在軟體和操作系統之間提供了一個層級，因此可以記錄/重放事件，如第 4.3.2 節和第 4.3.1.3 節所述。4.3.2 和 4.3.3 節中介紹的那樣。以下各節將根據各個層面介紹不同的方法。

4.3.1.1 硬體級重放

我們研究了硬體級重放領域的三種方法：硬體支持重放、全電路重放和基於虛擬化的重放。大多數硬體支持的重放方法都考慮了多處理器平臺。為了實現相似的執行，不同內核之間對共用記憶體的訪問會被記錄下來，併在重放過程中納入相同的序列。共用記憶體訪問的跟蹤可通過附加硬體實現。與基於軟體的方法相比，這種方法的優勢在於基於硬體的功能開銷低。全電路重放方法在FPGA綜合電路中添加了調試工具。這樣，就可以實時記錄和重放FPGA電路的數據流。不過，只能實時捕獲程式執行的一部分。其他方法實現了基於虛擬化的重放，對硬體進行模擬。此外，還有虛擬原型平臺 Quick Emulator（QEMU）。不過，虛擬原型平臺的基礎開銷較大，可能會影響與所連接感測器硬體的交互。

4.3.1.2 操作系統級重放

我們研究了操作系統級重放的三種不同方法：事件序列重放、同步事件重放和周期精確事件重放。為了重放相同的事件序列，一些方法使用操作系統 SDK 特定命令來跟蹤底層事件，併在重放過程中觸發相同的序列。RERAN使用 Android SDK的getevent和自帶的sendevent函數在Android移動平臺上進行跟蹤和重放。RERAN無需修改即可記錄和重放排名前100位的Android應用程式。記錄和重放觸摸屏上的複雜手勢輸入只需很低的開銷（約 1%）。不過，操作系統中必須有支持事件跟蹤和發送的功能。在多個內核上進行不同的調度或並行執行會導致另一種行為。並行執行需要同步事件，以實現對共用資源的相同訪問順序。SCRIBE是作為用於跟蹤和註入的Linux內核模塊實現的。它支持多處理器執行，並使用同步點實現並行訪問的同步。利用這種同步，即使在多個內核上運行，系統調用也能在記錄和重放過程中保持一致的順序。然而，實時系統有嚴格的時間要求，需要對中斷等事件進行精確的指令再現。RT-Replayer利用實時操作系統內核跟蹤中斷。為了進行重放，在發生中斷的記憶體地址上使用陷阱指令（類似於調試器的斷點）。因此，在重放過程中，軟體會在陷阱處停止，並觸發相同的中斷功能。

4.3.1.3 應用程式級回放

為了跟蹤和註入應用層事件，我們研究了三種不同的應用層回放方法：源代碼工具化回放、二進位工具化回放和基於檢查點的回放。使用源代碼工具，可以修改源代碼以跟蹤控制流和變數賦值。Jalangi提出了一種方法，即在運行時對變數的每次賦值進行工具化，並將賦值寫入跟蹤文件。在重放過程中，會註入跟蹤到的變數值。該方法是針對JavaScript提出的，但可移植到任何其他編程語言。Jalangi的缺點是：開銷大、跟蹤文件大，而且可能產生副作用。動態二進位代碼工具在執行過程中修改源代碼，例如記錄。它可在運行時對載入的二進位代碼進行動態檢測，並註入額外的跟蹤代碼。工具化代碼可以高度優化，執行代碼只需較低的開銷。PinPlay利用 Pin工具框架對二進位代碼進行動態工具化。它考慮了本節導言中介紹的幾種非確定性來源。不過Pin框架僅適用於特定指令集。檢查點方法能高頻捕捉當前進程狀態。從檢查點開始，所有非確定性事件（如系統調用）都會被捕獲。檢查點通常基於與平臺相關的操作系統SDK操作。

4.3.2 理論與演算法

上一節介紹了最先進的方法在不同系統級別記錄和重放錯誤的方式。本節將介紹我們自己為調試器工具跟蹤和重放錯誤的方法。它考慮了兩種非確定性輸入來源：感測器輸入和線程調度。我們不考慮記憶體違規，因為這類錯誤可以通過許多可用的記憶體剖析工具輕鬆檢測到。我們首先介紹感測器訪問的記錄/重放，然後介紹線程計劃的記錄/重放。
嵌入式軟體經常在定時器或中斷的觸發下訪問連接的設備。設備狀態以特定頻率被請求。例如，導航軟體可能以10Hz的頻率訪問 GPS 感測器。圖 4.4顯示瞭如何通過定時器功能訪問感測器。

可以通過在設備訪問結束的位置（我們定義為接收）暫停軟體執行來實現跟蹤。讀取的數據將寫入日誌文件。圖 4.5 展示了這一概念。

圖 4.5 記錄序列

在重放過程中，執行暫停在某個位置，在該位置中斷開始訪問設備（我們定義為請求）。跳過對感測器的訪問，跳轉到接收位置（定義為 Receive）。此時，將從日誌文件中讀取數據。這些數據被註入到執行過程中。這樣，記錄運行中的感測器數據就會被重放。這一概念可通過調試器工具實現，如第 4.3.3 節所述。4.3.3. 基於調試器的重放如圖 4.6 中的序列圖所示。

圖 4.6 重放序列圖

非確定性的其他來源可能是線程調度。線程計劃的記錄/重放基於線程事件和IO事件序列的重建。這樣，線上程操作（如 sem_wait和sem_post時的活動線程就會受到監控。在重放過程中，會觸發這些事件的相同調用序列。列表1和2顯示了行人識別軟體組件的兩個線程的示例：Proc線程用於識別圖片中的行人，GUI線程用於在檢測到行人的圖片中繪製矩形。如果交替執行這兩個線程，不會出現故障。但是，當Proc線程執行兩次時，有一幅圖片沒有繪製。此外，當Proc被執行兩次時，semaphore的值為2，GUI線程也會被執行兩次。因此，當前圖片在第4行的 GUI 線程中被釋放，下一次調用drawRec時會觸發已釋放的圖片。這種情況在正常執行中極少發生，因為線上程 Proc（第 2 行）中對圖像進行長時間的行人識別後，通常會觸發線程切換到 GUI。

我們的方法實現了活動線程的序列化，併在線程操作時隨機切換線程。因此，正常的線程調度器被鎖定，任何時候都只有一個線程處於活動狀態。這樣，活動線程就不會被其他線程搶占。在我們的概念中，線程切換由我們的工具線上程事件（如 sem_wait、sem_post）時觸發。腳本通過暫停相應函數並觸發線程切換來監控線程事件。在每個線程事件中，我們的工具都會觸發線程切換操作（見表 4.1）。
表 4.1 工具觸發的線程切換操作列表

我們的工具會為每個semaphore sem設置計數器。每當出現sem_wait，演算法都會檢查語義符號是否大於零，因此是否可以通過，並減少語義符號計數器sem。如果semaphore計數器為零，則線程被註冊為等待線程，並觸發切換到另一（非等待）線程。當sem_post 發生時，post結束，並觸發切換到隨機線程。在重放過程中，與跟蹤過程一樣，通過為隨機函數設置相同的種子，調用相同的隨機線程切換。使用這種方法，線程切換總是由腳本觸發。因此，腳本可以完全控制線程調度。

4.3.3 執行

調試器工具用於控制SUT的執行。GNU調試器是一種流行的調試工具，可用於不同的嵌入式平臺。目前GDB主頁列出了GDB支持的80 個主機平臺。此外，不同的供應商還將其適配到其他平臺。在正常使用過程中，GDB由開發人員手動控制，開發人員在控制台終端輸入命令。表 4.2 列出了最常用的 GDB 命令。

表 4.2 線程事件操作

GDB 提供了外部 API。通過該API，可以使用Python編程語言控制調試器的執行和命令。清單3顯示了一個可與GDB一起載入的簡單 Python腳本。它開始載入要測試的程式（第2行），併在方法foo上設置斷點（第3行）。腳本開始運行程式（第4行）。程式在調用 foo時暫停。腳本對foo的調用進行計數（第 6-8 行）。

這樣，調試器就由腳本邏輯控制了。其他調試器提供不同的 API 來控制被測軟體的執行。即使調試器只提供終端命令介面，也可以通過腳本模擬這些終端命令，並對終端輸出進行評估。我們基於調試器的方法就是利用這種調試器工具 API 來記錄和重放事件。清單4顯示了我們為 Navit 導航軟體實現 GPS 感測器數據重放的方法。

在開始請求設備和結束訪問設備的源代碼行（第1-2行）中設置斷點。在記錄時，執行會在接收GPS數據的位置暫停。在這種情況下，將列印當前的GPS值（第7-8行）並將其寫入日誌文件（第9行）。對於重放，執行暫停在開始訪問GPS的位置。使用跳轉命令跳過訪問（第12行），並註入日誌中的數據（第13-14行）。如果使用斷點進行基於調試器的記錄太慢，可以使用printf語句或跟蹤緩衝區來實現。

下一段將介紹如何控制被測程式以實現確定的線程調度。GDB為調試多線程程式提供了表4.3所列的命令。表4.3列出了用於調試多線程程式的命令，其中包括我們在實現過程中使用的三條命令。在每次斷點暫停時，開發人員可以手動檢查當前線程，也可以切換到線程列表中的其他線程。

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

清單5介紹了行人識別重放的實現（與第 4.3.4 節中介紹的游戲案例研究類似）。

命令"set scheduler-locking on"可禁用當前線程調度器（第5行）。激活該選項後，任何時候都只能執行一個線程。可移植的非搶占式線程庫也能達到類似效果。這樣，線程的並行執行就被序列化了。為了實現所需的線程切換，我們的工具會在使用的線程操作處設置斷點（見第4-5行）。每經過一個線程操作，我們的工具都會根據表4.1中的操作，用GDB的線程命令觸發線程開關（清單5，第14-17行）。線程計劃的控制與感測器重放集成在一起（清單5，第18行之後）。

與普通線程調度程式相比，線上程操作中使用隨機切換可實現更好的線程交錯覆蓋率。這樣，併發錯誤就能更快地顯現出來。

4.3.4 實驗

圖4.7顯示了我們在 X86 英特爾平臺的Ubuntu Linux上執行單線程軟體Navit時跟蹤或記錄感測器輸入數據的測量結果。測量考慮了一條有1200個GPS坐標的路線。這些坐標由Mockup GPS伺服器從文件中讀取。測試GPS頻率為50、33、20和10 Hz，同時以100Hz 捕獲用戶游標輸入（例如從觸摸屏）。正常執行（標記為"Normal"）和記錄執行（標記為"Rec"）之間的開銷幾乎保持不變，因為在斷點處暫停執行所用的時間被輪詢定時器的調用所占用。這樣，我們針對基於定時器軟體的方法就能將開銷降到最低。對於其他類型的軟體，還需要對跟蹤進行優化，例如將多個輸入分組，一次只跟蹤一組輸入。

圖 4.7 單線程 Navit 感測器輸入記錄的性能測量。

我們用兩個使用 POSIX 線程實現的嵌入式軟體示例測試了我們的確定性調度和記錄方法。這些示例的性能測量結果如圖4.8所示。第一個是基於 ASCII 碼的飛行射擊游戲。該游戲使用兩個線程，一個用於繪製場景，另一個用於讀取鍵盤信息。第二個例子是在車載攝像頭的視頻數據中識別行人（見第 4.3.2 節）。在每個例子中，我們都使用了兩種場景進行測量，一種是短場景，另一種是長場景。我們對游戲進行了測量，直到用戶在沒有互動的情況下損失5或10條生命為止。我們使用一組60或165張圖片作為輸入，對行人識別進行了測量。我們的實驗在配備ARM CPU和Linux操作系統的NVIDIA Tegra K1上執行了五次。

圖 4.8 確定性調度和錄製的性能測量結果

在記錄游戲場景時，短場景平均需要調度377次線程切換，長場景平均需要調度642次線程切換。在行人識別示例中，平均需要安排186次（短）和475次（長）線程切換。錄製行人軟體平均需要1.22倍和1.36倍的開銷。記錄游戲的開銷更高，平均為2.86倍和2.98倍，因為需要在更短的時間內觸發更多的線程開關。

我們觀察到，在兩個案例研究中，短時間和長時間的開銷都差不多。測量結果表明，只需極少的工作量就能實現高性能記錄。每個記錄和重放腳本的源代碼不到50行。此外，行人識別示例表明，如果使用我們的工具強制進行隨機切換，併發錯誤的檢測速度會更快。因此，在我們的測試中，使用我們的方法在幾秒鐘內就能檢測到示例錯誤，但在使用普通線程調度器進行10次圖片輸入時卻不會觸發該錯誤。為了測量性能，我們觸發了兩個線程的交替調用，以避免觸發錯誤。

4.4 重放期間的動態驗證

即使可以重現錯誤，也很難在重放過程中找到錯誤的根本原因。手動調試重放（如使用GDB）非常費力。源代碼通常由其他開發人員實現。因此，很難理解是哪一系列操作（如方法調用）導致了故障。此外，也很難理解錯誤的操作序列是如何造成的。運行時驗證領域的方法提供了在運行時通過將執行與正式規範進行比較來自動分析執行的概念。運行時驗證測試在執行過程中是否保持了一組特定屬性。觀察執行情況的組件稱為監控器。

4.4.1 技術現狀

線上監控器方法是在運行過程中與執行並行運行監控器。線上監控器必須非常高效，因為正常執行不應受到干擾。不過，線上監控器可能會對執行過程中觀察到的異常情況做出反應。出現異常時，可在運行過程中啟動故障安全或恢復模式。日誌監控器檢查在軟體長期運行過程中捕獲的日誌文件。跟蹤文件是在運行過程中有效生成的。為了不影響正常執行，跟蹤應精簡或使用快速的附加硬體來實現。離線時，會對跟蹤文件進行詳細分析。可以檢測出跟蹤文件中的錯誤事件序列，指出故障或甚至故障的根本原因。有些方法結合了軟體的記錄/重放和動態分析 。但是，這些方法沒有使用實現複雜斷言的框架，也沒有在嵌入式平臺上進行測試。
表4.4列出了每種模式的優缺點。這兩種方法不支持檢查故障是否仍然發生（控制測試）。此外，這兩種方法都不能細粒度應用（細粒度），因為它們會幹擾與用戶或其他系統的正常交互。我們的重放方法符合前兩類要求（控制測試和細粒度）。不過，只有在表 4.4 中總結的線上模式下才能激活恢復功能。我們認為，長期跟蹤和監控最好使用跟蹤日誌。
表 4.4 監控類型不同特性的比較

4.4.2 理論和工作流程

在重放過程中應用動態驗證的概念是基於只跟蹤軟體的相關輸入並離線重放的概念。在重放過程中，可以執行細粒度跟蹤。監控或分析可檢查這些跟蹤是否存在異常。與正常運行相比，重放期間對高效跟蹤和監控的要求較低。此外，生成的重放還可在錯誤修複後用作控制重放。我們認為，重放概念是系統測試的最佳選擇，因為生成的控制重放可用作以後的回歸測試用例。圖 4.9 顯示了自動化工具如何支持或取代不同的人工步驟。4.3.3節中介紹的隨機調度概念優化了多線程錯誤（A.）的檢測。4.3.3. 錯誤重放（B.）已實現自動化（見第 4.3 節），並可用作回歸測試（D.）。重放（B.）過程中的自動分析支持手動錯誤修複（C.）。下文將介紹這些分析工具。

圖4.9重放期間基於調試器的動態驗證工作流程

A. 系統錯誤檢測： 在實際操作中測試軟體。在這些測試過程中，會捕捉到進入軟體的事件。記錄機制通過符號調試器實現，以避免工具化並實現平臺相容性。因此，調試器由腳本控制。開發人員決定哪些事件是相關的，必須捕獲。因此，記錄可以保持精簡。為有效檢測多線程錯誤，線程調度器由腳本控制，在任何線程事件中觸發隨機開關。

B. 自動重放和分析： 故障序列可在實驗室中載入並確定性地重放。重放機制是通過攜帶型調試器工具實現的。軟體通過調試界面在與運行期間相同的硬體上執行，以安排與原始運行期間相同的系統行為。在重放過程中，故障會根據確定性重放再次發生。手動調試完整的執行序列甚至是事件的多個處理路徑非常耗時。因此，我們在重放過程中採用動態驗證來自動檢測潛在的異常情況。這些信息可以為故障提供提示。在運行過程中進行的線上分析會幹擾正常執行，但在重放過程中不會造成弊端，因為重放的執行不需要與用戶或外部組件進行交互。

C. 手動錯誤修複： 根據動態驗證報告，開發人員可以手動修複故障。該步驟的結果是一個已打補丁的程式。

D. 回歸重放： 修改後的程式可通過控制回放進行測試。使用記錄的故障輸入序列執行程式，觀察故障行為是否再次發生。最後，錯誤重放可作為回歸測試套件的測試用例存檔。

4.4.3 在回放過程中執行斷言

在上一節介紹的工作流程中，動態驗證是在重放過程中應用的，用於檢測錯誤原因。本節將展示如何使用斷言來檢測錯誤原因。這種斷言可以通過調試器輕鬆實現。因此，在基於調試器的重放過程中，也可以使用調試器監控執行情況。下文將討論行人識別軟體的多線程重放（如第4.3節所述）。在軟體重放過程中，可以使用基於斷言的驗證對事件序列進行分析。通過在相應的方法上設置斷點來監控方法調用的順序。在行人識別示例中，有三個相關事件：recogPed()、drawRec() 和 showImg()。在重放過程中，可以通過方法斷點或觀察點檢查時間條件。圖4.10中的自動機會檢查載入和處理圖像的正確順序是否被調用。如果發生其他轉換，則會檢測到違反規範的情況。

圖 4.10 行人識別動作序列自動機

這種監控器可以在GDB Python腳本中輕鬆實現（見清單 6）。第1-3行根據條件設置斷點和觀察點。第6-14行檢查達到的點和當前狀態。

參考資料

• 軟體測試精品書籍文檔下載持續更新 https://github.com/china-testing/python-testing-examples 請點贊，謝謝！
• 本文涉及的python測試開發庫 謝謝點贊！ https://github.com/china-testing/python_cn_resouce
• python精品書籍下載 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
• Linux精品書籍下載 https://www.cnblogs.com/testing-/p/17438558.html

4.4.4 實驗

圖 4.11顯示了不同監控場景下的性能測量結果與多線程記錄開銷的比較。

我們測量了使用GDB監控相應軟體所有方法中的2%、5%和10%（代表線上監控或日誌監控模式）時的運行時間。受監控的方法可與上一節中介紹的並行運行狀態機進行比較。我們隨機選取了一定比例（2%、5% 或 10%）的方法，併在這些方法上設置了斷點。我們還測量了執行多線程記錄方法（標記為 Record）的運行時間。我們使用了與第4.3節中相同的四種場景："飛行"和"射擊"。我們使用了與第4.3節中相同的四個場景：有5或10條生命的飛行射擊游戲，以及有60或165張視頻圖片的行人識別。在所有場景中2%的監測方法比記錄方法更快。5%的方法的監控速度慢於記錄速度，尤其是在游戲場景中。在監控10%的方法時，錄製場景的執行時間平均比運行時間快2.45 倍。不過，方法監控的性能主要取決於每個方法在執行過程中出現的頻率。表4.5顯示了記錄場景和每個方法監控場景（2、5 和 10%）的 GDB 停頓次數。

表 4.5 記錄和方法監控的GDB操作次數

暫停次數越多，記錄或監控時間就越長。然而，與監控方案相比，記錄方案的暫停次數較少，運行時開銷比例卻較高。造成這一結果的原因是，為實現記錄，每次斷點暫停都需要更多的GDB命令。此外，我們還測試了對15%的行人識別方法進行監控，但第一張圖片的監控在10分鐘後仍未完成。

4.5 根本原因分析

在上一節中，我們展示瞭如何通過將執行的操作與規範屬性進行比較來檢測錯誤的操作序列。錯誤序列觸發了錯誤，導致程式崩潰。然而，在許多情況下，並不存在正確或完整的操作規範。通常就是這種情況，因為規範屬性往往已經指出了潛在的故障，可以手動修複。在本節中，我們將考慮語義錯誤（在沒有規範的軟體中），即錯誤的根源在於數值處理或程式邏輯。我們將介紹一些概念，用於檢測處理過程中錯誤或缺失的方法調用，並確定相應錯誤邏輯的根本原因。

4.5.1 技術現狀

本節介紹了非崩潰錯誤定位和嵌入式軟體監控領域的最新技術。

4.5.1.1 Delta調試

《程式為何會失敗》一書介紹了軟體故障定位的不同概念。書中介紹了幾個動態分析概念，包括三角調試和異常檢測。其中一些概念在我們的工作中也有類似的考慮，例如我們的delta計算方法。後來Burger和Zeller的工作開發了用於定位非崩潰錯誤的動態切片。他們採用了多個步驟，通過回溯執行過程中的錯誤來隔離故障位置。然而delta調試基於對程式的實驗，以自動生成通過運行和失敗運行，這在嵌入式環境下是困難的，且耗費運行時間。

4.5.1.2 非崩潰錯誤的動態驗證

Zhang 等人提出了一種檢測錯誤配置導致的非崩潰錯誤的方法。它剖析了失敗配置和非失敗配置的執行情況。許多嵌入式軟體甚至不需要配置，錯誤可以在源代碼中找到。Liu等人應用支持向量機對非崩潰錯誤的通過運行和失敗運行進行分類。他們的方法在方法級別上生成行為圖，以比較不同的運行。為了進行分類，需要大量的輸入運行，而且只能檢測到可疑的方法（而不是相關的源代碼行）。Abreu使用基於頻譜的覆蓋率分析實現了嵌入式軟體的故障定位。他們應用基於模型的診斷來改進分析結果。與Tarantula類似，他們將每個失敗運行的執行語句覆蓋率與通過運行的語句覆蓋率進行比較。他們假定失敗運行和通過運行的測試用例集都是可用的。然而，所有方法都需要一組失敗運行，用於分類。在我們的系統測試用例中，沒有大量的非失敗運行和失敗運行可用於分類。

4.5.1.3 監控嵌入式軟體

為實現故障定位，必須對軟體進行監控。Amiar等人使用特殊的跟蹤硬體來監控嵌入式軟體。他們在單個跟蹤上應用基於頻譜的覆蓋分析。當檢測到一個故障周期時，將其與之前的類似周期進行比較，以檢測基於頻譜的覆蓋範圍脫差。不過，它們假設有適用於特定嵌入式平臺的跟蹤硬體。這種硬體通常價格昂貴。有幾種運行時驗證方法使用 GNU 調試器 (GDB)的廉價調試器介面來實現平臺相容性，但它們沒有提出在沒有規範的情況下檢測錯誤的概念。FLOMA使用概率採樣對軟體進行細粒度觀察，但並不監控每一行源代碼。它會隨機決定是否監控特定的執行步驟。不過，概率採樣可能會遺漏重要步驟，而且FLOMA需要對源代碼進行工具化。Zuo等人提出了一種分層監控方法來加速監控。他們的方法利用軟體來監控和分析方法調用序列。之後，只在源代碼行級監控可疑部分。通過這種方法，可以加快監控速度。我們的方法擴展了這一方法，並將其應用於調試器工具。

4.5.2 理論和概念

我們對故障回放進行根本原因分析，自動檢測出可能是故障根本原因的可疑源代碼行。分析結果將形成一份報告，為開發人員提示錯誤在源代碼中的位置。下麵，我們將介紹一個基於故障重放和非故障重放的工作流程。我們將軟體的執行分成幾個部分（見第4.5.2.1節）。一個分區的多個執行過程存在重疊，可以進行比較。一個分區的每次執行稱為一次運行。之後，必須檢測重放中執行故障的運行（見第4.5.2.2節）。重放中的故障運行將與重放中類似且未被歸類為故障運行的多個運行進行比較（見第4.5.2.3節）。為了將失敗運行與類似運行進行比較，我們對源代碼行進行了細粒度分析，目的是檢測出存在錯誤的源代碼行。我們展示了覆蓋率分析和不變數生成分析的指標（見第 4.5.2.4節）。然而，使用廉價的調試器介面進行細粒度監控可能會非常緩慢。因此，我們在第 4.5.2.5 節中介紹了一種加速方法。4.5.2.5.我們用開源導航軟體Navit中的一個非崩潰錯誤來舉例說明我們自己的方法。如果Navit接收到的GPS感測器數據角度小於 -360，車輛指針將在短時間內無法繪製。例如，在繁忙的街道上尋找正確的十字路口時，這個錯誤可能會幹擾駕駛員。這個錯誤不會產生異常。只是在圖形用戶界面中可以短暫觀察到。這是由於處理了錯誤的感測器數據（感測器發送的角度值為<-360造成的。當軟體與感測器硬體輸出不相容時，就會出現這種情況。該錯誤由Navit軟體中的錯誤計算引起（見下文）。

4.5.2.1 分區重放

異常檢測領域的最新方法提供了通過比較被測軟體的非失敗運行和失敗運行來檢測根本原因的概念。然而，複雜嵌入式軟體的執行可能包含執行不同功能的部分。對不同功能進行比較可能會導致許多誤報，尤其是在只有一小部分參考運行時。在我們的方法中，我們將嵌入式軟體的執行分成幾個可比較的部分（執行類似的功能）。嵌入式軟體通常會處理感測器數據以更新程式狀態。每次執行時的處理過程通常非常相似。圖 4.12舉例說明瞭Navit的重放概念。Navit重放包含不同類型的處理，例如GPS處理、觸摸屏輸入處理或交通數據處理。

從感測器硬體（在第 4.3 節中定義為接收點）讀取數據後，即開始處理感測器數據。處理過程由以下元組表示：

Processing = (Start, Run, End)

Start和End表示執行過程中傳遞的源代碼行數。Start是執行過程中系統開始處理感測器數據的位置。End是執行過程中感測器數據處理結束的位置。處理運行包括感測器數據處理過程中的所有操作Ops和方法調用M的列表：

Run = (M,Ops)

和

在我們的方法中，執行會在開始時中斷。從這個斷點開始，處理過程會在方法或源代碼行級別上被觀察到。

4.5.2.2 檢測故障運行

軟體分區的每次執行都被視為一次重放運行。在運行故障回放時，特定感測器處理的一次或多次運行會導致觀察到的故障。我們提出了一個輕量級概念，用於檢測回放中的故障運行。它將與非故障重放中的運行差異最大的運行分類為故障運行（如下所述）。重放的每個運行都可以與其他運行進行比較，因為會執行類似的操作和方法。運行中的差異可能指向故障。要檢測故障運行，我們的方法需要進行兩次重放。一個是導致故障的重放，另一個是不會導致故障的重放。出現故障的重放運行可與未出現故障的重放運行進行比較。可以通過檢查一次運行覆蓋了哪些源代碼行或方法來比較兩次運行。如第4.5.2.5節，在此階段考慮方法的覆蓋範圍更為有效。

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

可調用方法在行中表示。運行用列表示。單元格中的值1表示該行中的方法由相應列中的運行執行。可以使用漢明距離（hamming distance）比較兩個運行的差異，即計算兩列運行在行中的差異。在我們的例子中：distance(Run1,Run7)=2,distance(Run2,Run7)=3, distance(Run3,Run7)=3。為了簡單明瞭，我們考慮了一些偽方法m1-m4和繪製方法。

利用上述矩陣和漢明距離，通過比較故障重放中的每個運行和非故障重放中的每個運行來檢測故障。故障重放中與非故障重放中所有運行不相似（或差異最大）的運行被視為故障運行。圖4.13顯示了故障重放中的運行7與非故障重放中的每個運行的比較情況。Run7與非失敗運行的差異最大，因為缺少了對車輛指針的繪製方法的調用。每種方法的出現次數也可以與漢明距離相結合。這樣，如果一個運行比另一個運行執行了更多的方法，那麼兩個運行中的一個方法就可以被歸類為不同的方法。還可以考慮調用序列。不過，方法覆蓋率的監控速度要快於源代碼行覆蓋率（見第4.5.4節）。此外，還可以將若幹次運行歸類為失敗運行。例如，可以將與非失敗重放的運行相比出現20%差異的運行歸類為失敗運行。不過，以下解釋以一次失敗運行為基礎。註：如果多個運行排序的距離相同，則選擇最近的運行（因為預計錯誤將出現在重放的末尾）。

圖 4.13 檢測故障運行

在這裡，故障重放中的運行7與非故障重放中的所有其他運行差別最大。這意味著Run5、Run6和Run8在非故障重放中都有相應的運行，其漢明距離小於 Run7 與非故障重放中各運行的漢明距離。

4.5.2.3 檢測相似運行

在上一節中，我們介紹了檢測故障運行的概念。通過將故障運行與無故障運行進行比較，可以檢測出異常。因此，我們的方法會在故障回放中檢測與故障運行相似但未被歸類為故障運行的若幹運行，即使用漢明距離檢測與故障運行具有相似方法覆蓋範圍的運行。圖4.14顯示了失敗重放。在本例中，與失敗運行 Run7 最相似的運行是 Run5。這樣，故障運行就會與其最相似的運行進行詳細比較。這一概念基於近鄰模型，該模型同樣適用於跟蹤硬體的日誌文件。我們的方法是在發生故障運行的同一重放中檢測類似運行，這些類似運行是在與故障運行相同的上下文（例如，考慮配置上下文）下執行的。

圖 4.14 檢測類似運行
在測試中，我們檢測到三個運行與故障運行相似。我們將使用delta分析法對這些運行和故障運行進行詳細比較。

4.5.2.4 Delta計算

對故障運行和類似運行進行詳細比較，以檢測可指向故障根源的Delta。將類似運行與故障重放中的故障運行進行比較時，可採用不同的指標來識別可疑源代碼行。我們以Navit Bug為例，介紹Delta分析的概念和指標。
Navit bug基於GPS處理中的錯誤計算（偽代碼見清單 7）。如果角度小於0，第2行中的角度值會加上360。但是，如果角度小於-360，則角度在第2行後保持負值，第5+6行被跳過，並且不會繪製車輛指針。在正確的執行過程中，應該對角度計算進行數學調製運算，以產生一個正值。第5行和參數變數lazy將在下一節中解釋。

在我們的示例中，以下對vehicle_update方法的GPS輸入序列觸發了錯誤（...{42, 9, 40, 0}，{42, 9, 55, 0}，{42, 9, -370, 0}，{42, 9, 70, 0}）。這裡第三輸入端發送錯誤的角度數據，例如來自感測器設備的數據。

我們採用故障定位度量來檢測故障重放中此類錯誤的根本原因（在本例中，第2行中的錯誤計算）。我們用三個繫數來定義這些指標，每個可執行源代碼行都會生成這三個繫數。這些繫數用於計算滿足特定源代碼行op的特定特征的運行次數。這些特征定義了導致故障或未導致故障的運行次數。它們還定義了是否涵蓋特定源代碼行操作。

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

Tarantula衡量失敗運行主要執行哪些行。這些行被認為更有可能是失敗的根本原因。如果許多非故障運行也執行了該行，則其可疑程度會降低。Jaccard 繫數也是基於e_f，但當許多非失敗運行執行了該行或許多失敗運行未執行該行時，可疑排名會降低。Occhiai還對 $$e_p$ 和 n_f之間的差值進行了加權。因此，當許多非失敗運行同時執行該行，而許多失敗運行同時不執行該行時，排名就會降低。前面介紹的指標主要考慮的是哪些源代碼行經常出現在失敗運行中。然而，在嵌入式軟體出現非崩潰錯誤時，錯誤的原因可能是缺少對操作系統 SDK 庫的調用。此外，失敗運行中遺漏的源代碼行可能指向錯誤的條件邏輯評估。將失敗運行中的遺漏代碼與非失敗運行中的遺漏代碼進行比較，可以發現失敗的原因。因此，我們認為有必要對失敗運行中的缺失特征進行排序。AMPLE 指標（4.9）也考慮了失敗運行中的缺失特征。

表 4.7顯示了Navit錯誤示例（見清單 7）中三個相似運行RunSim和一個失敗運行RunFail的不同度量結果。得出的繫數越高，相應源代碼行的可疑度就越高。我們發現，每個指標都將索引為2的操作列為可疑操作。然而，儘管AMPLE將另外指向錯誤條件情況的操作5和6列為可疑操作，但卻未將其列為可疑操作。

表 4.7 按示例計算指標

在大多數故障定位方法中，度量指標會產生一個源代碼行列表，並根據其可疑程度進行排序。然而，要根據該列表對源代碼進行人工評估是很困難的。在我們的使用案例中，我們的工具會在重放過程中在最可疑的源代碼行上設置斷點。開發人員可以在重放過程中逐步查看可疑行，並檢查哪些行在失敗運行和非失敗運行中被執行。我們的工具只在AMPLE可疑度排名為1的源代碼行上設置斷點。此外，它還會在每一行可疑源代碼上註明，該行是否在故障運行中被執行（但未在任何類似運行中執行），或是否在每個類似運行中被執行（但未在故障運行中執行）。還有一些方法提出了可疑度量的組合，例如將AMPLE和Occhiai結合起來。這樣，機器學習演算法就會生成不同指標的加權組合。研究表明，使用組合指標可以獲得更好的指標結果。不過，這需要一個學習階段，而在我們的使用案例中這是不可能的。

之前，我們展示了delta計算如何能夠顯示故障重放中的故障運行與重放中一些類似運行之間的覆蓋率差異。然而，只有通過監控每一行源代碼中的所有變數值，才能發現從錯誤的變數賦值開始傳播的根本原因。

在我們的示例中，GPS 輸入的另一個序列也可能觸發錯誤：（{42, 9, 340, 0}，{42, 9, -355, 0}，{42, 9, -370, 0}，{42, 9, -355, 0}）。當感測器發送小於0的數據並逐步切換到小於-360的角度時，就會出現這種序列。在此序列的重放過程中應用基於覆蓋率的分析，無法檢測到錯誤的源代碼行（清單7中的第2行），因為第2行在每次運行中都會被執行。但是，如果監控每行源代碼中的所有變數值，就可以檢測到根本原因。

變數值中的異常情況可以使用不變數來檢測。不變式是為每次運行存儲的變數/值對的特征。非故障運行所持有的不變式可與故障運行所存儲的不變式進行比較。因此，我們會自動為非失敗運行和失敗運行生成不變式。範圍不變式檢查在運行期間觀察到的變數值的範圍。在我們的 Navit例子中，公式 (4.10) 中的不變式存儲在每次非失敗運行中。該不變數可在失敗運行中進行檢查，因為在失敗運行中該不變數被違反。在我們的實現中，我們為每一行通過的源代碼生成不變式。

然而，由於參考運行較少，很難建立範圍不變式。變數/值對之間的關係不變式檢查兩個數值變數之間的關係。變數關係通常在條件分支中進行檢查。這種關係可能是變數角度總是大於特定源行中的變數懶惰值（4.11）。

我們的分析將每個變數值與所有其他變數值進行比較，以檢測變數之間的關係。在Navit示例中，調用vehicle_update方法時總是使用第四個變數lazy，它定義了繪製模式，在大多數情況下為0或1。將變數angle與變數lazy比較，可以發現在操作2之前，angle<lazy。在操作2 之後，每次非故障運行都滿足 lazy<angle。但是，對於失敗運行，angle<(lazy==0)仍然成立。圖 4.15 顯示了變數 angle 和 lazy 之間的變數關係序列。

圖4.15檢測兩個 Navit GPS 處理之間的不變數Delta

在圖4.15中，故障運行中第3行和第4行的錯誤關係正好指向故障的根本原因。由此產生的分析報告包括通過比較故障運行與類似運行的覆蓋範圍而發現的異常。此外，報告還包括生成的關係不變式，這些關係不變式在故障運行和類似運行之間存在差異。

4.5.2.5 加速監控

許多方法使用特殊硬體來監控被測嵌入式軟體。然而，這種硬體可能很昂貴，甚至無法用於新平臺。因此，我們提出了一種如何優化監控以實現快速動態驗證結果的方法。大多數開發人員已經使用增量方法手動調試軟體。他們首先在方法上設置斷點，開始檢測方法調用序列中的異常。然後，他們檢查可疑方法，並逐步完善檢查。我們的工具通過自動應用這一概念，實現了對錯誤根源分析的加速監控。首先，我們定義了單級監控（SL）的基本概念。

單級監控-SL：在（處理）運行過程中，對每行已執行的源代碼進行單步監控。它監控每個被監控源代碼行的當前變數值。
上一節介紹的分析可應用於 SL 監控生成的跟蹤。不過，運行單級監控可能會比較慢。軟體方法的執行頻率通常遠低於源代碼行。因此，監控方法通常比監控每一行源代碼更快。

多層次監控 -ML：在第一次重放中，對方法調用進行監控。在此方法調用跟蹤中可應用以下活動： 檢測故障運行和檢測類似運行。在第二次重放中，通過單步監控詳細監控故障運行和類似運行。Delta計算可應用於生成的跟蹤。這樣，所有運行（儘管有故障）和類似運行都無需詳細監控。
圖 4.16舉例說明瞭這一概念。圖中顯示了兩個重放：一個用於方法級監控，另一個用於通過單步詳細監控相關運行。在方法層面，首先將故障運行與非故障重放進行比較，從而檢測到故障運行 (A.)，如第 4.5.2.2節所述。圖 4.16 中的故障運行是運行7。然後，在方法層 (B.) 上識別出與失敗運行類似的運行，如第4.5.2.3節所述。里的相似運行是Run5。不過，我們的方法可以檢測並處理多個類似運行。失敗運行與類似運行（Run5和Run7）之間的區別是通過單步監控（與SL相同）和分析每一行源代碼來實現的，如第4.5.2.4節所述。因此，在本示例中，不對 Run6 和 Run8 進行詳細監控。

然而，每次方法通過時暫停也會導致較長的監控時間（如第4.5.4節所述），尤其是在高頻率調用短方法時。因此，在下文中，我們提出了一種基於調試器的高效監控運行方法覆蓋率的概念。

ML方法監控-MLMethd： 方法覆蓋率監控只跟蹤一次運行中每個已執行的方法。
演算法1以偽代碼的形式展示了 MLMethd 的概念。通過這種方式，方法覆蓋率的監控是高效的，因為監控工具只需對每個方法跟蹤一次。

然而，在檢測到故障運行並計算出類似運行後，Delta計算步驟需要進行細粒度跟蹤。對該軌跡的監控可能非常緩慢。逐步細化可以加快監控速度。MLMethd會產生一個可疑方法（relmethds）列表，這些方法會在失敗運行或類似運行中執行。

ML 回溯監控-MLBack： 識別 relmethds 中方法的回溯。首先對這些回溯中出現的每個方法進行監控，而不介入被調用的方法（邊步驟）。在類似運行或失敗運行中執行的方法不會受到監控（無法進行比較）。MLBack 包括 MLMethd。
在 Navit 示例中，我們考慮了五種不同的方法：

• update：根據 GPS 輸入數據更新當前車輛狀態。
• route： 代表路線計算。
• vehi： 代表車輛繪製方法。
• set： 更改繪製模式。
• draw： 調用繪製車輛指針。
  圖 4.17 展示了 Navit bug 的 MLBack 概念。每條黑線（或實線）代表一個受監控的方法。每條紅線（或虛線）代表一個未監控的方法。
  

圖 4.17 多級回溯 (MLBack) 監控

首先，重放會監控方法覆蓋範圍，並檢測到失敗運行中的繪製方法未命中。根據方法監控，檢測出與失敗運行類似的幾個運行。在MLBack 期間，在非失敗運行中調用 draw 的回溯中出現的方法被收集到relmethds中。在第二次重放過程中relmethds中的方法會在相似運行和失敗運行中受到監控，但不會步入被調用（或側步）的方法。在步入這些方法的過程中，會對局部變數和方法參數變數的值進行監控。MLBack 的結果是包含異常suspectmethd 的方法列表。方法update和vehi.在不進入邊步驟（此處為路由和設置）的情況下受到監控。這樣，與我們考慮的錯誤無關但需要大量操作的路由計算就不會受到監控。此外，不監控繪製，因為它只出現在相似運行中，而不出現在故障運行中（無法比較）。在vehi中計算angle+=360後，可以檢測到變數值的第一次異常。

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

圖 4.18 多級步驟 (MLStep) 監控

在這裡，還通過側步驟對方法車輛進行監控。這包括步入方法集（以及圖 4.18 中未顯示的一些其他方法）。在Navit的另一種實現中，方法集（或由 vehi.調用的另一個方法）可能包括 $$angle+=360$$ 的錯誤源代碼行，之後角度和懶惰之間的錯誤關係會被檢測到。

4.5.3 執行

本節介紹如何通過單步跳過每一行源代碼來監控回放中的一組運行（單步監控）。在源代碼層面，對運行中執行的每一行源代碼的變數值進行監控。在第二次重放中，SL和ML都需要這種實現方式。我們將展示如何實現方法級監控（方法覆蓋監控）。在方法層面，運行中已執行方法的覆蓋率受到監控。此外，我們還展示瞭如何使用GDB Python腳本實現MLBack和MLStep。

4.5.3.1 單步監控

清單8顯示了Navit示例的單步監控實現（考慮到GPS處理）。第 1-2行在源代碼中GPS處理開始和結束的位置設置斷點。如果到達處理開始的位置（第7行），則激活監控（第8行）。如果激活了監控，則會通過列印局部變數和參數變數來監控處理過程中的每一步（第13-14行）。通過執行 GDB step命令（第16行）到達被測軟體的下一行源代碼。

4.5.3.2 方法覆蓋監控

清單9顯示了 Navit示例方法覆蓋監控的實現（考慮到GPS處理）。第 1-2行在源代碼中GPS處理開始和結束的位置設置斷點。此外，在 Navit 軟體的每個方法上都設置了斷點（第5-6行）；它們在執行開始時被禁用（第7行）。如果到達處理開始的位置（第10行），監控將被激活（第11行），此外，Navit 軟體中每個方法的斷點也會被啟用（第12行）。如果只需監控已執行方法的覆蓋範圍，可在首次通過後禁用每個斷點（第 18-19 行）。

4.5.3.3 方法回溯監控

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

4.5.4 實驗

前面幾節介紹了動態驗證如何幫助開發人員分析錯誤的根源。在第 4.5.2.5 節中，我們介紹了加速監控這些分析的優化技術。我們在西門子測試套件的Replace工具中測試了多級監控 (ML) 概念。Replace程式有32個不同版本，並包含多個測試用例。我們測試了前 20 個版本中的 19 個，它們都包含一個錯誤（我們無法手動檢測第 19 個版本中的錯誤）。為了生成可能的隨機重放，我們實施了一個重放生成器，從西門子測試套件故障矩陣中的 5542 個測試用例中隨機選擇 99 個不會導致故障的測試用例。在重放的最後，我們添加了一個執行錯誤的失敗運行作為運行 100。為了隨機選擇測試用例，我們使用了 Python 隨機函數，每次生成的重放均使用 100 種子。我們生成了包含 200 個非失敗運行的第二個重放，以模擬雜訊（使用相同的種子 100）。我們將此重放作為非故障重放，用於第 4.5.2.2 節中介紹的故障運行檢測。4.5.2.2. 對於 SL，我們監控了 100 次重放運行的執行情況，收集源代碼行覆蓋率以及局部變數和參數變數的數值。對於 ML，我們根據方法覆蓋率檢測失敗運行。在此實施過程中，我們還使用了特定方法的出現次數來構建 hamming 詞（如第 4.5.2.3 節所述，使用 threshold=5）。此外，還根據方法覆蓋率確定了與失敗運行最相似的三個運行。在第二次重放中，考慮到行覆蓋率和變數關係，對故障運行和相似運行進行了監測和比較。我們發現，ML 監控比 SL 監控要快得多。圖 4.19 顯示了單級（SL）監控與多級（ML）監控 Replace 的運行時間對比（對於我們可以使用演算法檢測到相應錯誤的版本）。

圖 4.19 對替換進行多層次分析的監控運行時間
對於一般評估，只包括監控運行時間，因為分析監控結果的運行時間取決於分析類型。ML包括方法級的第一次重放監控和行級的第二次重放監控。ML和SL監控了失敗運行和三個最相似運行的delta計算的所有局部變數、參數和巨集。我們發現，ML監控比SL監控快得多。對於Replace，監控速度提高了varnothing 9.5倍。表4.8 顯示了SL和ML報告的可疑行數，以及不同Replace版本的失敗運行與三個相似運行之間的漢明距離。

delta-ML/SL示報告的可疑行計數。Fail Detect（失敗檢測）顯示是否能在方法層面上檢測到失敗運行。Dist. Meth. Detect顯示是否通過覆蓋率delta計算或變數關係delta計算檢測到有問題的線路。在6個版本（3、4、7、13、14、16）中，ML和SL檢測到的相似運行是相同的。在這些情況下，報告的可疑行也是相同的。在15次實驗中，SL和ML檢測到了該版本的所有錯誤，這些錯誤要麼指向覆蓋率Delta (Cov)，要麼指向變數關係Delta (Rel)。有四個錯誤報告間接指向了失敗（第 12 版--關係三角中多次出現 MAXPAT；第15版和第18版--錯誤行中其他變數的關係差異；第14版--if-clause 封閉行中的關係差異）。我們用其他四個版本的Replace（2、9、10、11）測試了我們的工具，但在這些測試中，我們用ML和SL進行的delta分析無法檢測到有錯誤的源代碼行。在這裡，錯誤主要是由if子句中訪問數組（僅在寄存器中可用）的謂詞引起的。Fail Detect一行顯示的是可以在方法級別檢測到失敗運行的版本。在第4.5.2.2節中介紹的優化輕量級分類中，第6、14