AGA: An Accelerated Greedy Additional Algorithm for Test Case Prioritization
- 23 December 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. PP (00985589) , 1
Abstract
In recent years, many test case prioritization (TCP) techniques have been proposed to speed up the process of fault detection. However, little work has taken the efficiency problem of these techniques into account. In this paper, we target the Greedy Additional (GA) algorithm, which has been widely recognized to be effective but less efficient, and try to improve its efficiency while preserving effectiveness. In our Accelerated GA (AGA) algorithm, we use some extra data structures to reduce redundant data accesses in the GA algorithm and thus the time complexity is reduced from O(m2n) to O(kmn) when n > m, where m is the number of test cases, n is the number of program elements, and k is the iteration number. Moreover, we observe the impact of iteration numbers on prioritization efficiency on our dataset and propose to use a specific iteration number in the AGA algorithm to further improve the efficiency. We conducted experiments on 55 open-source subjects. In particular, we implemented each TCP algorithm with two kinds of widely-used input formats, adjacency matrix and adjacency list. Since a TCP algorithm with adjacency matrix is less efficient than the algorithm with adjacency list, the result analysis is mainly conducted based on TCP algorithms with adjacency list. The results show that AGA achieves 5.95X speedup ratio over GA on average, while it achieves the same average effectiveness as GA in terms of Average Percentage of Fault Detected (APFD). Moreover, we conducted an industrial case study on 22 subjects, collected from Baidu, and find that the average speedup ratio of AGA over GA is 44.27X, which indicates the practical usage of AGA in real-world scenarios.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61872008)
This publication has 69 references indexed in Scilit:
- Test case prioritization: a systematic mapping studySoftware Quality Journal, 2012
- Regression testing minimization, selection and prioritization: a surveySoftware Testing, Verification and Reliability, 2012
- Using spanning sets for coverage testingIEEE Transactions on Software Engineering, 2003
- Test-suite reduction and prioritization for modified condition/decision coverageIEEE Transactions on Software Engineering, 2003
- Test case prioritization: a family of empirical studiesIEEE Transactions on Software Engineering, 2002
- Prioritizing test cases for regression testingIEEE Transactions on Software Engineering, 2001
- Software error analysisACM SIGSOFT Software Engineering Notes, 1996
- Computer Solutions of the Traveling Salesman ProblemBell System Technical Journal, 1965
- An Analysis of Variance Test for Normality (Complete Samples)Biometrika, 1965
- On a Test of Whether one of Two Random Variables is Stochastically Larger than the OtherThe Annals of Mathematical Statistics, 1947