考慮缺陷關(guān)聯(lián)模型的軟件優(yōu)化測試策略

姚　弋，謝曉鳴，劉書涵，張　娜，俞成海

(1.浙江省消防總隊,杭州 310014;2.浙江理工大學信息學院，杭州 310018)

?

考慮缺陷關(guān)聯(lián)模型的軟件優(yōu)化測試策略

姚弋1，謝曉鳴2，劉書涵2，張娜2，俞成海2

(1.浙江省消防總隊,杭州 310014;2.浙江理工大學信息學院，杭州 310018)

軟件測試中，缺陷關(guān)聯(lián)是一種比較普遍的現(xiàn)象。已有研究表明，充分利用缺陷之間的關(guān)聯(lián)信息有助于提高軟件測試效率，同時，從缺陷自身角度分析，為了綜合權(quán)衡多個影響測試決策的因素(如缺陷等級、缺陷可檢測率和缺陷關(guān)聯(lián)關(guān)系)。提出一種基于缺陷關(guān)聯(lián)的受控馬爾科夫鏈測試模型，將測試過程轉(zhuǎn)換成基于多目標權(quán)值的路徑優(yōu)化問題，綜合權(quán)衡缺陷可檢測率、關(guān)聯(lián)系數(shù)和測試回扣；并運用Prim算法構(gòu)造最小生成樹以構(gòu)造基于多目標權(quán)值的軟件優(yōu)化測試策略。在資源約束下，該方法利用缺陷關(guān)聯(lián)引導測試決策的選取，優(yōu)先檢測關(guān)聯(lián)緊密、可檢測率大、回扣多的關(guān)聯(lián)缺陷。通過仿真實驗，證明了該方法的有效性。

軟件測試；受控馬爾科夫鏈；關(guān)聯(lián)缺陷；多目標權(quán)值；Prim算法

0　引　言

由于軟件開發(fā)過程仍嚴重依賴開發(fā)人員的技術(shù)和經(jīng)驗，缺乏客觀統(tǒng)一的評價標準，導致軟件失效的現(xiàn)象頻發(fā)，軟件可靠性[1]問題已成為制約軟件產(chǎn)業(yè)發(fā)展的瓶頸之一。作為軟件質(zhì)量保證的重要手段，軟件測試已成為學術(shù)界和工業(yè)界研究的重點。目前，部分研究者通過受控馬爾可夫鏈(controlled markov chain, CMC)理論構(gòu)建測試模型[2]，在資源約束下，希望以最小的成本檢測并剔除盡可能多的缺陷。但不同種類的軟件缺陷所引發(fā)的失效程度不同，因而缺陷被剔除后所產(chǎn)生的測試價值(回扣值)也不同，這就導致測試目標不僅僅是檢測更多的缺陷數(shù)量，同時也應(yīng)該兼顧測試價值。發(fā)現(xiàn)一個致命的軟件缺陷顯然比檢測到一些輕微的缺陷能產(chǎn)生更多的測試價值。此外，在實際測試過程中，缺陷之間往往相互關(guān)聯(lián)。盡管軟件企業(yè)力求以高內(nèi)聚低耦合[3]的標準去開發(fā)產(chǎn)品，但對多數(shù)程序而言，其所選擇語句的運行或多或少都要受到程序中其他已執(zhí)行語句的影響，這表明缺陷之間存在著關(guān)聯(lián)關(guān)系。研究表明，集成相同或者相似功能的測試用例通常能夠檢測出包含該特性的缺陷[4]。為此，如何有效地運用缺陷關(guān)聯(lián)性，并結(jié)合已有的測試模型設(shè)計基于多目標的軟件測試策略成為本文研究的重點。

本文在前期研究成果上[2]，提出了一種引入缺陷關(guān)聯(lián)度的CMC測試模型，將缺陷關(guān)聯(lián)系數(shù)、缺陷可檢測率和回扣三者作為權(quán)值，以支持基于多目標權(quán)值的決策選取標準。利用缺陷之間的關(guān)聯(lián)信息，以軟件缺陷作為頂點，關(guān)聯(lián)關(guān)系當作路徑，將測試過程轉(zhuǎn)換成求解帶權(quán)路徑優(yōu)化問題；運用Prim算法構(gòu)造最小生成樹以獲得基于多目標的軟件缺陷優(yōu)化測試策略。該方法利用關(guān)聯(lián)缺陷引導測試決策的選取，優(yōu)先檢測關(guān)聯(lián)緊密、可檢測率大、回扣多的關(guān)聯(lián)缺陷集。

1　相關(guān)工作

本文研究的內(nèi)容與關(guān)聯(lián)缺陷和基于受控馬爾科夫鏈測試模型的研究密切相關(guān)。

為形式化描述測試過程中軟件狀態(tài)的改變，降低建模復(fù)雜度，部分研究者對受控馬爾科夫鏈測試模型進行了一些特殊化的處理，主要包括[5-7]：a)假定被測軟件包含的缺陷數(shù)一定，b)假定不同的軟件缺陷被檢測到的概率相等，c)假定檢測到一個缺陷就立即剔除，d)假定剔除缺陷的決策不消耗測試資源(即代價)，e)假定剔除不同缺陷產(chǎn)生的回扣相等。為了縮小測試模型與實際運行時的環(huán)境差異，Hu等[8]完善了模型的假設(shè)條件，包括考慮了不同種類缺陷具有不同的可檢測率；啟用批量剔除策略等，提高了模型的實用性。包曉安等[2]對資源受限環(huán)境下的測試過程進行了探索，提出了一種資源受約束的CMC測試模型，并以此構(gòu)造軟件自適應(yīng)測試策略。雖然這些測試技術(shù)都經(jīng)過了理論分析和實踐驗證，較好的提升了軟件測試效率，但他們大都存在一個共同的缺陷：即忽略了軟件缺陷之間的關(guān)聯(lián)關(guān)系。

在實際測試過程中，測試人員通常會發(fā)現(xiàn)缺陷之間存在某種關(guān)聯(lián)，即失效關(guān)聯(lián)，而這種關(guān)聯(lián)關(guān)系可以影響相關(guān)缺陷的檢測能力，為測試人員提供某種啟發(fā)式的方法，從而對測試結(jié)果產(chǎn)生影響。李鵬等[9]基于面向?qū)ο蟮脑O(shè)計模型，分析了軟件缺陷的傳播過程。針對關(guān)聯(lián)缺陷的檢測，景濤等[10]從軟件缺陷角度分析失效關(guān)聯(lián)，提出一種基于缺陷放回的測試方法。這些文獻大多從缺陷關(guān)聯(lián)的現(xiàn)象進行分析，評估關(guān)聯(lián)失效對軟件可靠性造成的影響，認為關(guān)聯(lián)缺陷是造成軟件失效的根源之一。但已有研究也表明[11]，在單元測試中發(fā)現(xiàn)的多個程序錯誤很大程度上來自于同一函數(shù)或者模塊，受到相同程序結(jié)構(gòu)的影響，所以存在的錯誤往往具有相似性與關(guān)聯(lián)性。因此，如何利用缺陷關(guān)聯(lián)信息引導軟件測試過程，權(quán)衡多個影響測試決策選取的因素，設(shè)計基于多目標的優(yōu)化測試策略成為本文研究的重點。

2　基于缺陷關(guān)聯(lián)的軟件測試模型

2.1關(guān)聯(lián)缺陷定義

針對關(guān)聯(lián)缺陷的定義基于以下假設(shè)：

a)對于一個軟件系統(tǒng)，定義St=St(n)表示t時刻軟件系統(tǒng)剩余缺陷數(shù)，St(0)表示系統(tǒng)的終止態(tài)，表明系統(tǒng)中剩余缺陷為0，測試過程停止；

b)缺陷集合Defects={d1,d2,…，dn}；n>0,n為總?cè)毕輸?shù)；測試用例庫TCase={tc1,tc2,…，tcm},m>0,m為測試用例總數(shù)；

c)缺陷被修復(fù)后不引入新的缺陷；

定義1將DDP(di)表示為t時刻下測試用例 tcm檢測到缺陷di的概率，其中DDP表示缺陷檢測率(defectdetectedprobability，DDP)，tcm∈TCase，di∈Defects。

定義2對于同一個tcm而言，由于di被檢測到而使得dj被檢測到的概率變?yōu)镈DP1(dj)，則稱di關(guān)聯(lián)dj，記為di&dj={(di,dj)|rij}，其中關(guān)聯(lián)系數(shù)rij表示缺陷之間的關(guān)聯(lián)程度。

2.1基于Markov決策的測試模型構(gòu)建

原有的測試模型通過缺陷檢測率來實現(xiàn)軟件狀態(tài)的改變，沒有考慮每個缺陷的重要性和關(guān)聯(lián)性。本文引入缺陷關(guān)聯(lián)系數(shù)，并結(jié)合缺陷檢測率和回扣組成多目標權(quán)值作為軟件狀態(tài)轉(zhuǎn)移標準。針對軟件測試過程，本文的模型[12]基于以下假設(shè)：

a)測試開始時(t=0時刻)，軟件系統(tǒng)包含n個缺陷。

(1)

其中k=1,2，…，n.

d)在每個時刻t，總有m+1個可選決策A={1, 2…m, rev}，其中前m個決策用于檢測缺陷，每個決策消耗資源Cξt(At)，rev用于剔除缺陷，其執(zhí)行代價為C1，每當檢測到d個缺陷時候就執(zhí)行一次批量剔除。

e)元素rij代表缺陷i與缺陷j關(guān)聯(lián)且具有值為rij的關(guān)聯(lián)性。Rij組成n階缺陷關(guān)聯(lián)矩陣Ω：

(2)

f)缺陷檢測率用矩陣Θ表示：

(3)

g)在決策At下，某個缺陷被檢測并剔除后獲得一定的測試價值，即產(chǎn)生回扣δx。缺陷的性質(zhì)、成因以及其被檢測和修復(fù)的成本決定了其測試價值，對于那些包含在交互接口、底層框架、系統(tǒng)核心業(yè)務(wù)之中的缺陷，尤其具有較高的測試價值，因而也能產(chǎn)生較大的測試回扣。為了表示不同重要性等級的缺陷所產(chǎn)生的測試價值，將每個缺陷的期望回扣用向量δ=[δ1,δ2,…，δn]表示。

(4)

其中：x0和xr分別表示初始資源跟剩余資源，CSt(At)表示每次檢測所需的資源，(n/d+1)C1表示執(zhí)行批量剔除消耗的資源。則有：

(5)

3　多目標優(yōu)化測試策略設(shè)計

將待測缺陷作為圖中頂點，則V={1,2,3，…，n}，令Wij為邊的權(quán)值，用矩陣表示如下：

即用關(guān)聯(lián)缺陷系數(shù)、缺陷回扣、缺陷可檢測率的乘積表示缺陷i與j之間的權(quán)值。為了獲得基于權(quán)值的測試決策，需要在W中尋找包含最大權(quán)值的連通分量，并運用Prim算法來構(gòu)造最小生成樹以獲得缺陷的遍歷序列。

基于Prim算法的測試決策生成:

a)InitialS,v∈U,u∈V-U //Te為S中邊的集合,V為S中頂點的集合，(v,u)表示一條具有最大權(quán)值的邊;

b)S=DFS_MaxWeight(wij)//搜索具有最大權(quán)值的連通分量;

c)K=InitVex(S,U);//從第U個頂點出發(fā)構(gòu)造S的最小生成樹T，記錄T的各個頂點;

d)Edge_array[S.vexnum]//設(shè)置輔助數(shù)組,記錄S中具有最大權(quán)值的邊;

e)Init_Edge();//初始化輔助數(shù)組;

f)初始化U={u0};

g)RepeatuntilU=V;

h)k=MaxWeight(Edge_array);//求出T的下一個結(jié)點第k頂點;

i)//closedge[k].highcost=Max{closedge[vi].highcost|closedge[vi].highcost>0,vi∈V-U};

j)addTe(vi,ui);//在S尋找一條權(quán)值最大的邊并入集合Te;

k)addU(ui);//將u0并入U，直到U=V;

l)Output()//依次輸出最小生成樹的邊G={(v0,u0),(v1,u1)…(vi,ui)};

4　仿真驗證

本文選取隨機測試和參數(shù)已知的自適應(yīng)測試作為比較標準，來驗證測試模型和策略的有效性。在隨機測試中每個決策被選取的概率相等，缺陷檢測順序隨機選擇。為了減少自適應(yīng)測試中參數(shù)估計的準確性，避免對測試結(jié)果的干擾，本文用0.8作為實際參數(shù)估計的結(jié)果進行擬合。

所構(gòu)造的最小生成樹頂點集合為：G={3，5，1，6，4}，根據(jù)頂點集合G可得檢測順序為Di={5, 3, 4, 6, 1, 2, 7},那么根據(jù)轉(zhuǎn)移概率矩陣可知，決策選擇順序為：At={9，3，10，1，7，5，8}。

根據(jù)以上決策并結(jié)合給定的相關(guān)參數(shù)，將基于多目標的優(yōu)化測試策略(OT)分別與隨機測試(RT)和自適應(yīng)測試(AT)相比較。為了反映軟件狀態(tài)在測試過程中的變化，從多次測試結(jié)果集中隨機選取一條軟件狀態(tài)轉(zhuǎn)移路徑，并比較它們在3種測試策略下的代價，如表1所示。從表1中數(shù)據(jù)可知，優(yōu)化測試策略比隨機測試和自適應(yīng)測試分別少花費約30.51%和20.65%的代價。為了更形象地反映仿真結(jié)果，將表1數(shù)據(jù)繪制成圖1，其中橫坐標表示每個決策下的軟件狀態(tài)，縱坐標表示轉(zhuǎn)移代價。

表1　3種測試策略下軟件狀態(tài)轉(zhuǎn)移代價的比較

表2　剔除的缺陷數(shù)和回扣值比較

圖1　3種測試策略下軟件狀態(tài)轉(zhuǎn)移代價的比較

在初始資源相同的條件下，由于假設(shè)執(zhí)行決策所消耗的資源相同，為了顯示不同方法在檢測缺陷數(shù)和測試價值的差異，將問題轉(zhuǎn)化為在有限測試次數(shù)下比較3種方法剔除的缺陷數(shù)和產(chǎn)生的回扣值。表2顯示了在測試步數(shù)為30時，3種測試策略下的剔除缺陷數(shù)和回扣值。從表2中可知，OT比RT和AT分別多檢測46.63%和10.13%的缺陷數(shù)，同時，OT比RT和AT分別多產(chǎn)生45.62%和16.23%的回扣。

相比于缺陷獨立的假設(shè)，基于多目標的優(yōu)化測試略充分利用缺陷之間的關(guān)聯(lián)信息，提高相關(guān)缺陷的檢測率，并根據(jù)多目標權(quán)值選取測試決策，因而能夠產(chǎn)生更多的回扣。相比與其他兩種方法，本文的測試方法在軟件狀態(tài)轉(zhuǎn)移代價、缺陷剔除數(shù)和產(chǎn)生回扣上具有一定的優(yōu)勢。

5　結(jié)　語

在前期工作基礎(chǔ)上，本文利用關(guān)聯(lián)缺陷性質(zhì)改進受控馬爾科夫鏈測試模型，將測試過程轉(zhuǎn)換成基于多目標的帶權(quán)路徑優(yōu)化問題，并運用Prim算法構(gòu)造最小生成樹，以獲取基于缺陷回扣、缺陷檢測率、關(guān)聯(lián)系數(shù)的決策選取序列。通過與其他兩種方法進行比較，仿真實驗結(jié)果表明，本文所提的測試策略是可行和有效的。

[1] KAPUR P K, PHAN H, ANAND S,et al. A unified approach for developing software reliability growth models in the presence of imperfect debugging and error generation[J]. IEEE Trans on Reliability, 2011,60(1):331-340.

[2] 包曉安,姚瀾,張曉文,等.基于受控馬爾科夫鏈的軟件缺陷優(yōu)化測試策略[J].計算機科學，2012,39(5):117-119.

[3] 張莉,錢冠群,李琳. 基于變更傳播仿真的軟件穩(wěn)定性分析[J]. 計算機學報，2010,33(3): 440-451.

[4] ZHAO D, UPADHYAYA S. Dynamically partitioned test scheduling with adaptive TAM configuration for power-constrained SoC testing[J]. IEEE Transaction on Computer-aided Design of Integrated Circuits and Systems, 2005, 24(6): 956-965.

[5] CAI K Y. Optimal software testing and adaptive software testing in the context of software cybernetics[J]. Information and Software Technology,2002 ,44(02) : 841-855.

[6] WEYNS K, RUNESON P. Sensitivity of software system reliability to usage profile changes[C]//Proceedings of the 2007 ACM symposium on Applied computing. ACM, 2007: 1440-1444.

[7] CAI K Y, DONG Z, LIU K, et al. A mathematical modeling framework for software reliability testing[J]. International Journal of General Systems, 2006, 36(4): 399-463.

[8] HU H, JIANG C H, CAI KY. Adaptive software testing in the context of an improved controlled Markov chain model[C]//Computer Software and Applications, 2008. COMPSAC'08. 32nd Annual IEEE International. IEEE, 2008: 853-858.

[9] 李鵬, 趙逢禹. 軟件缺陷關(guān)聯(lián)分析與缺陷排除研究[J]. 計算機科學, 2013,40(10):159-161.

[10] 景濤,江昌海,胡得斌,等.軟件關(guān)聯(lián)缺陷的一種檢測方法[J]. 軟件學報，2005,16(1):17-18.

[11] 張云乾,鄭征,季曉慧,等. 基于馬爾可夫模型的軟件錯誤定位方法[J]. 計算機學報，2013, 36(2):445-456.

[12] 包曉安,謝曉鳴,張娜,等. 基于缺陷關(guān)聯(lián)度的Markov模型軟件優(yōu)化測試策略[J]. 軟件學報,2015, 26(1): 14-25.

(責任編輯： 陳和榜)

Software Optimization Testing Strategy Considering Defect Correlation Model

YAOYi1,XIEXiaoming2,LIUShuhan2,ZHANGNa2,YUChenghai2

(1.Fire Corps of Zhejiang Province, Hangzhou 310014, China; 2.School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China)

In software testing, defect correlation is a relatively common phenomenon. Studies have shown that making the best of associated information between defects is beneficial to improving software testing efficiency. Meanwhile, from the perspective of defects themselves, a controlled Markov chain model based-on the defect correlation is proposed in order to synthetically balance multiple factors influencing the decision-making (such as defect severity level, defect detecting rate and the relationships between correlated detects). The testing is converted to route optimization problem based on multi-objective weight. Besides, defect detection rate, correlation coefficient and testing rebates are measured overall. Prim algorithm is applied to construct minimum spanning tree so as to construct software optimization testing strategy based on multi-objective weight. Under resource constraint, this method utilizes defect correlation to guide selection of testing strategy, and preferentially detect correlated defects with close correlation, large detection rate and many rebates. The simulation experiment proves effectiveness of the method.

software testing; controlled markov chain; correlated defects; multi-objective weight; Prim algorithm

10.3969/j.issn.1673-3851.2016.01.013

2014-11-27

國家自然科學基金項目(61379036，61502430);浙江省自然科學基金項目(Y13F020175，LY12F02041);浙江省新苗計劃項目(2014R406073);浙江理工大學521人才培養(yǎng)計劃

姚弋(1975-)，男,浙江諸暨人，高級工程師，主要從事數(shù)據(jù)庫及軟件測試技術(shù)方面的研究。

張娜，E-mail: zhangna@zstu.edu.cn

TP311

A

1673- 3851 (2016) 01- 0078- 06 引用頁碼： 010601