Abstract

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.

Introduction

     It is a fact, nowadays, that the question of software reliability is extremely relevant, given the dependence society has on software systems. Quality of all such produced software systems must be ensured, and hence Verification & Validation (V&V) activities play a major role to be employed to achieve this goal [2]. Moreover, software testing is the most used V&V activity in practice [3], [4]. The goal of any software testing effort is to find defects1 in the software product, in this case very related to defects (faults) in the source code.

     Testing activity ensures the conformity of the software product with the requirements defined by the customer, through a systematic execution. However, in order to entirely achieve this goal, the ideal approach is to exhaustively test the software, which is impractical. In order to cope up with this impracticality, techniques are designed to use only a small subset of the input domain, but with a high probability of revealing the presence of defects, if they exist [3]. Therefore, it is essential to adopt a consolidated methodology that makes the test activity viable and effective. Some approaches have already been proposed [5], such as Test Case Selection (TCS), which selects a subset of the test cases for execution according to a specific objective; Test Suite Reduction (TSR), which reduces the size of the test suite; and Test Case Prioritization (TCP), which prioritizes test cases to be executed. The differential of TCP concerning TSR and TCS is that TCP uses the entire test suite. Every single test case will be considered in prioritization, thus reducing the risk of omitting some type of defect. As the main interest of this study is TCP, the paper will focus on its approaches.

Conclusions

     In this paper, we have reported the results of an SLR on TCP using Markov Chains. From the defined search string, a total of 468 studies obtained from five databases were returned (IEEEXplore, ACM, ScienceDirect, SpringerLink, and Scopus), of which only 12 persisted until the last selection step. For this study, 3 research questions were defined, whose objective is not only to clarify the technologies and methodologies involved in the application of Markov Chains and the prioritization of test cases but also to understand how research related to this field is being distributed and studied by the around the world.

     The main objective of this work was to investigate all the approaches and applications related to this topic, so that, based on the correlations between the studies found, we could trace possible future directions regarding this topic. Our motivation for this was the fact that Test Case Prioritization is a profitable field from the point of view of the entire software development cycle, as its application can be useful in many ways, such as saving time and budget since the goal is to optimize the process of software testing, which often consumes a good deal of effort on the part of the development team.