基于軟件運(yùn)行特征的故障檢測(cè)方法研究

王正陽(yáng)，王雅文,2

(1.北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876；2.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

0 引言

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

表1 Fortify掃描開(kāi)源程序的結(jié)果[9]

動(dòng)態(tài)分析技術(shù)主要通過(guò)動(dòng)態(tài)測(cè)試工具執(zhí)行被測(cè)程序，收集分析程序運(yùn)行時(shí)信息進(jìn)而發(fā)現(xiàn)或驗(yàn)證程序性質(zhì)。一般是通過(guò)插裝[10-11]的方式根據(jù)監(jiān)測(cè)需求在程序中插入一些探針函數(shù)，在不改變程序原有邏輯正確性以及完整性的基礎(chǔ)上，收集并分析程序運(yùn)行時(shí)信息如變量值、程序運(yùn)行路徑以及程序運(yùn)行時(shí)間等進(jìn)而檢驗(yàn)程序質(zhì)量，然而傳統(tǒng)動(dòng)態(tài)測(cè)試工具的故障檢測(cè)能力十分有限。

針對(duì)上述問(wèn)題，本文提出一種基于軟件運(yùn)行特征的故障檢測(cè)方法。核心思想是以動(dòng)態(tài)測(cè)試的方式，通過(guò)在軟件的執(zhí)行過(guò)程中監(jiān)控的程序狀態(tài)、系統(tǒng)狀態(tài)及執(zhí)行時(shí)間等軟件運(yùn)行信息對(duì)相應(yīng)故障模式進(jìn)行識(shí)別。首先通過(guò)對(duì)故障模式的分析構(gòu)建故障監(jiān)控探針插裝庫(kù)。再通過(guò)靜態(tài)分析識(shí)別故障監(jiān)控點(diǎn)，結(jié)合相應(yīng)的故障條件確定監(jiān)控內(nèi)容，在不改變?cè)写a邏輯的情況下，生成監(jiān)控探針插入到源程序中。以動(dòng)態(tài)測(cè)試的方式在程序運(yùn)行過(guò)程中自動(dòng)識(shí)別故障并在源程序中定位。該方法適用于邏輯復(fù)雜且可靠性要求高的軟件，是靜態(tài)方法的重要補(bǔ)充。

1 故障檢測(cè)的現(xiàn)狀

由于靜態(tài)分析中對(duì)于復(fù)雜的程序語(yǔ)句以及對(duì)于操作系統(tǒng)和庫(kù)函數(shù)調(diào)用的符號(hào)推理不夠精確導(dǎo)致靜態(tài)分析無(wú)法同時(shí)滿足可靠性和完備性，業(yè)界通常在靜態(tài)分析工具的效率與精度之間做出取舍，因此出現(xiàn)漏報(bào)的同時(shí)會(huì)出現(xiàn)大量的誤報(bào)。目前現(xiàn)有的靜態(tài)分析工具漏報(bào)率為9%～32% ，誤報(bào)率為35%～91%[12]。

對(duì)于靜態(tài)分析出現(xiàn)的大量誤報(bào)問(wèn)題，有很多針對(duì)誤報(bào)消除[13]技術(shù)的研究，文獻(xiàn)[14]提出了一種基于缺陷檢測(cè)系統(tǒng)的警報(bào)自動(dòng)聚類方法；文獻(xiàn)[15]在區(qū)間抽象域基礎(chǔ)上引入符號(hào)化三值邏輯抽象域，以支持表達(dá)變量間的邏輯關(guān)聯(lián)；文獻(xiàn)[16]提出了一種程序語(yǔ)義缺陷警報(bào)關(guān)聯(lián)的方法，通過(guò)挖掘警報(bào)間的深層次關(guān)聯(lián)信息建立警報(bào)關(guān)聯(lián)。這些技術(shù)有助于提升人工確認(rèn)的效率，但是仍然無(wú)法避免需要人工方式進(jìn)行確認(rèn)，因此開(kāi)發(fā)人員開(kāi)發(fā)軟件時(shí)使用靜態(tài)分析工具的意愿并不高。

動(dòng)態(tài)測(cè)試在運(yùn)行時(shí)所發(fā)現(xiàn)的代碼漏洞一定是真實(shí)存在的，不存在誤報(bào)情況[17]，傳統(tǒng)的動(dòng)態(tài)測(cè)試工具主要用于進(jìn)行覆蓋分析[18]，通過(guò)達(dá)到較高的測(cè)試覆蓋率保證軟件可靠性，然而對(duì)程序出現(xiàn)的故障沒(méi)有進(jìn)行分析確認(rèn)。

對(duì)于故障檢測(cè)技術(shù)的研究，無(wú)論是靜態(tài)方法還是動(dòng)態(tài)方法都已經(jīng)相對(duì)成熟，單純對(duì)靜態(tài)檢測(cè)方法或動(dòng)態(tài)檢測(cè)方法進(jìn)行改進(jìn)，沒(méi)有太大的提升空間。但是，動(dòng)靜結(jié)合的漏洞分析技術(shù)可以彌補(bǔ)互相的優(yōu)缺點(diǎn)，已經(jīng)成為目前研究的熱點(diǎn)。文獻(xiàn)[9]針對(duì)靜態(tài)分析報(bào)告的目標(biāo)程序中內(nèi)存泄漏的靜態(tài)警報(bào)，基于警報(bào)制導(dǎo)信息對(duì)目標(biāo)程序進(jìn)行混合執(zhí)行測(cè)試，結(jié)合動(dòng)態(tài)執(zhí)行的方式進(jìn)行故障確認(rèn)，然而該方法仍是通過(guò)靜態(tài)分析方式識(shí)別故障，對(duì)于邏輯復(fù)雜的軟件仍然難以避免誤報(bào)率較高的問(wèn)題，因此監(jiān)測(cè)軟件運(yùn)行時(shí)故障特征從而在動(dòng)態(tài)執(zhí)行時(shí)識(shí)別故障是一種新的思路，能夠有效彌補(bǔ)靜態(tài)分析的誤報(bào)問(wèn)題。

2 檢測(cè)軟件故障的插裝庫(kù)設(shè)計(jì)

2.1 故障模式

程序中出現(xiàn)的故障可能會(huì)導(dǎo)致程序崩潰或出現(xiàn)不可預(yù)料的錯(cuò)誤結(jié)果，大大降低軟件可靠性甚至?xí)a(chǎn)生嚴(yán)重后果。故障模式通常是由專業(yè)程序設(shè)計(jì)者以及專業(yè)測(cè)試人員總結(jié)出來(lái)經(jīng)常出現(xiàn)且具有一定模式的故障[19]，可以成為出現(xiàn)故障時(shí)故障原因的分析依據(jù)，也可用于軟件開(kāi)發(fā)時(shí)可靠性設(shè)計(jì)的依據(jù)。本文所研究的故障模式是在代碼上所體現(xiàn)出的一種錯(cuò)誤形式，當(dāng)具有某些特征的代碼被執(zhí)行時(shí)，會(huì)出現(xiàn)運(yùn)行時(shí)故障。因此故障模式可從出錯(cuò)的狀態(tài)上劃分為3類8種，如下。

1)導(dǎo)致錯(cuò)誤的程序狀態(tài)：在程序執(zhí)行過(guò)程中，表達(dá)式出現(xiàn)了非法的取值：

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

②數(shù)組越界模式——數(shù)組下標(biāo)表達(dá)式的取值超出上下界；

③非法計(jì)算模式——某些操作數(shù)或庫(kù)函數(shù)參數(shù)出現(xiàn)非法取值；

④緩沖區(qū)溢出模式——對(duì)目標(biāo)緩沖區(qū)的操作長(zhǎng)度超出其界限等。

2)導(dǎo)致錯(cuò)誤的系統(tǒng)狀態(tài)：在程序執(zhí)行過(guò)程中，分配到系統(tǒng)堆棧上的內(nèi)存出現(xiàn)了不正常的狀態(tài)：

⑤內(nèi)存泄漏[20]模式——被分配到堆棧上的內(nèi)存沒(méi)有及時(shí)釋放；

⑥資源泄漏模式——被分配到堆棧上的資源(文件、網(wǎng)絡(luò)、數(shù)據(jù)庫(kù))沒(méi)有及時(shí)釋放。

3)執(zhí)行時(shí)間異常：在程序執(zhí)行過(guò)程中，某些比較復(fù)雜的循環(huán)或函數(shù)的執(zhí)行時(shí)間超出預(yù)期：

⑦低效循環(huán)模式——循環(huán)結(jié)構(gòu)的執(zhí)行時(shí)間超出了預(yù)定的閾值；

⑧低效函數(shù)模式——函數(shù)調(diào)用的執(zhí)行時(shí)間超出了預(yù)定的閾值。

能夠體現(xiàn)故障模式出錯(cuò)時(shí)運(yùn)行環(huán)境狀態(tài)的代碼特征信息稱為故障特征，包括故障指令、故障對(duì)象和故障條件三部分。

1)故障指令：能夠觸發(fā)故障的程序指令，包括地址解引用操作、下標(biāo)操作、部分算術(shù)運(yùn)算操作符、以及部分內(nèi)存或算術(shù)運(yùn)算操作庫(kù)函數(shù)。

2)故障對(duì)象：程序中直接與故障指令相關(guān)的對(duì)象，如一個(gè)變量或表達(dá)式。

3)故障條件：對(duì)故障對(duì)象的約束，如表達(dá)式的取值范圍、內(nèi)存地址上的成對(duì)操作、函數(shù)或循環(huán)的執(zhí)行時(shí)間閾值。

2.2 擴(kuò)展的插裝庫(kù)

程序插裝技術(shù)最早是由文獻(xiàn)[10]于1979年提出的，程序插裝指的是在被測(cè)程序在保持原有代碼邏輯不發(fā)生改變的情況下，在程序中插入一些探針函數(shù)，通過(guò)分析探針函數(shù)在程序運(yùn)行時(shí)捕獲的運(yùn)行特征來(lái)獲得程序的控制流以及數(shù)據(jù)流信息。程序插裝的方式通常根據(jù)插裝對(duì)象的不同分為源代碼插裝和目標(biāo)代碼插裝。

源代碼插裝是最自然的插裝方式，通過(guò)對(duì)程序源文件進(jìn)行詞法分析、語(yǔ)法分析后，根據(jù)探針函數(shù)的功能確定在源代碼中的插裝位置，目標(biāo)代碼插裝技術(shù)不依賴程序源代碼和編程語(yǔ)言，通常是對(duì)目標(biāo)代碼進(jìn)行必要的分析以確定插裝位置，由于目標(biāo)代碼一般是可執(zhí)行的二進(jìn)制程序，因此人工插入代碼是很難實(shí)現(xiàn)的，一般通過(guò)調(diào)用對(duì)應(yīng)插裝工具提供的API實(shí)現(xiàn)對(duì)目標(biāo)代碼進(jìn)行插裝。

源代碼插裝的缺點(diǎn)主要是依賴源程序的編譯語(yǔ)言，且對(duì)程序源代碼分析工作量較大。但是由于對(duì)源文件進(jìn)行了較為完整的靜態(tài)分析，能夠獲得更多的語(yǔ)義信息，插裝點(diǎn)較為準(zhǔn)確，插入的探針在編譯時(shí)也會(huì)被當(dāng)作源代碼進(jìn)行編譯優(yōu)化，因此本文采用源代碼插裝。

傳統(tǒng)的動(dòng)態(tài)測(cè)試工具大多只是簡(jiǎn)單追求高測(cè)試覆蓋率，其插裝過(guò)程一般是按照所選取的覆蓋準(zhǔn)則根據(jù)獲得的控制流圖在程序中插入覆蓋監(jiān)控探針，根據(jù)輸入的測(cè)試用例進(jìn)行動(dòng)態(tài)執(zhí)行。在程序動(dòng)態(tài)運(yùn)行時(shí)，通過(guò)覆蓋監(jiān)控探針?lè)祷氐男畔⒔y(tǒng)計(jì)測(cè)試覆蓋率或是進(jìn)行代碼執(zhí)行頻度分析。本文的基于軟件運(yùn)行特征的故障檢測(cè)方法除了支持傳統(tǒng)的覆蓋分析，為支持故障的動(dòng)態(tài)檢測(cè)，研究設(shè)計(jì)了能夠檢測(cè)故障的探針函數(shù)。

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

基于前文故障模式與軟件運(yùn)行特征的研究具體設(shè)計(jì)如下八種相應(yīng)的故障監(jiān)控探針：

1)空指針引用故障監(jiān)控探針：探針收集指針表達(dá)式和位置信息，約束指針表達(dá)式取值為非NULL，若該指針表達(dá)式出現(xiàn)等于NULL的狀態(tài)時(shí)識(shí)別故障；

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

3)數(shù)組越界故障監(jiān)控探針：探針收集被監(jiān)控?cái)?shù)組的數(shù)組下界、數(shù)組上界、數(shù)組下標(biāo)的算術(shù)表達(dá)式和位置信息，約束數(shù)組下標(biāo)算術(shù)表達(dá)式處于數(shù)組上下界之間，若數(shù)組下標(biāo)算術(shù)表達(dá)式取值超出該范圍則識(shí)別故障；

4)緩沖區(qū)溢出故障監(jiān)控探針：探針收集目標(biāo)緩沖區(qū)長(zhǎng)度、源緩沖區(qū)地址和位置信息，約束源緩沖區(qū)地址長(zhǎng)度不大于目標(biāo)緩沖區(qū)長(zhǎng)度，若超出該范圍則識(shí)別故障；

5)內(nèi)存泄漏故障監(jiān)控探針：探針收集分配或釋放操作標(biāo)志、操作的內(nèi)存地址和位置信息，在程序退出后，內(nèi)存操作文件中對(duì)相同地址的操作應(yīng)該配對(duì)，否則識(shí)別故障；

6)資源泄漏故障監(jiān)控探針：探針收集分配或釋放操作標(biāo)志、操作的資源地址和位置信息，在程序退出后，內(nèi)存操作文件中對(duì)相同地址的操作應(yīng)該配對(duì)，否則識(shí)別故障；

7)低效循環(huán)故障監(jiān)控探針：探針收集進(jìn)入或退出循環(huán)標(biāo)志、時(shí)間戳、限定時(shí)間和位置信息，在退出循環(huán)后，約束退出和進(jìn)入循環(huán)的時(shí)間差應(yīng)不大于限定時(shí)間，否則識(shí)別故障；

8)低效函數(shù)故障監(jiān)控探針：探針收集進(jìn)入或退出函數(shù)標(biāo)志、時(shí)間戳、限定時(shí)間和位置信息，在退出函數(shù)后，約束退出和進(jìn)入函數(shù)的時(shí)間差應(yīng)不大于限定時(shí)間，否則識(shí)別故障。

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

故障監(jiān)控探針需要通過(guò)程序插裝技術(shù)插入在源程序中的相應(yīng)監(jiān)控位置，故障監(jiān)控點(diǎn)的位置判定則首先需要通過(guò)對(duì)故障模式的分析構(gòu)建故障模型庫(kù)，包含相關(guān)故障指令、故障對(duì)象及故障條件等內(nèi)容。其中，故障指令和故障對(duì)象可以用于定位監(jiān)控點(diǎn)。之后對(duì)于識(shí)別到相應(yīng)故障指令的監(jiān)控點(diǎn)，需要結(jié)合對(duì)應(yīng)故障對(duì)象以及故障條件，以插裝庫(kù)中的對(duì)應(yīng)故障監(jiān)控探針格式插入到源程序中。最后，故障監(jiān)控探針在程序的執(zhí)行過(guò)程中搜集程序狀態(tài)、系統(tǒng)狀態(tài)和執(zhí)行時(shí)間等信息來(lái)識(shí)別故障，并定位于源程序中。

3.1 基于故障特征的程序插裝設(shè)計(jì)

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

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

不同故障對(duì)應(yīng)的故障監(jiān)控探針插裝設(shè)計(jì)如下：

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

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

3)數(shù)組越界故障監(jiān)控探針插裝點(diǎn)位于數(shù)組成員引用操作之前，從檢索到的故障觸發(fā)指令對(duì)應(yīng)的語(yǔ)句中提取故障關(guān)聯(lián)對(duì)象，即數(shù)組下標(biāo)表達(dá)式，同時(shí)從符號(hào)表中提取相關(guān)數(shù)組的上下界作為約束條件；

4)緩沖區(qū)溢出故障監(jiān)控探針插裝點(diǎn)位于strcat、strcpy、strncpy、strcmp、strncmp等對(duì)緩沖區(qū)進(jìn)行操作的庫(kù)函數(shù)之前，從檢索到的故障觸發(fā)指令對(duì)應(yīng)的語(yǔ)句中提取故障關(guān)聯(lián)對(duì)象，即源緩沖區(qū)地址，同時(shí)計(jì)算目標(biāo)緩沖區(qū)的可用長(zhǎng)度作為約束條件；

5)內(nèi)存泄漏故障監(jiān)控探針插裝點(diǎn)位于malloc、calloc、realloc等具有內(nèi)存分配特性的庫(kù)函數(shù)之前，從檢索到的故障觸發(fā)指令對(duì)應(yīng)的語(yǔ)句中提取故障關(guān)聯(lián)對(duì)象，即被分配內(nèi)存的地址標(biāo)識(shí)符；其次，檢索free、delete等具有內(nèi)存釋放特性的庫(kù)函數(shù)并在這些函數(shù)調(diào)用前插入探針；

6)資源泄漏故障監(jiān)控探針插裝點(diǎn)位于fopen、socket、accept等資源分配函數(shù)之前，從檢索到的故障觸發(fā)指令對(duì)應(yīng)的語(yǔ)句中提取故障關(guān)聯(lián)對(duì)象，即被分配資源的地址標(biāo)識(shí)符；其次，檢索與分配資源對(duì)應(yīng)的資源關(guān)閉函數(shù)并在這些函數(shù)調(diào)用前插入探針；

7)低效循環(huán)故障監(jiān)控探針插裝點(diǎn)位于while、for、do等循環(huán)結(jié)構(gòu)開(kāi)始之前以及循環(huán)結(jié)構(gòu)結(jié)束位置之后；

8)低效函數(shù)故障監(jiān)控探針插裝點(diǎn)位于每個(gè)函數(shù)的入口處第一條語(yǔ)句之前和函數(shù)返回語(yǔ)句之前。

3.2 故障監(jiān)控探針插裝算法

針對(duì)本文研究的故障模式，根據(jù)對(duì)應(yīng)故障觸發(fā)指令定位其在程序中的插裝點(diǎn)，主要通過(guò)遍歷源程序靜態(tài)分析生成的抽象語(yǔ)法樹(shù)識(shí)別程序中的故障指令搜索故障監(jiān)控探針插裝點(diǎn)，并根據(jù)圖1的插裝流程提取需要監(jiān)控的故障對(duì)象在源程序中生成探針函數(shù)得到插裝后的程序，在程序執(zhí)行過(guò)程中收集探針?lè)祷匦畔z測(cè)故障。

算法1:描述了故障監(jiān)控探針插裝點(diǎn)定位算法，該算法將源程序通過(guò)靜態(tài)分析生成的抽象語(yǔ)法樹(shù)的根節(jié)點(diǎn)root以及初始化為空的插裝點(diǎn)集合instru_set作為輸入，輸出為確認(rèn)后的故障監(jiān)控探針插裝點(diǎn)集合instru_set。

故障監(jiān)控探針插裝點(diǎn)定位算法中所用到的定義如下：

ASTNode：抽象語(yǔ)法樹(shù)節(jié)點(diǎn)父類。

function_definition：函數(shù)體定義節(jié)點(diǎn)。

return_statement：return語(yǔ)句節(jié)點(diǎn)。

iteration_statement：循環(huán)體節(jié)點(diǎn)。

simple_statement：簡(jiǎn)單語(yǔ)句節(jié)點(diǎn)。

expression：表達(dá)式節(jié)點(diǎn)。

getType(node)：獲得節(jié)點(diǎn)node的節(jié)點(diǎn)類型。

getChildrenNodes(node)：獲得node節(jié)點(diǎn)的所有子節(jié)點(diǎn)。

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

addLEFOut(instru_set, node)：將返回語(yǔ)句前的低效函數(shù)故障監(jiān)控探針插裝點(diǎn)加入插裝點(diǎn)集合instru_set中。

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

check(node)：檢查簡(jiǎn)單語(yǔ)句節(jié)點(diǎn)node是否包含4種程序狀態(tài)出錯(cuò)故障觸發(fā)指令、內(nèi)存分配或釋放指令以及資源分配釋或放指令。

checkExpression(node)：檢查表達(dá)式節(jié)點(diǎn)node是否包含4種程序狀態(tài)出錯(cuò)故障觸發(fā)指令、內(nèi)存分配或釋放指令以及資源分配釋或放指令。

addFault(instru_set, node)：根據(jù)節(jié)點(diǎn)node中包含的故障指令，確定故障監(jiān)控探針類型并將對(duì)應(yīng)故障監(jiān)控探針插裝點(diǎn)加入插裝點(diǎn)集合instru_set中。

算法1：故障監(jiān)控探針插裝點(diǎn)定位算法

輸入：root //源程序的抽象語(yǔ)法樹(shù)根節(jié)點(diǎn)

輸出：instru_set //故障監(jiān)控探針插裝點(diǎn)集合

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. }

算法主要思想是通過(guò)深度優(yōu)先遍歷源程序抽象語(yǔ)法樹(shù)，識(shí)別對(duì)應(yīng)的故障指令確認(rèn)故障插裝位置。算法1～7行通過(guò)判斷語(yǔ)法樹(shù)節(jié)點(diǎn)類型識(shí)別函數(shù)體和循環(huán)體，定位低效函數(shù)和低效循環(huán)故障監(jiān)控探針插裝點(diǎn)；8～13行判斷簡(jiǎn)單語(yǔ)句或者表達(dá)式中是否包含空指針引用、非法計(jì)算、數(shù)組越界、緩沖區(qū)溢出以及內(nèi)存泄漏和資源泄漏的故障觸發(fā)指令從而生成對(duì)應(yīng)故障監(jiān)控探針插裝點(diǎn)。對(duì)于表達(dá)式節(jié)點(diǎn)需要拆分邏輯表達(dá)式，檢查所有子表達(dá)式是否包含故障指令。14～15行遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)，對(duì)子節(jié)點(diǎn)進(jìn)行故障監(jiān)控探針插裝點(diǎn)定位。

4 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)采用了CTS自帶的 Norton 命令的 Unix 環(huán)境復(fù)制版開(kāi)源項(xiàng)目deco，項(xiàng)目包含的10個(gè)C文件如表2所示。為驗(yàn)證本文提出的方法，對(duì)被測(cè)程序進(jìn)行了故障注入。其次，為了能夠有效觸發(fā)故障，通過(guò)CTS中人工輸入測(cè)試用例的方式進(jìn)行實(shí)驗(yàn)。

表2 被測(cè)程序

為準(zhǔn)確識(shí)別本文提及的兩種執(zhí)行時(shí)間異常故障，在程序中將進(jìn)程掛起5秒。通過(guò)在程序執(zhí)行后收集的故障監(jiān)控探針函數(shù)返回信息可以得到故障檢測(cè)結(jié)果，通常情況下，對(duì)于單次的測(cè)試用例生成是無(wú)法覆蓋程序中所有路徑，因此實(shí)驗(yàn)需要輸入大量的測(cè)試用例從而達(dá)到覆蓋所有觸發(fā)故障的路徑，但是可能會(huì)導(dǎo)致收集的信息包含了同一故障的多次記錄。因此，在分析故障監(jiān)控探針信息時(shí)，通過(guò)收集到的故障位置信息進(jìn)行故障去重，將去重后的故障作為實(shí)驗(yàn)統(tǒng)計(jì)的最終結(jié)果。根據(jù)3種出錯(cuò)狀態(tài)分別統(tǒng)計(jì)以本文方法檢測(cè)出的故障，實(shí)驗(yàn)結(jié)果如表3所示。

表3 故障檢測(cè)結(jié)果

實(shí)驗(yàn)結(jié)果表明本文所研究的八種故障模式均可通過(guò)該方法進(jìn)行有效檢測(cè)。根據(jù)實(shí)驗(yàn)所檢測(cè)出的故障，在注入故障的程序中定位分析后發(fā)現(xiàn)所報(bào)故障均為真實(shí)存在且故障定位準(zhǔn)確，不存在誤報(bào)情況，該方法可有效彌補(bǔ)靜態(tài)分析對(duì)于邏輯復(fù)雜軟件進(jìn)行故障檢測(cè)時(shí)由于缺少運(yùn)行時(shí)信息導(dǎo)致不精確的區(qū)間運(yùn)算和符號(hào)執(zhí)行產(chǎn)生的誤報(bào)問(wèn)題，大大減少了對(duì)于誤報(bào)問(wèn)題人工確認(rèn)的成本。部分故障監(jiān)控探針插裝點(diǎn)位于程序中不可達(dá)路徑上，無(wú)法通過(guò)生成測(cè)試用例執(zhí)行覆蓋到，已通過(guò)CTS自帶的不可達(dá)路徑[24]判斷功能進(jìn)行識(shí)別，實(shí)驗(yàn)符合預(yù)期。

5 結(jié)束語(yǔ)

本文針對(duì)靜態(tài)分析出現(xiàn)大量誤報(bào)的問(wèn)題，結(jié)合靜態(tài)分析和動(dòng)態(tài)測(cè)試提出了一種基于軟件運(yùn)行特征的故障檢測(cè)方法，通過(guò)研究按照出錯(cuò)狀態(tài)劃分為三類的八種故障模式，基于動(dòng)態(tài)測(cè)試的插裝技術(shù)，在傳統(tǒng)用于覆蓋分析的插裝庫(kù)中擴(kuò)充了用于監(jiān)控故障的探針函數(shù)。通過(guò)研究八種故障模式對(duì)應(yīng)的故障特征，設(shè)計(jì)了相應(yīng)的插裝算法。該方法是對(duì)靜態(tài)分析方法的重要補(bǔ)充，通過(guò)引入動(dòng)態(tài)分析的方式在程序?qū)嶋H運(yùn)行時(shí)收集程序路徑上下文真實(shí)信息，避免了使用純靜態(tài)分析進(jìn)行故障檢測(cè)時(shí)完整路徑上下文分析的組合爆炸[25]導(dǎo)致分析不準(zhǔn)確的問(wèn)題，有效彌補(bǔ)了靜態(tài)分析高誤報(bào)問(wèn)題，可適用于邏輯較為復(fù)雜的程序。

該方法可通過(guò)收集觸發(fā)故障對(duì)應(yīng)的測(cè)試用例進(jìn)行故障復(fù)現(xiàn)，幫助測(cè)試開(kāi)發(fā)人員進(jìn)行故障定位和修復(fù)。后續(xù)可以通過(guò)更精確的靜態(tài)分析對(duì)故障監(jiān)控探針插裝點(diǎn)進(jìn)行約簡(jiǎn)，但可能會(huì)導(dǎo)致插裝性能下降，可以根據(jù)不同需求進(jìn)行平衡。由于動(dòng)態(tài)測(cè)試十分依賴輸入的測(cè)試用例，不完備的測(cè)試用例會(huì)導(dǎo)致漏報(bào)[26]問(wèn)題，因此觸發(fā)故障導(dǎo)向的測(cè)試用例生成技術(shù)也將成為后續(xù)研究的方向。