A condition coverage-based black hole inspired meta-heuristic for test data generation

Abstract

As software becomes more complex, the importance of software testing increases by the day. It is very important to get as close to bug-free software as possible, especially for safety-critical systems. Some standards, such as DO-178, have been established to ensure that the safety requirements of safety-critical software are met. In these standards, the code coverage ratio is one of the parameters to measure test quality. To increase the coverage rate, test data must be generated in a systematic manner. Combinatorial Testing is one of the most commonly used methods to deal with this problem. However, for software that takes a large number of input parameters, CT causes test case explosion problems and it is not possible to test all produced test cases. To reduce the number of test cases, T-way testing is a technique for selecting a subset of huge numbers of test cases. However, because this technique does not choose test cases based on code coverage, the software is not tested with coverage values at the required height. The motivation of this study is to produce test cases by considering the condition coverage value. Thus, the condition coverage value and test quality will be increased without the need to test too many test cases of all possible combinations. This thesis focuses on the research question (RQ): How can we conduct a meta-heuristic method in Search-Based Combinatorial Testing (SBCT) that generates test data to achieve high coverage rates while avoiding local minima? To find answers to our research question, we reviewed the literature and discovered that Search-based Software Testing and Search (SBST) and Search-based Combinatorial Testing (SBCT) techniques are used to generate optimum test data using meta-heuristic approaches. Among the studies in the literature, we chose studies that work on problems similar to ours and studies that differ in terms of fitness function and data set, so we aimed to examine studies with various features as much as possible. As the results of our literature review, we discovered that meta-heuristics in Search-Based Combinatorial Testing (SBCT) could be used to generate test data for enhanced condition coverage in software testing. During our literature review, we realized that the Black Hole Algorithm (BHA), which is also a meta-heuristic approach, can be also used for our problem. Hence, after analysing alternative solutions, we decided to work on BHA for the following three main characteristics of our inspired study: (1) That study focused on a problem that is very similar to our problem, (2) Although BHA is a data clustering method, it is a novel method used in test data generation, (3) BHA was reported to be more efficient than another optimization algorithm (i.e., Particle Swarm Optimization (PSO)); and this finding inspired us to propose a stronger method. To achieve our goal, we present a novel approach based on a binary variation of the Black Hole Algorithm (BBH) in SBCT and adapt it to the CT difficulties. We reused some of the techniques in BBH, modified some of them, and introduced new methods as well. The proposed BBH version, BH-AllStar, aims the following: (1) obtaining higher condition coverage, (2) avoiding local minima, and (3) handling discrete input values. The main two significant differences between BH-AllStar and BBH are the new elimination mechanism and avoiding local minima by reassessing earlier removed stars and selecting the useful ones to add to the final population. Our contributions are as follows: (1) we perform more detailed tests by using detailed condition coverage rate criteria per each condition branch while generating test cases, (2) we develop a condition coverage-based test cases selecting mechanism and reduce the risk of eliminating the beneficial test cases wrongly, (3) we avoid local minima by providing variety achieved by re-evaluating the test cases which are destroyed before and giving chance them to be added to the final test case pool (4) we give higher priority to coverage rate than test case number unlike existing studies in the literature and thus, we provide more efficient tests with higher condition coverage rates and (5) we provide the validity of our BH-AllStar method by applying it to three different Software Under Test (SUT): one of them is a real-life safety-critical software and two of them are toy examples. Our new metaheuristic method can be applied on different software settings and all types of SUTs can be used on the experiment setup. We analyzed our approach in terms of condition coverage, number of test cases, and execution time. As a result, we observed that our BH-AllStar method provided up to 43% more coverage than BBH. Although BH-AllStar produced more test cases than BBH, this level of increase was acceptable to achieve higher coverage. Finally, we answered RQ by determining that the Black Hole phenomenon, which is provided as a meta-heuristic in SBCT, is a suitable strategy for producing test data in order to reach larger condition ratios while avoiding local minima by modifying and proposing novel features to it. As future work, BH-AllStar can be tested on different SUT, the randomization operation in initialization processes can be optimized and MC/DC tests can be studied. BH-AllStar.