›› 2015,Vol. 30 ›› Issue (5): 957-968.doi: 10.1007/s11390-015-1574-6

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

IPO类算法优化及最小化错误检测预期时间的通用策略

Shi-Wei Gao1(高世伟), Jiang-Hua Lv1*(吕江花), Bing-Lei Du1(杜冰磊), Charles J. Colbourn2, Shi-Long Ma1(马世龙)   

  1. 1 State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China;
    2 School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe AZ 85287-8809, U.S.A.
  • 收稿日期:2015-03-16 修回日期:2015-06-29 出版日期:2015-09-05 发布日期:2015-09-05
  • 通讯作者: Jiang-Hua Lv E-mail:jhlv@nlsde.buaa.edu.cn
  • 作者简介:Shi-Wei Gao received his B.S. degree in computer science and technology from Dezhou University, Dezhou, in 2007, and M.S. degree in information science and engineering from Yanshan University, Qinhuangdao, in 2010. He is currently a Ph.D. candidate in the School of Computer Science and Engineering of Beihang University, Beijing. He is a member of the State Key Laboratory of Software Development Environment of Beihang University. His research interests include software testing, software reliability theory, and formal methods.
  • 基金资助:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61300007 and 61305054, the Fundamental Research Funds for the Central Universities of China under Grant Nos. YWF-15-GJSYS-106 and YWF-14-JSJXY-007, and the Project of the State Key Laboratory of Software Development Environment of China under Grant Nos. SKLSDE-2015ZX-09 and SKLSDE-2014ZX-06.

Balancing Frequencies and Fault Detection in the In-Parameter-Order Algorithm

Shi-Wei Gao1(高世伟), Jiang-Hua Lv1*(吕江花), Bing-Lei Du1(杜冰磊), Charles J. Colbourn2, Shi-Long Ma1(马世龙)   

  1. 1 State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China;
    2 School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe AZ 85287-8809, U.S.A.
  • Received:2015-03-16 Revised:2015-06-29 Online:2015-09-05 Published:2015-09-05
  • Contact: Jiang-Hua Lv E-mail:jhlv@nlsde.buaa.edu.cn
  • About author:Shi-Wei Gao received his B.S. degree in computer science and technology from Dezhou University, Dezhou, in 2007, and M.S. degree in information science and engineering from Yanshan University, Qinhuangdao, in 2010. He is currently a Ph.D. candidate in the School of Computer Science and Engineering of Beihang University, Beijing. He is a member of the State Key Laboratory of Software Development Environment of Beihang University. His research interests include software testing, software reliability theory, and formal methods.
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61300007 and 61305054, the Fundamental Research Funds for the Central Universities of China under Grant Nos. YWF-15-GJSYS-106 and YWF-14-JSJXY-007, and the Project of the State Key Laboratory of Software Development Environment of China under Grant Nos. SKLSDE-2015ZX-09 and SKLSDE-2014ZX-06.

PDF (PC)

1302

IPO(In-Parameter-Order)算法是组合测试中构建软件测试用例集的一类广泛使用的策略。组合测试的目标是检测由参数之间的交互触发的错误。与已知的最小测试用例集相比, IPO类算法产生的测试用例集的规模不会大很多。在IPO类算法中, 对给定的t, 当整个测试用例集被执行后, 由t-way交互引起的所有错误一定会被发现。其基本策略包括水平和垂直扩展, 目的是解决测试用例集的规模问题。但在实际测试中, 测试用例在执行时还是期望尽可能早的发现错误, 以便错误被及早修复, 降低错误检测时间。本文通过对测试用例集中各个参数的取值分布均匀对IPO类算法进行改进, 并通过测试用例集重新排序策略提高IPO类算法错误检测率(平均提高了约31%)。并且, 本文提出的改进策略能减少测试用例集生成时间(平均减少了约两倍), 在某些情况下也能减小测试用例集规模。

Abstract: The In-Parameter-Order (IPO) algorithm is a widely used strategy for the construction of software test suites for Combinatorial Testing (CT) whose goal is to reveal faults triggered by interactions among parameters. Variants of IPO have been shown to produce test suites within reasonable amounts of time that are often not much larger than the smallest test suites known. When an entire test suite is executed, all faults that arise from t-way interactions for some fixed t are surely found. However, when tests are executed one at a time, it is desirable to detect a fault as early as possible so that it can be repaired. The basic IPO strategies of horizontal and vertical growth address test suite size, but not the early detection of faults. In this paper, the growth strategies in IPO are modified to attempt to evenly distribute the values of each parameter across the tests. Together with a reordering strategy that we add, this modification to IPO improves the rate of fault detection dramatically (improved by 31% on average). Moreover, our modifications always reduce generation time (2 times faster on average) and in some cases also reduce test suite size.

[1] Birnbaum Z W. On the importance of different components in a multicomponent system. In Multivariate Analysis, Krishnaiah P R (ed.), New York:Academic Press, 1969, pp.591-592.

[2] KuoW, Zhu X. Relations and generalizations of importance measures in reliability. IEEE Trans. Rel., 2012, 61(3):659- 674.

[3] Kuo W, Zhu X. Some recent advances on importance measures in reliability. IEEE Trans. Rel., 2012, 61(2):344-360.

[4] Anand S, Burke E K, Chen T Y et al. An orchestrated survey of methodologies for automated software test case generation. J. Sys. Software, 2013, 86(8):1978-2001.

[5] Chen T Y, Kuo F C, Liu H et al. Code coverage of adaptive random testing. IEEE Trans. Rel., 2013, 62(1):226-237.

[6] Grindal M, Offutt J, Andler S F. Combination testing strategies:A survey. Softw. Test. Verif. Rel., 2005, 15(3):167-199.

[7] Hao D, Zhang L M, Zhang L et al. A unified test-case prioritization approach. ACM Trans. Soft. Eng. Method, 2014, 24(2):10:1-10:31.

[8] Harman M, McMinn P. A theoretical and empirical study of search-based testing:Local, global, and hybrid search. IEEE Trans. Software Eng., 2010, 36(2):226-247.

[9] Nie C H, Leung H. A survey of combinatorial testing. ACM Comput. Surv., 2011, 43(2):11:1-11:29.

[10] Nebut C, Fleurey F, Le Traon Y et al. Automatic test generation:A use case driven approach. IEEE. Trans. Software Eng., 2006, 32(3):140-155.

[11] Perrouin G, Oster S, Sen S et al. Pairwise testing for software product lines:Comparison of two approaches. Software. Qual. J., 2012, 20(3/4):605-643.

[12] Xie T, Zhang L, Xiao X et al. Cooperative software testing and analysis:Advances and challenges. Journal of Computer Science and Technology, 2014, 29(4):713-723.

[13] Yoo S, Harman M. Regression testing minimization, selection and prioritization:A survey. Softw. Test. Verif. Rel., 2012, 22(2):67-120.

[14] Zhang D M, Xie T. Software analytics:Achievements and challenges. In Proc. the 35th Int. Conf. Software Eng., May 2013, p.1487.

[15] Yu K, Lin M, Chen J et al. Towards automated debugging in software evolution:Evaluating delta debugging on real regression bugs from the developers' perspectives. J. Sys. Software, 2012, 85(10):2305-2317.

[16] Bryce R C, Colbourn C J. One-test-at-a-time heuristic search for interaction test suites. In Proc. the 9th Annu. Conf. Genetic and Evolutionary Computation, Jul. 2007, pp.1082-1089.

[17] Kuhn D R, Reilly M J. An investigation of the applicability of design of experiments to software testing. In Proc. the 27th Annu. NASA Goddard Workshop on Software Eng., Dec. 2002, pp.91-95.

[18] Kuhn D R, Wallace D R, Gallo Jr J A. Software fault interactions and implications for software testing. IEEE Trans. Software Eng., 2004, 30(6):418-421.

[19] Cohen M B, Dwyer M B, Shi J. Constructing interaction test suites for highly-configurable systems in the presence of constraints:A greedy approach. IEEE Trans. Software Eng., 2008, 34(5):633-650.

[20] Lei Y, Kacker R, Kuhn D R et al. IPOG/IPOG-D:Efficient test generation for multi-way combinatorial testing. Softw. Test. Verif. Rel., 2008, 18(3):125-148.

[21] Tung Y W, Aldiwan W S. Automating test case generation for the new generation mission software system. In Proc. IEEE Aerospace Con., March 2000, pp.431-437.

[22] Wallace D R, Kuhn D R. Failure modes in medical device software:An analysis of 15 years of recall data. Int. J. Rel., Quality and Safety Eng., 2001, 8(4):351-371.

[23] Cohen D M, Dalal S R, Kajla A et al. The automatic efficient tests generator (AETG) system. In Proc. the 5th Int. Sympo. Software Rel. Eng., Nov. 1994, pp.303-309.

[24] Bryce R C, Colbourn C J. The density algorithm for pairwise interaction testing. Softw. Test. Verif. Rel., 2007, 17(3):159-182.

[25] Bryce R C, Colbourn C J. A density-based greedy algorithm for higher strength covering arrays. Softw. Test. Verif. Rel., 2009, 19(1):37-53.

[26] Lei Y, Tai K C. In-parameter-order:A test generation strategy for pairwise testing. In Proc. the 3rd Int. Symp. High- Assurance Sys. Eng., Nov. 1998, pp.254-261.

[27] Lei Y, Kacker R, Kuhn D R et al. IPOG:A general strategy for t-way software testing. In Proc. the 14th Annu. Int. Conf. Worshop. Eng. Computer-Based Sys., March 2007, pp.549-556.

[28] Forbes M, Lawrence J, Lei Y, Kacker R N, Kuhn D R. Refining the in-parameter-order strategy for constructing covering arrays. Journal of Research of the National Institute of Standards and Technology, 2008, 113(5):287-297.

[29] Cohen M B, Gibbons P B, Mugridge W B et al. Constructing test cases for interaction testing. In Proc. the 25th Int. Conf. Software Eng., May 2003, pp.38-48.

[30] Bryce R C, Colbourn C J. Expected time to detection of interaction faults. J. Combin. Mathematics and Combin. Comput., 2013, 86:87-110.

[31] Rothermel G, Untch R H, Chu C et al. Prioritizing test cases for regression testing. IEEE Trans. Software Eng., 2001, 27(10):929-948.

[32] Qu X, Cohen M B. A study in prioritization for higher strength combinatorial testing. In Proc. the 6th Int. Con. Software Testing, Verification and Validation, the 2nd Int. Workshops on Combinatorial Testing, March 2013, pp.285- 294.

[33] Qu X. Configuration aware prioritization techniques in regression testing. In Proc. the 31st Int. Conf. Software Engineering, Companion Volume, May 2009, pp.375-378.

[34] Qu X, Cohen M B, Rothermel G. Configuration-aware regression testing:An empirical study of sampling and prioritization. In Proc. Int. Symp. Software Tesing and Analysis, July 2008, pp.75-86.

[35] Bryce R C, Colbourn C J. Test prioritization for pairwise interaction coverage. In Proc. the 1st Int. Workshop on Advances in Model-Based Testing, May 2005.

[36] Bryce R C, Colbourn C J. Prioritized interaction testing for pair-wise coverage with seeding and constraints. Inform. Software Tech., 2006, 48(10):960-970.

[37] Huang R, Chen J, Li Z, Wang R, Lu Y. Adaptive random prioritization for interaction test suites. In Proc. the 29th Symp. Appl. Comput., March 2014, pp.1058-1063.

[38] Petke J, Yoo S, Cohen M B, Harman M. Efficiency and early fault detection with lower and higher strength combinatorial interaction testing. In Proc. the 12th Joint Meeting on European Software Engineering Conf. and the ACM SIGSOFT Symp. the Foundations of Software Eng. (ESEC/FSE 2013), August 2013, pp.26-36.

[39] Qu X, Cohen M B, Woolf K M. Combinatorial interaction regression testing:A study of test case generation and prioritization. In Proc. the 23rd Int. Conf. Software Maintenance, Oct. 2007, pp.255-264.

[40] Huang R, Chen J, Zhang T, Wang R, Lu Y. Prioritizing variable-strength covering array. In Proc. the 37th IEEE Annu. Computer Software and Applications Conf., July 2013, pp.502-511.

[41] Huang R, Xie X, Towey D, Chen T Y, Lu Y, Chen J. Prioritization of combinatorial test cases by incremental interaction coverage. Int. J. Softw. Eng. Know., 2014, 23(10):1427-1457.

[42] Bryce R C, Memon A M. Test suite prioritization by interaction coverage. In Proc. Workshop on Domain Specific Approaches to Software Test Automation, September 2007, pp.1-7.

[43] Lei Y, Kuhn D R. Advanced combinatorial testing suite (ACTS). http://csrc.nist.gov/groups/SNS/acts/index.html, Aug. 2015.

[44] Hutchins M, Foster H, Goradia T et al. Experiments of the effectiveness of dataflow and control-flow-based test adequacy criteria. In Proc. the 16th Int. Conf. Software Eng., May 1994, pp.191-200.

[45] Kuhn D R, Okun V. Pseudo-exhaustive testing for software. In Proc. the 30th Annu. IEEE/NASA Software Engineering Workshop, April 2006, pp.153-158.

[46] Soh Z H C, Abdullah S A C, Zamil K Z. A distributed tway test suite generation using "One-Parameter-at-a-Time" approach. Int. J. Advance Soft Compu. Appl., 2013, 5(3):91-103.

[47] Li X, Dong Z, Wu H et al. Refining a randomized postoptimization method for covering arrays. In Proc. the 7th IEEE Int. Conf. Software Testing, Verification and Validation Workshops (ICSTW), March 31-April 4, 2014, pp.143-152.

[48] Nayeri P, Colbourn C J, Konjevod G. Randomized postoptimization of covering arrays. Eur. J. Combin., 2013, 34(1):91-103.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 卢学妙;. On the Complexity of Induction of Structural Descriptions[J]. , 1987, 2(1): 12 -21 .
[2] 姚荣; 康泰; 陈廷槐;. Algorithms for the Determination of Cutsets in a Hypergraph[J]. , 1990, 5(1): 41 -46 .
[3] 孙昱东; 谢志良;. Macro-Dataflow Computational Model and Its Simulation[J]. , 1990, 5(3): 289 -295 .
[4] 蔡士杰; 张福炎;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[5] 张钹; 张铃;. A Relation Matrix Approach to Labelling Temporal Relations in Scheduling[J]. , 1991, 6(4): 339 -346 .
[6] 李卫东; 魏道政;. Test Derivation Through Critical Path Transitions[J]. , 1992, 7(1): 12 -18 .
[7] 沈一栋;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[8] 招兆铿; 戴军; 陈文丹;. Automated Theorem Proving in Temporal Logic:T-Resolution[J]. , 1994, 9(1): 53 -62 .
[9] 王晖; 刘大有; 王亚飞;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[10] 余盛可;. Reasoning in H-Net: A Unified Approach to Intelligent Hypermedia Systems[J]. , 1996, 11(1): 83 -89 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：