组合测试技术及应用研究
|
摘要
软件测试是保障被测软件质量的重要手段。但软件测试研究面临诸多挑战,例如被测软件制品的分析建模技术、测试充分性准则的设定、有效的测试用例生成技术、回归测试技术和变异测试等。组合测试作为一种重要的测试用例生成技术已经得到国内外学者的广泛关注。当完成对被测软件制品建模分析后,测试人员可以获得由因素和因素取值构成的实例,组合测试通过关注少数因素间取值组合的覆盖可以构造出小规模组合测试用例集,但最优组合测试用例集的构造已被证明为是一个NP难问题。
本文系统回顾和总结了组合测试技术和应用的已有研究成果,针对组合测试中典型的成对组合测试和一些组合测试扩展问题进行了深入研究,提出了多种基于元启发式搜索技术的有效测试用例集构造算法。同时针对回归测试中的测试用例集约简问题,提出了一种基于测试需求间成对组合覆盖的约简算法。具体贡献可以概括为以下三个方面。
(1)针对传统成对组合测试问题,本文提出一种基于粒子群优化的成对组合测试用例集构造算法。在生成单个测试用例时,尝试利用粒子群优化生成组合覆盖能力强的测试用例,并对搜索空间、适应值函数和启发式的合理设定进行了深入探讨。同时以上述单个测试用例生成算法为基础,提出两种不同的测试用例集构造算法,一种基于one-test-at-a-time策略,另一种基于类IPO策略。随后采用
一个压缩算法对组合测试用例集做进一步的压缩。最后通过实证研究分析了算法框架内的不同设定对最终构造出的测试用例集规模的影响,并与已有的经典算法和工具进行比较来验证该算法的有效性。
(2)针对组合测试扩展问题,本文将蚁群优化技术在传统成对组合测试问题上的应用进行扩展,使之可以有效构造基于优先级的组合测试用例集和可变强度组合测试用例集。具体来说,针对基于优先级的组合测试问题,本文采用one-test-at-a-time策略构造测试用例集,在构造单个测试用例时,提出四种不同的蚁群优化策略(AS、ASelite、ACS和MMAS)并针对该问题对其中的启发式设定进行了深入探讨,最后通过实例研究将这四种策略与经典的贪心策略WDA (Weighted Density Algorithm)进行了比较,同时也对这四种不同策略的具体执行效果进行了比较并验证了所提方法的有效性。针对可变强度组合测试问题,本文同样采用one-test-at-a-time策略来构造测试用例集,在构造单个测试用例时,采用ACS策略并针对该问题对其中的启发式设定进行了深入的探讨,随后采用一个压缩算法对组合测试用例集做进一步的压缩。最后通过实例研究与已有的经典方法和工具进行比较来验证该方法的有效性。
(3)针对测试用例集约简问题,传统测试用例集约简算法仅考虑对单个测试需求的覆盖,这类方法一般会大幅度削弱约简后的测试用例集缺陷检测能力。本文通过考虑对测试需求间成对组合的覆盖,提出了一种轻量级的测试用例集约简方法PWIR。在实证研究中,采用Siemens套件中的实际C语言程序作为实验对象。最终结果显示该方法可以仅通过添加少量测试用例就可以有效提高约简后的测试用例集缺陷检测能力。
Software testing is a key method to guarantee the quality of software under test. But software testing faces many challenges, such as the modeling techniques of software artifacts, the design of test adequacy criterion, the effective test case gen-eration techniques, regression testing, and mutation testing. Combinatorial testing (also known as interaction testing) is an important test case generation technique and is widely researched by many researchers. After modeling the software under test, testers can get an instance composed of factors and values. Combinatorial test-ing can generate test suites with small size by covering interactions of a few factors. Some empirical studies also show that it can effectively reduce the test suite size but still keep high fault detection ability in some testing scenarios. However, the construction of the optimal combinatorial test suite is demonstrated to be NP-hard.
In this dissertation, we systematically review the related work of combinato-rial testing technique and its applications. For traditional pairwise testing and its variants, we propose several effective test suite construction algorithms based on meta-heuristic search techniques. For test suite reduction in regression testing, we propose a test suite reduction approach based on pairwise interaction of test require-ments. The contributions of this dissertation can be summarized as follows:
(1) For traditional pairwise testing issue, we propose a framework of particle swarm optimization based pairwise testing. To generate a single test case, we apply particle swarm optimization aiming to cover more interactions. Meanwhile we dis-cuss the reasonable settings of search space, fitness function, and heuristics. Based on the above algorithm, we propose two different test suite construction algorithms. One is based on one-test-at-a-time strategy, the other is based on IPO-like strategy. In our empirical study, we analyze the impact factors in our framework and make a comparison with other well-known approaches to show the effectiveness of our framework.
(2) For the variant issues of combinatorial testing, we extend the application of ant colony optimization in traditional combinatorial testing to support the con-struction of prioritized combinatorial test suites and variable strength combinatorial test suites. In particular, to build prioritized combinatorial test suites, we use one-test-at-a-time strategy. To generate a single test case, we propose four concrete ant colony optimization strategies (AS, ASelite, ACS, and MM AS) and discuss the set-tings of heuristics. In the part of case studies, we compare our approach to a classical greedy approach WDA (Weighted Density Algorithm) and also make a comparison among these four different approaches. To build variable strength combinatorial test suites, we also use one-test-at-a-time strategy. To generate a single test case, we apply ant colony system (ACS) strategy aiming to cover more interactions and discuss the settings of heuristics. After the test suite is constructed, we can use a test suite minimization algorithm to further reduce this test suite size. In the final case studies, we compare this approach to some classical approaches and tools to show the effectiveness of our approach.
(3) For the test suite reduction issue in regression testing, most of traditional test suite reduction approaches only consider the coverage of individual test require-ment, but these approaches may significantly lose fault detection ability of original test suites. We propose a lightweight test suite reduction approach PWIR. In this approach, we consider the coverage of pairwise interaction of test requirements. In our empirical study, we use the Siemens suite as our subjects and find that this approach can effectively increase the fault detection ability of reduced test suite by adding only a few test cases.
本文系统回顾和总结了组合测试技术和应用的已有研究成果,针对组合测试中典型的成对组合测试和一些组合测试扩展问题进行了深入研究,提出了多种基于元启发式搜索技术的有效测试用例集构造算法。同时针对回归测试中的测试用例集约简问题,提出了一种基于测试需求间成对组合覆盖的约简算法。具体贡献可以概括为以下三个方面。
(1)针对传统成对组合测试问题,本文提出一种基于粒子群优化的成对组合测试用例集构造算法。在生成单个测试用例时,尝试利用粒子群优化生成组合覆盖能力强的测试用例,并对搜索空间、适应值函数和启发式的合理设定进行了深入探讨。同时以上述单个测试用例生成算法为基础,提出两种不同的测试用例集构造算法,一种基于one-test-at-a-time策略,另一种基于类IPO策略。随后采用
一个压缩算法对组合测试用例集做进一步的压缩。最后通过实证研究分析了算法框架内的不同设定对最终构造出的测试用例集规模的影响,并与已有的经典算法和工具进行比较来验证该算法的有效性。
(2)针对组合测试扩展问题,本文将蚁群优化技术在传统成对组合测试问题上的应用进行扩展,使之可以有效构造基于优先级的组合测试用例集和可变强度组合测试用例集。具体来说,针对基于优先级的组合测试问题,本文采用one-test-at-a-time策略构造测试用例集,在构造单个测试用例时,提出四种不同的蚁群优化策略(AS、ASelite、ACS和MMAS)并针对该问题对其中的启发式设定进行了深入探讨,最后通过实例研究将这四种策略与经典的贪心策略WDA (Weighted Density Algorithm)进行了比较,同时也对这四种不同策略的具体执行效果进行了比较并验证了所提方法的有效性。针对可变强度组合测试问题,本文同样采用one-test-at-a-time策略来构造测试用例集,在构造单个测试用例时,采用ACS策略并针对该问题对其中的启发式设定进行了深入的探讨,随后采用一个压缩算法对组合测试用例集做进一步的压缩。最后通过实例研究与已有的经典方法和工具进行比较来验证该方法的有效性。
(3)针对测试用例集约简问题,传统测试用例集约简算法仅考虑对单个测试需求的覆盖,这类方法一般会大幅度削弱约简后的测试用例集缺陷检测能力。本文通过考虑对测试需求间成对组合的覆盖,提出了一种轻量级的测试用例集约简方法PWIR。在实证研究中,采用Siemens套件中的实际C语言程序作为实验对象。最终结果显示该方法可以仅通过添加少量测试用例就可以有效提高约简后的测试用例集缺陷检测能力。
Software testing is a key method to guarantee the quality of software under test. But software testing faces many challenges, such as the modeling techniques of software artifacts, the design of test adequacy criterion, the effective test case gen-eration techniques, regression testing, and mutation testing. Combinatorial testing (also known as interaction testing) is an important test case generation technique and is widely researched by many researchers. After modeling the software under test, testers can get an instance composed of factors and values. Combinatorial test-ing can generate test suites with small size by covering interactions of a few factors. Some empirical studies also show that it can effectively reduce the test suite size but still keep high fault detection ability in some testing scenarios. However, the construction of the optimal combinatorial test suite is demonstrated to be NP-hard.
In this dissertation, we systematically review the related work of combinato-rial testing technique and its applications. For traditional pairwise testing and its variants, we propose several effective test suite construction algorithms based on meta-heuristic search techniques. For test suite reduction in regression testing, we propose a test suite reduction approach based on pairwise interaction of test require-ments. The contributions of this dissertation can be summarized as follows:
(1) For traditional pairwise testing issue, we propose a framework of particle swarm optimization based pairwise testing. To generate a single test case, we apply particle swarm optimization aiming to cover more interactions. Meanwhile we dis-cuss the reasonable settings of search space, fitness function, and heuristics. Based on the above algorithm, we propose two different test suite construction algorithms. One is based on one-test-at-a-time strategy, the other is based on IPO-like strategy. In our empirical study, we analyze the impact factors in our framework and make a comparison with other well-known approaches to show the effectiveness of our framework.
(2) For the variant issues of combinatorial testing, we extend the application of ant colony optimization in traditional combinatorial testing to support the con-struction of prioritized combinatorial test suites and variable strength combinatorial test suites. In particular, to build prioritized combinatorial test suites, we use one-test-at-a-time strategy. To generate a single test case, we propose four concrete ant colony optimization strategies (AS, ASelite, ACS, and MM AS) and discuss the set-tings of heuristics. In the part of case studies, we compare our approach to a classical greedy approach WDA (Weighted Density Algorithm) and also make a comparison among these four different approaches. To build variable strength combinatorial test suites, we also use one-test-at-a-time strategy. To generate a single test case, we apply ant colony system (ACS) strategy aiming to cover more interactions and discuss the settings of heuristics. After the test suite is constructed, we can use a test suite minimization algorithm to further reduce this test suite size. In the final case studies, we compare this approach to some classical approaches and tools to show the effectiveness of our approach.
(3) For the test suite reduction issue in regression testing, most of traditional test suite reduction approaches only consider the coverage of individual test require-ment, but these approaches may significantly lose fault detection ability of original test suites. We propose a lightweight test suite reduction approach PWIR. In this approach, we consider the coverage of pairwise interaction of test requirements. In our empirical study, we use the Siemens suite as our subjects and find that this approach can effectively increase the fault detection ability of reduced test suite by adding only a few test cases.
引文
[1]B. Hailpern and P. Santhanam, "Software debugging, testing, and verifica-tion," IBM Systems Journal, vol.41, no.1, pp.4-12,2002.
[2]P. Ammann and J. Offutt, Introduction to Software Testing. Cambridge University Press,2008.
[3]A. Mathur, Foundations of Software Testing. Pearson Education,2008.
[4]H. Zhu, P. Hall, and J. May, "Software unit test coverage and adequacy," A CM Computing Surveys, vol.29, no.4, pp.366-422,1997.
[5]A. Memon, M. Soffa, and M. Pollack, "Coverage criteria for gui testing," in Proceedings of the 9th International Symposium on Foundations of Software Engineering,2001, pp.256-267.
[6]A. Memon, "An event-flow model of gui-based applications for testing," soft-ware testing, verification, and reliability, vol.17, no.3, pp.137-157,2007.
[7]S. McMaster and A. Memon, "Call-stack coverage for gui test suite reduction," IEEE Transaction on Software Engineering, vol.34, no.1, pp.99-115,2008.
[8]S. Sampath, R. Bryce, G. Viswanath, V. Kandimalla, and A. Koru, "Prioritiz-ing user-session-based test cases for web application testing," in Proceedings of the 1st International Conference on Software Testing, Verification, and Vali-dation,2008, pp.141-150.
[9]S. Elbaum, G. Rothermel, S. Karre, and M. Fisher, "Leveraging user-session data to support web application testing," IEEE Transaction on Software En-gineering, vol.31, no.3, pp.187-202,2005.
[10]L. Mei, W. Chan, and T. Tse, "Data flow testing of service-oriented workflow applications," in Proceedings of 2008 International Conference on Software Engineering,2008, pp.371-380.
[11]L. Mei, W. K. Chan, and T. H. Tse, "Data flow testing of service choreog-raphy," in Proceedings of 2009 Symposium on the Foundations of Software Engineering,2009, pp.151-160.
[12]D. Cohen, S. Dalal, M. Fredman, and G. Patton, "The aetg system:an ap-proach to testing based on combinatorial design," IEEE Transactions on Soft-ware Engineering, vol.23, no.7, p.437-444,1997.
[13]C. Pacheco, S. Lahiri, M. Ernst, and T. Ball, "Feedback-directed random test generation," in Proceedings of 29th International Conference on Software Engineering,2007, pp.75-84.
[14]I. Ciupa, A. Leitner, M. Oriol, and B. Meyer, "Artoo:adaptive random testing for object-oriented software," in Proceedings of 30th International Conference on Software Engineering,2008, pp.71-80.
[15]——, "Experimental assessment of random testing for object-oriented soft-ware," in Proceedings of the Symposium on Software Testing and Analysis, 2007, pp.84-94.
[16]M. Harman and P. McMinn, "A theoretical & empirical znalysis of evo-lutionary testing and hill climbing for structural test data generation," in Proceedings of the Symposium on Software Testing and Analysis,2007, pp. 73-83.
[17]P. McMinn, M. Harman, D. Binkley, and P. Tonella, "The species per path ap-proach to searchbased test data generation," in Proceedings of the Symposium on Software Testing and Analysis,2006, pp.13-24.
[18]P. Tonella, "Evolutionary testing of classes," in Proceedings of the 2004 inter-national symposium on Software testing and analysis,2004, pp.119-128.
[19]R. Majumdar and K. Sen, "Hybrid concolic testing," in Proceedings of 29th International Conference on Software Engineering,2007, pp.416-426.
[20]K. Sen, D. Marinov, and G. Agha, "Cute:A concolic unit testing engine for c," in Proceedings of 13th International Symposium on Foundations of Sofware Engineering,2005, pp.263-272.
[21]M. Harrold and A. Orso, "Retesting software during development and main-tenance," in Frontiers of Software Maintenance,2008, pp.99-108.
[22]D. Schuler, V. Dallmeier, and A. Zeller:, "Efficient mutation testing by check-ing invariant violations," in Proceedings of the Eighteenth International Sym-posium on Software Testing and Analysis,2009, pp.69-80.
[23]L. Zhang, S. Hou, J. Hu, T. Xie, and H. Mei, "Is operator-based mutant selection superior to random mutant selection?" in Proceedings of the 32nd International Conference on Software Engineering,2010, pp.435-444.
[24]A. Namin, J. Andrews, and D. Murdoch, "Sufficient mutation operators for measuring test effectiveness," in Proceedings of 30th International Conference on Software Engineering,2008, pp.351-360.
[25]J. Jones, M. Harrold, and J. Stasko, "Visualization of test information to assist fault localization," in Proceedings of the 24th International Conference on Software Engineering,2002, pp.467-477.
[26]J. Jones and M. Harrold, "Empirical evaluation of the tarantula automatic fault-localization technique," in Proceedings of 20th International Conference on Automated Software Engineering,2005, pp.273-282.
[27]Y. Yu, J. Jones, and M. Harrold, "An empirical study of the effects of test-suite reduction on fault localization," in Proceedings of the 30th International Conference on Software Engineering,2008, pp.201-210.
[28]R. Santelices, J. Jones, Y. Yu, and M. Harrold, "Lightweight fault-localization using multiple coverage types," in Proceedings of 31st International Conference on Software Engineering,2009, pp.56-66.
[29]G. Baah, A. Podgurski, and M. Harrold, "The probabilistic program depen-dence graph and its application to fault diagnosis," in In Proceedings of the International Symposium on Software Testing and Analysis,2008, pp.189-200.
[30]——, "Causal inference for statistical fault localization," in Proceedings of the 19th International Symposium on Software Testing and Analysis,2010, pp. 73-84.
[31]S. Artzi, J. Dolby, F. Tip, and M. Pistoia, "Practical fault localization for dy-namic web applications," in Proceedings of the 32nd International Conference on Software Engineering,2010, pp.265-274.
[32]S. Park, R. Vuduc, and M. Harrold, "Falcon:fault localization in concurrent programs," in Proceedings of the 32nd International Conference on Software Engineering,2010, pp.245-254.
[33]D. Kuhn, D. Wallace, and A. Gallo, "Software fault interactions and impli-cations for software testing," IEEE Transactions on Software Engineering, vol.30, no.6, pp.418-421,2004.
[34]A. Williams, "Determination of test configurations for pair-wise interaction coverage," in Proceedings of Testing of Communicating System:Tools and Techniques,2000, pp.59-74.
[35]A. Williams and R. Probert, "A practical strategy for testing pair-wise cover-age of network interfaces," in Proceedings of Seventh International Symposium on Software Reliability Engineering,1996, pp.246-254.
[36]G. Sherwood, "Effective testing of factor combinations," in Proceedings of the 3rd International Conference on Software Testing, Analysis and Review,1994.
[37]Y. Tung and W. Aldiwan, "Automating test case generation for the new gen-eration mission software system," in Aerospace Conference,2000, pp.431-437.
[38]R. Bryce and C. Colbourn, "The density algorithm for pairwise interaction testing," Software Testing, Verification and Reliability, vol.17, no.3, pp.159-182,2007.
[39]L. Shi, C. Nie, and B. Xu, "Pairwise test data generation based on solution space tree," Chinese Journal of Computers, vol.29, no.6, pp.849-857,2006.
[40]K. Tai and Y. Lei, "A test generation strategy for pairwise testing," IEEE Transaction on Software Engineering, vol.28, no.1, pp.109-111,2002.
[41]M. Harman, "The current state and future of search based software engineer-ing," in Future of Software Engineering,2007, pp.342-357.
[42]M. Cohen, C. Colbourn, G. Gibbons, and W. Mugridge, "Constructing test suites for interaction testing," in Proceedings of the 25th International Con-ference on Software Engineering,2003, pp.38-48.
[43]T. Shiba, T. Tsuchiya, and T. Kikuno, "Using artificial life techniques to generate test cases for combinatorial testing," in Proceedings of International Conference on Computer Software and Applications Conference,2004, pp.72-77.
[44]R. Bryce and C. Colbourn, "One-test-at-a-time heuristic search for interac-tion test suites," in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation,2007, pp.1082-1089.
[45]A. Windisch, S. Wappler, and J. Wegener, "Applying particle swarm opti-mization to software testing," in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation,2007, pp.1121-1128.
[46]C. Yilmaz, M. Cohen, and A. Porter, "Covering arrays for efficient fault lo-calization in complex configuration space," IEEE Transactions on Software Engineering, vol.32, no.1, pp.20-34,2006.
[47]C. Nie, H. Leung, and B. Xu, "The minimal failure-causing schema of combina-torial testing," ACM Transaction on Software Engineering and Methodology, To Appear.
[48]W. Wang, Y. Lei, S. Sampath, R. Kacker, R. Kuhn, and J. Lawrence, "A combinatorial approach to building navigation graphs for dynamic web appli-cations," in proceedings of the 25th IEEE International Conference on Software Maintenance,2009, pp.211-220.
[49]X. Yuan, M. Cohen, and A. Memon, "Gui interaction testing:Incorporating event context," IEEE Transactions on Software Engineering, to appear.
[50]X. Qu, M. Cohen, and K. Woolf, "Combinatorial interaction regression testing: a study of test case generation and prioritization," in Proceedings of the IEEE International Conference on Software Maintenance,2007, pp.255-264.
[51]X. Qu, M. Cohen, and G. Rothermel, "Configuration-aware regression testing: an empirical study of sampling and prioritization," in Proceedings of the 2008 international symposium on Software testing and analysis,2008, pp.75-85.
[52]G. Rothermel, M. Harrold, J. Ostrin, and C. Hong, "An empirical study of the effects of minimization on the fault-detection capabilities of test suites," in Proceedings of the l^th International Conference on Software Maintenance, 1998, pp.34-43.
[53]A. Namin and D. Andrews, "The influence of size and coverage on test suite effectiveness," in Proceedings of the 10th International Symposium on Software Testing and Analysis,2009, pp.57-67.
[54]X. Chen, Q. Gu, X. Wang, and D. Chen, "Research advances in interaction testing," Journal of Computer Science, vol.37, no.3, pp.1-5,2010.
[55]X. Chen, Q. Gu, J. Qi, and D. Chen, "Applying particle swarm optimization to pairwise testing," in Proceedings of the 34th Annual IEEE Computer Software and Application Conference,2010, pp.107-116.
[56]X. Chen, Q. Gu, Z. Wang, and D. Chen, "A framework of particle swarm optimization based pairwise testing," Journal of Software, to Appear.
[57]R. Bryce and C. Colbourn, "Prioritized interaction testing for pair-wise cov-erage with seeding and constraints," Information and Software Technology, vol.48, no.10, pp.960-970,2006.
[58]X. Chen, Q. Gu, X. Zhang, and D. Chen, "Building prioritized pairwise in-teraction test suites with ant colony optimization," in Proceedings of the 9th International Conference on Quality Software,2009, pp.347-352.
[59]M.B.Cohen, C. Colbourn, J. Collofello, P. Gibbons, and W. Mugridge, "Vari-able strength interaction testing of components," in Proceedings of 27th Inter-national Computer Software and Applications Conference,2003, pp.413-418.
[60]Z. Wang, B. Xu, and C. Nie, "Greedy heuristic algorithms to generate vari-able strength combinatorial test suite," in proceedings of the 8th International Conference on Quality Software,2008, pp.155-160.
[61]X. Chen, Q. Gu, A. Li, and D. Chen, "Variable strength interaction testing with an ant colony system approach," in Proceedings of the 16th Asia-Pacific Software Engineering Conference,2009, pp.160-167.
[62]X. Chen, L. Zhang, Q. Gu, H. Zhao, Z. Wang, X. Sun, and D. Chen, "A test suite reduction approach based on pairwise interaction of requirements," in Proceedings of the 26th Symposium On Applied Computing,2011, pp.1395-1402.
[63]G. Myers, The Art of Software Testing. John Wiley and Sons,1979.
[64]M. Grindal and J. Offutt, "Input parameter modeling for combination strate-gies," in Proceedings of the 25th conference on IASTED International Multi-Conference:Software Engineering,2007, pp.255-260.
[65]A. Hedayat, N. Sloane, and J. Stufken, Orthogonal Arrays. Springer-Verlag, 1999.
[66]M. Cohen, M. Dwyer, and J. Shi, "Interaction testing of highly-configurable systems in the presence of constraints," in Proceedings of the 2007 Interna-tional Symposium on Software Testing and Analysis,2007, pp.129-139.
[67]M.B.Cohen, M.B.Dwyer, and J.F.Shi, "Exploiting constraint solving history to construct interaction test suites," in Proceedings of the Testing:Academic and Industrial Conference Practice and Research Techniques,2007, pp.121-132.
[68]M. Cohen, M. Dwyer, and J. Shi, "Constructing interaction test suites for highly-configurable systems in the presence of constraints:A greedy ap-proach," IEEE Transaction on Software Engineering, vol.34, no.5, pp.633-650,2008.
[69]B. Garvin, M. Cohen, and M. Dwyer, "An improved meta-heuristic search for constrained interaction testing," in Proceedings of the 2009 1st International Symposium on Search Based Software Engineering,2009, pp.13-22.
[70]——, "Evaluating improvements to a meta-heuristic search for constrained interaction testing," Empirical Software Engineering,2010, to appear.
[71]B. Chen, J. Yan, and J. Zhang,"Combinatorial testing with shielding parame-ters," in Proceedings of the 17th Asia-Pacific Software Engineering Conference. 2010, pp.280-289.
[72]R. Bryce and C. Colbourn, "A density-based greedy algorithm for higher strength covering arrays," Software Testing, Verification and Reliability, vol.19, pp.37-53,2009.
[73]Y. Lei, R. Kacker, D. Kulin, V. Okun, and J. Lawrence, "Ipog/ipog-d:effi-cient test generation for multi-way combinatorial testing,'" Software Testing, Verification and Reliability, vol.18, pp.125-148,2008.
[74]M. Cohen, C. Colbourn. and A. Ling. "Augmenting simulated annealing to build interaction test suites," in proceedings of 14th IEEE International Sym-posium on Software Reliability Engineering,2003. pp.394-405.
[75]Z. Wang, B. Xu, L. Chen, and Z. Chen, "Cost-effective combinatorial test case prioritization for varying combination weights," in proceedings of the 22th In-ternational Conference on Software Engineering and Knowledge Engineering, 2010, pp.273-278.
[76]"Tvg," http://sourceforge.net/projects/tvg.
[77]J. Czerwonka, "Pairwise testing in real world:practical extensions to test case generator," in Proceedings of 24th Pacific Northwest Software Quality Conference,2006, pp.419-430.
[78]C. Nie, B. Xu, and L. Shi, "A new pairwise covering test data generation algorithm for the system with many 2-level factors," Chinese Journal of Com-puters, vol.29, no.6, pp.841-848,2006.
[79]Z. Wang, C. Nie, B. Xu, and L. Shi, "Optimal test suite generation methods for neighbor factors combinatorial testing," Chinese Journal of Computers, vol.30, no.2, pp.200-211,2007.
[80]R. Bryce, C. Colbourn, and M. Cohen, "A framework of greedy methods for constructing interaction tests," in Proceedings of the 27th International Conference on Software Engineering,2005, pp.146-155.
[81]R. Mandl, "Orthogonal latin squares:An application of experimental design to compiler testing," Communications of the ACM, vol.28, no.10, pp.1054-1058,1985.
[82]M. Grindal, J. Offutt, and S. Andler, "Combination testing strategies:A survey," Software Testing, Verification and Reliability, vol.5, no.3, pp.167-199,2004.
[83]J. Yan and J. Zhang, "Combinatorial testing:Principles and methods," Jour-nal of Software, vol.20, no.6, pp.1393-1405,2009.
[84]Z. Wang, B. Xu, and C. Nie, "Survey of combinatorial test generation," Jour-nal of Frontiers of Computer Science and Technology, vol.06, pp.571-588, 2008.
[85]C. Nie, B. Xu, and H. Leung, "A survey of combinatorial testing," ACM Computing Survey, To Appear.
[86]J. Yan and J. Zhang, "Backtracking algorithms and search heuristics to gen-erate test suites for combinatorial testing," in Proceedings of the 30th Annual International Computer Software and Applications Conference,2006, pp.385-394.
[87]——, "A backtracking search tool for constructing combinatorial test suites," Journal of System and Software, vol.81, no.10, pp.1681-1693,2008.
[88]D. Cohen, S. Dalal, J. Parelius, and G. Patton, "The combinatorial design approach to automatic test generation," IEEE Software, vol.13, no.5, pp. 83-88,1996.
[89]J. Stardom, "Metaheuristics and the search for covering and packing arrays,' Master's thesis, Simon Fraser University,2001.
[90]C. Yilmaz, M. Cohen, and A. Porter, "Covering arrays for efficient fault char-acterization in complex configuration spaces," in Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis,2004, pp. 45-54.
[91]S. Fouche, M. Cohen, and A. Porter, "Incremental covering array failure characterization in large configuration spaces," in proceedings of International Symposium on Software Testing and Analysis,2009, pp.177-187.
[92]B. Xu, C. Nie, L. Shi, and H. Chen, "A software failure debugging m ethod based on combinatorial design approach for testing," Chines Journal of Com-puters, vol.29, no.1, pp.132-138,2006.
[93]W. Wang, S. Sampath, Y. Lei, and R. Kacker, "An interaction-based test sequence generation approach for testing web applications," in Proceedings of 11th IEEE High Assurance Systems Engineering Symposium,2008, pp.209-218.
[94]R. Bryce, S. Sampath, and A. Memon, "Developing a single model and test pri-oritization strategies for event-driven software," IEEE Transactions on Soft-ware Engineering, To Appear.
[95]H. Srikanth, M. Cohen, and X. Qu, "Reducing field failures in system config-urable software:Cost-based prioritization," in proceedings of the 20th annual International Symposium on Software Reliability Engineering,2009, pp.61-70.
[96]M. Harman and B. F. Jones, "Search-based software engineering," Information and Software Technology, vol.43, no.14, pp.833-839,2001.
[97]P. McMinn, "Search-based software test data generation:A survey," Software Testing, Verification and Reliability, vol.14, no.2, pp.105-156,2004.
[98]J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of IEEE International Conference on Neural Networks,1995, pp.1942-1948.
[99]J. Robinson and Y. Rahmat-Samii, "Particle swarm optimization in electro-magnetics," IEEE Transactions on Antennas and Propagation, vol.52, no.2, pp.397-407,2004.
[100]D. Kreher and D. Stinson, Combinatorial Algorithms, Generation, Enumera-tion and Search. CRC Press,1999.
[101]M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system:optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man, and Cy-bernetics, vol.26, no.1, pp.29-41,1996.
[102]M. Dorigo and C. Blum, "Ant colony optimization theory:a survey," Theo-retical Computer, vol.344, no.2-3, pp.243-278,2005.
[103]E. Alba and F. Chicano, "Searching for liveness property violations in con-current systems with aco," in Proceedings of the 10th annual conference on Genetic and evolutionary computation,2008, pp.1727-1734.
[104]E. Alba and J. Chicano, "Finding safety errors with aco," in Proceedings of the 9th annual conference on Genetic and evolutionary computation,2007, pp. 1066-1073.
[105]K. Ayari, S. Bouktif, and G. Antoniol, "Automatic mutation test input data generation via ant colony," in Proceedings of the 9th Genetic and Evolutionary Computation Conference,2007, pp.1074-1081.
[106]G. Rothermel, R. Untch, C. Chu, and M. Harrold, "Prioritizing test cases for regression testing," ACM Transactions on Software Engineering and Method-ology, vol.27, no.10, pp.929-948,2001.
[107]T. Stutzle and H. Hoos, "Max-min ant system," Future Generation Computer Systems, vol.16, no.8, pp.889-914,2000.
[108]M. Dorigo and L. Gambardella, "Ant colony system:A cooperative learning approach to the traveling salesman problem," IEEE Transactions on Evolu-tionary Computation, vol.1, no.1, pp.53-66,1997.
[109]D. Merkle, M. Middendorf, and H. Schmeck, "Ant colony optimization for resource-constrainted project scheduling," IEEE Transactions on Evoluionary Computation, vol.6, no.4, pp.333-346,2002.
[110]T. Chen and M. Lau, "A new heuristic for test suite reduction," Information and Software Technology, vol.4, pp.347-354,1998.
[111]M. Harrold, R. Gupta, and M. Soffa, "A methodology for controlling the size of a test suite," ACM Transactions on Software Engineering and Methodology, vol.2, no.3, pp.270-285,1993.
[112]M. Nashat and E. Khalid, "Simulated annealing and genetic algorithms for optimal regression testing," Journal of Software Maintenance:Research and Practice, vol.11, no.1, pp.19-34,1999.
[113]S. Tallam and N. Gupta, "A concept analysis inspired greedy algorithm for test suite minimization," in Proceedings of the 6th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering,2005, pp. 35-42.
[114]D. Jeffrey and X. Gupta, "Improving fault detection capability by selectively retaining test cases during test suite reduction," IEEE Transactions on Soft-ware Engineering, vol.33, no.2, pp.108-123,2007.
[115]J. Black, E. Melachrinoudis, and D. Kaeli, "Bi-criteria models for all-uses test suite reduction," in Proceedings of the 26th International Conference on Software Engineering,2004. pp.106-115.
[116]H. Hsu and A. Orso, "Mints:A general framework and tool for supporting test-suite minimization," in Proceedings of the 31st International Conference on Software Engineering.2009, pp.419-429.
[117]W. Wong, J. Horgan, S. London, and A. Mathur, "Effect of test set mini-mization on fault detection effectiveness," Software Practice and Experience, vol.28, no.4, pp.347-369,1998.
[118]H. Do, S. Elbaum, and G. Rothermel, "Supporting controlled experimentation with testing techniques:An infrastructure and its potential impact," Empirical Software Engineering, vol.10, no.4, pp.405-435,2005.
[119]G. Rothermel and M. Harrold, "A safe, efficient regression test selection tech-nique," A CM Transactions on Software Engineering and Methodology, vol.6, no.2, pp.173-210,1997.
[120]M. Harrold, J. Jones, T. Li, D. Liang, M. P. A. Orso, S. Sinha, and S. Spoon, "Regression test selection for Java software," in Proceedings of ACM Confer-ence on Object-Oriented Programming, System, Languages, and Applications, 2001, pp.312-326.
[121]A. Orso, N. Shi, and M. Harrold, "Scaling regression testing to large software systems," in Proceedings of the 12th ACM SIGSOFT Internatinal Symposium on Foundations of Software Engineering,2004, pp.241-251.
[122]G. Xu and A. Rountev:, "Regression test selection for aspectj software," in Proceedings of 29th International Conference on Software Engineering,2007, pp.65-74.
[123]S. Yoo and M. Harman, "Pareto efficient multi-objective test case selection," in Proceedings of the Symposium on Software Testing and Analysis,2007, pp. 140-150.
[124]G. Rothermel, R. Untch, C. Chu, and M. Harrold, "Prioritizing test cases for regression testing," IEEE Transaction on Software Engineering, vol.27, no.10, pp.929-948,2001.
[125]S. Elbaum, A. Malishevsky, and G. Rothermel, "Test case prioritization: A family of empirical studies," IEEE Transaction on Software Engineering, vol.28, no.2, pp.159-182,2002.
[126]S. Yoo, M. Harman, P. Tonella, and A. Susi, "Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge," in Pro-ceedings of the Eighteenth International Symposium on Software Testing and Analysis,2009, pp.201-212.
[127]L. Zhang, S. Hou, C. Guo, T. Xie, and H. Mei, "Time-aware test-case prior-itization using integer linear programming," in Proceedings of the Eighteenth International Symposium on Software Testing and Analysis.2009, pp.213 224.
[128]K. Walcott, M. Soffa, G. Kapfhammer, and R. Roos, "Timeaware test suite prioritization," in Proceedings of the Symposium on Software Testing and Anal-ysis,2006, pp.1-12.
[129]S. Yoo and M. Harman, "Regression testing minimization, selection and pri-oritization:a survey," Software Testing, Verification and Reliability,2010, to Appear.
[130]R. Santelices, P. Chittimalli, T. Apiwattanapong, A. Orso, and M. Harrold, "Test-suite augmentation for evolving software," in Proceedings of 23rd Inter-national Conference on Automated Software Engineering,2008, pp.218-227.
[131]Z. Xu, Y. Kim, M. Kim, G. Rothermel, and M. Cohen, "Directed test suite augmentation:Techniques and tradeoffs," in Proceedings of the 18th Interna-tional Symposium on Foundations of software engineering,2010, pp.257-266.
[132]D. Qi, A. Roychoudhury, and Z. Liang, "Test generation to expose changes in evolving programs," in Proceedings of the 24th International Conference on Automated Software Engineering,2010, pp.397-406.
[133]S. Sprenkle, S. Sampath, E. Gibson, L. Pollock, and A. Souter, "An empirical comparison of test suite reduction techniques for user-session-based testing of web applications,"in Proceedings of the 21st IEEE International Conference on Software Maintenance,2005, pp.587-596.
[134]X. Zhang, Q. Gu, X. Chen, J. Qi, and D. Chen, "A study of relative re-dundancy in test-suite reduction while retaining or even improving fault-localization," in Proceedings of the 25th Symposium On Applied Computing, 2010, pp.2229-2236.
[135]J. Horgan and S. London, "Data flow coverage and the c language," in Pro-ceedings of the Symposium on Testing, Analysis and Verification,1991, pp. 87-97.
[136]J. Jones and M. Harrold, "Test-suite reduction and prioritization for modified condition/decision coverage," IEEE Transactions on Software Engineering, vol.29, no.3, pp.195209,2003.
[137]B. Vaysburg, L. Tahat, and B. Korel, "Dependence analysis in reduction of requirement based test suites," in Proceedings of the 3rd International Sym-posium on Software Testing and Analysis,2002, pp.107-111.
[138]M. Harder, J. Mellen, and M. Ernst, "Improving test suites via operational abstraction," in Proceedings of the 25th International Conference on Software Engineering,2003, pp.60-71.
[139]M. Martina and A. Bertolino, "Using spanning sets for coverage testing," IEEE Transactions on Software Engineering, vol.29, no.11, pp.974-984,2003.
[140]M. Heimdahl and D. George, "Test-suite reduction for model based tests: Effects on test quality and implications for testing," in Proceedings of 19th International Conference on Automated Software Engineering,2004, pp.176-185.
[141]Z. Chen, B. Xu, X. Zhang, and C. Nie, "A novel approach for test suite reduction based on requirement relation contraction," in Proceedings of the 2008 ACM Symposium on Applied Computing,2008, pp.390-394.
[2]P. Ammann and J. Offutt, Introduction to Software Testing. Cambridge University Press,2008.
[3]A. Mathur, Foundations of Software Testing. Pearson Education,2008.
[4]H. Zhu, P. Hall, and J. May, "Software unit test coverage and adequacy," A CM Computing Surveys, vol.29, no.4, pp.366-422,1997.
[5]A. Memon, M. Soffa, and M. Pollack, "Coverage criteria for gui testing," in Proceedings of the 9th International Symposium on Foundations of Software Engineering,2001, pp.256-267.
[6]A. Memon, "An event-flow model of gui-based applications for testing," soft-ware testing, verification, and reliability, vol.17, no.3, pp.137-157,2007.
[7]S. McMaster and A. Memon, "Call-stack coverage for gui test suite reduction," IEEE Transaction on Software Engineering, vol.34, no.1, pp.99-115,2008.
[8]S. Sampath, R. Bryce, G. Viswanath, V. Kandimalla, and A. Koru, "Prioritiz-ing user-session-based test cases for web application testing," in Proceedings of the 1st International Conference on Software Testing, Verification, and Vali-dation,2008, pp.141-150.
[9]S. Elbaum, G. Rothermel, S. Karre, and M. Fisher, "Leveraging user-session data to support web application testing," IEEE Transaction on Software En-gineering, vol.31, no.3, pp.187-202,2005.
[10]L. Mei, W. Chan, and T. Tse, "Data flow testing of service-oriented workflow applications," in Proceedings of 2008 International Conference on Software Engineering,2008, pp.371-380.
[11]L. Mei, W. K. Chan, and T. H. Tse, "Data flow testing of service choreog-raphy," in Proceedings of 2009 Symposium on the Foundations of Software Engineering,2009, pp.151-160.
[12]D. Cohen, S. Dalal, M. Fredman, and G. Patton, "The aetg system:an ap-proach to testing based on combinatorial design," IEEE Transactions on Soft-ware Engineering, vol.23, no.7, p.437-444,1997.
[13]C. Pacheco, S. Lahiri, M. Ernst, and T. Ball, "Feedback-directed random test generation," in Proceedings of 29th International Conference on Software Engineering,2007, pp.75-84.
[14]I. Ciupa, A. Leitner, M. Oriol, and B. Meyer, "Artoo:adaptive random testing for object-oriented software," in Proceedings of 30th International Conference on Software Engineering,2008, pp.71-80.
[15]——, "Experimental assessment of random testing for object-oriented soft-ware," in Proceedings of the Symposium on Software Testing and Analysis, 2007, pp.84-94.
[16]M. Harman and P. McMinn, "A theoretical & empirical znalysis of evo-lutionary testing and hill climbing for structural test data generation," in Proceedings of the Symposium on Software Testing and Analysis,2007, pp. 73-83.
[17]P. McMinn, M. Harman, D. Binkley, and P. Tonella, "The species per path ap-proach to searchbased test data generation," in Proceedings of the Symposium on Software Testing and Analysis,2006, pp.13-24.
[18]P. Tonella, "Evolutionary testing of classes," in Proceedings of the 2004 inter-national symposium on Software testing and analysis,2004, pp.119-128.
[19]R. Majumdar and K. Sen, "Hybrid concolic testing," in Proceedings of 29th International Conference on Software Engineering,2007, pp.416-426.
[20]K. Sen, D. Marinov, and G. Agha, "Cute:A concolic unit testing engine for c," in Proceedings of 13th International Symposium on Foundations of Sofware Engineering,2005, pp.263-272.
[21]M. Harrold and A. Orso, "Retesting software during development and main-tenance," in Frontiers of Software Maintenance,2008, pp.99-108.
[22]D. Schuler, V. Dallmeier, and A. Zeller:, "Efficient mutation testing by check-ing invariant violations," in Proceedings of the Eighteenth International Sym-posium on Software Testing and Analysis,2009, pp.69-80.
[23]L. Zhang, S. Hou, J. Hu, T. Xie, and H. Mei, "Is operator-based mutant selection superior to random mutant selection?" in Proceedings of the 32nd International Conference on Software Engineering,2010, pp.435-444.
[24]A. Namin, J. Andrews, and D. Murdoch, "Sufficient mutation operators for measuring test effectiveness," in Proceedings of 30th International Conference on Software Engineering,2008, pp.351-360.
[25]J. Jones, M. Harrold, and J. Stasko, "Visualization of test information to assist fault localization," in Proceedings of the 24th International Conference on Software Engineering,2002, pp.467-477.
[26]J. Jones and M. Harrold, "Empirical evaluation of the tarantula automatic fault-localization technique," in Proceedings of 20th International Conference on Automated Software Engineering,2005, pp.273-282.
[27]Y. Yu, J. Jones, and M. Harrold, "An empirical study of the effects of test-suite reduction on fault localization," in Proceedings of the 30th International Conference on Software Engineering,2008, pp.201-210.
[28]R. Santelices, J. Jones, Y. Yu, and M. Harrold, "Lightweight fault-localization using multiple coverage types," in Proceedings of 31st International Conference on Software Engineering,2009, pp.56-66.
[29]G. Baah, A. Podgurski, and M. Harrold, "The probabilistic program depen-dence graph and its application to fault diagnosis," in In Proceedings of the International Symposium on Software Testing and Analysis,2008, pp.189-200.
[30]——, "Causal inference for statistical fault localization," in Proceedings of the 19th International Symposium on Software Testing and Analysis,2010, pp. 73-84.
[31]S. Artzi, J. Dolby, F. Tip, and M. Pistoia, "Practical fault localization for dy-namic web applications," in Proceedings of the 32nd International Conference on Software Engineering,2010, pp.265-274.
[32]S. Park, R. Vuduc, and M. Harrold, "Falcon:fault localization in concurrent programs," in Proceedings of the 32nd International Conference on Software Engineering,2010, pp.245-254.
[33]D. Kuhn, D. Wallace, and A. Gallo, "Software fault interactions and impli-cations for software testing," IEEE Transactions on Software Engineering, vol.30, no.6, pp.418-421,2004.
[34]A. Williams, "Determination of test configurations for pair-wise interaction coverage," in Proceedings of Testing of Communicating System:Tools and Techniques,2000, pp.59-74.
[35]A. Williams and R. Probert, "A practical strategy for testing pair-wise cover-age of network interfaces," in Proceedings of Seventh International Symposium on Software Reliability Engineering,1996, pp.246-254.
[36]G. Sherwood, "Effective testing of factor combinations," in Proceedings of the 3rd International Conference on Software Testing, Analysis and Review,1994.
[37]Y. Tung and W. Aldiwan, "Automating test case generation for the new gen-eration mission software system," in Aerospace Conference,2000, pp.431-437.
[38]R. Bryce and C. Colbourn, "The density algorithm for pairwise interaction testing," Software Testing, Verification and Reliability, vol.17, no.3, pp.159-182,2007.
[39]L. Shi, C. Nie, and B. Xu, "Pairwise test data generation based on solution space tree," Chinese Journal of Computers, vol.29, no.6, pp.849-857,2006.
[40]K. Tai and Y. Lei, "A test generation strategy for pairwise testing," IEEE Transaction on Software Engineering, vol.28, no.1, pp.109-111,2002.
[41]M. Harman, "The current state and future of search based software engineer-ing," in Future of Software Engineering,2007, pp.342-357.
[42]M. Cohen, C. Colbourn, G. Gibbons, and W. Mugridge, "Constructing test suites for interaction testing," in Proceedings of the 25th International Con-ference on Software Engineering,2003, pp.38-48.
[43]T. Shiba, T. Tsuchiya, and T. Kikuno, "Using artificial life techniques to generate test cases for combinatorial testing," in Proceedings of International Conference on Computer Software and Applications Conference,2004, pp.72-77.
[44]R. Bryce and C. Colbourn, "One-test-at-a-time heuristic search for interac-tion test suites," in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation,2007, pp.1082-1089.
[45]A. Windisch, S. Wappler, and J. Wegener, "Applying particle swarm opti-mization to software testing," in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation,2007, pp.1121-1128.
[46]C. Yilmaz, M. Cohen, and A. Porter, "Covering arrays for efficient fault lo-calization in complex configuration space," IEEE Transactions on Software Engineering, vol.32, no.1, pp.20-34,2006.
[47]C. Nie, H. Leung, and B. Xu, "The minimal failure-causing schema of combina-torial testing," ACM Transaction on Software Engineering and Methodology, To Appear.
[48]W. Wang, Y. Lei, S. Sampath, R. Kacker, R. Kuhn, and J. Lawrence, "A combinatorial approach to building navigation graphs for dynamic web appli-cations," in proceedings of the 25th IEEE International Conference on Software Maintenance,2009, pp.211-220.
[49]X. Yuan, M. Cohen, and A. Memon, "Gui interaction testing:Incorporating event context," IEEE Transactions on Software Engineering, to appear.
[50]X. Qu, M. Cohen, and K. Woolf, "Combinatorial interaction regression testing: a study of test case generation and prioritization," in Proceedings of the IEEE International Conference on Software Maintenance,2007, pp.255-264.
[51]X. Qu, M. Cohen, and G. Rothermel, "Configuration-aware regression testing: an empirical study of sampling and prioritization," in Proceedings of the 2008 international symposium on Software testing and analysis,2008, pp.75-85.
[52]G. Rothermel, M. Harrold, J. Ostrin, and C. Hong, "An empirical study of the effects of minimization on the fault-detection capabilities of test suites," in Proceedings of the l^th International Conference on Software Maintenance, 1998, pp.34-43.
[53]A. Namin and D. Andrews, "The influence of size and coverage on test suite effectiveness," in Proceedings of the 10th International Symposium on Software Testing and Analysis,2009, pp.57-67.
[54]X. Chen, Q. Gu, X. Wang, and D. Chen, "Research advances in interaction testing," Journal of Computer Science, vol.37, no.3, pp.1-5,2010.
[55]X. Chen, Q. Gu, J. Qi, and D. Chen, "Applying particle swarm optimization to pairwise testing," in Proceedings of the 34th Annual IEEE Computer Software and Application Conference,2010, pp.107-116.
[56]X. Chen, Q. Gu, Z. Wang, and D. Chen, "A framework of particle swarm optimization based pairwise testing," Journal of Software, to Appear.
[57]R. Bryce and C. Colbourn, "Prioritized interaction testing for pair-wise cov-erage with seeding and constraints," Information and Software Technology, vol.48, no.10, pp.960-970,2006.
[58]X. Chen, Q. Gu, X. Zhang, and D. Chen, "Building prioritized pairwise in-teraction test suites with ant colony optimization," in Proceedings of the 9th International Conference on Quality Software,2009, pp.347-352.
[59]M.B.Cohen, C. Colbourn, J. Collofello, P. Gibbons, and W. Mugridge, "Vari-able strength interaction testing of components," in Proceedings of 27th Inter-national Computer Software and Applications Conference,2003, pp.413-418.
[60]Z. Wang, B. Xu, and C. Nie, "Greedy heuristic algorithms to generate vari-able strength combinatorial test suite," in proceedings of the 8th International Conference on Quality Software,2008, pp.155-160.
[61]X. Chen, Q. Gu, A. Li, and D. Chen, "Variable strength interaction testing with an ant colony system approach," in Proceedings of the 16th Asia-Pacific Software Engineering Conference,2009, pp.160-167.
[62]X. Chen, L. Zhang, Q. Gu, H. Zhao, Z. Wang, X. Sun, and D. Chen, "A test suite reduction approach based on pairwise interaction of requirements," in Proceedings of the 26th Symposium On Applied Computing,2011, pp.1395-1402.
[63]G. Myers, The Art of Software Testing. John Wiley and Sons,1979.
[64]M. Grindal and J. Offutt, "Input parameter modeling for combination strate-gies," in Proceedings of the 25th conference on IASTED International Multi-Conference:Software Engineering,2007, pp.255-260.
[65]A. Hedayat, N. Sloane, and J. Stufken, Orthogonal Arrays. Springer-Verlag, 1999.
[66]M. Cohen, M. Dwyer, and J. Shi, "Interaction testing of highly-configurable systems in the presence of constraints," in Proceedings of the 2007 Interna-tional Symposium on Software Testing and Analysis,2007, pp.129-139.
[67]M.B.Cohen, M.B.Dwyer, and J.F.Shi, "Exploiting constraint solving history to construct interaction test suites," in Proceedings of the Testing:Academic and Industrial Conference Practice and Research Techniques,2007, pp.121-132.
[68]M. Cohen, M. Dwyer, and J. Shi, "Constructing interaction test suites for highly-configurable systems in the presence of constraints:A greedy ap-proach," IEEE Transaction on Software Engineering, vol.34, no.5, pp.633-650,2008.
[69]B. Garvin, M. Cohen, and M. Dwyer, "An improved meta-heuristic search for constrained interaction testing," in Proceedings of the 2009 1st International Symposium on Search Based Software Engineering,2009, pp.13-22.
[70]——, "Evaluating improvements to a meta-heuristic search for constrained interaction testing," Empirical Software Engineering,2010, to appear.
[71]B. Chen, J. Yan, and J. Zhang,"Combinatorial testing with shielding parame-ters," in Proceedings of the 17th Asia-Pacific Software Engineering Conference. 2010, pp.280-289.
[72]R. Bryce and C. Colbourn, "A density-based greedy algorithm for higher strength covering arrays," Software Testing, Verification and Reliability, vol.19, pp.37-53,2009.
[73]Y. Lei, R. Kacker, D. Kulin, V. Okun, and J. Lawrence, "Ipog/ipog-d:effi-cient test generation for multi-way combinatorial testing,'" Software Testing, Verification and Reliability, vol.18, pp.125-148,2008.
[74]M. Cohen, C. Colbourn. and A. Ling. "Augmenting simulated annealing to build interaction test suites," in proceedings of 14th IEEE International Sym-posium on Software Reliability Engineering,2003. pp.394-405.
[75]Z. Wang, B. Xu, L. Chen, and Z. Chen, "Cost-effective combinatorial test case prioritization for varying combination weights," in proceedings of the 22th In-ternational Conference on Software Engineering and Knowledge Engineering, 2010, pp.273-278.
[76]"Tvg," http://sourceforge.net/projects/tvg.
[77]J. Czerwonka, "Pairwise testing in real world:practical extensions to test case generator," in Proceedings of 24th Pacific Northwest Software Quality Conference,2006, pp.419-430.
[78]C. Nie, B. Xu, and L. Shi, "A new pairwise covering test data generation algorithm for the system with many 2-level factors," Chinese Journal of Com-puters, vol.29, no.6, pp.841-848,2006.
[79]Z. Wang, C. Nie, B. Xu, and L. Shi, "Optimal test suite generation methods for neighbor factors combinatorial testing," Chinese Journal of Computers, vol.30, no.2, pp.200-211,2007.
[80]R. Bryce, C. Colbourn, and M. Cohen, "A framework of greedy methods for constructing interaction tests," in Proceedings of the 27th International Conference on Software Engineering,2005, pp.146-155.
[81]R. Mandl, "Orthogonal latin squares:An application of experimental design to compiler testing," Communications of the ACM, vol.28, no.10, pp.1054-1058,1985.
[82]M. Grindal, J. Offutt, and S. Andler, "Combination testing strategies:A survey," Software Testing, Verification and Reliability, vol.5, no.3, pp.167-199,2004.
[83]J. Yan and J. Zhang, "Combinatorial testing:Principles and methods," Jour-nal of Software, vol.20, no.6, pp.1393-1405,2009.
[84]Z. Wang, B. Xu, and C. Nie, "Survey of combinatorial test generation," Jour-nal of Frontiers of Computer Science and Technology, vol.06, pp.571-588, 2008.
[85]C. Nie, B. Xu, and H. Leung, "A survey of combinatorial testing," ACM Computing Survey, To Appear.
[86]J. Yan and J. Zhang, "Backtracking algorithms and search heuristics to gen-erate test suites for combinatorial testing," in Proceedings of the 30th Annual International Computer Software and Applications Conference,2006, pp.385-394.
[87]——, "A backtracking search tool for constructing combinatorial test suites," Journal of System and Software, vol.81, no.10, pp.1681-1693,2008.
[88]D. Cohen, S. Dalal, J. Parelius, and G. Patton, "The combinatorial design approach to automatic test generation," IEEE Software, vol.13, no.5, pp. 83-88,1996.
[89]J. Stardom, "Metaheuristics and the search for covering and packing arrays,' Master's thesis, Simon Fraser University,2001.
[90]C. Yilmaz, M. Cohen, and A. Porter, "Covering arrays for efficient fault char-acterization in complex configuration spaces," in Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis,2004, pp. 45-54.
[91]S. Fouche, M. Cohen, and A. Porter, "Incremental covering array failure characterization in large configuration spaces," in proceedings of International Symposium on Software Testing and Analysis,2009, pp.177-187.
[92]B. Xu, C. Nie, L. Shi, and H. Chen, "A software failure debugging m ethod based on combinatorial design approach for testing," Chines Journal of Com-puters, vol.29, no.1, pp.132-138,2006.
[93]W. Wang, S. Sampath, Y. Lei, and R. Kacker, "An interaction-based test sequence generation approach for testing web applications," in Proceedings of 11th IEEE High Assurance Systems Engineering Symposium,2008, pp.209-218.
[94]R. Bryce, S. Sampath, and A. Memon, "Developing a single model and test pri-oritization strategies for event-driven software," IEEE Transactions on Soft-ware Engineering, To Appear.
[95]H. Srikanth, M. Cohen, and X. Qu, "Reducing field failures in system config-urable software:Cost-based prioritization," in proceedings of the 20th annual International Symposium on Software Reliability Engineering,2009, pp.61-70.
[96]M. Harman and B. F. Jones, "Search-based software engineering," Information and Software Technology, vol.43, no.14, pp.833-839,2001.
[97]P. McMinn, "Search-based software test data generation:A survey," Software Testing, Verification and Reliability, vol.14, no.2, pp.105-156,2004.
[98]J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of IEEE International Conference on Neural Networks,1995, pp.1942-1948.
[99]J. Robinson and Y. Rahmat-Samii, "Particle swarm optimization in electro-magnetics," IEEE Transactions on Antennas and Propagation, vol.52, no.2, pp.397-407,2004.
[100]D. Kreher and D. Stinson, Combinatorial Algorithms, Generation, Enumera-tion and Search. CRC Press,1999.
[101]M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system:optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man, and Cy-bernetics, vol.26, no.1, pp.29-41,1996.
[102]M. Dorigo and C. Blum, "Ant colony optimization theory:a survey," Theo-retical Computer, vol.344, no.2-3, pp.243-278,2005.
[103]E. Alba and F. Chicano, "Searching for liveness property violations in con-current systems with aco," in Proceedings of the 10th annual conference on Genetic and evolutionary computation,2008, pp.1727-1734.
[104]E. Alba and J. Chicano, "Finding safety errors with aco," in Proceedings of the 9th annual conference on Genetic and evolutionary computation,2007, pp. 1066-1073.
[105]K. Ayari, S. Bouktif, and G. Antoniol, "Automatic mutation test input data generation via ant colony," in Proceedings of the 9th Genetic and Evolutionary Computation Conference,2007, pp.1074-1081.
[106]G. Rothermel, R. Untch, C. Chu, and M. Harrold, "Prioritizing test cases for regression testing," ACM Transactions on Software Engineering and Method-ology, vol.27, no.10, pp.929-948,2001.
[107]T. Stutzle and H. Hoos, "Max-min ant system," Future Generation Computer Systems, vol.16, no.8, pp.889-914,2000.
[108]M. Dorigo and L. Gambardella, "Ant colony system:A cooperative learning approach to the traveling salesman problem," IEEE Transactions on Evolu-tionary Computation, vol.1, no.1, pp.53-66,1997.
[109]D. Merkle, M. Middendorf, and H. Schmeck, "Ant colony optimization for resource-constrainted project scheduling," IEEE Transactions on Evoluionary Computation, vol.6, no.4, pp.333-346,2002.
[110]T. Chen and M. Lau, "A new heuristic for test suite reduction," Information and Software Technology, vol.4, pp.347-354,1998.
[111]M. Harrold, R. Gupta, and M. Soffa, "A methodology for controlling the size of a test suite," ACM Transactions on Software Engineering and Methodology, vol.2, no.3, pp.270-285,1993.
[112]M. Nashat and E. Khalid, "Simulated annealing and genetic algorithms for optimal regression testing," Journal of Software Maintenance:Research and Practice, vol.11, no.1, pp.19-34,1999.
[113]S. Tallam and N. Gupta, "A concept analysis inspired greedy algorithm for test suite minimization," in Proceedings of the 6th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering,2005, pp. 35-42.
[114]D. Jeffrey and X. Gupta, "Improving fault detection capability by selectively retaining test cases during test suite reduction," IEEE Transactions on Soft-ware Engineering, vol.33, no.2, pp.108-123,2007.
[115]J. Black, E. Melachrinoudis, and D. Kaeli, "Bi-criteria models for all-uses test suite reduction," in Proceedings of the 26th International Conference on Software Engineering,2004. pp.106-115.
[116]H. Hsu and A. Orso, "Mints:A general framework and tool for supporting test-suite minimization," in Proceedings of the 31st International Conference on Software Engineering.2009, pp.419-429.
[117]W. Wong, J. Horgan, S. London, and A. Mathur, "Effect of test set mini-mization on fault detection effectiveness," Software Practice and Experience, vol.28, no.4, pp.347-369,1998.
[118]H. Do, S. Elbaum, and G. Rothermel, "Supporting controlled experimentation with testing techniques:An infrastructure and its potential impact," Empirical Software Engineering, vol.10, no.4, pp.405-435,2005.
[119]G. Rothermel and M. Harrold, "A safe, efficient regression test selection tech-nique," A CM Transactions on Software Engineering and Methodology, vol.6, no.2, pp.173-210,1997.
[120]M. Harrold, J. Jones, T. Li, D. Liang, M. P. A. Orso, S. Sinha, and S. Spoon, "Regression test selection for Java software," in Proceedings of ACM Confer-ence on Object-Oriented Programming, System, Languages, and Applications, 2001, pp.312-326.
[121]A. Orso, N. Shi, and M. Harrold, "Scaling regression testing to large software systems," in Proceedings of the 12th ACM SIGSOFT Internatinal Symposium on Foundations of Software Engineering,2004, pp.241-251.
[122]G. Xu and A. Rountev:, "Regression test selection for aspectj software," in Proceedings of 29th International Conference on Software Engineering,2007, pp.65-74.
[123]S. Yoo and M. Harman, "Pareto efficient multi-objective test case selection," in Proceedings of the Symposium on Software Testing and Analysis,2007, pp. 140-150.
[124]G. Rothermel, R. Untch, C. Chu, and M. Harrold, "Prioritizing test cases for regression testing," IEEE Transaction on Software Engineering, vol.27, no.10, pp.929-948,2001.
[125]S. Elbaum, A. Malishevsky, and G. Rothermel, "Test case prioritization: A family of empirical studies," IEEE Transaction on Software Engineering, vol.28, no.2, pp.159-182,2002.
[126]S. Yoo, M. Harman, P. Tonella, and A. Susi, "Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge," in Pro-ceedings of the Eighteenth International Symposium on Software Testing and Analysis,2009, pp.201-212.
[127]L. Zhang, S. Hou, C. Guo, T. Xie, and H. Mei, "Time-aware test-case prior-itization using integer linear programming," in Proceedings of the Eighteenth International Symposium on Software Testing and Analysis.2009, pp.213 224.
[128]K. Walcott, M. Soffa, G. Kapfhammer, and R. Roos, "Timeaware test suite prioritization," in Proceedings of the Symposium on Software Testing and Anal-ysis,2006, pp.1-12.
[129]S. Yoo and M. Harman, "Regression testing minimization, selection and pri-oritization:a survey," Software Testing, Verification and Reliability,2010, to Appear.
[130]R. Santelices, P. Chittimalli, T. Apiwattanapong, A. Orso, and M. Harrold, "Test-suite augmentation for evolving software," in Proceedings of 23rd Inter-national Conference on Automated Software Engineering,2008, pp.218-227.
[131]Z. Xu, Y. Kim, M. Kim, G. Rothermel, and M. Cohen, "Directed test suite augmentation:Techniques and tradeoffs," in Proceedings of the 18th Interna-tional Symposium on Foundations of software engineering,2010, pp.257-266.
[132]D. Qi, A. Roychoudhury, and Z. Liang, "Test generation to expose changes in evolving programs," in Proceedings of the 24th International Conference on Automated Software Engineering,2010, pp.397-406.
[133]S. Sprenkle, S. Sampath, E. Gibson, L. Pollock, and A. Souter, "An empirical comparison of test suite reduction techniques for user-session-based testing of web applications,"in Proceedings of the 21st IEEE International Conference on Software Maintenance,2005, pp.587-596.
[134]X. Zhang, Q. Gu, X. Chen, J. Qi, and D. Chen, "A study of relative re-dundancy in test-suite reduction while retaining or even improving fault-localization," in Proceedings of the 25th Symposium On Applied Computing, 2010, pp.2229-2236.
[135]J. Horgan and S. London, "Data flow coverage and the c language," in Pro-ceedings of the Symposium on Testing, Analysis and Verification,1991, pp. 87-97.
[136]J. Jones and M. Harrold, "Test-suite reduction and prioritization for modified condition/decision coverage," IEEE Transactions on Software Engineering, vol.29, no.3, pp.195209,2003.
[137]B. Vaysburg, L. Tahat, and B. Korel, "Dependence analysis in reduction of requirement based test suites," in Proceedings of the 3rd International Sym-posium on Software Testing and Analysis,2002, pp.107-111.
[138]M. Harder, J. Mellen, and M. Ernst, "Improving test suites via operational abstraction," in Proceedings of the 25th International Conference on Software Engineering,2003, pp.60-71.
[139]M. Martina and A. Bertolino, "Using spanning sets for coverage testing," IEEE Transactions on Software Engineering, vol.29, no.11, pp.974-984,2003.
[140]M. Heimdahl and D. George, "Test-suite reduction for model based tests: Effects on test quality and implications for testing," in Proceedings of 19th International Conference on Automated Software Engineering,2004, pp.176-185.
[141]Z. Chen, B. Xu, X. Zhang, and C. Nie, "A novel approach for test suite reduction based on requirement relation contraction," in Proceedings of the 2008 ACM Symposium on Applied Computing,2008, pp.390-394.