Int J Performability Eng ›› 2020, Vol. 16 ›› Issue (12): 1921-1932.doi: 10.23940/ijpe.20.12.p8.19211932

• Orginal Article • Previous Articles     Next Articles

Large-Scale Test Case Prioritization using Viterbi Algorithm

Tingting Huoa, Yan Zhanga, *, Chunyan Xiaa, Zijiang Yangb, Weisong Sunb   

  1. aSchool of Computer and Information Technology, Mudanjiang Normal University, Mudanjiang, 157012, China;
    bShenzhen Research Institute of Nanjing University, Shenzhen, 518000, China
  • Submitted on ; Revised on ; Accepted on
  • Contact: * Corresponding author. E-mail address:
  • Supported by:
    This study is supported by the Education Department of Heilongjiang Province (No. 1354MSYQN019), Heilongjiang Provincial Natural Science Foundation of China (No. LH2020F038), and Research Foundation of Mudanjiang Normal University (No. YB2020010).

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