A Systematic Literature Review on prioritizing software test cases using Markov chains

Context: Software Testing is a costly activity since the size of the test case set tends to increase as the construction of the software evolves. Test Case Prioritization (TCP) can reduce the effort and cost of software testing. TCP is an activity where a subset of the existing test cases is selected in order to maximize the possibility of finding defects. On the other hand, Markov Chains representing a reactive system, when solved, can present the occupation time of each of their states. The idea is to use such information and associate priority to those test cases that consist of states with the highest probabilities.Objective: The objective of this paper is to conduct a survey to identify and understand key initiatives for using Markov Chains in TCP. Aspects such as approaches, developed techniques, programming languages, analytical and simulation results, and validation tests are investigated.Methods: A Systematic Literature Review (SLR) was conducted considering studies published up to July 2021 from five different databases to answer the three research questions.Results: From SLR, we identified 480 studies addressing Markov Chains in TCP that have been reviewed in order to extract relevant information on a set of research questions.Conclusion: The final 12 studies analyzed use Markov Chains at some stage of test case prioritization in a distinct way, that is, we found that there is no strong relationship between any of the studies, not only on how the technique was used but also in the context of the application. Concerning the fields of application of this subject, 6 forms of approach were found: Controlled Markov Chain, Usage Model, Model-Based Test, Regression Test, Statistical Test, and Random Test. This demonstrates the versatility and robustness of the tool. A large part of the studies developed some prioritization tool, being its validation done in some cases analytically and in others numerically, such as: Measure of the software specification, Optimal Test Transition Probabilities, Adaptive Software Testing, Automatic Prioritization, Ant Colony Optimization, Model Driven approach, and Monte Carlo Random Testing.