Providing a solution for selecting and prioritizing regression test cases based on genetic approach

Dissertation for Master's Degree in Computer Engineering, Software Orientation

Abstract

Many of the costs of software development, related to frequent tests, are in the phase of software maintenance in evolution and modification; Because making any change in the software code results in a new version, the correctness of which requires the design of new tests as well as re-doing all the previous tests to ensure that the current performance of the software is not adversely affected by the changes. This process is called software regression testing. Due to the limitation of test resources and time, it is not possible to re-execute this large and growing volume of tests in each round of test repetition. One of the most important techniques presented to overcome the problem of the high cost of software regression testing is the selection and prioritization of test items, which means the selection and implementation of the most important test items according to the merit criteria to achieve the test goal faster. The problem of most of the presented selection and prioritization techniques is to ignore the continuity of the regression test execution, the effect of the efficiency of the tests in each repetition of the regression test on the efficiency of the next steps, the difference between the cost of the test and the difficulty of the error, as well as the limitation of time and resources in the real environment of the test execution. In this thesis, a method for selecting and prioritizing test cases based on background and aware of the cost using genetic algorithm based on five criteria of test case error detection efficiency record, previous selection probability, their execution history during multiple regression test executions, test cost and error difficulty is presented, and the effect of resource limitations on test execution is also applied.

In order to quantitatively evaluate the speed of error detection for the proposed method, an implementation was carried out, which was evaluated using It is done from the APFDc metric. The performance of the proposed method has been compared with the background-based method and the random method. The results presented in the thesis indicate an improvement of about 30% in the speed and earlier error detection of the proposed method compared to the compared methods.

Key words: software regression testing, test case selection, test case prioritization, prioritization based on history, cost-aware

Chapter 1: Introduction

1- Objective

In the development and maintenance phase To fix the errors in the software and also to implement the changes made in the program, the software is periodically modified and changes are made in it. After each change in the software, they repeat the current tests to check that the behavior does not affect the unchanged parts and also for revalidation. At the same time, the validation of the changed parts of the software requires the design of a number of new tests each time, so the volume of software tests is constantly increasing. Therefore, this essential phase in the development of a software product, which is carried out to reveal software defects and determine its quality level according to a series of selected characteristics [1], accounts for most of the software development costs (between 30 and 50%). These frequent tests in the maintenance phase of evolving and modifying software, which are performed with each change in the software code, to ensure that the unmodified parts of the code are not adversely affected by the changes, are called software regression testing[1].

Due to the limited time and resources available to the test team in the real world, full testing is often impractical [2,1]. Various methods have been proposed to solve the problem of high cost of regression testing. Among these methods, the three main methods that are based on the reuse of the test pool are: "selective regression test", "test set reduction" and "test case prioritization [2]" [2]. The selective regression testing method uses information about the program, the modified program, and the test cases that are selected for the test subset. Test selection techniques typically use the application's source code to determine which test cases are best to run during the regression testing phase [3]. One of the important goals of choosing test items is to increase the rate of error detection. The test case prioritization method tries to improve software regression testing by arranging the execution of test cases based on a merit criterion so that the most important ones are executed first.One of the main goals [4] in prioritizing test cases is to increase the average of error detection during the test execution as much as possible by implementing test cases that execute a larger number of errors, so that by discovering these errors faster, it is possible to provide faster feedback to the software development group and send it for editing and error correction. With this, we can be sure that in case the test flow is stopped and incomplete anywhere, the most effective tests have been performed and the maximum errors have been discovered. Our goal is to improve these methods.

1-2-Motivation

The selective regression test is used to increase the speed of the test phase, in this method, they select a number from the test set based on the criteria that have been determined in advance. Selective regression testing seeks to minimize the test sequence, which is mostly modification-aware. Test case selection is used only on the current version, but it focuses on the part of the program that has been modified [5].

The problem of prioritizing test cases is actually determining a permutation of all the test cases in the test string, so that this order of execution reveals the maximum possible errors; Therefore, the problem of prioritizing the test cases is actually a search problem, and the references consider this problem and its complexity to be equivalent to the backpack problem, which is NP-hard and has no definite solution. Therefore, the existing solutions for the problem of prioritizing test cases are necessarily heuristics, and none of them are considered optimal solutions [2].

In 1997, the first official definition of the problem of selecting and prioritizing test cases, as well as the APFD metric [3], which is the average percentage of errors discovered in the execution of the test set, was presented to evaluate the test selection and prioritization methods in terms of the probability of early detection of errors [2]; But this metric has two limitations, firstly, it considers the difficulty of errors to be the same, and secondly, it considers the cost of each test case to be the same; Therefore, the APFDc criterion [4] of the average percentage of discovered errors in the cost was introduced to eliminate this limitation. 1-3- Overview of the proposed methods In most of the existing prioritization methods, there is a limited view and the model that researchers have used in their experimental studies for regression testing, they consider it as a "one-time" test, while the model is suitable for testing Regression, which indicates its characteristics, is a "continuous" and "long-term" test, and it is executed sequentially after each change in the software, so that the efficiency of each of them affects the subsequent tests.

In this regard, in [6] for the first time, the discussion of "memorizing" the regression test and using the background information of the performance of the test items, in prioritizing the test set, was raised. The discovery method presented in [6] is actually a combination of "background-based selection method in the test" and then prioritizing the test items. In this way, in each regression step, the history of the execution of the test cases is used for the next selection of the test cases, and in each step, a subset of the initial test set (without its permanent reduction) is selected for prioritization and execution on the new version of the software. It has been shown that [6] such a revelation can reduce the cost after long executions and reduce the efficiency of regression testing in limited development environments.

The problem of the current background-based method is that in the background information of the execution of the test cases, the only effect is the "recent" failure of the test case to be executed or the detection of an error or its absence in the previous execution, which is "zero and one" in the recursive relationship of the probability of selecting cases. The test is considered. While for prioritizing the background-based efficiency, both the efficiency of error detection during executions should be considered and the low prioritization and permanent obsolescence of a series of tests should be avoided. This method combines three types of background information about test cases, such as the number of executions and the number of error detection times, in one relationship. They give a constant coefficient to each of these criteria, so each criterion has a constant effect on the probability of selection, then the probability of selection is calculated and the test cases are scheduled in descending order according to the probability of selection. Khalilian et al. presented a relationship for prioritizing the test case in [8], which uses background information.