改進型程序切片方法的測試需求約簡技術研究*

張 軍， 劉 鋒， 馬竹娟， 朱二周

(1.安徽大學 計算機科學與技術學院,安徽 合肥 230601; 2.安徽農業大學 經濟技術學院,安徽 合肥 230036)

改進型程序切片方法的測試需求約簡技術研究*

張 軍1， 劉 鋒1， 馬竹娟2， 朱二周1

(1.安徽大學 計算機科學與技術學院,安徽 合肥 230601; 2.安徽農業大學 經濟技術學院,安徽 合肥 230036)

傳統的測試用例集約簡技術大多采用由測試需求集直接生成測試用例集的方法。該方法雖然能夠約簡測試用例集，但出現測試需求冗余，約簡后的測試用例集不夠精準等問題。針對這些問題，提出了一種基于六元結構表的程序切片方法。利用程序切片精簡測試代碼，省去構造程序依賴圖的復雜步驟；根據代碼間的相互關系和模塊間的耦合度，利用啟發式算法約簡測試需求；在約簡后的測試需求上，精簡測試用例集。將該方法應用到當前主流的Android平臺上比較約簡前后G，GRE的用例集。實驗結果表明:約簡后的測試需求集能夠在獲得較少的測試用例集的前提下保證較高的覆蓋率。

程序切片; 測試需求約簡; 耦合度; 六元結構表

0 引 言

隨著移動互聯網的快速發展，越來越多用戶使用移動設備，Android版App軟件已經被越來越多的人使用[1]。但隨著App版本不斷地迭代，出現舊的測試用例和新的測試用例重合，導致敏捷開發效率低下。在軟件開發過程中軟件測試是必不可少的環節，它在整個軟件的生命周期中具有舉足輕重的地位。在軟件測試之前，測試人員根據測試需求，生成測試用例，然后發現軟件開發過程中存在的問題并加以糾正，保證軟件質量。隨著軟件版本的迭代，測試用例集的規模也隨之增長，不可避免出現用例冗余。如何有效降低冗余，提高測試效率，成為研究軟件測試的必備內容，此即測試用例集約簡的目的。

現有測試用例集約簡方法是針對原測試需求集，生成相應的測試用例集，然后尋找測試用例集的某個子集，用盡可能少的測試用例滿足測試需求。測試用例集約簡方法主要包括貪心算法、一些啟發式算法、整數規范等方法[2]。這些方法是在滿足已知的測試需求和測試用例關系條件下直接約簡測試用例集。但忽視了測試需求間的相互關系，導致約簡后的測試用例集出現測試效果不明顯的現象。

針對傳統的測試用例集約簡方法的不足，結合文獻[3]和程序切片技術，提出了一種利用結構表構造的程序切片約簡測試需求集的新方法。程序切片是一種分析和理解程序的技術，主要應用于程序分析、軟件測試及領域[3],通過對源代碼進行分析和研究，刪除與興趣點無關的語句和謂詞，達到縮減程序代碼，保證所得的程序與源程序在語義上一致性。

1 六元結構表程序切片

程序切片技術的發展經歷了從靜態到動態、從過程內到過程間等幾個方面的過程，每種切片都有各自的優勢與劣勢。從軟件需求角度考慮，若需求包含完整的輸出描述，則需求可以看作初始化過程到最終功能語句之間的靜態切片；若從測試用例集方面考慮，每個用例都對應著不同狀態下的動態切片。

傳統的靜態程序切片算法是基于系統依賴圖(SDG)的遍歷算法。SDG以程序依賴圖為基礎，反映程序的數據和控制依賴等信息。但生成SDG需要計算與切片無關的數據依賴，造成時間和空間上的浪費。本文結合文獻[4]提出的五元結構[4]，提出了基于六元結構表程序切片構造方法，既能夠降低時間和空間復雜度，又能夠保證約簡后代碼功能的完整性。

1.1 結構表模型構造

構造結構表模型需要以下3個步驟：

1)通過詞法和語法分析生成TOKEN序列，在TOKEN序列基礎上進行代碼標準化[5]，生成標準TOKEN序列。

2)在步驟(1)基礎上，生成對應的六元結構表和復合語句信息表。

3)利用六元結構表和復合語句信息表，得到程序切片。

1.2 六元結構表構造

定義1 六元結構表(imnNCf)〈i,m,n,N,C,f〉為程序中變量的聲明、賦值和函數調用、使用參數的關系。其中，i為語句的行號；m為聲明變量或函數所在的行號；n為i行定義的變量；N為i行使用變量或函數形參的集合；C為i行復合關系的集合；f為i行調用函數名。imnNCf中值不存在用?表示。

1.3 復合語句信息表構造

定義2 復合語句信息表為表示復合語句結構信息。其中，id為語句的標示；name為語句名；beginline為語句開始行；endline為語句結束行；f為是否存在調用函數；?表示不存在。

圖1為Android代碼例子。由于篇幅所限僅列表1、表2，為showViews函數的六元結構表以及復合信息結構表，其中，監聽和點擊事件歸屬于showViews。

表1 showViews函數的六元結構表

表2 showViews復合信息結構表

程序代碼塊的功能:1)展示圖書類別；2)編輯圖書類別；3)刪除圖書類別。限于篇幅,代碼簡化,模塊流程不變。

1 public class BCLActivity extends Activity {

2 BCSAdapter adapter;

3 ListView lv;

4 List>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(“確認”,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的構造過程是對程序進行逆向流分析，在保證程序數據和控制依賴完整性的同時，剔除與興趣結點無關的代碼。算法1和算法2為具體的構造過程。其中，算法1為構造六元結構表算法，算法2為構造復合信息結構表算法。

算法1 六元結構表算法:

1)判斷興趣點是函數語句還是賦值語句：若為函數語句跳轉步驟(2)，若為賦值語句跳轉步驟(3)。

2)逆向遍歷imnNCf，遍歷f值是否和興趣點值相同。若相同，跳轉步驟(4);若不相同，跳轉步驟(5)。

3)逆向遍歷imnNCf，遍歷n值是否和興趣點值相同。若相同，切片中加入該語句;若不相同，跳轉步驟(6)。

4)記錄i值，即程序的結束行，加入到切片，跳轉步驟(5)。

5)查看對應行的N值：若值為?，表示不進行參數傳遞，跳轉到對應函數f的imnNCf進行逆序遍歷；若值不為?，表示進行了參數傳遞，若實參為數值傳遞，被調函數中形參不影響實參，無需計算被調函數的子切片；若實參為地址傳遞，計算被調函數的子切片。跳轉步驟(8)。

6)查看對應行的N值：若為?，即賦值語句右側是函數，跳轉步驟(7)；若不為?，查看f值，若為?，是變量賦值，首先進行逆向流分析，逆向遞歸計算其使用變量的子切片，然后加入到切片中；若不為?，則跳轉步驟(5)。

7)逆向遍歷對應行f的imnNCf，查找C值，則跳轉步驟(8)。

8)對于C值：若不為?，查找復合信息結構表，記錄復合函數切片；若為?，則結束。

算法2 復合信息結構表算法：

1)根據imnNCf中C值，查找復合結構表中id值，若C=id，跳轉步驟(2)；若C≠id，逆序遍歷復合結構表，直到C=id。

2)若復合關系未被處理過，加入到切片中；若有未處理變量，查找beginline-endline對應的imnNCf，若變量和imnNCf中某一行n值相同，加入切片，跳轉步驟(3)。

3)逆向循環遍歷對應行的N值和C值，步驟同算法1。

在圖1中，若以(28,bookClassId)為切片，計算結果為{28,26,1,5,6,7,8, 9,13,14,17,19,20,21,22,23}。

切片結果的準確度直接影響到測試需求的準確性。切片的準確度Pslice為

(1)

式中Sstandard為標準切片集合；Scurrent為本文計算的切片集合；Pslice∈(0～1)，若值越接近于1，表示切片準確度越高。

對于切片準則(28, bookClassId)，標準的切片結果{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 程序切片和測試需求的結合

2.1 測試需求之間的關系和約簡方法

在軟件設計中應盡可能使用松耦合關系。耦合是指各模塊間相互依賴程度的度量[6]。測試需求[7]之間的關系主要有包含、獨立和重合關系。若為獨立關系，則不必考慮耦合度；若為重合關系，則需要考慮耦合度；若為包含關系，即全耦合。以下給出測試需求ri和rj約簡步驟：

1)若ri包含了rj，則覆蓋了ri的測試用例均可以覆蓋rj。在進行測試時只需保留ri，即若ri和rj是相互包含關系，取ri或者rj中的一個。

3)若ri和rj是獨立關系，則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是包含關系

R′=R-{ri};∥合并測試需求rj，保留測試需求ri

else if(rj∩ri)then

R′=R-{rj};∥去除測試需求rj，保留測試需求ri

else if(ri∩rj≠?)then∥若ri和rj是重合關系

R′=ri+rj-ri∩rj

else if(ri∩rj==?)then∥若ri和rj是獨立關系不約簡測試需求

end if end if end if end if

end while

2.3 程序切片約簡測試需求

定義3 方法內切片準則：

方法內切片準則是一個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，耦合度越高，說明關聯性越大，代碼之間的重合度越高，冗余度越大，越要進行約簡。

對于showViews(bookClassId)函數，有13個測試需求，圖1中每一個箭頭表示一個測試需求，即b1～b13。結合程序分析[8]，通過imnNCf和啟發式算法可知b6≡b8≡b9，b11≡b13，b2≡b4，b2?b1，b10?b7，b3?b2，b5?b2，b12?b9。其中，≡為等價關系，?為包含關系。通過式(2)計算語句24和語句29的耦合度為13/22。結合代碼的耦合度和啟發式算法進行計算，使得原13個測試需求變為4個，精簡的測試需求集R′={b1,b7,b9,b11}。對原程序進行測試時，只需考慮這4項測試需求，即可實現分支覆蓋的測試目標。

圖1 showViews(bookClassId)函數代碼流程

b1b2b3b4b5b6b7b8b9b10b11b12b13t1****t2********t3********t4**********t5*********t6*********t7*********

表3所示，對于原測試需求集R，當測試用例集T={t1,t2,t3,t4,t5,t6,t7}時，G獲得用例集{t4,t5,t7}，然而，基于精簡后的測試需求集R′，G′和GRE′獲得用例集{t4,t5}。且由于R′的規模較小，一定程度上減少了測試用例集的計算量。

3 仿真實驗

圖書管理系統分為采購管理模塊、查詢功能模塊、系統管理模塊等。利用切片耦合度的測試需求約簡流程如圖2所示。

圖2 測試需求約簡流程

3.1 實驗環境

Android環境下，實驗平臺使用eclipse4.2，JDK1.6，Android SDK22.3，測試工具EclEmma，切片工具Soot。

3.2 用例集對比

分別用G，GRE算法對用戶功能模塊、圖書管理模塊、查詢功能模塊中的7個java文件進行對比。對約簡前測試需求集T和約簡后測試需求集T′用2種算法各進行8次實驗，實驗數據取8次實驗的平均值。圖3給出了約簡前后測試需求個數和測試用例個數對比關系。

圖3 G和GRE用例集對比

實驗結果表明：約簡前和約簡后測試用例集數量大大減少，減少了約30 %，同時G算法優于GRE算法。在某些節點，變化趨于平緩，這是因為不同代碼模塊之間的耦合性不是很大，同時也說明本方法的可行性。

3.3 約簡前后檢錯數對比

在用例集約簡的同時，要保證約簡后的用例集能夠覆蓋對應的測試，即約簡后的用例集個數能保證一定的覆蓋率。方法是通過對程序注入錯誤，考察約簡前、后測試用例集的測試效果，比較對注入錯誤的識別能力。如果用較少的測試用例發現錯誤數量與原測試用例發現錯誤數量差別不大，那么該方法在用例集約簡的同時也能保證覆蓋率。

實驗從圖書管理系統中抽取完整的4個模塊，注入錯誤。4個模塊的代碼規模適中，模塊編號用N表示，代碼規模用S表示，注入錯誤數用I表示，簡化前檢錯數用C表示，簡化后檢錯數用C′表示。實驗數據和結果如圖4所示。

圖4 檢錯數對比

通過仿真實驗可以看出：約簡前、后，在模塊代碼量小的情況下，約簡前、后檢錯數相同。在模塊代碼量比較大的情況下，檢錯數浮動不明顯。表明，利用結構表的方法構造程序切片，可在用例集約簡的同時，保證較高的檢錯率。

3.4 不同方法覆蓋度對比

為了評價本方法的有效性，開發了一種網上書城的Web項目，設計測試用例和測試需求，利用G算法和GRE算法對程序的測試覆蓋度進行對比，測試覆蓋度[9]為

(3)

式中 |T(rj)|為滿足測試需求rj的測試用例的個數；n為用例ti滿足需求的個數。表4使用原G算法、原GRE算法與本文方法應用于G算法和GRE算法進行比較的結果。可以看出：使用本方法在需求數量減少的同時，能夠保證和約簡前相應的覆蓋度。

3.5 結構表復雜度對比

對于結構表程序切片的時間復雜度，考慮最壞情況，假設結構表中元素個數為n，切片準則中包括程序中所有的變量，結合算法1和算法2，循環遍歷結構表，最多執行n次，其開銷為o(n(n+N+C+f))，計算切片的時間復雜度為o(n2)。而利用SDG計算切片的時間復雜度為o(n4)。對于空間復雜度，結構表的存儲空間為6×n，即空間復雜度為o(n)，而存儲SDG的數據依賴和控制依賴利用矩陣，其大小為n×n，空間復雜度為o(n2)。

表4 G和GRE算法覆蓋度對應表

4 結束語

本文針對傳統構造程序切片的缺點，借鑒已有構造程序切片的方法，提出了基于結構表的方法構造程序切片，并將該方法運用到Android環境下，很大程度上簡化了生成切片的時間和空間復雜度。根據程序之間耦合性和啟發式算法，將之運用到約簡測試需求上，提高了測試用例集約減度，同時在一定程度上保證了覆蓋率。

雖然改進的方法取得明顯的效果，但還需對構造過程作進一步的改進。本文針對代碼約簡后，通過模塊之間的耦合性，利用啟發式算法約簡測試需求，可以考慮使用另一種算法約簡測試用例，比如利用符號執行方法約簡測試用例。如何進行約簡是下一步的研究方向。

[1] 羅 彪,李 彬,張岱峰，等.基于Android系統的無線多點測溫系統設計[J].傳感器與微系統,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] 徐寶文,聶長海,章曉芳.一種基于測試需求約簡的測試用例集優化方法[J].軟件學報,2007,18(4):821-831.

[4] 蘇小紅,龔丹丹,王甜甜，等.一種新的過程間靜態切片快速算法[J].哈爾濱工業大學學報,2015,47(5):25-31.

[5] 龔丹丹,王甜甜,蘇小紅，等.冗余代碼缺陷檢測方法[J].哈爾濱工業大學學報,2012,44(7):58-63.

[6] 孫永榮,劉建業,劉瑞華，等.微小型導航系統中高精度導航計算機設計[J].傳感器與微系統,2006,25(10):54-56.

[7] 程安宇,趙 恬,申 帥.基于CAN總線ECU診斷功能的一致性測試設計[J].傳感器與微系統,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].湖南科技大學學報：自然科學版,2015,30(2):99-103.

劉 鋒(1962-)，教授，碩士生導師，主要從事并行計算與云計算研究工作，E—mail:fengliu@ahu.edu.cn。

朱二周(1981-)，男，通訊作者，副教授，碩士生導師，主要從事虛擬化與程序分析工作，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

國家自然科學基金資助項目(61300169)；安徽省教育廳自然科學重點資助項目(KJ2016A257)

TP 311

A

1000—9787(2017)09—0017—05

張 軍(1989-)，男，碩士研究生，主要研究領域為程序分析，E—mail:1213250514@qq.com。