IEEE Transactions on Reliability 70 (2): 654-675 (2021)

Beating Random Test Case Prioritization 1

Zhi Quan Zhou 2 , Chen Liu 3 , Tsong Yueh Chen 4 , T.H. Tse 5 , and Willy Susilo 3

[paper from IEEE Xplore | technical report TR-2020-04]


Existing test case prioritization (TCP) techniques have limitations when applied to real-world projects, because these techniques require certain information to be made available before they can be applied. For example, the family of input-based TCP techniques are based on test case values or test script strings; other techniques use test coverage, test history, program structure, or requirements information. Existing techniques also cannot guarantee to always be more effective than random prioritization (RP) that does not have any precondition. As a result, RP remains the most applicable and most fundamental TCP technique. This paper proposes an extremely simple, effective, and efficient way to prioritize test cases through the introduction of a dispersity metric. Our technique is as applicable as RP. We conduct empirical studies using 43 different versions of 15 real-world projects. Empirical results show that our technique is more effective than RP. Our algorithm has a linear computational complexity and, therefore, provides a practical solution to the problem of prioritizing very large test suites (such as those containing hundreds of thousands, or millions, of test cases), where the execution time of conventional nonlinear prioritization algorithms can be prohibitive. Our technique also provides a practical solution to TCP when neither input-based nor execution-based techniques are applicable due to lack of information.

Index Terms: Dispersity, dispersity metric, dispersity-based prioritization, dissimilarity, random prioritization, natural distance, adaptive random testing, adaptive random sequence

1. This work was supported in part by a linkage grant of the Australian Research Council (Project ID: LP160101691), an Australian Government Research Training Program scholarship, the General Research Fund of the Research Grants Council of Hong Kong (project number 716612), and a Western River entrepreneurship grant. We wish to thank Morphick Solutions Pty Ltd, Australia, for supporting this research.
2. (Corresponding author.)
School of Computer Science and Software Engineering, University of Wollongong, Wollongong, NSW 2522, Australia.
3. School of Computer Science and Software Engineering, University of Wollongong, Wollongong, NSW 2522, Australia.
4. Department of Computer Science and Software Engineering, Swinburne University of Technology, Hawthorn, VIC 3122, Australia.
5. Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong.


  Cumulative visitor count