[1]周吴杰,张德平,徐宝文.快速生成两两组合测试用例集算法[J].东南大学学报(自然科学版),2011,41(5):943-948.[doi:10.3969/j.issn.1001-0505.2011.05.010]
 Zhou Wujie,Zhang Deping,Xu Baowen.A new speedy generation algorithm for pairwise testing[J].Journal of Southeast University (Natural Science Edition),2011,41(5):943-948.[doi:10.3969/j.issn.1001-0505.2011.05.010]
点击复制

快速生成两两组合测试用例集算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
41
期数:
2011年第5期
页码:
943-948
栏目:
计算机科学与工程
出版日期:
2011-09-20

文章信息/Info

Title:
A new speedy generation algorithm for pairwise testing
作者:
周吴杰12张德平3徐宝文24
(1东南大学计算机科学与工程学院,南京 210096)
(2南京大学软件新技术国家重点实验室,南京 210093)
(3南京航空航天大学信息科学与技术学院,南京 210016)
(4南京大学计算机科学与技术系,南京 210093)
Author(s):
Zhou Wujie12Zhang Deping3Xu Baowen24
(1School of Computer Science and Engineering, Southeast University, Nanjing 210096, China)
(2State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China)
(3College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)
(4Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China)
关键词:
组合测试两两组合测试覆盖表测试用例生成
Keywords:
combinatorial testing pairwise testing covering array generation of test suite
分类号:
TP311
DOI:
10.3969/j.issn.1001-0505.2011.05.010
摘要:
研究了二元待测系统的最优二维覆盖表的构造,在此基础上提出了快速生成一般待测软件系统的二维覆盖表的算法.该算法首先针对二元待测系统生成相应的基本块B(0,1)和约简块R(0,1),然后对任意的取值组合对(a,b),通过替换生成相应的基本块B(a,b)或约简块R(a,b),最后累加所有的块得到二维覆盖表.因此当待测系统是二元时该算法能生成最优的覆盖表,并且在各因素的可取值数目较小时算法的效果较好.设待测系统的因素数目为k,该算法的时间复杂性为O(klog k),因此对于大规模的待测系统,算法生成测试用例集的速度很快.算法的分层性有利于以后的错误定位工作.另外,给出了两两覆盖表的数学构造性上界,其上界是关于因素数对数阶增长的.最后通过实验验证了该算法的有效性.
Abstract:
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.

参考文献/References:

[1] Lei Y,Tai K C.In_Parameter_Oder:a test generation strategy for pairwise testing,TR-2001-03 [R].Raleigh,NC,USA:Department of Computer Science,North Carolina State University,2001.
[2] Cohen D M,Dalal S R,Fredman M L,et al.The AETG system:an approach to testing based on combinatorial design[J].IEEE Transactions on Software Engineering,1997,23(7):437-444.
[3] Kobayashi N,Tsuchiya T,Kikuno T.A new method for constructing pair-wise covering designs for software testing[J].Information Processing Letters,2002,81(2):85-91.
[4] Williams A W.Software component interaction testing:coverage measurement and generation of configurations [D].Ottawa,Ontario,Canada:Ottawa-Carleton Institute for Computer Science,School of Information Technology and Engineering,University of Ottawa,2002.
[5] 史亮,聂长海,徐宝文.基于解空间树的组合测试数据生成[J].计算机学报,2006,29(6):849-857.
  Shi Liang,Nie Changhai,Xu Baowen.Pairwise test data generation based on solution space tree[J].Chinese Journal of Computers,2006,29(6):849-857.(in Chinese)
[6] 査日军,张德平,聂长海,等.组合测试数据生成的交叉熵与粒子群算法及比较[J].计算机学报,2010,33(10):1896-1908.
  Zha Rijun,Zhang Deping,Nie Changhai,et al.Test data generation algorithms of combinatorial testing and comparison based on cross-entropy and particle swarm optimization method [J].Chinese Journal of Computers,2010,33(10):1896-1908.(in Chinese)
[7] Yan J,Zhang J.A backtracking search tool for constructing combinatorial test suites[J].The Journal of Systems and Software,2008,81(10):1681-1693.
[8] Lei Y,Kacker R,Kuhn D R,et al.IPOG-D:efficient test generation for multi-way combinatorial testing [J].Software Testing,Verification and Reliability,2008,18(3):125-148.
[9] Cheng Xiang,Gu Qing,Li Ang,et al.Variable strength interaction testing with an ant colony system approach[C]//16th Asia-Pacific Software Engineering Conference.Batu Ferringhi,Penang,Malaysia,2009:160-167.
[10] Hartman A.Software and hardware testing using combinatorial covering suites[C]//Interdisciplinary Applications of Graph Theory,Combinatorics,and Algorithms.Norwell,MA,USA,2005:237-266.

相似文献/References:

[1]王勇,黄志球,韦良芬,等.基于组合故障频繁树的最小失效诱因模式定位方法[J].东南大学学报(自然科学版),2018,48(2):253.[doi:10.3969/j.issn.1001-0505.2018.02.010]
 Wang Yong,Huang Zhiqiu,Wei Liangfen,et al.Locating minimal failure-causing schema based on combinatorial fault frequent tree[J].Journal of Southeast University (Natural Science Edition),2018,48(5):253.[doi:10.3969/j.issn.1001-0505.2018.02.010]

备注/Memo

备注/Memo:
作者简介:周吴杰(1973—),男,博士生,讲师;徐宝文(联系人),男,博士,教授,博士生导师,bwxu@nju.edu.cn.
引文格式: 周吴杰,张德平,徐宝文.快速生成两两组合测试用例集算法[J].东南大学学报:自然科学版,2011,41(5):943-948.[doi:10.3969/j.issn.1001-0505.2011.05.010]
更新日期/Last Update: 2011-09-20