測(cè)試用例執(zhí)行軌跡分析的故障定位方法

曹 迅,周寬久

(大連理工大學(xué) 軟件學(xué)院,遼寧 大連 116620)

1 引 言

隨著計(jì)算機(jī)軟件在現(xiàn)代社會(huì)中的廣泛應(yīng)用,軟件的代碼量和復(fù)雜程度都不斷提高.大型系統(tǒng)軟件的設(shè)計(jì)過(guò)程中,由于設(shè)計(jì)缺陷或者程序員的編碼失誤而引入的軟件故障無(wú)法避免.據(jù)統(tǒng)計(jì),軟件測(cè)試和軟件調(diào)試的花費(fèi)已經(jīng)占到軟件生命周期的50%以上[1].程序調(diào)試(Program Debugging)技術(shù)作為一種定位并修復(fù)軟件故障的技術(shù),在軟件開(kāi)發(fā)生命周期中的地位重要性越來(lái)越高.程序調(diào)試通常包括故障定位(Fault Localization)和故障修復(fù)(Fault Recovery)兩方面,其中如何準(zhǔn)確并且快速地定位故障源已經(jīng)成為軟件設(shè)計(jì)中的主要難點(diǎn).高效的程序調(diào)試技術(shù)特別是軟件故障定位技術(shù),對(duì)于節(jié)約軟件開(kāi)發(fā)成本、提高軟件產(chǎn)品質(zhì)量有著十分重要的意義.

國(guó)內(nèi)外關(guān)于軟件故障定位技術(shù)的研究已經(jīng)持續(xù)了近30年,科研人員從不同角度和尺度提出了許多故障定位的方案,現(xiàn)有的技術(shù)大致可以分為:

基于程序頻譜的故障定位(Spectrum-based Fault Localization)通過(guò)執(zhí)行測(cè)試用例獲得一組抽象的程序執(zhí)行軌跡(程序頻譜),通過(guò)分析程序頻譜從而定位軟件故障.Tarantula[2]技術(shù)最早將程序頻譜應(yīng)用于軟件故障定位,分別統(tǒng)計(jì)語(yǔ)句在失敗用例和成功用例中的執(zhí)行次數(shù),并賦予那些被更多錯(cuò)誤測(cè)試用例覆蓋的語(yǔ)句更高的懷疑程度.Ochiai[3]方法基于代碼塊定位故障源,同時(shí)還考慮了那些不會(huì)導(dǎo)致錯(cuò)誤結(jié)果的故障情形.DStar[4]方法基于相似度系數(shù)設(shè)計(jì)懷疑度計(jì)算公式,在定位多個(gè)故障時(shí)效果理想.此類(lèi)方法中,無(wú)論是語(yǔ)句級(jí)別還是代碼塊級(jí)別的懷疑度都可以通過(guò)設(shè)計(jì)或改良懷疑度計(jì)算公式來(lái)得到,實(shí)現(xiàn)時(shí)較為容易.另一方面,基于程序頻譜的故障定位將程序看成一個(gè)黑盒,并沒(méi)有考慮語(yǔ)句或者代碼塊之間的依賴(lài)關(guān)系.

基于統(tǒng)計(jì)方法的故障定位(Statistical-based Fault Localization)考慮故障語(yǔ)句與執(zhí)行結(jié)果的統(tǒng)計(jì)關(guān)系,通過(guò)建立程序語(yǔ)句或者代碼塊與執(zhí)行結(jié)果之間的統(tǒng)計(jì)學(xué)模型定位故障.Wong[5]等人根據(jù)覆蓋率信息構(gòu)造交叉表,通過(guò)卡方檢驗(yàn)計(jì)算語(yǔ)句與測(cè)試結(jié)果的從屬關(guān)系,從而得到懷疑度值.Hao[6]等人提出基于相似度感知的故障定位方法,將測(cè)試用例看作一個(gè)模糊集,從而減少相似測(cè)試用例對(duì)于故障定位結(jié)果的影響.Abreu[7]根據(jù)覆蓋關(guān)系計(jì)算組件(代碼塊)的錯(cuò)誤關(guān)系,使用貝葉斯方法計(jì)算代碼塊的懷疑度.Zhang[8]使用最小二乘法擬合狀態(tài)與測(cè)試結(jié)果之間的非線(xiàn)性關(guān)系,用平均標(biāo)準(zhǔn)偏差作為狀態(tài)的懷疑度值,該方法在正確樣本數(shù)較少時(shí)的優(yōu)勢(shì)明顯.基于概率統(tǒng)計(jì)的方法考慮到了測(cè)試用例之間、測(cè)試用例與測(cè)試結(jié)果之間、程序之間的關(guān)聯(lián)關(guān)系,但仍然沒(méi)有充分考慮程序內(nèi)部的依賴(lài)關(guān)系,同時(shí)統(tǒng)計(jì)模型多種多樣,設(shè)計(jì)和實(shí)驗(yàn)成本高.

基于模型的故障定位(Model-based Fault Localization)從模型角度描述程序和故障.謂詞模型[9]通過(guò)對(duì)謂詞在成功執(zhí)行和錯(cuò)誤執(zhí)行時(shí)的取值進(jìn)行建模,判斷謂詞出錯(cuò)的可能性.Yilmaz[10]提出時(shí)間頻譜模型,通過(guò)跟蹤方法或者模塊一次執(zhí)行所消耗的時(shí)間來(lái)預(yù)測(cè)故障,在定位故障時(shí)使用了聚類(lèi)方法.Zhang[11]等人將程序中可能出現(xiàn)的錯(cuò)誤類(lèi)型看作一個(gè)離散的隨機(jī)過(guò)程,使用馬爾科夫模型預(yù)測(cè)錯(cuò)誤類(lèi)型,從而選擇最佳的錯(cuò)誤定位技術(shù).Zong[12]將故障定位分為函數(shù)級(jí)定位和語(yǔ)句級(jí)定位兩個(gè)步驟,函數(shù)級(jí)定位時(shí)采用基于模型的方法,語(yǔ)句級(jí)定位時(shí)采用基于頻譜的方法.

基于依賴(lài)關(guān)系的故障定位(Dependence-based Fault Localization)考慮程序內(nèi)部的數(shù)據(jù)依賴(lài)和控制依賴(lài)對(duì)于定位結(jié)果的影響.程序切片技術(shù)[13]被用于軟件故障定位,可以縮小定位故障時(shí)的搜索空間.馬凱[14]根據(jù)程序的控制流圖對(duì)程序進(jìn)行分塊,通過(guò)控制流塊的覆蓋率、關(guān)系分析故障在相鄰控制流塊中的影響系數(shù).Baah[15]在程序依賴(lài)圖的基礎(chǔ)上,通過(guò)增加節(jié)點(diǎn)和邊得到概率依賴(lài)圖,根據(jù)程序執(zhí)行的失敗信息計(jì)算節(jié)點(diǎn)存在故障的條件概率.Yang[16]等人分析Java程序運(yùn)行時(shí)變量操作狀態(tài)變化及其依賴(lài)關(guān)系,提出基于數(shù)據(jù)鏈路的故障定位方法.

基于數(shù)據(jù)挖掘的故障定位(Data-mining-based Localization)隨著近些年數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)技術(shù)的興起被應(yīng)用到軟件故障定位領(lǐng)域.文獻(xiàn)[17]將C4.5決策樹(shù)算法應(yīng)用于軟件故障定位,該方法認(rèn)為相同的情況下執(zhí)行失敗的測(cè)試用例最有可能由相同的錯(cuò)誤造成,提出用決策樹(shù)劃分的方式來(lái)對(duì)測(cè)試用例進(jìn)行分類(lèi).文獻(xiàn)[18-20]使用神經(jīng)網(wǎng)絡(luò)訓(xùn)練與虛擬測(cè)試用例預(yù)測(cè)相結(jié)合的方法來(lái)定位錯(cuò)誤,其中文獻(xiàn)[18]使用BP神經(jīng)網(wǎng)絡(luò),文獻(xiàn)[19]使用RBF神經(jīng)網(wǎng)絡(luò),文獻(xiàn)[20]使用DNN網(wǎng)絡(luò).這三篇文獻(xiàn)中都將代碼的覆蓋率信息作為輸入,將程序的執(zhí)行結(jié)果作為輸出,用于訓(xùn)練神經(jīng)網(wǎng)絡(luò).網(wǎng)絡(luò)訓(xùn)練完成后,將一個(gè)虛擬測(cè)試用例輸入網(wǎng)絡(luò)中,預(yù)測(cè)每條語(yǔ)句出錯(cuò)的可能性.

目前基于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的軟件故障定位被認(rèn)為最具發(fā)展前景,但現(xiàn)有的方法都將被測(cè)程序看成黑盒,僅從語(yǔ)句或者狀態(tài)是否被覆蓋進(jìn)行預(yù)測(cè),并沒(méi)有考慮軟件本身的結(jié)構(gòu)特性.同時(shí)在運(yùn)行測(cè)試用例時(shí)代碼或者函數(shù)的覆蓋次數(shù)、執(zhí)行的先后順序都沒(méi)有被充分考慮.因此本文在現(xiàn)有研究的基礎(chǔ)上,提出基于執(zhí)行軌跡的軟件故障定位方法.我們將待測(cè)軟件在執(zhí)行一次測(cè)試用例時(shí)的執(zhí)行軌跡表示為一個(gè)序列,并將序列數(shù)據(jù)用于循環(huán)神經(jīng)網(wǎng)絡(luò)的訓(xùn)練和預(yù)測(cè).

本文的主要?jiǎng)?chuàng)新點(diǎn)包括:

1) 使用基于控制流分析的執(zhí)行軌跡信息表示測(cè)試用例,為故障定位算法保留更多有效信息;

2) 將循環(huán)神經(jīng)網(wǎng)絡(luò)應(yīng)用于測(cè)試用例訓(xùn)練和懷疑度預(yù)測(cè),循環(huán)神經(jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)到測(cè)試用例中的順序信息,故障定位的效果更加準(zhǔn)確.

全文章節(jié)安排:第2節(jié)分析了故障定位的基本問(wèn)題;第3節(jié)介紹了本文使用的循環(huán)神經(jīng)網(wǎng)絡(luò)的基本結(jié)構(gòu)和訓(xùn)練過(guò)程;第4節(jié)中介紹了本文所提方法的具體流程;第5節(jié)進(jìn)行了實(shí)驗(yàn)和結(jié)果分析,驗(yàn)證了方法的有效性;最后是總結(jié)和展望部分.

2 問(wèn)題分析

2.1 使用程序頻譜描述測(cè)試用例

軟件故障定位的最終目的是通過(guò)目標(biāo)程序在一組測(cè)試用例上的執(zhí)行情況,尋找最有可能導(dǎo)致當(dāng)前測(cè)試結(jié)果的軟件故障所在的位置,定位具體位置可以是代碼行、代碼塊或者函數(shù)級(jí)別.為了表述方便,在接下來(lái)的內(nèi)容中我們將代碼行、代碼塊和函數(shù)統(tǒng)一稱(chēng)為組成程序的組件.在正式定位軟件故障之前,需要對(duì)待測(cè)試軟件在輸入測(cè)試用例后的執(zhí)行情況進(jìn)行表示,目前被廣泛使用的一種測(cè)試用例表示方法是程序頻譜技術(shù).

假設(shè)程序P由m個(gè)組件組成,表示為C={c1,c2,…,cm},其中cj代表第j個(gè)組件.程序P在n個(gè)測(cè)試用例上進(jìn)行了測(cè)試,測(cè)試用例表示為T(mén)={t1,t2,…,tn},測(cè)試結(jié)果儲(chǔ)存于n維向量e中,e中的每個(gè)元素代表相應(yīng)測(cè)試用例的執(zhí)行結(jié)果,具體的:ei=0代表測(cè)試用例ti在程序P執(zhí)行成功;ei=1代表測(cè)試用例ti執(zhí)行失敗,失敗的情形包括程序輸出與預(yù)期結(jié)果不一致、運(yùn)行崩潰等.為了加以區(qū)分,用Tpass表示成功執(zhí)行的測(cè)試用例,表示為T(mén)pass={ti|ti∈T,ei=0};用Tfailed表示沒(méi)有成功執(zhí)行的測(cè)試用例,表示為T(mén)failed={ti|ti∈T,ei=1}.使用一個(gè)n×m的矩陣A記錄測(cè)試用例對(duì)于組件的覆蓋情況,A中的每個(gè)元素aij表示在執(zhí)行測(cè)試用例ti時(shí)組件cj是否被覆蓋,如果覆蓋則aij的值為1,否則aij的值為0.最終,合并后的矩陣[A,e]就是能夠刻畫(huà)測(cè)試用例執(zhí)行的程序頻譜.

圖1 程序頻譜舉例Fig.1 An example of program spectrum

圖1是一個(gè)程序頻譜的例子,該程序由c1到c6總共六個(gè)組件組成,并且在5個(gè)測(cè)試用例上進(jìn)行了測(cè)試.從圖1中的例子可以看出,程序頻譜的每一個(gè)測(cè)試用例僅包含了通過(guò)的組件和測(cè)試結(jié)果兩類(lèi)信息,并不能完全反映被測(cè)程序在執(zhí)行測(cè)試用例時(shí)的全貌.因此,基于這樣的測(cè)試信息進(jìn)行故障推斷時(shí)損失了一部分測(cè)試信息.

2.2 使用控制流圖描述測(cè)試用例

使用控制流圖(CFG,Control Flow Graph)可以精確表示測(cè)試用例在被測(cè)程序中的執(zhí)行情況,相比于程序頻譜,控制流圖保留了程序內(nèi)部的調(diào)用關(guān)系、執(zhí)行的先后順序等信息.控制流圖用有向圖G表示,G中的節(jié)點(diǎn)稱(chēng)為基本塊(basic block),一個(gè)基本塊是一段不包含跳轉(zhuǎn)或分支語(yǔ)句的順序代碼集合,位于基本塊中的代碼在一次執(zhí)行中要么全部被執(zhí)行,要么全部被跳過(guò),G中的所有基本塊可以表示為B={b1,b2,…,bm}.G中的有向邊稱(chēng)為跳轉(zhuǎn),跳轉(zhuǎn)連接了兩個(gè)不同的基本塊,一條從基本塊bε指向基本塊bγ的邊表示程序執(zhí)行完bε中的所有代碼,同時(shí)使程序處于將要執(zhí)行bγ的狀態(tài),G中的所有跳轉(zhuǎn)可以表示為E={ei|ei=,bε,bγ∈B,ε≠γ}.此外,G中還包含兩類(lèi)特殊節(jié)點(diǎn)代表程序的入口和出口,分別用bin和bexit表示.圖2中列舉了控制流圖的幾種常見(jiàn)結(jié)構(gòu).

2.3 基于控制圖的測(cè)試路徑生成

圖2 控制流圖Fig.2 Control flow graph

控制流圖包含了目標(biāo)程序中的結(jié)構(gòu)信息,借助控制流圖可以精確地分析測(cè)試用例在被測(cè)程序中的執(zhí)行情況,當(dāng)一個(gè)測(cè)試用例被輸入到目標(biāo)程序中之后,會(huì)從控制流圖的入口節(jié)點(diǎn)開(kāi)始執(zhí)行,經(jīng)過(guò)多次跳轉(zhuǎn)后達(dá)到出口節(jié)點(diǎn),測(cè)試用例執(zhí)行完畢.因此給出測(cè)試用例執(zhí)行軌跡的定義:測(cè)試用例ti的執(zhí)行軌跡是其輸入程序控制流圖中后經(jīng)過(guò)的所有基本塊組成的序列,用符號(hào)Seqti表示,顯然Seqti總是從bin出發(fā)最終到bexit.以圖2(c)中的冒泡排序?yàn)槔?假設(shè)測(cè)試用例ti的輸入為數(shù)組[3,2],則通過(guò)觀(guān)察測(cè)試用例在控制流圖中的執(zhí)行情況,可以得到測(cè)試路徑Seqti:b1→b2→b3→b4→b2→b1→b5,記為Seqti=b1b2b3b4b2b1b5.

通過(guò)一個(gè)例子比較基于程序頻譜的故障定位和基于路徑的故障定位,圖3中的is_num_constant()函數(shù)選自西門(mén)子測(cè)試套件中的print_tokens2程序的v6錯(cuò)誤版本,該函數(shù)的功能是判斷一個(gè)字符串是否全部由數(shù)字組成,如果是則返回TRUE否則返回FALSE.

圖3 Is_num_constant的覆蓋情況Fig.3 Coverage info of is_num_constant

圖3中的第一列是程序代碼,從錯(cuò)誤描述中可以看出錯(cuò)誤出現(xiàn)在代碼的第3行中.第二列是代碼行,用si表示,在標(biāo)記時(shí)略過(guò)了沒(méi)有實(shí)際意義的代碼(如:“else”、“}”等).第三列是根據(jù)代碼行劃分的基本塊.第四列對(duì)應(yīng)一組若干測(cè)試用例,每個(gè)測(cè)試用例包括用例編號(hào)、測(cè)試輸入、代碼行以及最終的測(cè)試結(jié)果.用“?”表示用例覆蓋了對(duì)應(yīng)的代碼行和基本塊,最后的F代表測(cè)試用例執(zhí)行失敗,P代表測(cè)試用例執(zhí)行通過(guò).以用例t1為例,該用例的測(cè)試輸入為字符串“1”,用例執(zhí)行的過(guò)程中覆蓋到的基本塊和代碼行包括:b1(s1,s2),b2(s3),b3(s4),b5(s6),最終的測(cè)試結(jié)果為F,也就是函數(shù)錯(cuò)誤的把字符串“1”判斷成不是全部由數(shù)字組成,并返回了結(jié)果FALSE.

通過(guò)圖3中的覆蓋表可以得到包含覆蓋矩陣和測(cè)試結(jié)果向量的程序頻譜,通過(guò)程序頻譜進(jìn)行預(yù)測(cè).然而,觀(guān)察測(cè)試用例t3,t4和t5會(huì)發(fā)現(xiàn)這三個(gè)測(cè)試用例對(duì)于代碼行和代碼塊的覆蓋情況完全相同,但測(cè)試結(jié)果t3和t5顯示為測(cè)試通過(guò),而t4則顯示為測(cè)試失敗.也就是說(shuō)在對(duì)應(yīng)的程序頻譜中對(duì)于用例t3,t4和t5對(duì)測(cè)試情況的描述完全相同,但在測(cè)試結(jié)果上確存在差別,因而無(wú)法區(qū)分.

對(duì)比程序頻譜,使用基于控制流圖的路徑分析方法表示圖3中的測(cè)試用例,路徑分析的結(jié)果顯示在圖4中.對(duì)比圖4中的執(zhí)行路徑發(fā)現(xiàn),雖然用例t4與t5在基本塊的覆蓋情況上沒(méi)有區(qū)別,但是觀(guān)察對(duì)應(yīng)的路徑會(huì)發(fā)現(xiàn)t4的執(zhí)行路徑Seqt4=b1b2b3b4b2b6,t5的執(zhí)行路徑Seqt5=b1b2b3b4b2b3b4b2b6,兩者的執(zhí)行路徑存在區(qū)別,因此可以通過(guò)執(zhí)行路徑將兩個(gè)測(cè)試用例加以區(qū)分.

圖4 Is_num_constant的執(zhí)行路徑分析結(jié)果Fig.4 Exectuion trajectory of is_num_constant

通過(guò)上述分析可以看出,基于程序控制流圖的測(cè)試序列分析與程序頻譜分析相比,前者不僅包含了每個(gè)測(cè)試用例執(zhí)行時(shí)組件的覆蓋情況,還包含了被覆蓋組件的執(zhí)行次數(shù)和執(zhí)行的先后順序.

3 循環(huán)神經(jīng)網(wǎng)絡(luò)

3.1 循環(huán)神經(jīng)網(wǎng)絡(luò)簡(jiǎn)介

循環(huán)神經(jīng)網(wǎng)絡(luò)作為一種具有記憶功能的人工神經(jīng)網(wǎng)絡(luò),在處理序列化的數(shù)據(jù)時(shí)具有獨(dú)特的優(yōu)勢(shì).與基本的人工神經(jīng)網(wǎng)絡(luò)相比,循環(huán)神經(jīng)網(wǎng)絡(luò)最大的不同是存在于各隱藏層節(jié)點(diǎn)間的連接邊,這些連接在隱藏層的前后狀態(tài)間建立起聯(lián)系,使得神經(jīng)網(wǎng)絡(luò)具備“記憶”功能.

圖5中比較了基本的神經(jīng)網(wǎng)絡(luò)和循環(huán)神經(jīng)網(wǎng)絡(luò)在結(jié)構(gòu)上的不同,這兩種神經(jīng)網(wǎng)絡(luò)都由輸入層、隱藏層和輸出層組成(每一層都可以包含若干個(gè)神經(jīng)元節(jié)點(diǎn),這里抽象成一個(gè)).圖5(a)是一個(gè)最基本的神經(jīng)網(wǎng)絡(luò),向量x表示輸入層狀態(tài),向量s表示隱藏層狀態(tài),向量o表示輸出層狀態(tài),U是連接輸入層節(jié)點(diǎn)和隱藏層各節(jié)點(diǎn)之間權(quán)重矩陣,V是隱藏層和輸出層之間的權(quán)重矩陣,從該結(jié)構(gòu)中可以看出隱藏狀態(tài)s取決于輸入層狀態(tài)x,表示成s=f(Ux).圖5(b)是循環(huán)神經(jīng)網(wǎng)絡(luò)的基本結(jié)構(gòu),可以看出與基本的神經(jīng)網(wǎng)絡(luò)最大的不同是同一隱藏層節(jié)點(diǎn)之間通過(guò)一個(gè)權(quán)重矩陣W連接,這樣的結(jié)構(gòu)使得循環(huán)神經(jīng)網(wǎng)絡(luò)的隱藏層狀態(tài)s不僅僅取決于當(dāng)前輸入x,還取決于上一次隱藏層的狀態(tài).將圖5(b)中的循環(huán)神經(jīng)網(wǎng)絡(luò)展開(kāi)可以得到圖5(c)中的結(jié)構(gòu),從這個(gè)結(jié)構(gòu)可以更加清晰的地看到參數(shù)在網(wǎng)絡(luò)中的傳遞情況.st的值不僅取決于當(dāng)前的輸入xt還取決于隱藏層上一次的狀態(tài)st-1,可以表示成st=f(Uxt+Wst-1).

圖5 基本的人工神經(jīng)網(wǎng)絡(luò)與循環(huán)神經(jīng)網(wǎng)絡(luò)Fig.5 Artificial neural network and recurrent neural network

3.2 訓(xùn)練過(guò)程

圖6 多輸入單輸出循環(huán)神經(jīng)網(wǎng)絡(luò)Fig.6 RNN with multi inputs and single output

3.2.1 損失函數(shù)

(1)

對(duì)于多分類(lèi)問(wèn)題,通常使用交叉熵作為損失函數(shù),損失函數(shù)的形式如下:

(2)

3.2.2 更新參數(shù)V

βt=Vst+c

(3)

(4)

(5)

上述公式中的×代表矩陣乘法,⊙代表矩陣中的元素相乘.

3.2.3 更新參數(shù)W和U

與參數(shù)V不同,參數(shù)W和U在整個(gè)循環(huán)神經(jīng)網(wǎng)絡(luò)中沿著從后向前的方向傳播了t次,可以通過(guò)循環(huán)的方式計(jì)算梯度.為了方便表示,用αt表示隱藏層在t時(shí)刻的輸入值.在計(jì)算全局梯度之前,需要先計(jì)算每個(gè)時(shí)刻的局部梯度,計(jì)算公式為:

αt=Uxt+Wst-1+b

(6)

(7)

(8)

利用局部梯度計(jì)算U和W的梯度:

(9)

(10)

得到梯度公式后,就可以根據(jù)設(shè)定的學(xué)習(xí)率對(duì)參數(shù)進(jìn)行更新.以上就是基于反向傳播算法的循環(huán)神經(jīng)網(wǎng)絡(luò)的整個(gè)訓(xùn)練過(guò)程.

4 基于循環(huán)神經(jīng)網(wǎng)絡(luò)的故障定位方法

4.1 獲取測(cè)試用例執(zhí)行軌跡

在開(kāi)始故障定位之前需要獲得測(cè)試用例的執(zhí)行軌跡信息,本文使用基于控制流圖的方法分析測(cè)試用例的執(zhí)行軌跡,將基本塊作為程序執(zhí)行的基本單位.同一基本塊中的代碼在所有測(cè)試用例中的被執(zhí)行和調(diào)用的情況完全相同,因此同一基本塊中的代碼存在故障的懷疑度值也是無(wú)差別的,故障定位到基本塊級(jí)別之后只需在當(dāng)前基本塊中順序搜索即可.

本文進(jìn)行故障定位分析的目標(biāo)程序是C/C++程序,使用插樁的方式獲得執(zhí)行軌跡信息.使用的插裝函數(shù)如圖7所示,在執(zhí)行測(cè)試之前在每個(gè)基本塊中插入樁函數(shù),當(dāng)基本塊被執(zhí)行時(shí)會(huì)向日志文件中輸出一個(gè)唯一標(biāo)識(shí),最終得到的標(biāo)識(shí)序列就是測(cè)試用例的執(zhí)行軌跡.

在插樁時(shí)需要考慮兩類(lèi)特殊情況:

1)函數(shù)

當(dāng)基本塊中有函數(shù)調(diào)用時(shí),需要將調(diào)用函數(shù)的部分看作單獨(dú)的基本塊,并在函數(shù)調(diào)用前插入裝函數(shù)記錄被調(diào)用函數(shù)的入口,使得在分析測(cè)試用例的執(zhí)行路徑時(shí)更加清晰.

圖7 插樁函數(shù)Fig.7 Stub function

2)復(fù)合邏輯謂詞

由于多個(gè)邏輯謂詞在組合使用時(shí)存在短路現(xiàn)象(如:1||0、0&&1等),因此在遇到這種情況時(shí)需要對(duì)每個(gè)可能產(chǎn)生短路的謂詞單獨(dú)插樁,插樁的方式如圖8所示.

圖8 復(fù)合謂詞插樁Fig.8 Stubs of composite predicate

通過(guò)插樁的方式獲得的是一組不同長(zhǎng)度的由組件標(biāo)識(shí)構(gòu)成的序列(如圖4所示),但這樣的序列不適合直接用于循環(huán)神經(jīng)網(wǎng)絡(luò)的訓(xùn)練,因此需要對(duì)序列進(jìn)行標(biāo)準(zhǔn)化.路徑序列的標(biāo)準(zhǔn)化算法如算法1所示.

算法1.路徑序列標(biāo)準(zhǔn)化

輸入:測(cè)試路徑集合Seq

輸出:標(biāo)準(zhǔn)化矩陣M

1.Initialize MapState2Index= {(None:0)}

2.Initialize ListM= []

3.InitializeMaxLength= 0

4.InitializeIndex= 1

5.forSeqiinSeqdo

6.MaxLength= max(MaxLength,length(Seqi))

7. forbjinSeqi

8. ifState2Index.find(bj) = ?

9.State2Index[bj] =Index

10.Index=Index+ 1

11. end if

12. end for

13.end for

14.forSeqiinSeqdo

15. Initialize Listtemp= []

16. Initializecurlength= length(Seqi)

17. forbjinSeqi

18.temp.append(State2Index[bj])

19. end for

20. whilecurlength

21.temp.append(State2Index[None])

22. end while

23.M.append(temp)

24.end for

25.returnM

算法1的輸入為測(cè)試序列集合Seq,輸出是標(biāo)準(zhǔn)化后的矩陣M.算法首先遍歷Seq中的每一條路徑,遍歷的目的是找到所有測(cè)試用例中的基本塊并且為每個(gè)基本塊映射唯一的索引號(hào),同時(shí)獲得最大序列長(zhǎng)度MaxLength.第二次遍歷時(shí),將序列中的每個(gè)基本塊對(duì)應(yīng)的索引號(hào)放入矩陣M,在當(dāng)前序列的長(zhǎng)度小于最大序列MaxLength時(shí),用0補(bǔ)齊剩下的部分.應(yīng)用算法1處理圖3中的例子的結(jié)果顯示在圖9中.

4.2 訓(xùn)練網(wǎng)絡(luò)

在開(kāi)始訓(xùn)練之前,需要設(shè)置網(wǎng)絡(luò)的循環(huán)次數(shù)、各層節(jié)點(diǎn)數(shù)、激活函數(shù)等,圖10展示了網(wǎng)絡(luò)的訓(xùn)練過(guò)程.

圖10 訓(xùn)練網(wǎng)絡(luò)過(guò)程Fig.10 Training process

圖中輸入層節(jié)點(diǎn)數(shù)為基本塊數(shù),隱藏層節(jié)點(diǎn)數(shù)可以根據(jù)實(shí)際情況設(shè)置,輸出層節(jié)點(diǎn)數(shù)為目標(biāo)類(lèi)別數(shù).訓(xùn)練時(shí)將標(biāo)準(zhǔn)化矩陣M作為網(wǎng)絡(luò)的輸入,每次訓(xùn)練輸入一行,代表一個(gè)測(cè)試用例.數(shù)據(jù)輸入時(shí)按照先后順序每次向輸入層輸入一個(gè)代表基本塊的標(biāo)識(shí),在實(shí)際應(yīng)用中通常對(duì)輸入數(shù)據(jù)進(jìn)行編碼處理后再作為網(wǎng)絡(luò)的輸入,編碼的方法如算法2所示.

算法2.一位有效編碼

輸入:標(biāo)準(zhǔn)化矩陣M,基本塊個(gè)數(shù)L

輸出:編碼后的矩陣MEncode

1.Initialize ListMEncode= []

2.forlineiinM

3. InitializenewLine= []

4. foritemjinlinei

5. InitializenewItem= {0} with sizeL

6. ifitemj!= 0

7.newItem[itemi- 1] = 1

8. end if

9. end for

10.end for

11.returnMEncode

以圖10中的測(cè)試用例t1為例,t1的測(cè)試序列經(jīng)一位標(biāo)準(zhǔn)編碼后,對(duì)應(yīng)的輸出結(jié)果為[[1,0,0,0,0,0,0],[0,1,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]].

循環(huán)神經(jīng)網(wǎng)絡(luò)中輸入層到隱藏層間的激活函數(shù)通常使用雙曲正切函數(shù),計(jì)算公式為:

y=(ex-e-x)/(ex+e-x)

(11)

循環(huán)神經(jīng)網(wǎng)絡(luò)的隱藏層輸入不僅來(lái)自本次的輸入層,還來(lái)自與上一次循環(huán)時(shí)隱藏層的輸出值.特別地,在第一次循環(huán)時(shí)將來(lái)自上一隱藏層的輸入s0設(shè)置為0向量.通過(guò)觀(guān)查網(wǎng)絡(luò)的輸入數(shù)據(jù)可以發(fā)現(xiàn),當(dāng)路徑序列的標(biāo)識(shí)變?yōu)?時(shí),輸入層數(shù)輸入值變?yōu)閇0,0,…,0],這時(shí)輸入網(wǎng)絡(luò)中的數(shù)據(jù)不再有意義,因此隱藏結(jié)束向后傳播并且將數(shù)據(jù)輸出到輸出層.以圖10中的測(cè)試用例t1和t5為例,t1在第4步后結(jié)束循環(huán),同時(shí)向輸出層輸出此時(shí)的隱藏層狀態(tài)s4;t5則在全部數(shù)據(jù)輸入完后,將最后一步的隱藏層狀態(tài)s9輸出到輸出層.

由于一條測(cè)試用例的測(cè)試結(jié)果只有成功和失敗兩種情況,因此輸出層的節(jié)點(diǎn)個(gè)數(shù)設(shè)置為2.同時(shí),輸出值經(jīng)過(guò)softmax函數(shù)處理后變?yōu)闇y(cè)試用例成功或者失敗的概率分布,輸出的形式為:

(12)

其中p表示測(cè)試用例失敗的概率,1-p表示測(cè)試用例成功的概率.對(duì)于測(cè)試用例的正確標(biāo)簽y,也需要進(jìn)行one-hot處理:

y=[1-q,q],(q∈{0,1})

(13)

(14)

之后可以使用反向傳播算法進(jìn)行訓(xùn)練,當(dāng)誤差小于設(shè)定值或者訓(xùn)練次數(shù)達(dá)到設(shè)定值時(shí)結(jié)束訓(xùn)練,得到最終的網(wǎng)絡(luò).

4.3 預(yù)測(cè)過(guò)程

網(wǎng)絡(luò)訓(xùn)練完成后可以用于測(cè)試用例預(yù)測(cè),假設(shè)有一組虛擬的測(cè)試用例v1,v2,…,vm,這組虛擬測(cè)試用例的執(zhí)行軌跡為:

{πv1,πv2,…,πvm}={b1,b2,…,bm}

每一條虛擬測(cè)試用例vi(i=1,2,…,m)執(zhí)行時(shí)僅經(jīng)過(guò)一個(gè)基本塊bi,如果測(cè)試用例vi執(zhí)行失敗,那么基本塊bi就很有可能包含故障,因此調(diào)試時(shí)應(yīng)當(dāng)優(yōu)先考慮.但在現(xiàn)實(shí)中,這樣的一組虛擬測(cè)試用例是無(wú)法設(shè)計(jì)出來(lái)的,所以為了獲得這些虛擬測(cè)試用例的執(zhí)行結(jié)果,我們建立一個(gè)循環(huán)神經(jīng)網(wǎng)絡(luò),并將現(xiàn)有的測(cè)試數(shù)據(jù)輸入網(wǎng)絡(luò)中進(jìn)行訓(xùn)練.當(dāng)網(wǎng)絡(luò)訓(xùn)練完成后,將虛擬測(cè)試用例的執(zhí)行路徑標(biāo)準(zhǔn)化后輸入到網(wǎng)絡(luò)中,網(wǎng)絡(luò)的輸出對(duì)應(yīng)基本塊的懷疑度.預(yù)測(cè)過(guò)程如圖11所示.

上述過(guò)程可以總結(jié)以下幾個(gè)步驟:

1)使用插樁的方法獲取測(cè)試用例的執(zhí)行序列集合Seq,使用算法1將序列集合Seq轉(zhuǎn)換為可以用于循環(huán)神經(jīng)網(wǎng)絡(luò)訓(xùn)練的標(biāo)準(zhǔn)化矩陣M;

圖11 預(yù)測(cè)過(guò)程Fig.11 Predicting process

2)建立一個(gè)包含L個(gè)輸入層節(jié)點(diǎn)(L為程序P中的基本塊個(gè)數(shù)),h個(gè)隱藏層節(jié)點(diǎn)(本文中h設(shè)為30)和2個(gè)輸出層節(jié)點(diǎn)的循環(huán)神經(jīng)網(wǎng)絡(luò).設(shè)置輸入層和隱藏層之間的傳遞函數(shù)為雙曲正切函數(shù)tanh,輸出層的轉(zhuǎn)換函數(shù)為softmax函數(shù).

3)訓(xùn)練循環(huán)神經(jīng)網(wǎng)絡(luò),將準(zhǔn)化矩陣M作為網(wǎng)絡(luò)的輸入,將測(cè)試用例對(duì)應(yīng)的執(zhí)行結(jié)果作為期望的輸出,在訓(xùn)練時(shí)為了克服過(guò)擬合問(wèn)題使用到了Dropout隨機(jī)丟棄算法;

4)將虛擬測(cè)試用例輸入到訓(xùn)練好的網(wǎng)絡(luò)中,得到預(yù)測(cè)值pv1,pv2,…,pvm;

5)使用pv1,pv2,…,pvm對(duì)基本塊b1,b2,…,bm進(jìn)行排名,然后按照懷疑度從高到低的順序在每個(gè)基本塊中查找錯(cuò)誤,直到錯(cuò)位被定位到.

表1 預(yù)測(cè)結(jié)果
Table 1 Results of prediction

基本塊預(yù)測(cè)值基本塊預(yù)測(cè)值b10.43503392b50.78848398b20.96262193b60.83428442b30.26716137b70.00091218b40.15842001——

作為示例,使用本文所提方法對(duì)圖3中給出的is_num_constant函數(shù)進(jìn)行故障定位.is_num_constant總共被劃分為7個(gè)基本塊,并且在6個(gè)測(cè)試用例上進(jìn)行了測(cè)試,每個(gè)測(cè)試用例對(duì)應(yīng)的執(zhí)行路徑顯示在圖4中.通過(guò)對(duì)這6個(gè)測(cè)試用例進(jìn)行標(biāo)準(zhǔn)化處理后得到圖9中的標(biāo)準(zhǔn)化矩陣M.可以看出第一個(gè)測(cè)試用例t1的輸入序列為(1,2,3,4,0,0,0,0,0)對(duì)應(yīng)的期望結(jié)果為0,以此類(lèi)推.

根據(jù)矩陣M的結(jié)構(gòu),設(shè)置循環(huán)神經(jīng)網(wǎng)絡(luò)的輸入層節(jié)點(diǎn)數(shù)為7,隱藏層節(jié)點(diǎn)數(shù)為30,輸出層節(jié)點(diǎn)數(shù)為2,當(dāng)訓(xùn)練步數(shù)達(dá)到1000時(shí)停止訓(xùn)練.

將圖11中的虛擬測(cè)試用例逐行輸入網(wǎng)絡(luò)中,得到表1中的預(yù)測(cè)結(jié)果,表中的預(yù)測(cè)值表示對(duì)應(yīng)的基本塊懷疑度.排序后得到最終的懷疑度排名是b2,b6,b5,b1,b3,b4,b7,結(jié)果表明基本塊b2包括錯(cuò)誤的可能性最高,與實(shí)際情況相符.

5 實(shí)驗(yàn)與對(duì)比

5.1 測(cè)試數(shù)據(jù)集

為了證明本文所提方法的有效性,從SIR官方網(wǎng)站獲得了Siemens測(cè)試套件并進(jìn)行了故障定位實(shí)驗(yàn).實(shí)驗(yàn)的軟件環(huán)境分為兩部分,測(cè)試執(zhí)行和數(shù)據(jù)收集工作在Ubuntu 16.04環(huán)境下進(jìn)行,使用到的gcc和gcov均為5.4.0版本.數(shù)據(jù)分析部分在windows 7環(huán)境下進(jìn)行,使用到的Python版本為3.5.4,訓(xùn)練神經(jīng)網(wǎng)絡(luò)時(shí)使用的TensorFlow版本為1.4.0.硬件環(huán)境為i7-6600U 2.6GHz CPU和12GB RAM.

表2 Siemens套件
Table 2 Siemens suit

ProgramVer.LOCCasesDescriptionprint_tokens7563(+159)4230詞法分析器print_tokens210508(+57)4115詞法分析器replace325635542模式匹配與替換schedule94102650優(yōu)先級(jí)調(diào)度器schedule210307(+66)2710優(yōu)先級(jí)調(diào)度器tcas411731608高度分離程序tot_info23406(+158)1052信息統(tǒng)計(jì)程序

Siemens測(cè)試套件是一組在軟件故障定位領(lǐng)域被廣泛使用的測(cè)試數(shù)據(jù)集,它包含了7個(gè)獨(dú)立的C語(yǔ)言程序,每個(gè)程序都包括一個(gè)完全正確的源程序以及若干個(gè)包含故障的版本,同時(shí)還包含了大量的測(cè)試用例,測(cè)試套件有關(guān)信息整理在表2中.表2中每一列的數(shù)據(jù)分別代表:程序的名稱(chēng)、錯(cuò)誤版本數(shù)、代碼行數(shù)、測(cè)試用例數(shù)和以及程序的功能描述.其中在統(tǒng)計(jì)代碼行數(shù)時(shí)僅對(duì)main函數(shù)所在的文件進(jìn)行了統(tǒng)計(jì),其余文件(如.h文件)的代碼行數(shù)顯示在括號(hào)中.

5.2 實(shí)驗(yàn)過(guò)程

實(shí)驗(yàn)分為以下幾個(gè)步驟:

1)Siemens測(cè)試套件提供了大量的測(cè)試用例,但并沒(méi)有提供這些測(cè)試用例對(duì)應(yīng)的執(zhí)行結(jié)果,因此首先需要在正確版本的源程序上執(zhí)行測(cè)試用例,獲得正確的輸出;

2)為了獲得測(cè)試用例的執(zhí)行軌跡信息,對(duì)于程序的每個(gè)錯(cuò)誤版本,使用4.1節(jié)中的方法進(jìn)行插樁并運(yùn)行測(cè)試用例,獲得程序的實(shí)際輸出以及測(cè)試用例的執(zhí)行軌跡信息;

3)為了獲得測(cè)試用例的覆蓋率信息用于對(duì)比,使用gcov工具在gcc環(huán)境下運(yùn)行測(cè)試用例,并從測(cè)試結(jié)果文件中解析出測(cè)試用例的覆蓋矩陣;

4)將測(cè)試用例在錯(cuò)誤版本程序上的輸出與正確輸出比較,獲得測(cè)試用例在該錯(cuò)誤版本程序上的執(zhí)行結(jié)果;

5)將測(cè)試用例的執(zhí)行軌跡標(biāo)準(zhǔn)化后作為循環(huán)神經(jīng)網(wǎng)絡(luò)的輸入,測(cè)試用例的執(zhí)行結(jié)果作為輸出,使用反向傳播算法訓(xùn)練神經(jīng)網(wǎng)絡(luò);

6)將一組虛擬測(cè)試用例輸入訓(xùn)練好的網(wǎng)絡(luò)中,獲得對(duì)應(yīng)基本塊的懷疑度值,將排序后的結(jié)果作為最終的預(yù)測(cè)結(jié)果.

為了評(píng)價(jià)故障定位方法的性能,使用score值作為評(píng)價(jià)標(biāo)準(zhǔn),score值通過(guò)下面的公式獲得:

(15)

上述公式中N代表尚未被測(cè)試的代碼行數(shù),LOC代表總的代碼行數(shù),顯然score的取值范圍為[0,1),因?yàn)楣收隙ㄎ粫r(shí)按照懷疑度排名檢索錯(cuò)誤,最好的情況下在檢索到第一行代碼時(shí)就成功發(fā)現(xiàn)了錯(cuò)誤,此時(shí)N=LOC-1;而最壞時(shí)則需要一直檢測(cè)到懷疑度列表中的最后一行代碼時(shí)才能發(fā)現(xiàn)錯(cuò)誤,此時(shí)N=0.在衡量故障定位算法的性能時(shí),score值越高意味著能在更短的時(shí)間內(nèi)和更小的代價(jià)下定位到錯(cuò)誤;相反地score的值越小則表明故障定位算法需要檢測(cè)更多的不相關(guān)代碼后才能發(fā)現(xiàn)錯(cuò)誤,故障定位效果欠佳.

5.3 結(jié)果分析

我們將本文方法與幾個(gè)經(jīng)典故障定位方法進(jìn)行了比較,分別是:文獻(xiàn)[2]中的Tarantula方法,文獻(xiàn)[9]中的SOBER方法,文獻(xiàn)[5]中的Crosstab方法,以及文獻(xiàn)[18]中的BPNN方法.Siemens測(cè)試套件中總共包含了132個(gè)錯(cuò)誤版本,本文的方法基于以下規(guī)則進(jìn)行了一些刪減:

1) 故障版本中的主程序不存在錯(cuò)誤,錯(cuò)誤代碼位于頭文件中,如print_tokens的v4和v6版本;

2) 所有的測(cè)試用例在錯(cuò)誤版本中都成功執(zhí)行,無(wú)法獲得錯(cuò)誤信息,如schedule的v9版本;

3) 故障版本存在段錯(cuò)誤,導(dǎo)致所有的測(cè)試用例均無(wú)法成功執(zhí)行,如replace的v27和v32版本,最終使用了122個(gè)錯(cuò)誤版本.在其他故障定位方法中也根據(jù)各自情況進(jìn)行了一些調(diào)整.

表3 Score值分布
Table 3 Score distribution

score(%)TarantulaSOBERCrosstabBPNN本文方法[90,100)55.7352.3058.1450.0059.02[80,90)5.7421.5414.7324.5922.13[70,80)9.843.856.9811.489.02[60,70)8.204.6213.187.387.38[50,60)7.380.771.553.280.82[40,50)0.820.770.783.280.82[30,40)0.822.311.550.000.82[20,30)4.12.312.330.000.00[10,20)7.382.310.760.000.00[0,10)0.009.220.000.000.00

為方便統(tǒng)計(jì),將score值劃分為10個(gè)區(qū)間,分別統(tǒng)計(jì)每種故障定位方法在各個(gè)區(qū)間上能夠定位的故障版本數(shù)的分布情況.表3為按區(qū)間統(tǒng)計(jì)的定位結(jié)果,最后一列為本文所提方法.從表中可以看出本文方法在僅檢查10%的代碼的情況下能夠定位59%左右的故障版本,而同等情況下其余四種方法能定位的故障版本數(shù)為:55.73%,52.30%,58.14%和50.00%.

圖12中使用折線(xiàn)圖更加清晰地展示了表3中的信息,圖中的x軸代表尚未檢測(cè)的代碼行數(shù)占總代碼行數(shù)的百分比,y軸代表已經(jīng)成功定位到的故障版本的百分比.圖中的每個(gè)節(jié)點(diǎn)代表在當(dāng)前百分比代碼已經(jīng)被檢測(cè)過(guò)的情況下,成功定位到錯(cuò)誤的故障版本的比例.從圖中可以看出,在已經(jīng)檢測(cè)的代碼行數(shù)相同的情況下,基于本文方法能夠定位的故障版本數(shù)高于其它幾種方法.

圖12 實(shí)驗(yàn)結(jié)果對(duì)比Fig.12 Results of comparative experiments

如果把檢測(cè)到故障需要檢查的代碼行數(shù)區(qū)間看作隨機(jī)變量X,將在該區(qū)間內(nèi)定位到的故障版本百分比看作隨機(jī)概率P,可以得到這三種方法在定位故障時(shí)需要檢測(cè)的代碼的數(shù)學(xué)期望E,分別是:E(Tarantula)=0.276,E(SOBER)=0.282,E(Crosstab)=0.210,E(BPNN)=0.199,E(RNN)=0.175,結(jié)果表明本文所提方法在定位軟件故障時(shí)需要檢查的代碼百分比為17.5%,期望值最低.

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

軟件故障定位是軟件調(diào)試過(guò)程中的重要環(huán)節(jié),現(xiàn)有的軟件故障定位方法中沒(méi)有完全利用故障程序在執(zhí)行測(cè)試時(shí)的測(cè)試信息.因此本文提出從程序的執(zhí)行軌跡信息中定位軟件故障,該方法基于程序的控制流圖得到測(cè)試用例的執(zhí)行軌跡,執(zhí)行軌跡不僅包含了程序的覆蓋率信息還包含了基本塊的執(zhí)行順序和次數(shù).通過(guò)將序列信息輸入循環(huán)神經(jīng)網(wǎng)絡(luò)中訓(xùn)練,并使用一組虛擬測(cè)試用例進(jìn)行預(yù)測(cè),最終得到基本塊的懷疑度值.

本文所提方法在實(shí)驗(yàn)數(shù)據(jù)集上取得了較好的故障定位效果,但在一些方面依然存在不足:首先,實(shí)際軟件規(guī)模巨大時(shí),得到的測(cè)試序列的長(zhǎng)度也會(huì)超出想象,過(guò)長(zhǎng)的序列會(huì)給神經(jīng)網(wǎng)絡(luò)的訓(xùn)練帶來(lái)挑戰(zhàn);其次,使用測(cè)試序列的定位方案目前僅適用于單線(xiàn)程程序,對(duì)于多線(xiàn)程程序而言無(wú)法獲得唯一的測(cè)試序列,因此無(wú)法推廣.接下來(lái)的工作重點(diǎn)是考慮如何從長(zhǎng)測(cè)試序列中提取有效性信息以及在多線(xiàn)程程序中的應(yīng)用問(wèn)題.