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

An Approach of Iterative Partition Testing Based on Priority Sampling

随机测试和划分测试是两种重要的测试方法,关于两者在失效检测能力和效率方面的比较一直是软件测试领域的研究热点之一.适应性随机测试是对随机测试的一种增强,通过实现测试用例在输入域上的均匀分布,提高了随机测试的失效检测能力.该文从划分测试出发,借鉴了均匀分布的思想,提出了一种基于优先级的迭代划分测试方法(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.