Using Static Information of Programs to Partition the Input Domain in Search-based Test Data Generation
Subject Areas : IT StrategyAtieh Monemi Bidgoli 1 , Hassan haghighi 2 *
1 - Shahid Beheshti University
2 - Shahid Beheshti
Keywords: search-based software testing, , test data generation, , ant colony optimization, , input space partitioning,
Abstract :
The quality of test data has an important effect on the fault-revealing ability of software testing. Search-based test data generation reformulates testing goals as fitness functions, thus, test data generation can be automated by meta-heuristic algorithms. Meta-heuristic algorithms search the domain of input variables in order to find input data that cover the targets. The domain of input variables is very large, even for simple programs, while this size has a major influence on the efficiency and effectiveness of all search-based methods. Despite the large volume of works on search-based test data generation, the literature contains few approaches that concern the impact of search space reduction. In order to partition the input domain, this study defines a relationship between the structure of the program and the input domain. Based on this relationship, we propose a method for partitioning the input domain. Then, to search in the partitioned search space, we select ant colony optimization as one of the important and prosperous meta-heuristic algorithms. To evaluate the performance of the proposed approach in comparison with the previous work, we selected a number of different benchmark programs. The experimental results show that our approach has 14.40% better average coverage versus the competitive approach
[1] P. McMinn, M. Harman, K. Lakhotia, Y. Hassoun, and J. Wegener, “Input domain reduction through irrelevant variable removal and its effect on local, global, and hybrid search-based structural test data generation,” IEEE Trans. Softw. Eng., vol. 38, no. 2, pp. 453–477, 2012, doi: 10.1109/TSE.2011.18.
[2] C. Mao, L. Xiao, X. Yu, and J. Chen, “Adapting ant colony optimization to generate test data for software structural testing $,” Swarm Evol. Comput., vol. 20, pp. 23–36, 2014, doi: 10.1016/j.swevo.2014.10.003.
[3] S. Anand et al., “An Orchestrated Survey on Automated Software Test Case Generation,” J. Syst. Softw., vol. 86, no. 8, pp. 1978–2001, 2013, doi: 10.1016/j.jss.2013.02.061.
[4] S. Ali, L. C. Briand, H. Hemmati, and R. K. Panesar-Walawege, “A Systematic Review of the Application and Empirical Investigation of Evolutionary Testing,” IEEE Trans. Softw. Eng., vol. 36, no. 6, pp. 742–762, 2010, doi: http://doi.ieeecomputersociety.org/10.1109/TSE.2009.52.
[5] P. Ammann and J. Offutt, Introduction to software testing. Cambridge University Press, 2016.
[6] M. Weiser, “Program Slicing,” IEEE Trans. Softw. Eng., vol. SE-10, no. 4, pp. 352–357, 1984, doi: 10.1109/TSE.1984.5010248. [7] B. F. Jones, H. H. Sthamer, and D. E. Eyres, “Automatic structural testing using genetic algorithms,” Softw. Eng. J., vol. 11, pp. 299–306, 1996.
[8] R. Pargas, M. J. Harrold, and R. Peck, “Test-Data Generation Using Genetic Algorithms,” J. Softw. Testing, Verif. Reliab., vol. 9, pp. 263–282, 1999.
[9] P. Mcminn, “Search-Based Software Testing : Past , Present and Future,” pp. 153–163, 2011, doi: 10.1109/ICSTW.2011.100.
[10] M. Harman and P. McMinn, “A theoretical and empirical study of search-based testing: Local, global, and hybrid search,” IEEE Trans. Softw. Eng., vol. 36, no. 2, pp. 226–247, 2010, doi: 10.1109/TSE.2009.71.
[11] G. Fraser and A. Arcuri, “Whole test suite generation,” IEEE Trans. Softw. Eng., vol. 39, no. 2, pp. 276–291, 2013, doi: 10.1109/TSE.2012.14.
[12] N. Tracey, “An Automated Framework for Structural Test-Data Generation 2 Optimisation-Based Struc- tural Test-Data Generation 1 Introduction,” 1904.
[13] M. B. Cohen, C. J. Colbourn, and A. C. H. Ling, “Augmenting simulated annealing to build interaction test suites,” Proc. - Int. Symp. Softw. Reliab. Eng. ISSRE, vol. 2003-Janua, pp. 394–405, 2003, doi: 10.1109/ISSRE.2003.1251061.
[14] E. Elbeltagi, T. Hegazy, and D. Grierson, “Comparison among five evolutionary-based optimization algorithms,” Adv. Eng. Informatics, vol. 19, no. 1, pp. 43–53, 2005, doi: 10.1016/j.aei.2005.01.004.
[15] K. Socha and M. Dorigo, “Ant colony optimization for continuous domains,” Eur. J. Oper. Res., vol. 185, no. 3, pp. 1155–1173, 2008, doi: 10.1016/j.ejor.2006.06.046.
[16] C. Simons and J. Smith, “A comparison of evolutionary algorithms and ant colony optimization for interactive software design,” 2012.
[17] B. Suri and P. Jajoria, “Using ant colony optimization in software development project scheduling,” in 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2013, pp. 2101–2106.
[18] J. T. de Souza, C. L. B. Maia, T. do Nascimento Ferreira, R. A. F. Do Carmo, and M. M. A. Brasil, “An ant colony optimization approach to the software release planning with dependent requirements,” in International symposium on search based software engineering, 2011, pp. 142–157.
[19] D. Azar and J. Vybihal, “An ant colony optimization algorithm to improve software quality prediction models: Case of class stability,” Inf. Softw. Technol., vol. 53, no. 4, pp. 388–393, 2011.
[20] B. Suri, “Literature Survey of Ant Colony Optimization in Software Testing,” 2010.
[21] H. Li, “An Ant Colony Optimization Approach to Test Sequence Generation for State-Based Software Testing,” no. 1, pp. 255–262, 2005.
[22] P. R. Srivastava and K. Baby, “Automated Software Testing Using Metahurestic Technique Based on an Ant Colony Optimization,” Electron. Syst. Des. (ISED), 2010 Int. Symp., 2010, doi: 10.1109/ISED.2010.52.
[23] A. Bouchachia, R. Mittermeir, P. Sielecky, S. Stafiej, and M. Zieminski, “Nature-inspired techniques for conformance testing of object-oriented software,” Appl. Soft Comput. J., vol. 10, no. 3, pp. 730–745, 2010, doi: 10.1016/j.asoc.2009.09.003.
[24] K. Li, Z. Zhang, and W. Liu, “Automatic Test Data Generation Based on Ant Colony Optimization,” 2009 Fifth Int. Conf. Nat. Comput., vol. 6, pp. 216–220, 2009, doi: 10.1109/ICNC.2009.239.
[25] H. Sharifipour, M. Shakeri, and H. Haghighi, “Structural test data generation using a memetic ant colony optimization based on evolution strategies,” Swarm Evol. Comput., vol. 40, pp. 76–91, 2018, doi: 10.1016/j.swevo.2017.12.009.
[26] A. M. Bidgoli and H. Haghighi, “Augmenting ant colony optimization with adaptive random testing to cover prime paths,” J. Syst. Softw., vol. 161, p. 110495, 2020.
[27] A. Monemi Bidgoli, H. Haghighi, T. Zohdi Nasab, and H. Sabouri, Using Swarm Intelligence to Generate Test Data for Covering Prime Paths, vol. 10522 LNCS. 2017.
[28] X. Lv, S. Huang, and H. Ji, “Input Domain Reduction of Search-based Structural Test Data Generation using Interval Arithmetic.,” Int. J. Performability Eng., vol. 14, no. 6, 2018.
[29] M. Harman, Y. Hassoun, K. Lakhotia, P. McMinn, and J. Wegener, “The impact of input domain reduction on search-based test data generation,” Proc. 6th Jt. Meet. Eur. Softw. Eng. Conf. ACM SIGSOFT Symp. Found. Softw. Eng., pp. 155–164, 2007, doi: 10.1145/1287624.1287647.
[30] C. Cadar and M. Nowack, “KLEE symbolic execution engine in 2019.”
[31] M. Dorigo and L. M. Gambardella, “Ant colonies for the travelling salesman problem,” BioSystems, vol. 43, no. 2, pp. 73–81, 1997, doi: 10.1016/S0303-2647(97)01708-5.
[32] V. Maniezzo, “Ant System: Optimization by a Colony of Cooperating Agents,” vol. 26, no. 1, pp. 1–13, 1996.
[33] H. Coles, T. Laurent, C. Henard, M. Papadakis, and A. Ventresque, “PIT: A practical mutation testing tool for Java (Demo),” ISSTA 2016 - Proc. 25th Int. Symp. Softw. Test. Anal., pp. 449–452, 2016, doi: 10.1145/2931037.2948707.
[34] R Developement Core Team, “R: A Language and Environment for Statistical Computing,” R Found. Stat. Comput., vol. 1, p. 409, 2015, doi: 10.1007/978-3-540-74686-7.