改进型程序切片方法的测试需求约简技术研究*

张 军， 刘 锋， 马竹娟， 朱二周

(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。