A Novel Regression Test Selection Method with Graph-Based Genetic Algorithm

Öz

Regression testing is a re-running test to ensure that previously developed and tested software is not affected by changes. Testing a software after changes is important and necessary in order to maintain the software development and maintenance processes. However, repeating all tests after each change is not feasible especially in large-scale projects. Regression test selection which means selecting a subset of tests has emerged as a solution to this issue. This paper presents a GBGA (graph-based genetic algorithm) with the most compatible neighbor crossover as a solution to the regression test selection problem. In this GBGA, each individual in the population is located on a node of predefined graph structure and the probabilities of the crossover are limited depending on the neighborhood relations to increase population diversity, prevent premature convergence, and refine the convergence performance. This GBGA is applied to this problem to find the minimum set of test cases to enhance the performance of the GA by locating populations on graphs and limiting the crossover option with neighborhood connections to increase the diversity. The results show that the proposed GBGA with the most compatible neighbor crossover has superior performance in terms of fitness value when compared to genetic algorithm.

Anahtar Kelimeler

• Regression test selection
• graph-based genetic algorithm
• compatible crossover
• optimization

Kaynakça

1. Aggrawal, K. K., Singh, Y., & Kaur, A. (2004). Code coverage based technique for prioritizing test cases for regression testing. In Proceedings of ACM SIGSOFT Software Engineering Notes. Akhin, M., & Itsykson, V. (2009). A regression test selection technique based on incremental dynamic analysis. In Proceedings of Software Engineering Conference in Russia CEE-SECR. Briand, L. C., Labiche, Y., & He, S. (2009). Automating regression test selection based on UML designs. Information and Software Technology, 51, 16–30.
2. Bryden, Kenneth M., Ashlock, D. A., McCorkle, D. S., & Urban, G. L. (2003). Optimization of heat transfer utilizing graph based evolutionary algorithms. International Journal of Heat and Fluid Flow, 24(2), 267–277.
3. Bryden, Kenneth Mark, Ashlock, D. A., Corns, S., & Willson, S. J. (2006). Graph-Based Evolutionary Algorithms. 10(5), 550–567.
4. Chittimalli, P. K., & Harrold, M. J. (2008). Regression Test Selection on System Requirements. In Proceedings of the 1st India Software Engineering Conference,87–96.
5. Cobb, H. G., & Grefenstette, J. J. (1993). Genetic Algorithms for Tracking Changing Environments. In Proceedings of the 5th International Conference on Genetic Algorithms 523–530.
6. De, K. (1988). Learning with Genetic Algorithms : An Overview. 121–138.
7. Doerr, B., Klein, C., & Storch, T. (2007). Faster evolutionary algorithms by superior graph representation. In Proceedings of the 2007 IEEE Symposium on Foundations of Computational Intelligence, FOCI, 245–250.
8. Engström, E., Runeson, P., & Ljung, A. (2011). Improving regression testing transparency and efficiency with history-based prioritization - An industrial case study. In Proceedings of the 4th IEEE International Conference on Software Testing, Verification, and Validation, ICST.

9. Engström, E., Runeson, P., & Skoglund, M. (2010). A systematic review on regression test selection techniques. Information and Software Technology, 52(1), 14–30.
10. Farooq, Q., Iqbal, M. Z. Z., Malik, Z. I., & Nadeem, A. (2007). An approach for selective state machine based regression testing. In Proceedings of the 3rd International Workshop on Advances in ModelBased Testing - A-MOST, 44–52.
11. Garousi, V., Özkan, R., & Betin-Can, A. (2018). Multiobjective regression test selection in practice: An empirical study in the defense software industry. Information and Software Technology, 103.
12. Ghoumari, A., & Nakib, A. (2019). Graph based adaptive evolutionary algorithm for continuous optimization. September. http://arxiv.org/abs/1908.08014
13. Gorthi, R. P., Pasala, A., Chanduka, K. K., & Leong, B. (2008). Specification-based approach to select regression test suite to validate changed software. Neonatal, Paediatric and Child Health Nursing, 153–160.
14. Gotshall, S., & Rylander, B. (2000). Optimal population size and the genetic algorithm. In Proceedings On Genetic And Evolutionary Computation Conference, 1–5.
15. Graves, T. L., Harrold, M. J., Kim, J. M., Porter, A., & Rothermel, G. (2001). An empirical study of regression test selection techniques. ACM Transactions on Software Engineering and Methodology, 10(2), 184–208. Gu, Q., Tang, B., & Chen, D. (2010). Optimal Regression Testing based on Selective Coverage of Test Requirements. In Proceedings of International Symposium on Parallel and Distributed Processing with Applications, ISPA.
16. Gupta, R., Harrold, M. J., & Soffa, M. L. (1992). An approach to regression testing using slicing. Software Maintenance, 1992.
17. Harman, M. (2011). Making the case for MORTO: Multi objective regression test optimization. In Proceedings of 4th IEEE International Conference on Software Testing, Verification, and Validation Workshops, ICSTW, 111–114.
18. Jones, J. a., & Harrold, M. J. (2001). Test-suite reduction and prioritization for modified condition/decision coverage. In Proceedings of IEEE International Conference on Software Maintenance, ICSM, 92– 103. Korkmaz, E. E., & Üçoluk, G. (2004). A controlled genetic programming approach for the deceptive domain. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 34(4), 1730–1742.
19. Koza, J. R., & Stanford, K. E. (1990). Genetic Programming: A Paradigm For Genetically Breeding Populations Of Computer Programs To Solve Problems.
20. Krishnamoorthi, R., & Sahaaya Arul Mary, S. A. (2009). Factor Oriented Requirement Coverage Based System Test Case Prioritization of New and Regression Test Cases. Informaton and Software Technology, 51, 799–808.
21. Lee, Z. J., Su, S. F., Chuang, C. C., & Liu, K. H. (2008). Genetic algorithm with ant colony optimization (GAACO) for multiple sequence alignment. Applied Soft Computing Journal, 8(1), 55–78. Li, Z., Harman, M., & Hierons, R. M. (2007). Search algorithms for regression test case prioritization. IEEE Transactions on Software Engineering, 33(4), 225–237.
22. Lu, J., Fang, N., Shao, D., & Liu, C. (2007). An improved immune-genetic algorithm for the traveling salesman problem. In Proceedings of International Conference on Natural Computation, ICNC, 297–301.
23. Miller, G. F. . T. P. M. (n.d.). Designing Neural Networks using Genetic Algorithms.
24. Mirarab, S., Akhlaghi, S., & Tahvildari, L. (2012). Sizeconstrained regression test case selection using multicriteria optimization. IEEE Transactions on Software Engineering, 38(4), 936–956. Mirjalili, S. (2019). Evolutionary Algorithms and Neural Networks. Springer, Cham.
25. Mittal, S., & Sangwan, O. P. (2018). Prioritizing test cases for regression techniques using metaheuristic techniques. Journal of Information and Optimization Sciences, 39(1), 39–51.
26. Özkan, R. (2017). Multi-Objective Regression Test Selection in Practice: An Industrial Case Study. METU.
27. Panichella, A., Oliveto, R., Di Penta, M., & De Lucia, A. (2015). Improving multi-objective test case selection by injecting diversity in genetic algorithms. IEEE Transactions on Software Engineering, 41(4), 358– 383.
28. Rothermel, G. (1996). ERothermel, G. (1996). Efficient, Effective Regression Testing Using Safe Test Selection Techniques. Clemson University.fficient, Effective Regression Testing Using Safe Test Selection Techniques.
29. Rothermel, G., & Harrold, M. J. (1997). A safe, efficient regression test selection technique. ACM Transactions on Software Engineering and Methodology, 6(2), 173–210. Samuel, W. S. Y. (2008). A Graph Based Evolutionary Algorithm. In Thesis (Issue July).
30. Srikanth, H., Hettiarachchi, C., & Do, H. (2016). Requirements Based Test Prioritization Using Risk Factors. Informaton and Software Technology, 69, 71–83.
31. Syswerda, G. (1991). A Study of Reproduction in Generational and Steady-State Genetic Algorithms. Foundations of Genetic Algorithms, 1, 94–101.
32. Toffolo, A., & Benini, E. (2003). Genetic diversity as an objective in multi-objective evolutionary algorithms. Evolutionary Computation, 11(2).
33. Toroidal graph. (2021). In Wikipedia.
34. Vokolos, F. I., & Frankl, P. G. (1998). Empirical Evaluation of the Textual Differencing Regression Testing Technique Outsource Laboratories. In Proceedings of ACM Sigsoft International Conference on Software Testing and Analysis, ISSTA, 44–53.
35. Whitley, D., Rana, S., & Heckendorn, R. B. (1999). The island model genetic algorithm: On separability, population size and convergence. In Journal of Computing and Information Technology, 7(1), 33– 47.
36. Yadav, D. K., & Dutta, S. (2017). Regression test case prioritization technique using genetic algorithm. Advances in Intelligent Systems and Computing, 509, 133–140.
37. Yamuç, A., Cingiz, M. Ö., Biricik, G., & Kalipsiz, O. (2017). Solving test suite reduction problem using greedy and genetic algorithms. In Proceedings of International Conference on Electronics, Computers and Artificial Intelligence, ECAI, 1–5.