基于軟件運行特征的故障檢測方法研究

王正陽，王雅文,2

(1.北京郵電大學 網絡與交換技術國家重點實驗室，北京 100876；2.桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004)

0 引言

軟件測試[1]是發現軟件故障、提高軟件可靠性的重要手段，源代碼分析可以根據是否執行被測程序分為靜態分析[2-4]和動態分析[5-7]兩種方式。靜態方法不需要執行被測程序，而是掃描被分析程序的源代碼，通過使用符號執行技術進行靜態路徑分析、區間運算并根據設計的缺陷模式狀態機檢測代碼中可能存在的非功能性故障。以靜態分析工具HPFortify[8]為例，通過靜態掃描得到的缺陷數量龐大，如表1所示，其中不可避免地包含了分析誤報，程序通過靜態分析出現的誤報需要專業的測試人員進行人工缺陷確認，對于工程級別的代碼，所需要人工確認的缺陷數量可能是十分龐大的，反而降低了靜態分析的檢測效率。

表1 Fortify掃描開源程序的結果[9]

動態分析技術主要通過動態測試工具執行被測程序，收集分析程序運行時信息進而發現或驗證程序性質。一般是通過插裝[10-11]的方式根據監測需求在程序中插入一些探針函數，在不改變程序原有邏輯正確性以及完整性的基礎上，收集并分析程序運行時信息如變量值、程序運行路徑以及程序運行時間等進而檢驗程序質量，然而傳統動態測試工具的故障檢測能力十分有限。

針對上述問題，本文提出一種基于軟件運行特征的故障檢測方法。核心思想是以動態測試的方式，通過在軟件的執行過程中監控的程序狀態、系統狀態及執行時間等軟件運行信息對相應故障模式進行識別。首先通過對故障模式的分析構建故障監控探針插裝庫。再通過靜態分析識別故障監控點，結合相應的故障條件確定監控內容，在不改變原有代碼邏輯的情況下，生成監控探針插入到源程序中。以動態測試的方式在程序運行過程中自動識別故障并在源程序中定位。該方法適用于邏輯復雜且可靠性要求高的軟件，是靜態方法的重要補充。

1 故障檢測的現狀

由于靜態分析中對于復雜的程序語句以及對于操作系統和庫函數調用的符號推理不夠精確導致靜態分析無法同時滿足可靠性和完備性，業界通常在靜態分析工具的效率與精度之間做出取舍，因此出現漏報的同時會出現大量的誤報。目前現有的靜態分析工具漏報率為9%～32% ，誤報率為35%～91%[12]。

對于靜態分析出現的大量誤報問題，有很多針對誤報消除[13]技術的研究，文獻[14]提出了一種基于缺陷檢測系統的警報自動聚類方法；文獻[15]在區間抽象域基礎上引入符號化三值邏輯抽象域，以支持表達變量間的邏輯關聯；文獻[16]提出了一種程序語義缺陷警報關聯的方法，通過挖掘警報間的深層次關聯信息建立警報關聯。這些技術有助于提升人工確認的效率，但是仍然無法避免需要人工方式進行確認，因此開發人員開發軟件時使用靜態分析工具的意愿并不高。

動態測試在運行時所發現的代碼漏洞一定是真實存在的，不存在誤報情況[17]，傳統的動態測試工具主要用于進行覆蓋分析[18]，通過達到較高的測試覆蓋率保證軟件可靠性，然而對程序出現的故障沒有進行分析確認。

對于故障檢測技術的研究，無論是靜態方法還是動態方法都已經相對成熟，單純對靜態檢測方法或動態檢測方法進行改進，沒有太大的提升空間。但是，動靜結合的漏洞分析技術可以彌補互相的優缺點，已經成為目前研究的熱點。文獻[9]針對靜態分析報告的目標程序中內存泄漏的靜態警報，基于警報制導信息對目標程序進行混合執行測試，結合動態執行的方式進行故障確認，然而該方法仍是通過靜態分析方式識別故障，對于邏輯復雜的軟件仍然難以避免誤報率較高的問題，因此監測軟件運行時故障特征從而在動態執行時識別故障是一種新的思路，能夠有效彌補靜態分析的誤報問題。

2 檢測軟件故障的插裝庫設計

2.1 故障模式

程序中出現的故障可能會導致程序崩潰或出現不可預料的錯誤結果，大大降低軟件可靠性甚至會產生嚴重后果。故障模式通常是由專業程序設計者以及專業測試人員總結出來經常出現且具有一定模式的故障[19]，可以成為出現故障時故障原因的分析依據，也可用于軟件開發時可靠性設計的依據。本文所研究的故障模式是在代碼上所體現出的一種錯誤形式，當具有某些特征的代碼被執行時，會出現運行時故障。因此故障模式可從出錯的狀態上劃分為3類8種，如下。

1)導致錯誤的程序狀態：在程序執行過程中，表達式出現了非法的取值：

①空指針引用模式——被解引用的指針表達式的取值等于NULL；

②數組越界模式——數組下標表達式的取值超出上下界；

③非法計算模式——某些操作數或庫函數參數出現非法取值；

④緩沖區溢出模式——對目標緩沖區的操作長度超出其界限等。

2)導致錯誤的系統狀態：在程序執行過程中，分配到系統堆棧上的內存出現了不正常的狀態：

⑤內存泄漏[20]模式——被分配到堆棧上的內存沒有及時釋放；

⑥資源泄漏模式——被分配到堆棧上的資源(文件、網絡、數據庫)沒有及時釋放。

3)執行時間異常：在程序執行過程中，某些比較復雜的循環或函數的執行時間超出預期：

⑦低效循環模式——循環結構的執行時間超出了預定的閾值；

⑧低效函數模式——函數調用的執行時間超出了預定的閾值。

能夠體現故障模式出錯時運行環境狀態的代碼特征信息稱為故障特征，包括故障指令、故障對象和故障條件三部分。

1)故障指令：能夠觸發故障的程序指令，包括地址解引用操作、下標操作、部分算術運算操作符、以及部分內存或算術運算操作庫函數。

2)故障對象：程序中直接與故障指令相關的對象，如一個變量或表達式。

3)故障條件：對故障對象的約束，如表達式的取值范圍、內存地址上的成對操作、函數或循環的執行時間閾值。

2.2 擴展的插裝庫

程序插裝技術最早是由文獻[10]于1979年提出的，程序插裝指的是在被測程序在保持原有代碼邏輯不發生改變的情況下，在程序中插入一些探針函數，通過分析探針函數在程序運行時捕獲的運行特征來獲得程序的控制流以及數據流信息。程序插裝的方式通常根據插裝對象的不同分為源代碼插裝和目標代碼插裝。

源代碼插裝是最自然的插裝方式，通過對程序源文件進行詞法分析、語法分析后，根據探針函數的功能確定在源代碼中的插裝位置，目標代碼插裝技術不依賴程序源代碼和編程語言，通常是對目標代碼進行必要的分析以確定插裝位置，由于目標代碼一般是可執行的二進制程序，因此人工插入代碼是很難實現的，一般通過調用對應插裝工具提供的API實現對目標代碼進行插裝。

源代碼插裝的缺點主要是依賴源程序的編譯語言，且對程序源代碼分析工作量較大。但是由于對源文件進行了較為完整的靜態分析，能夠獲得更多的語義信息，插裝點較為準確，插入的探針在編譯時也會被當作源代碼進行編譯優化，因此本文采用源代碼插裝。

傳統的動態測試工具大多只是簡單追求高測試覆蓋率，其插裝過程一般是按照所選取的覆蓋準則根據獲得的控制流圖在程序中插入覆蓋監控探針，根據輸入的測試用例進行動態執行。在程序動態運行時，通過覆蓋監控探針返回的信息統計測試覆蓋率或是進行代碼執行頻度分析。本文的基于軟件運行特征的故障檢測方法除了支持傳統的覆蓋分析，為支持故障的動態檢測，研究設計了能夠檢測故障的探針函數。

故障觸發的條件是程序執行到故障點時，故障對象的取值滿足故障條件的約束，因此檢測故障的探針首先需要插入到程序中可能觸發故障的位置，通過動態測試執行到插裝點時收集程序執行到故障點時的相關運行特征，判斷收集到的運行特征是否滿足對應的故障約束條件從而達到識別故障并定位的功能。軟件運行特征對于描述軟件行為具有重要作用[21]。本文所涉及的軟件運行特征可根據研究的故障模式大致分為程序狀態、系統狀態以及執行時間三類。程序狀態包括程序中可見變量的類型和取值情況、函數調用情況等，系統狀態主要為程序執行過程中的系統資源使用情況，執行時間包括函數執行時間、循環執行時間以及語句序列執行時間等。

基于前文故障模式與軟件運行特征的研究具體設計如下八種相應的故障監控探針：

1)空指針引用故障監控探針：探針收集指針表達式和位置信息，約束指針表達式取值為非NULL，若該指針表達式出現等于NULL的狀態時識別故障；

2)非法計算故障監控探針：探針收集敏感操作符或庫函數名稱、算術表達式和位置信息，針對傳入敏感操作符或庫函數名稱，約束算術表達式的取值，若該算術表達式的取值與約束相悖則識別故障；

3)數組越界故障監控探針：探針收集被監控數組的數組下界、數組上界、數組下標的算術表達式和位置信息，約束數組下標算術表達式處于數組上下界之間，若數組下標算術表達式取值超出該范圍則識別故障；

4)緩沖區溢出故障監控探針：探針收集目標緩沖區長度、源緩沖區地址和位置信息，約束源緩沖區地址長度不大于目標緩沖區長度，若超出該范圍則識別故障；

5)內存泄漏故障監控探針：探針收集分配或釋放操作標志、操作的內存地址和位置信息，在程序退出后，內存操作文件中對相同地址的操作應該配對，否則識別故障；

6)資源泄漏故障監控探針：探針收集分配或釋放操作標志、操作的資源地址和位置信息，在程序退出后，內存操作文件中對相同地址的操作應該配對，否則識別故障；

7)低效循環故障監控探針：探針收集進入或退出循環標志、時間戳、限定時間和位置信息，在退出循環后，約束退出和進入循環的時間差應不大于限定時間，否則識別故障；

8)低效函數故障監控探針：探針收集進入或退出函數標志、時間戳、限定時間和位置信息，在退出函數后，約束退出和進入函數的時間差應不大于限定時間，否則識別故障。

3 基于故障特征的程序插裝

故障監控探針需要通過程序插裝技術插入在源程序中的相應監控位置，故障監控點的位置判定則首先需要通過對故障模式的分析構建故障模型庫，包含相關故障指令、故障對象及故障條件等內容。其中，故障指令和故障對象可以用于定位監控點。之后對于識別到相應故障指令的監控點，需要結合對應故障對象以及故障條件，以插裝庫中的對應故障監控探針格式插入到源程序中。最后，故障監控探針在程序的執行過程中搜集程序狀態、系統狀態和執行時間等信息來識別故障，并定位于源程序中。

3.1 基于故障特征的程序插裝設計

基于故障特征的程序插裝主要分為如圖1所示3個階段：首先源程序進行靜態分析，通過在靜態分析過程中構建的如抽象語法樹(Abstract Syntax Tree， AST)、控制流圖以及符號表等程序抽象模型[22]中搜索故障觸發指令，定位程序中所有與故障模式相關的位置。之后進行故障關聯信息提取，從定位處提取故障模式相應關聯對象。最后基于相應故障模式的觸發條件，面向關聯對象生成監控探針插入到源程序中。

圖1 基于故障特征的程序插裝流程

不同故障對應的故障監控探針插裝設計如下：

1)空指針引用故障監控探針插裝點位于空指針故障模式的觸發指令之前，故障觸發操作符包括對成員引用->、內容引用*、數組引用[]，故障觸發庫函數包括fclose、fopen、strcat、strcpy、strcmp等約束空參數的函數引用；

2)非法計算故障監控探針插裝點位于非法計算故障模式的觸發指令之前，故障觸發操作符包括%、/、%=、/=等對右操作數有限制要求的，故障觸發庫函數包括asin、acos、atan、div、fmod、ldiv、log、log10、sqrt等對參數有限制要求的算術運算函數；

3)數組越界故障監控探針插裝點位于數組成員引用操作之前，從檢索到的故障觸發指令對應的語句中提取故障關聯對象，即數組下標表達式，同時從符號表中提取相關數組的上下界作為約束條件；

4)緩沖區溢出故障監控探針插裝點位于strcat、strcpy、strncpy、strcmp、strncmp等對緩沖區進行操作的庫函數之前，從檢索到的故障觸發指令對應的語句中提取故障關聯對象，即源緩沖區地址，同時計算目標緩沖區的可用長度作為約束條件；

5)內存泄漏故障監控探針插裝點位于malloc、calloc、realloc等具有內存分配特性的庫函數之前，從檢索到的故障觸發指令對應的語句中提取故障關聯對象，即被分配內存的地址標識符；其次，檢索free、delete等具有內存釋放特性的庫函數并在這些函數調用前插入探針；

6)資源泄漏故障監控探針插裝點位于fopen、socket、accept等資源分配函數之前，從檢索到的故障觸發指令對應的語句中提取故障關聯對象，即被分配資源的地址標識符；其次，檢索與分配資源對應的資源關閉函數并在這些函數調用前插入探針；

7)低效循環故障監控探針插裝點位于while、for、do等循環結構開始之前以及循環結構結束位置之后；

8)低效函數故障監控探針插裝點位于每個函數的入口處第一條語句之前和函數返回語句之前。

3.2 故障監控探針插裝算法

針對本文研究的故障模式，根據對應故障觸發指令定位其在程序中的插裝點，主要通過遍歷源程序靜態分析生成的抽象語法樹識別程序中的故障指令搜索故障監控探針插裝點，并根據圖1的插裝流程提取需要監控的故障對象在源程序中生成探針函數得到插裝后的程序，在程序執行過程中收集探針返回信息檢測故障。

算法1:描述了故障監控探針插裝點定位算法，該算法將源程序通過靜態分析生成的抽象語法樹的根節點root以及初始化為空的插裝點集合instru_set作為輸入，輸出為確認后的故障監控探針插裝點集合instru_set。

故障監控探針插裝點定位算法中所用到的定義如下：

ASTNode：抽象語法樹節點父類。

function_definition：函數體定義節點。

return_statement：return語句節點。

iteration_statement：循環體節點。

simple_statement：簡單語句節點。

expression：表達式節點。

getType(node)：獲得節點node的節點類型。

getChildrenNodes(node)：獲得node節點的所有子節點。

addLEFIn(instru_set, node)：將函數入口處的低效函數故障監控探針插裝點加入插裝點集合instru_set中。

addLEFOut(instru_set, node)：將返回語句前的低效函數故障監控探針插裝點加入插裝點集合instru_set中。

addLEC(instru_set, node)：將循環體之前以及之后的低效循環故障監控探針插裝點加入插裝點集合instru_set中。

check(node)：檢查簡單語句節點node是否包含4種程序狀態出錯故障觸發指令、內存分配或釋放指令以及資源分配釋或放指令。

checkExpression(node)：檢查表達式節點node是否包含4種程序狀態出錯故障觸發指令、內存分配或釋放指令以及資源分配釋或放指令。

addFault(instru_set, node)：根據節點node中包含的故障指令，確定故障監控探針類型并將對應故障監控探針插裝點加入插裝點集合instru_set中。

算法1：故障監控探針插裝點定位算法

輸入：root //源程序的抽象語法樹根節點

輸出：instru_set //故障監控探針插裝點集合

1. instru (ASTNode node, List instru_set) {

2. if getType (node) == function_definition then

3. addLEFIn (instru_set, node);

4. if getType (node) == return_statement then

5. addLEFOut (instru_set, node);

6. if getType (node) == iteration_statement then

7. addLEC (instru_set, node);

8. if getType (node) == simple_statement then

9. if (check (node)) then

10. addFault (instru_set, node);

11. if getType (node) == expression then

12. if (checkExpression (node)) then

13. addFault (instru_set, node);

14. for each n getChildrenNodes (node)

15. instru (n, instru_set);

16. }

算法主要思想是通過深度優先遍歷源程序抽象語法樹，識別對應的故障指令確認故障插裝位置。算法1～7行通過判斷語法樹節點類型識別函數體和循環體，定位低效函數和低效循環故障監控探針插裝點；8～13行判斷簡單語句或者表達式中是否包含空指針引用、非法計算、數組越界、緩沖區溢出以及內存泄漏和資源泄漏的故障觸發指令從而生成對應故障監控探針插裝點。對于表達式節點需要拆分邏輯表達式，檢查所有子表達式是否包含故障指令。14～15行遍歷當前節點的子節點，對子節點進行故障監控探針插裝點定位。

4 實驗結果與分析

前文已經介紹了基于故障特征的程序插裝技術，為驗證本文提出的基于軟件運行特征的故障檢測方法故障檢測能力，將該技術應用于代碼測試系統[23](Code Testing System， CTS)中進行實驗驗證，實驗環境為Ubuntu 12.04操作系統，配置AMD Ryzen 9 5900HX(3.30 GHz)處理器，8 GB內存以及512 GB SSD硬盤。

實驗采用了CTS自帶的 Norton 命令的 Unix 環境復制版開源項目deco，項目包含的10個C文件如表2所示。為驗證本文提出的方法，對被測程序進行了故障注入。其次，為了能夠有效觸發故障，通過CTS中人工輸入測試用例的方式進行實驗。

表2 被測程序

為準確識別本文提及的兩種執行時間異常故障，在程序中將進程掛起5秒。通過在程序執行后收集的故障監控探針函數返回信息可以得到故障檢測結果，通常情況下，對于單次的測試用例生成是無法覆蓋程序中所有路徑，因此實驗需要輸入大量的測試用例從而達到覆蓋所有觸發故障的路徑，但是可能會導致收集的信息包含了同一故障的多次記錄。因此，在分析故障監控探針信息時，通過收集到的故障位置信息進行故障去重，將去重后的故障作為實驗統計的最終結果。根據3種出錯狀態分別統計以本文方法檢測出的故障，實驗結果如表3所示。

表3 故障檢測結果

實驗結果表明本文所研究的八種故障模式均可通過該方法進行有效檢測。根據實驗所檢測出的故障，在注入故障的程序中定位分析后發現所報故障均為真實存在且故障定位準確，不存在誤報情況，該方法可有效彌補靜態分析對于邏輯復雜軟件進行故障檢測時由于缺少運行時信息導致不精確的區間運算和符號執行產生的誤報問題，大大減少了對于誤報問題人工確認的成本。部分故障監控探針插裝點位于程序中不可達路徑上，無法通過生成測試用例執行覆蓋到，已通過CTS自帶的不可達路徑[24]判斷功能進行識別，實驗符合預期。

5 結束語

本文針對靜態分析出現大量誤報的問題，結合靜態分析和動態測試提出了一種基于軟件運行特征的故障檢測方法，通過研究按照出錯狀態劃分為三類的八種故障模式，基于動態測試的插裝技術，在傳統用于覆蓋分析的插裝庫中擴充了用于監控故障的探針函數。通過研究八種故障模式對應的故障特征，設計了相應的插裝算法。該方法是對靜態分析方法的重要補充，通過引入動態分析的方式在程序實際運行時收集程序路徑上下文真實信息，避免了使用純靜態分析進行故障檢測時完整路徑上下文分析的組合爆炸[25]導致分析不準確的問題，有效彌補了靜態分析高誤報問題，可適用于邏輯較為復雜的程序。

該方法可通過收集觸發故障對應的測試用例進行故障復現，幫助測試開發人員進行故障定位和修復。后續可以通過更精確的靜態分析對故障監控探針插裝點進行約簡，但可能會導致插裝性能下降，可以根據不同需求進行平衡。由于動態測試十分依賴輸入的測試用例，不完備的測試用例會導致漏報[26]問題，因此觸發故障導向的測試用例生成技術也將成為后續研究的方向。