Multi-Objective Test Case Selection: A study of the influence of the Catfish effect on PSO based strategies

• Luciano S. de Souza IFNMG / UFPE
• Ricardo B. C. Prudêncio UFPE
• Flavia de A. Barros UFPE

DOI: https://doi.org/10.5753/wtf.2014.22943

Resumo

During the software testing process many test suites can be generated in order to evaluate and assure the quality of the products. In some cases, the execution of all suites can not fit the available resources (time, people, etc). Hence, automatic Test Case (TC) selection could be used to reduce the suites based on some selection criterion. This process can be treated as an optimization problem, aiming to find a subset of TCs which optimizes one or more objective functions (i.e., selection criteria). In this light, we developed mechanisms for TC selection in context of structural and functional testing. The proposed algorithms consider two objectives simultaneously: maximize branch coverage (or functional requirements coverage) while minimizing execution cost (time). These mechanisms were implemented by deploying multi-objective techniques based on Particle Swarm Optimization (PSO). Additionally, we added the so-called catfish effect into the multi-objective selection algorithms in order to improve their results. The performed experiments revealed the feasibility of the proposed strategies.

Referências

Aranha, E. and Borba, P. (2008). Using process simulation to assess the test design effort reduction of a model-based testing approach. In ICSP, pages 282–293.

Barltrop, K., Clement, B., Horvath, G., and Lee, C.-Y. (2010). Automated test case selection for flight systems using genetic algorithms. In Proceedings of the AIAA Infotech@Aerospace Conference (I@A 2010). Atlanta, GA.

Borba, P., Cavalcanti, A., Sampaio, A., and Woodcock, J., editors (2010). Testing Techniques in Software Engineering, Second Pernambuco Summer School on Software Engineering, PSSE 2007, Recife, Brazil, December 3-7, 2007, Revised Lectures, volume 6153 of Lecture Notes in Computer Science. Springer.

Chuang, L.-Y., Tsai, S.-W., and Yang, C.-H. (2011). Improved binary particle swarm optimization using catfish effect for feature selection. Expert Syst. Appl., 38(10):12699–12707.

Coello, C., Pulido, G., and Lechuga, M. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3):256–279.

Coello, C. A. C., Lamont, G. B., and van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems, volume 5. Springer.

de Souza, L. S., Miranda, P. B. C., Prudêncio, R. B. C., and Barros, F. d. A. (2011). A multi-objective particle swarm optimization for test case selection based on functional requirements coverage and execution effort. In In Proceedings of the 23rd International Conference on Tools with Artificial Intelligence (ICTAI 2011), Boca Raton, FL, USA.

de Souza, L. S., Prudêncio, R. B., de A. Barros, F., and da S. Aranha, E. H. (2013). Search based constrained test case selection using execution effort. Expert Systems with Applications, 40(12):4887 – 4896.

de Souza, L. S., Prudêncio, R. B. C., and Barros, F. d. A. (2010). A constrained particle swarm optimization approach for test case selection. In In Proceedings of the 22nd International Conference on Software Engineering and Knowledge Engineering (SEKE 2010), Redwood City, CA, USA.

Deb, K. and Kalyanmoy, D. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, 1 edition.

Do, H., Elbaum, S., and Rothermel, G. (2005). Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Softw. Engg., 10(4):405–435.

Eberhart, R. C. and Shi, Y. (1998). Comparison between genetic algorithms and particle swarm optimization. LNCS, 1447:611–616.

Harman, M. (2011). Making the case for morto: Multi objective regression test optimization. In Fourth International IEEE Conference on Software Testing, Verification and Validation, pages 111–114. IEEE Computer Society.

Harold, M. J., Gupta, R., and Soffa, M. L. (1993). A methodology for controlling the size of a test suite. ACM Trans. Softw. Eng. Methodol., 2(3):270–285.

Kaur, A. and Bhatt, D. (2011). Hybrid particle swarm optimization for regression testing. International Journal on Computer Science and Engineering, 3 (5):1815–1824.

Kennedy, J. and Eberhart, R. C. (1995). Particle swarm optimization. In Proceedings of the IEEE International Joint Conference on Neural Networks, pages 1942–1948.

Kennedy, J. and Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm. In Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, pages 4104–4109.

Lin, J.-W. and Huang, C.-Y. (2009). Analysis of test suite reduction with enhanced tiebreaking techniques. Inf. Softw. Technol., 51(4):679–690.

Ma, X.-Y., Sheng, B.-K., and Ye, C.-Q. (2005). Test-suite reduction using genetic algorithm. Lecture Notes in Computer Science, 3756:253–262.

Mansour, N. and El-Fakih, K. (1999). Simulated annealing and genetic algorithms for optimal regression testing. Journal of Software Maintenance, 11(1):19–34.

Nethercote, N. and Seward, J. (2003). Valgrind: A program supervision framework. In In Third Workshop on Runtime Verification (RVï¿1/2 03).

Ramler, R. and Wolfmaier, K. (2006). Economic perspectives in test automation - balancing automated and manual testing with opportunity cost. In Workshop on Automation of Software Test, ICSE 2006.

Santana, R. A., Pontes, M. R., and Bastos-Filho, C. J. A. (2009). A multiple objective particle swarm optimization approach using crowding distance and roulette wheel. In Proceedings of the 2009 Ninth International Conference on Intelligent Systems Design and Applications, ISDA ’09, pages 237–242, Washington, DC, USA. IEEE Computer Society.

Windisch, A., Wappler, S., and Wegener, J. (2007). Applying particle swarm optimization to software testing. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, GECCO ’07, pages 1121–1128, New York, NY, USA. ACM.

Yoo, S. and Harman, M. (2007). Pareto efficient multi-objective test case selection. In Proceedings of the 2007 International Symposium on Software Testing and Analysis, pages 140–150.

Yoo, S. and Harman, M. (2010a). Regression testing minimization, selection and prioritization: a survey. Software Testing, Verification and Reliability, 22(2):67–120.

Yoo, S. and Harman, M. (2010b). Using hybrid algorithm for pareto efficient multi-objective test suite minimisation. J. Syst. Softw., 83:689–701.

Yoo, S., Harman, M., and Ur, S. (2011a). Highly scalable multi objective test suite minimisation using graphics cards. In Proceedings of the Third international conference on Search based software engineering, SSBSE’11, pages 219–236, Berlin, Heidelberg. Springer-Verlag.

Yoo, S., Nilsson, R., and Harman, M. (2011b). Faster fault finding at google using multi objective regression test optimisation. In 8th European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE 11), Szeged, Hungary.

Young, M. and Pezze, M. (2005). Software Testing and Analysis: Process, Principles and Techniques. John Wiley & Sons.