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

• Special Section on Software Systems • Previous Articles     Next Articles

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

1301

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] Lu Xuemiao;. On the Complexity of Induction of Structural Descriptions[J]. , 1987, 2(1): 12 -21 .
[2] Yao Rong; Kang Tai; Chen Tinghuai;. Algorithms for the Determination of Cutsets in a Hypergraph[J]. , 1990, 5(1): 41 -46 .
[3] Sun Yudong; Xie Zhiliang;. Macro-Dataflow Computational Model and Its Simulation[J]. , 1990, 5(3): 289 -295 .
[4] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[5] Zhang Bo; Zhang Ling;. A Relation Matrix Approach to Labelling Temporal Relations in Scheduling[J]. , 1991, 6(4): 339 -346 .
[6] Li Weidong; Wei Daozheng;. Test Derivation Through Critical Path Transitions[J]. , 1992, 7(1): 12 -18 .
[7] Shen Yidong;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[8] Zhao Zhaokeng; Dai Jun; Chen Wendan;. Automated Theorem Proving in Temporal Logic:T-Resolution[J]. , 1994, 9(1): 53 -62 .
[9] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[10] Yu Shengke;. Reasoning in H-Net: A Unified Approach to Intelligent Hypermedia Systems[J]. , 1996, 11(1): 83 -89 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved