張 軍, 劉 鋒, 馬竹娟, 朱二周
(1.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 合肥 230601; 2.安徽農(nóng)業(yè)大學(xué) 經(jīng)濟技術(shù)學(xué)院,安徽 合肥 230036)
改進型程序切片方法的測試需求約簡技術(shù)研究*
張 軍1, 劉 鋒1, 馬竹娟2, 朱二周1
(1.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 合肥 230601; 2.安徽農(nóng)業(yè)大學(xué) 經(jīng)濟技術(shù)學(xué)院,安徽 合肥 230036)
傳統(tǒng)的測試用例集約簡技術(shù)大多采用由測試需求集直接生成測試用例集的方法。該方法雖然能夠約簡測試用例集,但出現(xiàn)測試需求冗余,約簡后的測試用例集不夠精準(zhǔn)等問題。針對這些問題,提出了一種基于六元結(jié)構(gòu)表的程序切片方法。利用程序切片精簡測試代碼,省去構(gòu)造程序依賴圖的復(fù)雜步驟;根據(jù)代碼間的相互關(guān)系和模塊間的耦合度,利用啟發(fā)式算法約簡測試需求;在約簡后的測試需求上,精簡測試用例集。將該方法應(yīng)用到當(dāng)前主流的Android平臺上比較約簡前后G,GRE的用例集。實驗結(jié)果表明:約簡后的測試需求集能夠在獲得較少的測試用例集的前提下保證較高的覆蓋率。
程序切片; 測試需求約簡; 耦合度; 六元結(jié)構(gòu)表
隨著移動互聯(lián)網(wǎng)的快速發(fā)展,越來越多用戶使用移動設(shè)備,Android版App軟件已經(jīng)被越來越多的人使用[1]。但隨著App版本不斷地迭代,出現(xiàn)舊的測試用例和新的測試用例重合,導(dǎo)致敏捷開發(fā)效率低下。在軟件開發(fā)過程中軟件測試是必不可少的環(huán)節(jié),它在整個軟件的生命周期中具有舉足輕重的地位。在軟件測試之前,測試人員根據(jù)測試需求,生成測試用例,然后發(fā)現(xiàn)軟件開發(fā)過程中存在的問題并加以糾正,保證軟件質(zhì)量。隨著軟件版本的迭代,測試用例集的規(guī)模也隨之增長,不可避免出現(xiàn)用例冗余。如何有效降低冗余,提高測試效率,成為研究軟件測試的必備內(nèi)容,此即測試用例集約簡的目的。
現(xiàn)有測試用例集約簡方法是針對原測試需求集,生成相應(yīng)的測試用例集,然后尋找測試用例集的某個子集,用盡可能少的測試用例滿足測試需求。測試用例集約簡方法主要包括貪心算法、一些啟發(fā)式算法、整數(shù)規(guī)范等方法[2]。這些方法是在滿足已知的測試需求和測試用例關(guān)系條件下直接約簡測試用例集。但忽視了測試需求間的相互關(guān)系,導(dǎo)致約簡后的測試用例集出現(xiàn)測試效果不明顯的現(xiàn)象。
針對傳統(tǒng)的測試用例集約簡方法的不足,結(jié)合文獻[3]和程序切片技術(shù),提出了一種利用結(jié)構(gòu)表構(gòu)造的程序切片約簡測試需求集的新方法。程序切片是一種分析和理解程序的技術(shù),主要應(yīng)用于程序分析、軟件測試及領(lǐng)域[3],通過對源代碼進行分析和研究,刪除與興趣點無關(guān)的語句和謂詞,達到縮減程序代碼,保證所得的程序與源程序在語義上一致性。
程序切片技術(shù)的發(fā)展經(jīng)歷了從靜態(tài)到動態(tài)、從過程內(nèi)到過程間等幾個方面的過程,每種切片都有各自的優(yōu)勢與劣勢。從軟件需求角度考慮,若需求包含完整的輸出描述,則需求可以看作初始化過程到最終功能語句之間的靜態(tài)切片;若從測試用例集方面考慮,每個用例都對應(yīng)著不同狀態(tài)下的動態(tài)切片。
傳統(tǒng)的靜態(tài)程序切片算法是基于系統(tǒng)依賴圖(SDG)的遍歷算法。SDG以程序依賴圖為基礎(chǔ),反映程序的數(shù)據(jù)和控制依賴等信息。但生成SDG需要計算與切片無關(guān)的數(shù)據(jù)依賴,造成時間和空間上的浪費。本文結(jié)合文獻[4]提出的五元結(jié)構(gòu)[4],提出了基于六元結(jié)構(gòu)表程序切片構(gòu)造方法,既能夠降低時間和空間復(fù)雜度,又能夠保證約簡后代碼功能的完整性。
1.1 結(jié)構(gòu)表模型構(gòu)造
構(gòu)造結(jié)構(gòu)表模型需要以下3個步驟:
1)通過詞法和語法分析生成TOKEN序列,在TOKEN序列基礎(chǔ)上進行代碼標(biāo)準(zhǔn)化[5],生成標(biāo)準(zhǔn)TOKEN序列。
2)在步驟(1)基礎(chǔ)上,生成對應(yīng)的六元結(jié)構(gòu)表和復(fù)合語句信息表。
3)利用六元結(jié)構(gòu)表和復(fù)合語句信息表,得到程序切片。
1.2 六元結(jié)構(gòu)表構(gòu)造
定義1 六元結(jié)構(gòu)表(imnNCf)〈i,m,n,N,C,f〉為程序中變量的聲明、賦值和函數(shù)調(diào)用、使用參數(shù)的關(guān)系。其中,i為語句的行號;m為聲明變量或函數(shù)所在的行號;n為i行定義的變量;N為i行使用變量或函數(shù)形參的集合;C為i行復(fù)合關(guān)系的集合;f為i行調(diào)用函數(shù)名。imnNCf中值不存在用?表示。
1.3 復(fù)合語句信息表構(gòu)造
定義2 復(fù)合語句信息表為表示復(fù)合語句結(jié)構(gòu)信息。其中,id為語句的標(biāo)示;name為語句名;beginline為語句開始行;endline為語句結(jié)束行;f為是否存在調(diào)用函數(shù);?表示不存在。
圖1為Android代碼例子。由于篇幅所限僅列表1、表2,為showViews函數(shù)的六元結(jié)構(gòu)表以及復(fù)合信息結(jié)構(gòu)表,其中,監(jiān)聽和點擊事件歸屬于showViews。
表1 showViews函數(shù)的六元結(jié)構(gòu)表
表2 showViews復(fù)合信息結(jié)構(gòu)表
程序代碼塊的功能:1)展示圖書類別;2)編輯圖書類別;3)刪除圖書類別。限于篇幅,代碼簡化,模塊流程不變。
1 public class BCLActivity extends Activity {
2 BCSAdapter adapter;
3 ListView lv;
4 List
5 String bookClassId;
6 Public void onCreate(Bundle savedInstanceState) {
7 showViews(bookClassId);}
8 private void showViews(bookClassId) {
9 lv=(ListView)findViewById(R.id.h_list_view);
10 list = getDatas();
11 adapter=new BCSAdapter(this,list,R.layout);
12 lv.setAdapter(adapter);
13 lv.setOCCMListener(bCLIListener);}
14 Private OCCMListener bCLIListener = new OCCMListener(){
15 public void OCCM(ContextMenu menu,View v,ContextMenuInfo menuInfo) {
16 menu.add(0,0,0,“刪除圖書類別”);
17 menu.add(0,1,0,“編輯圖書類別”);
18 menu.add(0,2,0,"展示圖書類別")} };
19 public boolean onContextItemSelected(MenuItem item){
20 AdapterCMInfocontextMenuInfo=(AdapterCMInfo)
item.getMenuInfo();
21 int position=contextMenuInfo.position;
22 StringbookId=(getDatas().get(position).get(“bookClassId”).toString());
23 bookClassId=bookId;
24 if(item.getItemId()==0){
25 dialog(bookClassId);
26 }else if (item.getItemId()==1){
27 EditBookActivity(BookClassEditActivity,bookClassId);
28 setViews(bookClassId);}
29 else if(item.getItemId()==2){
30 showViews(bookClassId);}}
31 protected void dialog(bookClassId){∥刪除
32 Builder builder=new Builder(BCLActivity.this);
33 builder.setPositiveButton(“確認(rèn)”,new OnClickListener(){
34 public void onClick(DialogInterface dialog,int which){
35 HashMap〈String,String〉params=new HashMap〈String,String〉();
36 params.put(“action”,“delete”);
37 remove(bookClassList,params);
38 setViews(bookClassId);}});}
39 private List〈Map〈String,Object〉〉getDatas(){
40 list=new ArrayList〈Map〈String,Object〉〉();
41 try{
42 List〈BookClass〉bookClassList=bCLHander.getBCList();
43 for(int i=0;i 44 Map〈String,Object〉map=new HashMap〈String,Object〉(); 45 map.put(“bookClassId”,bookClassList.get(i).getBookClassId()); 46 list.add(map);} 47 }catch(Exception e){} 48 return list; 49 }} imnNCf的構(gòu)造過程是對程序進行逆向流分析,在保證程序數(shù)據(jù)和控制依賴完整性的同時,剔除與興趣結(jié)點無關(guān)的代碼。算法1和算法2為具體的構(gòu)造過程。其中,算法1為構(gòu)造六元結(jié)構(gòu)表算法,算法2為構(gòu)造復(fù)合信息結(jié)構(gòu)表算法。 算法1 六元結(jié)構(gòu)表算法: 1)判斷興趣點是函數(shù)語句還是賦值語句:若為函數(shù)語句跳轉(zhuǎn)步驟(2),若為賦值語句跳轉(zhuǎn)步驟(3)。 2)逆向遍歷imnNCf,遍歷f值是否和興趣點值相同。若相同,跳轉(zhuǎn)步驟(4);若不相同,跳轉(zhuǎn)步驟(5)。 3)逆向遍歷imnNCf,遍歷n值是否和興趣點值相同。若相同,切片中加入該語句;若不相同,跳轉(zhuǎn)步驟(6)。 4)記錄i值,即程序的結(jié)束行,加入到切片,跳轉(zhuǎn)步驟(5)。 5)查看對應(yīng)行的N值:若值為?,表示不進行參數(shù)傳遞,跳轉(zhuǎn)到對應(yīng)函數(shù)f的imnNCf進行逆序遍歷;若值不為?,表示進行了參數(shù)傳遞,若實參為數(shù)值傳遞,被調(diào)函數(shù)中形參不影響實參,無需計算被調(diào)函數(shù)的子切片;若實參為地址傳遞,計算被調(diào)函數(shù)的子切片。跳轉(zhuǎn)步驟(8)。 6)查看對應(yīng)行的N值:若為?,即賦值語句右側(cè)是函數(shù),跳轉(zhuǎn)步驟(7);若不為?,查看f值,若為?,是變量賦值,首先進行逆向流分析,逆向遞歸計算其使用變量的子切片,然后加入到切片中;若不為?,則跳轉(zhuǎn)步驟(5)。 7)逆向遍歷對應(yīng)行f的imnNCf,查找C值,則跳轉(zhuǎn)步驟(8)。 8)對于C值:若不為?,查找復(fù)合信息結(jié)構(gòu)表,記錄復(fù)合函數(shù)切片;若為?,則結(jié)束。 算法2 復(fù)合信息結(jié)構(gòu)表算法: 1)根據(jù)imnNCf中C值,查找復(fù)合結(jié)構(gòu)表中id值,若C=id,跳轉(zhuǎn)步驟(2);若C≠id,逆序遍歷復(fù)合結(jié)構(gòu)表,直到C=id。 2)若復(fù)合關(guān)系未被處理過,加入到切片中;若有未處理變量,查找beginline-endline對應(yīng)的imnNCf,若變量和imnNCf中某一行n值相同,加入切片,跳轉(zhuǎn)步驟(3)。 3)逆向循環(huán)遍歷對應(yīng)行的N值和C值,步驟同算法1。 在圖1中,若以(28,bookClassId)為切片,計算結(jié)果為{28,26,1,5,6,7,8, 9,13,14,17,19,20,21,22,23}。 切片結(jié)果的準(zhǔn)確度直接影響到測試需求的準(zhǔn)確性。切片的準(zhǔn)確度Pslice為 (1) 式中Sstandard為標(biāo)準(zhǔn)切片集合;Scurrent為本文計算的切片集合;Pslice∈(0~1),若值越接近于1,表示切片準(zhǔn)確度越高。 對于切片準(zhǔn)則(28, bookClassId),標(biāo)準(zhǔn)的切片結(jié)果{19,20,21,22,23,24,25,26,27,28,29,16,17,14,13,12,11,10,9,8,7,6,5,1}。利用式(1),計算Pslice為66.7 %。 2.1 測試需求之間的關(guān)系和約簡方法 在軟件設(shè)計中應(yīng)盡可能使用松耦合關(guān)系。耦合是指各模塊間相互依賴程度的度量[6]。測試需求[7]之間的關(guān)系主要有包含、獨立和重合關(guān)系。若為獨立關(guān)系,則不必考慮耦合度;若為重合關(guān)系,則需要考慮耦合度;若為包含關(guān)系,即全耦合。以下給出測試需求ri和rj約簡步驟: 1)若ri包含了rj,則覆蓋了ri的測試用例均可以覆蓋rj。在進行測試時只需保留ri,即若ri和rj是相互包含關(guān)系,取ri或者rj中的一個。 3)若ri和rj是獨立關(guān)系,則ri和rj之間的測試用例沒有交集部分。這時,就無法約簡測試需求。 2.2 測試需求約簡算法 算法3 基于測試需求的約簡算法: 輸入:原測試需求集R。 輸出:精簡測試需求集R′。 R′:=R; ∥初始化 Pair:={(ri,rj)|ri,rj∈R(i,j=1,2,…,m,i While(Pair不為空) if(ri?rj)then∥若ri和rj是包含關(guān)系 R′=R-{ri};∥合并測試需求rj,保留測試需求ri else if(rj∩ri)then R′=R-{rj};∥去除測試需求rj,保留測試需求ri else if(ri∩rj≠?)then∥若ri和rj是重合關(guān)系 R′=ri+rj-ri∩rj else if(ri∩rj==?)then∥若ri和rj是獨立關(guān)系不約簡測試需求 end if end if end if end if end while 2.3 程序切片約簡測試需求 定義3 方法內(nèi)切片準(zhǔn)則: 方法內(nèi)切片準(zhǔn)則是一個3元組(M,s,v),其中,s為方法M的一條語句,v為在s點引用的變量。 定義4 方法耦合: Slice(M,s,v1)和Slice(M,s,v2)分別為方法v1和v2在s入口點的切片,方法v1和v2之間的耦合度Coupling(v1,v2)為 (2) 式中 0≤Coupling(v1,v2)≤1,耦合度越高,說明關(guān)聯(lián)性越大,代碼之間的重合度越高,冗余度越大,越要進行約簡。 對于showViews(bookClassId)函數(shù),有13個測試需求,圖1中每一個箭頭表示一個測試需求,即b1~b13。結(jié)合程序分析[8],通過imnNCf和啟發(fā)式算法可知b6≡b8≡b9,b11≡b13,b2≡b4,b2?b1,b10?b7,b3?b2,b5?b2,b12?b9。其中,≡為等價關(guān)系,?為包含關(guān)系。通過式(2)計算語句24和語句29的耦合度為13/22。結(jié)合代碼的耦合度和啟發(fā)式算法進行計算,使得原13個測試需求變?yōu)?個,精簡的測試需求集R′={b1,b7,b9,b11}。對原程序進行測試時,只需考慮這4項測試需求,即可實現(xiàn)分支覆蓋的測試目標(biāo)。 圖1 showViews(bookClassId)函數(shù)代碼流程 b1b2b3b4b5b6b7b8b9b10b11b12b13t1****t2********t3********t4**********t5*********t6*********t7********* 表3所示,對于原測試需求集R,當(dāng)測試用例集T={t1,t2,t3,t4,t5,t6,t7}時,G獲得用例集{t4,t5,t7},然而,基于精簡后的測試需求集R′,G′和GRE′獲得用例集{t4,t5}。且由于R′的規(guī)模較小,一定程度上減少了測試用例集的計算量。 圖書管理系統(tǒng)分為采購管理模塊、查詢功能模塊、系統(tǒng)管理模塊等。利用切片耦合度的測試需求約簡流程如圖2所示。 圖2 測試需求約簡流程 3.1 實驗環(huán)境 Android環(huán)境下,實驗平臺使用eclipse4.2,JDK1.6,Android SDK22.3,測試工具EclEmma,切片工具Soot。 3.2 用例集對比 分別用G,GRE算法對用戶功能模塊、圖書管理模塊、查詢功能模塊中的7個java文件進行對比。對約簡前測試需求集T和約簡后測試需求集T′用2種算法各進行8次實驗,實驗數(shù)據(jù)取8次實驗的平均值。圖3給出了約簡前后測試需求個數(shù)和測試用例個數(shù)對比關(guān)系。 圖3 G和GRE用例集對比 實驗結(jié)果表明:約簡前和約簡后測試用例集數(shù)量大大減少,減少了約30 %,同時G算法優(yōu)于GRE算法。在某些節(jié)點,變化趨于平緩,這是因為不同代碼模塊之間的耦合性不是很大,同時也說明本方法的可行性。 3.3 約簡前后檢錯數(shù)對比 在用例集約簡的同時,要保證約簡后的用例集能夠覆蓋對應(yīng)的測試,即約簡后的用例集個數(shù)能保證一定的覆蓋率。方法是通過對程序注入錯誤,考察約簡前、后測試用例集的測試效果,比較對注入錯誤的識別能力。如果用較少的測試用例發(fā)現(xiàn)錯誤數(shù)量與原測試用例發(fā)現(xiàn)錯誤數(shù)量差別不大,那么該方法在用例集約簡的同時也能保證覆蓋率。 實驗從圖書管理系統(tǒng)中抽取完整的4個模塊,注入錯誤。4個模塊的代碼規(guī)模適中,模塊編號用N表示,代碼規(guī)模用S表示,注入錯誤數(shù)用I表示,簡化前檢錯數(shù)用C表示,簡化后檢錯數(shù)用C′表示。實驗數(shù)據(jù)和結(jié)果如圖4所示。 圖4 檢錯數(shù)對比 通過仿真實驗可以看出:約簡前、后,在模塊代碼量小的情況下,約簡前、后檢錯數(shù)相同。在模塊代碼量比較大的情況下,檢錯數(shù)浮動不明顯。表明,利用結(jié)構(gòu)表的方法構(gòu)造程序切片,可在用例集約簡的同時,保證較高的檢錯率。 3.4 不同方法覆蓋度對比 為了評價本方法的有效性,開發(fā)了一種網(wǎng)上書城的Web項目,設(shè)計測試用例和測試需求,利用G算法和GRE算法對程序的測試覆蓋度進行對比,測試覆蓋度[9]為 (3) 式中 |T(rj)|為滿足測試需求rj的測試用例的個數(shù);n為用例ti滿足需求的個數(shù)。表4使用原G算法、原GRE算法與本文方法應(yīng)用于G算法和GRE算法進行比較的結(jié)果??梢钥闯觯菏褂帽痉椒ㄔ谛枨髷?shù)量減少的同時,能夠保證和約簡前相應(yīng)的覆蓋度。 3.5 結(jié)構(gòu)表復(fù)雜度對比 對于結(jié)構(gòu)表程序切片的時間復(fù)雜度,考慮最壞情況,假設(shè)結(jié)構(gòu)表中元素個數(shù)為n,切片準(zhǔn)則中包括程序中所有的變量,結(jié)合算法1和算法2,循環(huán)遍歷結(jié)構(gòu)表,最多執(zhí)行n次,其開銷為o(n(n+N+C+f)),計算切片的時間復(fù)雜度為o(n2)。而利用SDG計算切片的時間復(fù)雜度為o(n4)。對于空間復(fù)雜度,結(jié)構(gòu)表的存儲空間為6×n,即空間復(fù)雜度為o(n),而存儲SDG的數(shù)據(jù)依賴和控制依賴?yán)镁仃?,其大小為n×n,空間復(fù)雜度為o(n2)。 表4 G和GRE算法覆蓋度對應(yīng)表 本文針對傳統(tǒng)構(gòu)造程序切片的缺點,借鑒已有構(gòu)造程序切片的方法,提出了基于結(jié)構(gòu)表的方法構(gòu)造程序切片,并將該方法運用到Android環(huán)境下,很大程度上簡化了生成切片的時間和空間復(fù)雜度。根據(jù)程序之間耦合性和啟發(fā)式算法,將之運用到約簡測試需求上,提高了測試用例集約減度,同時在一定程度上保證了覆蓋率。 雖然改進的方法取得明顯的效果,但還需對構(gòu)造過程作進一步的改進。本文針對代碼約簡后,通過模塊之間的耦合性,利用啟發(fā)式算法約簡測試需求,可以考慮使用另一種算法約簡測試用例,比如利用符號執(zhí)行方法約簡測試用例。如何進行約簡是下一步的研究方向。 [1] 羅 彪,李 彬,張岱峰,等.基于Android系統(tǒng)的無線多點測溫系統(tǒng)設(shè)計[J].傳感器與微系統(tǒng),2016,35(3):56-59. [2] Harrold M Jean,Gupta Rajiv,Soffa Mary Lou.A methodology for controlling the size of a test suite[J].ACM Transaction on Software Engineering and Methodology,1993,2(3):270-285. [3] 徐寶文,聶長海,章曉芳.一種基于測試需求約簡的測試用例集優(yōu)化方法[J].軟件學(xué)報,2007,18(4):821-831. [4] 蘇小紅,龔丹丹,王甜甜,等.一種新的過程間靜態(tài)切片快速算法[J].哈爾濱工業(yè)大學(xué)學(xué)報,2015,47(5):25-31. [5] 龔丹丹,王甜甜,蘇小紅,等.冗余代碼缺陷檢測方法[J].哈爾濱工業(yè)大學(xué)學(xué)報,2012,44(7):58-63. [6] 孫永榮,劉建業(yè),劉瑞華,等.微小型導(dǎo)航系統(tǒng)中高精度導(dǎo)航計算機設(shè)計[J].傳感器與微系統(tǒng),2006,25(10):54-56. [7] 程安宇,趙 恬,申 帥.基于CAN總線ECU診斷功能的一致性測試設(shè)計[J].傳感器與微系統(tǒng),2013,32(7):93-96. [8] Marre Martina,Bertolino Antonia.Using spanning sets for cove-rage testing[J].IEEE Transaction on Software Engineering,2003,29(11):974-984. [9] 華 麗,李曉月,王成勇,等.能提高錯誤檢測能力的回歸測試用例集約簡[J].湖南科技大學(xué)學(xué)報:自然科學(xué)版,2015,30(2):99-103. 劉 鋒(1962-),教授,碩士生導(dǎo)師,主要從事并行計算與云計算研究工作,E—mail:fengliu@ahu.edu.cn。 朱二周(1981-),男,通訊作者,副教授,碩士生導(dǎo)師,主要從事虛擬化與程序分析工作,E—mail:ezzhu@ahu.edu.cn。 DOI:10.13873/J.1000—9787(2017)09—0025—04 Research on test requirement reduction technique based on improved program slicing method* ZHANG Jun1, LIU Feng1, MA Zhu-juan2, ZHU Er-zhou1 (1.School of Computer Science and Technology,Anhui University,Hefei 230601,China; 2.School of Economics and Technology,Anhui Agricultural University,Hefei 230036,China) Traditional test suite reduction method generates test case set directly from the testing requirement set.Although the test case can be reduced,the method ignores the problem of redundancy testing requirements,results in inaccuracy.Aiming at this problem,a program slicing technique based on the method of six-element structure table is proposed.Program slicing is used to streamline test code,for saving the complex steps depending on graphic constructure.Use heuristic algorithm to reduce testing requirements based on the correlation between code and coupling degree between modules.After reducing test requirements,streamline test suite.The method is applied to the Android platform,to compare G and GRE algorithm case set before and after reduction.Experimental result shows that the testing requirement set after reduction ensures a higher coverage rate when it obtains less test suite. program slicing; testing requirement reduction; coupling degree; six-element structure table 10.13873/J.1000—9787(2017)09—0017—05 2016—09—06 國家自然科學(xué)基金資助項目(61300169);安徽省教育廳自然科學(xué)重點資助項目(KJ2016A257) TP 311 A 1000—9787(2017)09—0017—05 張 軍(1989-),男,碩士研究生,主要研究領(lǐng)域為程序分析,E—mail:1213250514@qq.com。2 程序切片和測試需求的結(jié)合
3 仿真實驗
4 結(jié)束語