陳 琪,周世健,樊 鑫,2,鄔凱勝,2,肖 鵬,2
(1.南昌航空大學 軟件學院,南昌 330038;2.南昌航空大學 軟件測評中心,南昌 330038)
軟件正成為低成本實現(xiàn)各種系統(tǒng)中復雜功能的首選技術(shù),日常生活的許多方面都依賴于軟件的正確操作,因此保證軟件的質(zhì)量和及時的維護在每個開發(fā)過程中都起著至關(guān)重要的作用。測試指的是檢查軟件的正確性和它是否符合給定的規(guī)范的實踐狀態(tài)。雖然測試用例自動生成工具愈漸成熟,仍然存在部分由開發(fā)人員手工制作的測試用例,在暴露錯誤行為方面測試是有效的,但識別失敗背后的根本原因仍然主要是一種手動活動,需要大量的時間和成本。
各種故障定位方法用來幫助開發(fā)人員定位故障的根本原因,例如,基于頻譜的故障定位[1-6],基于切片的故障定位[7-8],基于機器學習的故障定位[9-10],和基于突變的故障定位[11-14]。其中,基于頻譜的故障定位技術(shù)是研究最廣泛的故障定位技術(shù)之一。盡管SBFL是一種特別輕量級的方法,但與其他方法相比,它已被證明具有競爭力,且具備與語言無關(guān)、易于使用,并且在測試執(zhí)行時間相對開銷較低的特性。
理想的故障定位技術(shù)總是將故障程序?qū)嶓w排在前列。然而在實踐中,盡管已經(jīng)提出了各種SBFL技術(shù),如Jaccard/Ochiai[2],Op2[4]和Tarantula[1],沒有一種技術(shù)可以總是表現(xiàn)最好的,開發(fā)人員通常必須在找到真正的錯誤之前檢查各種非故障實體(即程序頻譜中的一個維度)。利用失敗和成功的測試用例提供的證據(jù),根據(jù)被測實體參與錯誤行為的懷疑程度進行分析和排序。直觀地說,一個實體在測試用例失敗時使用得越多,它就越可疑,即它就越有可能與這種不正確性的原因有關(guān)。類似地,成功的測試用例所使用的實體越多,它就越被認為不可疑。
現(xiàn)有的SBFL技術(shù)的一個局限性是,它們不能完全捕獲每個已執(zhí)行的測試用例的結(jié)果與所涉及的程序單元之間的本地關(guān)系。例如,SBFL技術(shù),如Dstar[15],會假設(shè)兩個失敗的測試用例對在兩個測試用例中執(zhí)行的一個程序單元的懷疑性貢獻相同,而不管在測試用例中涉及的程序?qū)嶓w的數(shù)量不同。在實踐中,一個失敗的測試用例可能比其他用例更有價值,因為它只涉及幾個程序?qū)嶓w。其次,在許多現(xiàn)有的SBFL技術(shù)中,存在一個被忽略的事實,即程序?qū)嶓w可能以不同的方式協(xié)作貢獻每個測試用例的結(jié)果。
我們的關(guān)鍵見解是,存在一種更豐富的頻譜增強形式,考慮了如何增強失敗的測試用例中的頻譜分析,可以提供更有效的故障定位。詳細來說,存在兩個測試和,它們都是失敗的測試,其中覆蓋了100個程序?qū)嶓w,而只覆蓋了10個程序。根據(jù)我們的直覺,在故障定位方面比較有幫助,因為有一個更小的搜索空間來定位故障(s)。由于每一個執(zhí)行失敗的測試用例都必然執(zhí)行了錯誤語句,即錯誤語句必然被覆蓋,那么[16]已經(jīng)證實了在單故障情況下,將所有執(zhí)行失敗的測試用例的覆蓋情況取交集,則會縮小故障語句的覆蓋范圍,從而提高查找效率。經(jīng)過頻譜增強后的測試用例作為新的增強版測試用例來對程序進行驗證。傳統(tǒng)的SBFL技術(shù)忽略了這些有用的信息,并認為和在SBFL上做出了相同的貢獻,例如,和執(zhí)行的程序?qū)嶓w將被作為相同的處理,而不管測試所覆蓋的實體數(shù)量。
為了克服現(xiàn)有的SBFL技術(shù)的局限性,我們通過明確地考慮失敗測試用例的貢獻,更有效地增強了現(xiàn)有的程序頻譜?;谝陨弦娊?,我們提出了基于頻譜增強的軟件多故障定位方法(SBFL(E),spectrum-based fault localization(enhanced)),充分利用了執(zhí)行失敗測試用例的程序語句覆蓋情況,縮減了運行時的執(zhí)行失敗測試用例數(shù)量,對基于頻譜的故障定位方法進行改良,并將單故障擴展到多故障實驗,極大提高了軟件故障定位的效率和有效性。
SBFL使用程序頻譜和測試結(jié)果來定位軟件故障。程序頻譜是測試用例的覆蓋信息和執(zhí)行結(jié)果的集合。一個程序的頻譜,通常以一個矩陣的形式出現(xiàn),它描述了該程序的動態(tài)行為。測試結(jié)果將記錄測試用例是否失敗或通過。通過較多失敗測試用例的實體,通過較少成功測試用例的實體就越可疑[17-18]。相反,實體通過越少的失敗測試用例,通過越多成功的測試用例,實體的可疑度值就越低。程序譜中所涉及的實體類型可以是語句、分支、函數(shù)、謂詞等,本文以語句作為實體。
SBFL的主要思想是與故障相關(guān)的執(zhí)行信息更有可能是導致程序失效的原因,這些信息往往包含在失敗的測試用例,而更少發(fā)生在成功的測試用例當中。如圖1所示,SBFL分析了實體與測試用例通過或失敗之間的動態(tài)相關(guān)性,這個相關(guān)性近似于一個實體導致程序失效的可能性。頻譜信息矩陣由M個測試用例和每個測試用例中的N條語句構(gòu)成,最后得到測試結(jié)果向量R。對于一個語句X_MN,其值是二進制的(0/1),“1”表示相應的語句被測試用例執(zhí)行,“0”表示相應的語句沒有被測試用例執(zhí)行。在結(jié)果向量R中,其值也是二進制的,“0”表示測試用例的結(jié)果為通過,“1”表示測試用例的結(jié)果為失敗。
圖1 SBFL覆蓋信息矩陣圖
程序執(zhí)行信息從圖1中提取,表示為四元組(Nef,Nep,Nnf,Nnp),其中Nef代表語句被執(zhí)行的失敗測試用例數(shù),Nep代表語句被執(zhí)行的通過測試用例數(shù),Nnf代表語句未被執(zhí)行的失敗測試用例數(shù),Nnp代表語句未被執(zhí)行的通過測試用例數(shù)。根據(jù)以上4個參數(shù),程序中各單元元素的可疑值可以通過表1中的可疑值計算公式來計算,這里只列出了部分但常用的公式。如果一個語句的Nef值相對較高,而Nep值較低,則該語句的可疑分值較高。
表1 SBFL可疑度值計算公式
單故障程序指的是在程序中只存在唯一確定的一處故障,導致整個程序的失效;多故障程序則指錯誤數(shù)目不定,存在兩處或兩處以上的故障影響導致程序失效。盡管各種故障定位技術(shù)已經(jīng)被提出,但它們在多故障程序中的應用仍然有限。多故障定位(MFL,multiple fault localization)是指在一個有故障的軟件程序中識別多重故障(一個以上的故障)的定位行為。與單故障定位(SFL,single fault localization)假設(shè)軟件系統(tǒng)中只包含一個故障的傳統(tǒng)做法相比,這種方法更加復雜、繁瑣,而且成本高。工作流程對比如圖2所示。
圖2 單故障與多故障定位
單故障程序中所有失敗的測試用例均指向相同的故障,因此測試用例的數(shù)量與質(zhì)量則顯得尤為關(guān)鍵,成為優(yōu)化故障定位方式的突破口。在多故障環(huán)境下,除了受到測試用例的影響,更令人棘手的是故障干擾的問題。
這些相互作用可能表現(xiàn)為導致測試用例失敗,而通常情況下,由于任何單一故障的存在都不會失敗。另外,一個測試通常由于一個故障而失敗的測試用例,在增加了另一個故障后,該測試用例可能不再失敗,因為它干擾了第一個故障的導致程序失效的作用。當然也存在多個故障于同一個程序中,但不會以通過檢查測試用例可以觀察到故障的方式相互干擾。在這種情況下。程序中每個故障的影響似乎是獨立于其他故障。本文則對故障干擾不做出假設(shè),專注于提升測試用例尤其是失敗的測試用例,使用傳統(tǒng)的定位技術(shù)同時定位多個故障是困難的,因為它們依賴于失敗的測試執(zhí)行來識別錯誤的語句。
綜合來看,單故障與多故障定位的差異除了存在于需要定位的故障數(shù)目的不同,也不免對測試用例的統(tǒng)計處理以及失敗測試用例的質(zhì)量造成消極影響。當故障之間的干擾導致程序包含多個故障時,現(xiàn)有故障定位技術(shù)的有效性會降低。程序中的故障越多,開發(fā)人員就定位故障的復雜性就越高,從而大大增加故障定位的難度與開銷成本。
SBFL是基于程序執(zhí)行的統(tǒng)計數(shù)據(jù)設(shè)計的,其中包括測試覆蓋率和測試結(jié)果。執(zhí)行統(tǒng)計數(shù)據(jù)可以被視為SBFL分析的信息源,其中決定了SBFL的準確性的關(guān)鍵在于測試用例的性質(zhì)。冗余的測試用例大大增加了開發(fā)人員的時間成本與故障定位的精確性,一個含故障程序?qū)嵗绫?所示。
表2 多故障實例
在現(xiàn)有的研究方法中,我們考慮了一個有缺陷的程序來評估我們技術(shù)的效率。Zakari等人[19]用一個例子來解釋3種方法:一次調(diào)試方法、并行調(diào)試方法和多次調(diào)試方法。在本文中,我們采用了同樣的例子程序來展示我們的方法的工作過程。余曉菲等人[16]已經(jīng)證實了頻譜增強在單故障程序中的有效性,因此表2實例僅對多故障程序進行詳細分析。在表2中,我們顯示了示例程序。原始的程序測試套件T由10個測試用例(T0,T1,T2,T3,T4,T5,T6,T7,T8,T9)和13條程序語句組成,其中語句5和語句10都是錯誤的。標有“●”的語句執(zhí)行標志著該語句在該測試運行中被測試用例執(zhí)行,否則為空。測試用例(T6,T7,T8,T9)是失敗的測試用例,而(T0,T1,T2,T3,T4,T5)是通過的測試用例。在這個例子中,每個語句的可疑性是用Tarantula系數(shù)計算的,這是SBFL中常用的故障定位技術(shù)之一。
對于單次故障的調(diào)試很簡單,根據(jù)語句的可疑度得分,開發(fā)人員通過使用Tarantula,檢查4條語句就能清楚地識別出有故障的語句10(可疑度值為0.57)。然而,在多故障情況下,在語句10中發(fā)現(xiàn)的故障必須被修復,并且程序必須被重新測試以發(fā)現(xiàn)第二個故障語句5(可疑度值為0.23)。在多故障調(diào)試過程中,開發(fā)人員在找到語句10中的第一個故障后不會停止,而是繼續(xù)搜索下一個故障,直到找到所有故障或預先指定的搜索上限。設(shè)置上限的方法(即開發(fā)人
員在進入下一個迭代之前可以搜索可疑語句排名列表的70%或60%)已被現(xiàn)有研究采用[20-21]。在我們的研究中,我們沒有設(shè)置搜索上限,而是在找到所有故障之前停止搜索。
采取多故障場景下頻譜增強的方法,實例為雙故障程序,覆蓋第一個故障語句5的失敗測試用例僅為T8,因此頻譜增強后的測試用例Ta保留T8的覆蓋信息并剔除原有T8。失敗測試用例T6和T7覆蓋了第二個故障語句10,且覆蓋信息高度重合,對二者進行測試用例精簡,采取邏輯與運算得到測試用例Tb,并將T6和T7從測試用例集中去除。頻譜增強后可用測試用例為T0~T5以及T9~Tb,再進行SBFL可疑度值計算。
表2清楚地顯示,Tarantula計算的錯誤語句的等級為4和11。在采用頻譜增強的方法進行優(yōu)化后,我們的技術(shù)分別給有問題的語句分配了等級2和等級11。這表明,我們的研究方法比其他現(xiàn)有的方法更有效地優(yōu)化了可疑性分數(shù),并且能夠定位那些使程序失效的語句。
對基于頻譜的故障定位方法而言,故障定位的效果和效率都高度依賴于測試用例,所以測試用例的選取以及使用測試用例的多少都對實驗有至關(guān)重要的影響。針對測試用例的研究,本文引入頻譜增強方法,充分利用了執(zhí)行失敗測試用例的程序語句覆蓋信息,精簡了運行時的執(zhí)行失敗測試用例數(shù)量,從而提升了測試用例的質(zhì)量以及軟件故障定位的效率。
由于語句執(zhí)行的覆蓋信息都為二進制表示方法,因此將所有失敗測試用例的覆蓋信息做邏輯與運算,則能夠精簡頻譜信息,從而縮小查找故障語句的范圍,并且通過頻譜增強后的測試用例一定會覆蓋存在故障的語句。我們將與運算操作取得的覆蓋信息這個操作稱為頻譜增強。再使用增強過的頻譜信息進行SBFL可疑度值計算,最后根據(jù)優(yōu)化后的可疑度排名列表進行更高效的故障定位。整體流程如圖3所示。
圖3 SBFL(E)流程圖
單故障場景下,頻譜增強后得到唯一的失敗測試用例。程序運行時,唯一的故障語句必然被所有失敗測試用例所覆蓋,否則測試用例通過,運行結(jié)果正確,程序成功執(zhí)行。而多故障場景中,并不是所有的故障語句都被每一個失敗測試用例所覆蓋,我們采取根據(jù)多故障數(shù)量k進行頻譜增強的方式,最后得到k個頻譜增強后的失敗測試用例。
將失敗測試用例集設(shè)為T,T={T1,T2,…,Ti,…,Tm},其中Ti為第i個失敗測試用例的執(zhí)行情況,具體失敗測試用例的覆蓋信息設(shè)為集合t,t={ti1,ti2,…,tij,…,tin},其中i為執(zhí)行失敗測試用例編號,j為語句行號,n為總語句數(shù),ti為第i個執(zhí)行失敗測試用例的執(zhí)行情況,tij為第i個執(zhí)行失敗測試用例的第j條語句的覆蓋情況,覆蓋情況取值為0或1,0為未被覆蓋語句,1為被覆蓋語句b。頻譜增強E={e1,e2,…,el,…,en},其中:
(1)
以表2中多故障程序Mid為例,執(zhí)行失敗測試用例數(shù)為4,語句總數(shù)為13,故障,有4個失敗執(zhí)行覆蓋t6,t7,t8和t9,其中以t6為例,t6={1,1,1,0,0,0,0,1,1,1,0,0,1}。利用頻譜增強的定義,通過頻譜增強方法可以得到該例子中E1={e1,e2,…,el,…,en}。
為驗證本文方法的有效性,實驗比較了SBFL(未經(jīng)過頻譜增強)和SBFL(E)(經(jīng)過頻譜增強)的故障定位性能。實驗運行環(huán)境為Windows10和Ubuntu系統(tǒng),2.60 GHz Intel(R)i5四核處理器,16 GB 物理內(nèi)存。
我們采取基準程序進行了5個案例研究,其中3個程序是西門子(Siemens)程序套件的一部分,其余兩個程序來自Defects4j,數(shù)據(jù)集的詳細信息在表3中列出?;谌斯す收系奈鏖T子程序選取了Tcas,Totinfo和Printtokens2;基于真實故障的Defects4j程序選取了Apache Common Lang和JFree Chart。這些C語言(Siemens)和JAVA(Defects4j)程序被廣泛用于軟件測試和故障定位的實驗中,也用于我們之前的研究工作當中。
表3 數(shù)據(jù)集
所有基準程序的單故障版本可以分別從SIR(software-artifact infrastructure repository)和Defects4j資源庫下載。在多故障版本中,故障是手動播種到原始程序中的。由于大多數(shù)程序都是單故障,我們將單故障版本結(jié)合起來,建立多故障版本。Rui[22]和Zakari[19]也創(chuàng)建了包含2、3、4和5個故障的多故障版本,以產(chǎn)生Siemens-M案例研究。
在本文中,我們采用EXAM和Top-N用于評估我們提出的SBFL(E)方法的性能的指標,并將其與其他故障定位技術(shù)的有效性進行比較。
根據(jù)Wong等人提出的評價標準[23],我們的研究采用EXAM作為評價指標,其定義為發(fā)現(xiàn)程序中所有故障時需要檢查的代碼行數(shù)占程序總代碼行數(shù)的百分比。具體公式為:
(2)
Top-N用于評估故障元素的絕對排名,它通過檢查排名列表的前n個位置來計算成功定位的故障總數(shù)。N越小,故障定位技術(shù)就越有效。值得注意的是,程序員在實踐中會更多地關(guān)注最可疑的元素,他們不是一個一個地檢查排名列表中的語句,而是在排名列表中的不同位置之間表現(xiàn)出某種形式的跳躍,直到關(guān)于故障原因的假設(shè)得到確認[25]。此外,排名靠前的位置很少被程序員跳過,所以Top-1對于評估故障定位技術(shù)的有效性和準確性極為關(guān)鍵。
基于上述提出的方法,本節(jié)對實驗進行了詳細描述和分析。我們建立了一個名為SBFL(E)的故障定位技術(shù),它通過頻譜增強來優(yōu)化SBFL,為了評估我們方法的有效性,我們采用了4個常用的SBFL技術(shù)作為基準。
在我們的實驗研究中,我們執(zhí)行了5個基準程序,包括3個西門子套件和兩個Defects4j實用程序,每個程序中都包含一個故障。圖4顯示了Dstar,Jaccard,Ochiai和Tarantula對3個西門子程序(Tcas,Totinfo和Printtokens2)的推廣技術(shù)的比較;Defects4j數(shù)據(jù)集中Chart和Lang的整體表現(xiàn)也可以在圖5中見證。在每張圖中,橫軸表示EXAM分數(shù)的百分比,而縱軸表示能檢測到存在故障版本的百分比。
圖4 單故障西門子程序EXAM指數(shù)
圖5 單故障Defects4j程序EXAM指數(shù)
從圖4和圖5的結(jié)果分析中,我們發(fā)現(xiàn)由頻譜增強的技術(shù)在尋找單一故障方面比現(xiàn)有的技術(shù)表現(xiàn)得更好,尤其是Ochiai(E)方法EXAM在分數(shù)為15%~20%時表現(xiàn)突出,它能夠定位90%以上的故障版本。Jaccard(E)和Dstar(E)也在圖5中的相同范圍內(nèi)保持了類似的趨勢,能夠定位大約95%的故障版本。
我們在單故障程序中手動添加了一個故障,從而得到雙故障程序。我們執(zhí)行每個有兩個故障的基準程序,計算了EXAMF和EXAML值,以評估我們技術(shù)的準確性,如圖6和7所示。并介紹了4種技術(shù)對西門子程序的EXAMF和EXAML的比較。同樣,對于Defects4j程序,4種技術(shù)的比較見圖8和9。從結(jié)果分析中,我們可以看到,所提出的技術(shù)SBFL(E)在大多數(shù)情況下都優(yōu)于傳統(tǒng)SBFL。由于確保頻譜增強技術(shù)確實在多故障程序中起到了優(yōu)化作用,我們在每個西門子和Defects4j基準程序中手動添加到3個故障,準備了三故障程序來進行進一步實驗研究。圖10~12分別給出了4種技術(shù)對西門子程序的EXAMF,EXAMM,以及EXAML值的比較。對于Defects4j程序,類似的比較如圖9所示。綜合來看,我們提出的技術(shù)比現(xiàn)有的SBFL技術(shù)表現(xiàn)得更好。
圖6 雙故障西門子程序EXAMF和EXAML指數(shù)
圖8 三故障西門子程序EXAMF、EXAMM和EXAML指數(shù)
圖9 三故障Defects4j程序EXAMF、EXAMM和EXAML指數(shù)
為了評估他們對頂級可疑元素的表現(xiàn),使用了Top-n作為測量指標。95%的審查都是從排序列表中的第1個可疑元素開始的,這意味著首位很少被程序員跳過。因此,如何提高故障定位的準確性,特別是Top-1可疑元素,對故障定位的實用性至關(guān)重要。如表4所示,SBFL(E)技術(shù)通過檢查單故障程序中的Top-1、Top-3和Top-5可疑語句,分別成功定位了數(shù)量更多的故障。表4突出了西門子程序的性能,每一種技術(shù)都得到了不同程度的改善,其他采用頻譜增強技術(shù)在Top-1上比傳統(tǒng)技術(shù)可以多定位到約20%以上的故障,在Top-3和Top-5上都有同比增長。同樣,表4也顯示了Defects4j中同樣的8種技術(shù)進行比較,所有的SBFL技術(shù)的效率都因為頻譜增強所提升。最明顯的變化是Dstar(E)在重要的Top-1上,故障定位數(shù)量從49增加到61。
表4 單故障程序中Top-N指數(shù)名稱
在多故障程序中,Top-N在SBFL和SBFL(E)技術(shù)之間展示了不同程度的增長。如表5所示,在雙故障的西門子程序中,Dstar(E)通過檢查前1、3和5條可疑語句,可以分別定位24、53和66個故障(約占所有故障的20.3%、44.9%和55.9%)。Dstar(E)和Tarantula(E)保持著類似的趨勢,且表現(xiàn)比Ochiai(E)好。如表5所示,在3個故障的西門子程序中,Dstar(E)通過檢查前1、3和5條可疑語句,分別可以定位36、67和88個故障(約占所有故障的19.6%、36.4%和47.8%)。Jaccard(E),Ochiai(E)和Tarantula(E)的存在相同的趨勢,且差異較小。如表5和6所示,在多故障Defects4j程序中的優(yōu)勢更為顯著,SBFL(E)在Top-1,Top-3以及Top-5中都保持較好的性能,盡管在少數(shù)情況下,與傳統(tǒng)的SBFL技術(shù)相比,它未能定位更多的故障。
表6 三故障程序中Top-N指數(shù)名稱
故障定位是困難且代價高的,這就是為什么我們在過去20年中看到了各種故障定位技術(shù)被提出。多故障定位正在成為軟件測試研究領(lǐng)域中最關(guān)鍵的問題之一。在實踐中,我們發(fā)現(xiàn)在傳統(tǒng)的SBFL中冗余的失敗測試用例會給故障定位效率帶來消極影響,這阻礙了程序員在調(diào)試故障時的效率和生產(chǎn)力。此外,我們注意到使用頻譜增強的邏輯與運算可以有效精簡失敗測試用例的頻譜信息,優(yōu)化可疑度值以提高故障元素的等級。
在本文中,我們提出了基于頻譜增強的多故障定位方法。首先,使用頻譜增強的方法精簡失敗的測試用例,再利用SBFL的統(tǒng)計公式對新的頻譜信息進行評估,并根據(jù)其可疑度對潛在的故障語句進行排序。最后,被SBFL(E)排在前N位的語句根據(jù)其新的分數(shù)排序。所提出的故障定位方法緩解了SBFL的缺點,提高了故障定位的準確性。通過使用5個開源基準程序的案例研究來評估我們框架的性能。為了顯示我們提出的技術(shù)的效率,將我們的工作與4個密切相關(guān)的故障定位技術(shù),即Dstar、Jaccard、Ochiai和Tarantula進行了比較。實驗結(jié)果表明,與典型的SBFL定位方法相比,基于頻譜增強的方法可以顯著減少代碼檢查的范圍,尤其是在高性能范圍內(nèi)(即EXAM5%和Top-1),明顯提高了故障定位的性能。
但是在這個領(lǐng)域還有很大的發(fā)展空間,也有一些問題需要解決。存在程序中如果失敗測試用例過少的問題,而測試用例質(zhì)量及其數(shù)量對結(jié)果有很重要的影響;以及頻譜增強的思想能否運用到其他故障定位方法當中。后期研究人員還需要努力減少其負面影響,甚至解決這些問題。雖然本實驗選擇的基準程序在故障定位領(lǐng)域具有代表性,具有說服力,但在今后的工作中,我們將把重點放在更真實的工程程序上??偟膩碚f,隨著研究界對SFL研究的極大興趣,以及最近該領(lǐng)域出版物的一致性,我們希望在未來幾年會有更多具體的解決方案來解決多故障問題。