一种基于优先级的迭代划分测试方法  

An Approach of Iterative Partition Testing Based on Priority Sampling

作　　者：章晓芳[1,2] 章宗长[1] 谢晓园[3] 周谊成[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006 [2]南京大学计算机软件新技术国家重点实验室,南京210023 [3]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《计算机学报》2016年第11期2307-2323,共17页Chinese Journal of Computers

基　　金：国家自然科学基金(61103045;61502329;61502323;61572375);软件新技术与产业化协同创新中心部分资助~~

摘　　要：随机测试和划分测试是两种重要的测试方法,关于两者在失效检测能力和效率方面的比较一直是软件测试领域的研究热点之一.适应性随机测试是对随机测试的一种增强,通过实现测试用例在输入域上的均匀分布,提高了随机测试的失效检测能力.该文从划分测试出发,借鉴了均匀分布的思想,提出了一种基于优先级的迭代划分测试方法(Iterative Partition Testing based on Priority Sampling,IPT-PS).首先迭代划分输入域并选取划分后子域的中心点作为待执行的测试用例,随后采取优先级策略,将待执行的测试用例分为3种不同优先等级并依次执行.迭代划分和中心采样仅需要已知输入域的空间信息,优先级执行则考虑了测试用例的不同空间特性,上述3种操作均仅需要很少的时间开销并力求实现测试用例在输入域上的均匀分布,以提高失效检测能力.该文通过理论分析给出了IPT-PS检测出对应失效所需测试用例数量的上界,并通过一系列实验结果表明:IPT-PS在仅使用接近随机测试时间开销的情况下,可以获得与适应性随机测试相近甚至更好的失效检测能力,是一种高效的测试方法.Random testing and partition-based testing are two important test case generation methods.Comparisons on the efficiency and effectiveness between these two methods have been a popular research area.As an enhanced version of random testing,Adaptive Random Testing(ART)aims to evenly spread test cases within the input domain,in order to achieve better failure detection effectiveness.This paper follows the intuition of ART that high diversity is helpful in detecting failures,and proposes a novel algorithm,named Iterative Partition Testing based on Priority Sampling(IPT-PS).IPT-PS iteratively divides the input domain into grids,and selects the center point of each grid as test case.Priority-based execution strategy is then applied on newly generated test cases in each round of iteration.Iterative partition and fixed-center-point sampling only require information of the input domain,while priority-based execution considers different spatial characteristics of test cases.All these three steps need trivial time cost,and help to sample test cases much more even than traditional fixed-size partition testing,such that betterfailure detection effectiveness can be achieved.We theoretically prove the upper bound of the effectiveness for our method,and conduct comprehensive empirical analysis.Our experimental results show that IPT-PS can achieve effectiveness as high as ART,but with time cost as low as random testing.

关 键 词：软件测试 划分测试 随机测试 适应性随机测试 测试用例生成 失效率 F-度量 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]