Large-Scale Test Case Prioritization using Viterbi Algorithm

doi:10.23940/ijpe.20.12.p8.19211932

Abstract

Abstract: Test case prioritization is an effective way to improve test efficiency and to reduce test costs. To deal with the problem that the application of group intelligent searching algorithm in large-scale test case prioritization causes slow convergence rate and premature convergence, leading to unstable error detection ability, in this paper, we propose a novel approach for large-scale test case prioritization based on the Viterbi algorithm. Specifically, we first use the sequential grid search idea of the Viterbi algorithm to encode the test case set in the priority ranking model of multi-objective test cases to form the state space of sequential grid search. Then, the code coverage and the effective execution time of test cases are taken as the path measurement of state transition. Finally, the path with the largest path metric is selected as the survival path to complete the priority ranking of test cases. Experimental results show that the algorithm has a higher convergence speed and higher defect detection rate.

Key words: large-scale test case prioritization, viterbi algorithm, surviving path, code coverage, effective execution time

Tingting Huo, Yan Zhang, Chunyan Xia, Zijiang Yang, Weisong Sun. Large-Scale Test Case Prioritization using Viterbi Algorithm [J]. Int J Performability Eng, 2020, 16(12): 1921-1932.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

1. W. E. Wong, X. L. Li,P. A. Laplante, “Be More Familiar with Our Enemies and Pave the Way Forward: A Review of the Roles Bugs Played in Software Failures,”Journal of Systems and Software, Vol. 133, pp. 68-94, 2017
2. M. Bohme, A. Roychoudhury,B. C. D.S. O liveira, “Regression Testing of Evolving Problems,” Advances in Computers, Vol. 89, No. 2, pp. 53-88, 2013
3. M. K. Ramanathan, M. Koyuturk, A. Grama,S. Jagannathan, “Phalanx: A Graph-Theoretic Framework for Test Case Prioritization,” inProceedings of the 2008 ACM Symposium on Applied Computings (SAC 2005), pp. 667-673, Fortaleza, Ceara Brazil, 2008
4. G. Rothermel, R. H. Untch, C. Chu,M. J. Harrold, “Prioritization Test Cases for Regression Testing,” IEEE Transactions on Software Engineering, Vol. 27, No. 10, pp. 929-948, 2001
5. G. Y.Chen and J. Rogers, “Arranging Software Test Cases Through an Optimization Method,” inProceeding of Portland International Conference on Management of Engineering and Technology (PICMET), pp. 1-5, Phuket, Thailand, 2010
6. Y. Singh, A. Kaur,B. Suri, “Test Case Prioritization using Antcolony Optimization,” ACM Sigsoft Software Engineering Notes, Vol. 35, No. 4, pp. 1-7, 2010
7. H. Srikanth, M. B. Cohen,X. Qu, “Reducing Field Failures in System Configurable Software: Cost-based Prioritization,” inProceedings of 2009 20th International Symposium on Software Reliability Engineering, pp. 61-70, Mysuru, Karnataka, India, 2009
8. R. Krishnamoorthi and S. A. Mary, “Regression Test Suite Prioritization using Genetic Algorithms,”International Journal of Hybrid Information Technology, No. 3, pp. 35-52, 2009
9. J. -M. Kim and A. Porter, “A History-based Test Prioritization Technique for Regression Testing in Resource Constrained Environments,” inProceedings of the 24th International Conference on Software Engineering, pp. 119-129, Orlando, Florida, USA, 2002
10. S. Yoo and M. Harman, “Pareto Efficient Multi-Objective Test Case Selection,” inProceedings of the 2007 International Symposium on Software Testing and Analysis, pp. 140-150, London, United Kingdom, 2007
11. K. R. Walcott, M. L. Soffa, G. M. Kapfhammer,R. S. Roos, “Time Aware Test Suite Prioritization,” inProceedings of the 2006 International Symposium on Software Testing and Analysis, pp. 1-12, Portland Maine , USA, 2006
12. Y. Bian, F. Yuan, J. -X. Guo, Z. Li, and R. -L. Zhao, “CPU + GPU Heterogeneous Computing Orientated Multi-Objective Test Case Prioritization,” Vol. 27, pp. 943-954, 2016
13. C. GU, Z. Li,R. Zhao, “ACO based Test Case Prioritization and Impact Analysis of Parameters,” Journal of Frontiers of Computer Science and Technology, Vol. 8, No. 12, pp. 1463-1473, 2014
14. H. M. Wang, J. Z. Li, Y. Xing,X. G. Zhou, “Multi-Objective Test Case Prioritization based on Multi-Population Cooperative Particle Swarm Optimization,” The Journal of China Universities of Posts and Telecommunications, Vol. 27, No. 1, pp. 42-54, 2020
15. X. Hu and R. C. Eberhart, “Multi Objective Optimization using Dynamic Neighborhood Particle Swarm Optimization,” inProceedings of the 2002 Congress on Evolutionary Computation, pp. 1667-1681, Honolulu, HI, USA, 2002
16. X. Li, “Better Spread and Convergence: Particle Swarm Multi-Objective Optimization using the Maximum Fitness Function,”Genetic and Evolutionary Computation - GECCO 2004, Vol. 3102, pp. 117-128, 2004
17. U. K.Wickramasinghe and X. Li, “Integrating User Preferences with Particle Swarms for Multi-Objective Optimization,” inProceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 745-752, Atlanta GA, USA, 2008
18. W. Peng and Q. Zhang, “Decomposition-based Multi-Objective Particle Swarm Optimization Algorithm for Continuous Optimization Algorithm Problems,” inProceedings of 2008 IEEE International Conference on Granular Computing, pp. 534-537, Hangzhou, China, 2008
19. A. J. Viterbi, “Viterbi Algorithm,” Wiley Online Library, 2003
20. W. E. Wong, J. R. Horgan, S. London,A. P. Mathur, “Effect of Test Set Minimization on Fault Detection Effectiveness,” Software Practice and Experience, Vol. 28, No. 4, pp. 347-369, 1998
21. W. E. Wong, J. R. Horgan, S. London,A. P. Mathur, “Effect of Test Set Size and Block Coverage on Fault Detection Effectiveness,” inProceedings of the 5th IEEE International Symposium on Software Reliability Engineering, pp. 230-238, Monterey, California, USA, November 1994
22. S. Yoo, M. Harmen,D. Clark, “Fault Localization Prioritization: Comparing Information-Theoretic and Coverage-based Approaches,” ACM Transactions on Software Engineering and Methodology, Vol. 22, No. 3, 2013
23. S. Mirarab and L. Tahvildari, “A Prioritization Approach for Software Test Cases based on Bayesian Networks,” inFundamental Approaches to Software Engineering, pp. 276-290, Braga, Portugal, 2007
24. R. Carlson, H. Do,A. Denton, “A Clustering Approach to Improving Test Case Prioritization: An Industrial Case Study,” (Available: https://http://cs.ndsu.edu/～hdo/pdf files/icsm11.pdf
25. S. Yoo, M. Harman, P. Tonella,A. Susi, “Clustering Test Cases to Achieve Effective and Scalable Prioritisation Incorporating Expert Knowledge,” inProceedings of the Eighteenth International Symposium on Software Testing and Analysis, pp. 201-212, New York, USA, 2009
26. Y. Huang, K. Peng,C. Huang, “A History-based Cost-Cognizant Test Case Prioritization Technique in Regression Testing,” Journal of Systems and Software, Vol. 85, No. 3, pp. 626-637, 2012

[1]	Chen-Hua Lee and Chin-Yu Huang. Applying Cluster-based Approach to Improve the Effectiveness of Test Suite Reduction [J]. Int J Performability Eng, 2022, 18(1): 1-10.
[2]	Binbin Yu. Communication Protocols for Distributed Wireless Sensor Network based on Viterbi Algorithm [J]. Int J Performability Eng, 2018, 14(11): 2553-2560.