快速生成两两组合测试用例集算法  

A new speedy generation algorithm for pairwise testing

作　　者：周吴杰[1,2] 张德平[3] 徐宝文[2,4] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]南京大学软件新技术国家重点实验室,南京210093 [3]南京航空航天大学信息科学与技术学院,南京210016 [4]南京大学计算机科学与技术系,南京210093

出　　处：《东南大学学报（自然科学版）》2011年第5期943-948,共6页Journal of Southeast University：Natural Science Edition

摘　　要：研究了二元待测系统的最优二维覆盖表的构造,在此基础上提出了快速生成一般待测软件系统的二维覆盖表的算法.该算法首先针对二元待测系统生成相应的基本块B(0,1)和约简块R(0,1),然后对任意的取值组合对(a,b),通过替换生成相应的基本块B(a,b)或约简块R(a,b),最后累加所有的块得到二维覆盖表.因此当待测系统是二元时该算法能生成最优的覆盖表,并且在各因素的可取值数目较小时算法的效果较好.设待测系统的因素数目为k,该算法的时间复杂性为O(klog k),因此对于大规模的待测系统,算法生成测试用例集的速度很快.算法的分层性有利于以后的错误定位工作.另外,给出了两两覆盖表的数学构造性上界,其上界是关于因素数对数阶增长的.最后通过实验验证了该算法的有效性.The structure of the optimal binary pairwise covering arrays is studied,and the algorithm to rapidly generate the pairwise test data of a general software is proposed.The algorithm first generates the basic block B（0,1） and the reduced block R（0,1）,then generates the corresponding block B（a,b） or R（a,b） by substitution to cover each value pair（a,b）,and finally obtains the pairwise covering array by vertically concatenating these blocks.So the obtained covering array is optimal when the software under test is binary,and the covering array is near optimal when each factor has small size set of discrete valid value.The time complexity of the algorithm is O（klog k）,where k is the number of factors of a system,so the test suite can be rapidly generated using the algorithm in large-scale software systems.The hierarchical property is beneficial to the successive fault diagnostic stage.A constructive upper bound can be obtained that grows as O（log k）.The experimental results show that the algorithm is effective.

关 键 词：组合测试 两两组合测试 覆盖表 测试用例生成 

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