Combinatorial Testing (CT) strategy is one of the well-known methods to achieve high code coverage rates during testing for safety critical systems. While generating test data in CT, we often encounter the problem of test case explosion, especially for the systems with multiple parameters and values. To overcome this challenge, search-based CT (CSST) strategies are introduced. In this study, we propose a new algorithm that inspires from a binary variant of Black Hole Algorithm (BBH) in CSST and adopt BBH according to the CT challenges in an industrial context. The proposed BBH version, BH-AllStar, aims the following: (1) obtaining higher condition coverage, (2) avoiding being stuck in local minima and (3) handling discrete input values. We finalize the solution space of BH-AllStar by reassessing the previously removed stars and incorporating the useful ones into it. We evaluate our approach on a real-life software project in the safety-critical domain with respect to condition coverage, number of test cases and execution time. Compared to BBH, BH-AllStar generates more test cases which achieve up to 43% increase in condition coverage.
The complexity and the criticality of the safety critical systems in the defense industry are growing [1, 2], hence, these systems require more thorough and efficient testing technologies, such as test automation and regression test selection/prioritization [3] and continuous integration. The software testing field in the defense industry needs to develop more efficient and qualified techniques to meet security-critical requirements. [1]. For instance, various test techniques such as Boundry-Value Analysis and Equivalence Partitioning are used to meet the DO178 Standard to ensure safety-critical requirements, which has been imposed by the U.S. Federal Aviation Administration (FAA). [4, 5]. To assess the effectiveness of these methods, different coverage criteria are employed [6]. During functional testing, Combinatorial Testing (CT) methods are widely utilized especially for software systems in which there exist many parameters and conditions that take a combination of multiple input values [7, 8]. CT method such as t-way testing executes the software using test cases with the interaction of the possible input values [9]. The radar software in our industrial context, for instance, takes 12 input parameters each takes two to six values. If we would like to test this software with full input coverage, we would end up executing 63.34.24.5=1,399,680 test cases. This is an impossible goal to reach, and instead in practice, we follow t-way testing with the IPOG strategy [10]: select the t value as high as possible with the cost of increasing the number of test cases. The current limitation of the employed t-way testing in our industrial setting is the lack of relationship between the selected test cases and their code coverage, because the strategy of selecting the test inputs is not dependent on the covered branches/conditions of the software system.
To address this challenge, combinatorial search-based software testing (CSST) approaches are suitable [11]. One of the studies by AlSammarraie and Jawawi [9] inspired our work. The authors propose three new approaches namely Binary Black Hole (BBH), Multiple Black Hole (MBH) and Binary Multiple Black Hole (BMBH) based on the Black Hole Algorithm (BHA), which is first introduced in [12] as an alternative to Particle Swarm Optimization (PSO). Their aim was generating test inputs with respect to the number of test cases and code coverage. The authors also aim to avoid being stuck in local minima and they propose a novel energy mechanism for MBH that helps to choose useful black hole populations only. The results show that MBH outperforms PSO and BHA in terms of the number of test cases, consistency and high coverage rates.
We share the same goal with [9] of generating
test data using a search-based meta-heuristic,
which avoids local minima and achieves higher
coverage than BBH. The approach in [9] could be
well fitted in our industrial problem because of
two main motivations: (1) their problem domain
and data set are similar to our project, i.e., radar
software, (
The remainder of this paper is organized as follows: Section 2 presents the related work. We report the details of our approach BH-AllStar and research methodology in Section 3. Section 4 shows the results and discussion; Section 5 explains the threats to validity. Finally, Section 6 concludes this study with future directions.
Combinatorial Search-based Software Testing (CSST) is a testing method based on Combinatorial Testing (CT). CT aims at generating input vectors combining possible input values of all input parameters of the Software Under Test (SUT) [10]. The SUT can have n input parameters: ci (i = 1,2,3…n). Every parameter can take a set of values Vi where i can be from 1 to n. For example, V1 is the value set of c1 and contains m different values. (v1,v2,…,vm ). One test case is composed of a set of values from all Vi of all ci (e.g. vx ∈ V1, vy ∈ V2, vz ∈ V3) [10]. There are different methods to build all combinations of input parameters for CT such as t-way testing or randomization-based methods in the literature [13]. CSST is one of the search-based approaches to reduce the large solution space [9]. To find the optimum solution of a problem, especially for the problems, which contain very large sets of solutions and have computational constraints, meta-heuristic search techniques are commonly implemented [14]. These meta-heuristic search techniques are based on initially generated random solution space and narrowing down the search space based on the evaluation criteria.
A recent systematic mapping study in [14] highlights 260 relevant studies in CSST, and narrows down to 42 primary studies to investigate the proposed approaches and their test case generation accuracy. The authors summarize well-known meta-heuristic search techniques as follows: Genetic Algorithm (GA), Particle Swarm Optimization Algorithm (PSO), Simulated Annealing Algorithm (SA), and Ant Colony Optimization (ACO). Their mapping strategies show that GA is the most popularly applied technique, whereas some combine multiple algorithms such as GA and SA. They conclude that the primary studies provide benefits in terms of code coverage and execution time.
In Table 1, we list a sample of studies obtained from [14] that we examine in terms of the approach, dataset on which the approaches are evaluated, and the fitness criteria. Among the studies, we selected eight studies targeting a similar objective to our industry problem, and varying in terms of fitness functions and datasets. The studies [15-19] utilize nature inspired optimization methods for CSST, whereas [9, 12, 20] use a heuristic based on black hole phenomenon. All studies in Table 1 show that the improved versions of nature inspired optimization methods outperform original methods with respect to code coverage or execution time. All the prior studies validate the success of their proposed approach on simple functions like the source code that calculates the greatest common divisor or checking the validity of the date, etc. Unfortunately these projects are not representative of real programs, and achieving high coverage is relatively easier with few test cases. Except one study [15], all studies focus on branch coverage as one of their evaluation criteria, although in practice wıth more complex algorithms, multiple conditions need to be taken into account with a condition converage criterion. Below, we give more description on our baseline algorithm BHA [12] and its application on test case generation [9].
BHA has been first introduced in the study [12] as a new heuristic algorithm inspired by the black hole phenomenon. Based on Newton’s law, scientists invented a concept about the stars with high power and strong gravitational field [21]. They name this star as “black hole”. The reason of this name is that any object moving around this special star cannot escape and is absorbed into the black hole if the objects cross the Schwarzschild radius [21]. This special star is described with the adjective ‘black’ because light cannot be reflected and make this star invisible [21, 22]. With the inspiration of the nature of black holes, BHA is proposed for data clustering [12]. Fig.1 presents the pseudocode of BHA adopted from [9, 12]. According to the terminology used in [9], a population with random stars is initially generated, and a fitness value is calculated for every star in this population. The best star with the best fitness value is selected as the black hole. Later, all stars in the population are moved towards the black hole as described in Eq.1. The new location of the current star x(t+1) is calculated by multiplying a random number with the difference between the BH Star and the current star (BH-currentStar), and adding the result to the previous location x(t). The current star is moved closer to the BH Star as a result of this operation. Movement of the stars towards the black hole provides a grouping process and force all the other stars to converge to the best fitness value. If a star crosses the event horizon (R) of the black hole defined in Eq.2, it is destroyed, and a new random star is generated and added into the population. The R value is calculated as the ratio of the fitness value of BH Star and sum of the fitness function outcomes of all stars in the population. This step leads to adding various stars to the population and increases the probability of convergence to the desired solution.
x(t+1) = x(t) + rand x (BH-currentStar) (1)
R = (
)/ ∑=1 (
( ))
(
The searching process stops if the stopping criterion is met. This criterion can be the maximum number of iterations or a sufficiently good fitness criterion [9, 12].
Hatamlou conducted an experiment on the
sixbenchmark dataset [12] and highlights two
advantages of BHA: (1) simple and easy to
implement, (
Based on the BHA proposed in [12], Al
and
Jawawi [9] propose three variations of BHA for test case generation: BBH, MBH and BMBH. Terms and function names used in the study [9] are described in Table 2. For the inputs that has discrete values like binary values (0,1), moveStars operation (Eq. 1) does not work because it causes a shift in the continuous domain due to the multiplication of the distance with a random value. To handle this issue, a binary variant of black hole is proposed. This approach generates a random value rd between 0 and 1. This random value is compared against the constant value, pr (Eq. 3). If it is greater than rd, the new location of the star is going to be equal to that of black hole. Otherwise, new location of is equal to its own old value [9].
Terminology of BBH used in [9]
Meaning x: can take values x1, x2, x3 y: can take values y1, y2, y3. … [x1 y2 z3 t4] [star1, star2…starn] Calculate the coverage of every star in the population and determine the best star as the black hole.
Change location of stars towards the blackhole.
Update the radius value of black hole.
Remove the current star and generate a new one.
Radius of the black hole (eq.2) ( + 1) =
( ) < ( ) ℎ (3) being stuck in local minima since there is no mutation operation. The authors point that the population initialization and operations could be improved. moveStars
Our work complements the previous study [9]
in several ways: (1)We propose a condition
coverage-based elimination mechanism instead of
a distance-based one to keep the test cases that
likely
contribute to total coverage. (
The software under test in this study is part of a large-scale radar software developed for the defense industry.
Due to its confidentiality constraints, we are not able to give the details of the algorithm or its pseudocode. We can briefly describe the complexity of our SUT: it takes 12 input parameters with different possible values, and outputs an integer value. It contains two functions with 17 if and nested if statements with up to three levels, two for loops, two switch case statements and 72 branches in total. We built a technological setup, in order to conduct our analysis on BBH and its variants including BHAllStar. Our analysis starts by selecting the baseline algorithm as shown in Fig 2, namely BBH, to generate test cases, i.e., a black hole (BH) surrounded with
stars, and our software is executed against this test case. Then the system collects the information of missed conditions using
Based on the decisions, the algorithm generates
new test cases (stars) and the cycle continues. The
algorithm terminates after K (
We modify several operations in [9] and propose our approach: BH-AllStar.
We use initializePopulation() and updateFitness() methods as is, but modify moveStars(), and created a new star elimination criterion. We also propose two new
methods to select the final population both of which will be described below. Our motivation is also determining the best BH in reaching as high coverage rates as possible, and shaping the other stars around it without being stuck in local minima. During our analysis, we noticed that the distance criteria defined in [9] removes some stars although they contribute to the coverage ratio. It also prioritizes to keep the number of test cases as few as possible. Increasing the number of test cases is preferable for our industrial setting than having low coverage rates. Fig. 3 shows the pseudocode of our approach. Our contributions are presented in the below subsections.
We calculate condition coverage for each branch existing in our testing code. For example, an “if” statement with one condition, e.g. x<5, contains two branches, true or false, and the condition coverage for this branch can be 0, 50% or 100%. If an “if” statement has two conditions, e.g. x<5 && y>10, then it has 4 conditions (TT, TF, FT, FF). With the input set (x=3, y=11; x=3, y=9; x=6, y=9), the condition coverage for this branch is calculated as 75%. Only traditional branch coverage is not enough for our study since we need to cover all the conditions of each branch in our testing code. Therefore, we replace the distance based mechanism, which calculates to what extent the distance between current star and black hole exceeds the R value to decide whether to destroy the star or keep it alive, with our condition coverage based mechanism, as shown in Fig.3 described as isBestAtLeastOnOneBranch() and calculateBranchRatio() methods. With this condition coverage-based mechanism for all branches of our SUT, we give chance to the stars with lower coverage ratios then the BH Star to cover uncovered branches. We have two steps in our decision mechanism:
isBestAtLeastOnOneBranch We control if the current star is the best among all stars in the population in terms of covering at least one more branch. This operation would keep an efficient star, even if it has a smaller coverage ratio compared to other stars.
calculateBranchRatio We compare current star and black hole in terms of covering all branches one by one and calculate the ratio of the number of branches that current star covers better than black hole, and the number of branches that current star covers worse than black hole. We use here a coefficient=3 to multiply the number of better covered branches in order to give a star more chance (see Eq. 4). We have made several tests with different coefficients and chosen the value 3 as the optimum value for deciding the stars to be accepted or not.
# ℎ ∗3 # ℎ (4)
Fig. 4 illustrates a sample of stars: An eliminated star (purple), a previously eliminated but later revived star (yellow), and an always alive star (orange) with their coverage values in the timeline, when our proposed mechanism is applied. The total coverage significantly increases at the end of the iterations as we let a previously killed star (yellow) to be included into the final population. Eliminating a star (purple) also increase total coverage during 18th iteration.
In moveStars() operation, to shift the stars towards the black hole, we propose an indexbased method for discrete-valued parameters, similar to ‘Binary Variants’ in [9]. We store our input parameters in an array and we generate a random index value between the input value index of the current star and the BH. Then we move current star to this index and assign the value to the current star as the updated input parameter.
In keepPopulationWithMaxTotalCoverage(), we keep the population generated in all iterations of BBH including coverage rates and alive/dead states of each star. At the end of the iterations, we select the population that has the highest coverage ratio, not the last population according to BH. 3.4.
In allStar() method, we compare all the stars between t0 and tend against the BH at tn, and add the best stars in terms of condition coverage into our final population. Although this causes an increase in the number of test cases, it also increases the coverage of the final population.
The variants of BBH are as follows: (1) Best
BBH (BBH*): We incorporate “Choosing Best
Population from History” approach into BBH. (
The results over different iterations and with variants of BBH, reported in Table 3, show that higher code coverage rates are obtained compared to BBH. For instance, with 500 iterations, coverage values are 69.4% in BBH, whereas 75% in BBH*, 70.8% in BBHCC, 73.6% in BBHCC* and 76.8% in BH-AllStar. We observe that same coverage rates can be achieved with fewer test cases but higher execution time for different number of iterations. The maximum code coverage rate is approximately 76% in iterations 150 and 500 with BH-AllStar. Solution space consists of 190 test cases for 150 iterations and executes in 327 secs. However, for 500 iterations, only 19 test cases are used but execution time is 815 secs.
In addition, the baseline algorithm, BBH has a better coverage (72.2%) than our condition coverage based BBH approach (65.3%) for 300 iterations. However, our additions help to increase the coverage from 65.3% to 75% in BH-AllStar. BBH* always reaches better coverage rates than BBH. When the coverage criterion is set as condition (BBHCC), we do not always see a better convergence than BBH. But choosing the best population and adding all the “good” stars eventually converge to much higher coverage ratios. Instead of defining multiple black hole as in [9], we stick to the single black hole phenomenon but we give a certain flexibility to the star selection and achieve a similar improvement like in [9]. We can confirm the prior finding that a black hole inspired meta-heuristic could be successful at generating test data for software systems with too many parameters.
Considering the number of test cases, we observe that BH-AllStar may take higher values with respect to the positions of the stars, condition coverage ratios of each star and the black hole star. In 150 iterations, we generate 190 test cases, which is a higher value compared to the other experiment results. Since we pick the best stars in terms of coverage during All-Star operation, there may be many “best” stars in the population compared to the selected black hole. We did not perform any filtering on these best stars like pruning, but it might be possible to reduce those that cover similar conditions as a final step.
Table 4 presents the coverage rate of the BH Star, Alive Stars and BH-AllStar in the final solution space. In both BBH and our proposed approach, the black hole has the same coverage rate (51.4%). Alive stars in the solution space have a minimum of 23.6%, a maximum of %51.4 (BH itself) and a median of 43% coverage ratios. A star with less coverage ratio than the BH Star is acceptable in our study because it might have a higher coverage on any branch compared to the BH star.
Fig. 5 presents the coverage rates of all the branches according to 190 stars in the solution space for 150 iterations. As depicted in Fig.5, there are still some branches (e.g., 19th to 27th) which are not sufficiently covered although we increase the total coverage ratio. This is partly due to the fact that BH algorithm essentially revolves around the black star that is picked. So, some of the areas in the search space might be missed during the iterations.
Coverage Density Graph based on StarID and BranchID (Contour Plot) Coverage
< 0,0 0,0 – 0,2 0,2 – 0,4 0,4 – 0,6 0,6 – 0,8 0,8 – 1,0 > 1,0 190 180 170 160 150 140 130 120 110 IrD100 ta 90 S 7800 60 50 40 231000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
BranchID Figure 5 Coverage Density Graph based on Star ID and Branch ID
Fig. 6 illustrates the change in the total coverage ratio of BBH and BH-AllStar for 150 iterations. It is seen that one or more populations were found with BBH (around 60th and 100th iterations) that reach a higher coverage, but there were later lost. The final coverage ratio was also smaller at the end. On the other hand, in our approach, a peak can be seen just after all the iterations are executed, at t=151. The population with the best coverage has been kept and the good stars over the history are added to that population.
Figure 6 Coverage in the timeline of BBH
The results show that our Choosing Best Population from History approach always provides better coverage rates. Since the nature of the movement to the black hole and random generation of stars might cause a decrease in total coverage in BBH, we handle this problem by keeping the population with maximum coverage. The main reason that BH-AllStar outperforms BBH is that the latter eliminates stars because it is too close to the black hole star. However, it does not mean that these stars do not contribute to total coverage.
We highlight several issues that might jeopardize the validity of our findings, and discuss these in this section. The first issue is related to the construct defined as the fitness criteria of our proposed algorithm. We aim to improve the final population of the algorithm by assessing the condition coverage ratio, which is calculated through Jacoco tool for each branch of the tested algorithm. Jacoco gives a condition coverage ratio for each branch, but it does not specifically say which conditions are satisfied in that branch. When two stars having 50% condition coverage for the same branch are evaluated, we consider those the same. But we do not know whether both cover different conditions and complement each other. This might have caused to falsely eliminate some stars from the population. We plan to work on this issue in our future studies by checking other unit testing tools.
The second issue is related to the binary strategy applied to turn BHA to BBH algorithm. In Section III, we describe how the movement of the stars happens on a discrete scale. Unfortunately, the description in [9] was not detailed enough and we had to make some assumptions. This might cause a deviation between BBH in [9] and BBH we developed here. It does not affect our comparisons between BBH, its variants and BH-AllStar on the software under test in this paper.
The third issue is related to the internal validity of the experimental design. We are aware that choosing a different coefficient value in Eq.4 in BH-AllStar would impact our results, in fact, we tried multiple values and observed the convergence of the algorithm in terms of condition coverage to pick the final value as 3. We also think the randomness in the initial population, and the selection of best stars from all the iterations could affect the final results. We plan to work on these as future works as both require empirical analysis of different strategies. Finally, our results are limited to a single industrial context because we chose to solve the problem of our industrial partner through an improved CSST method. The prior works often assess their approaches on simple programming exercises, which suffer from generalization of the results on real life projects. We believe our study validates the real application of Black Hole inspired approaches adopted to condition coverage criterion.
In this study, we present a new approach to generate test data by implementing a previously proposed meta-heuristic searching technique BBH on a real-life engineering problem that we face for our safety critical systems in the industry. Our BBH variants and new algorithm BH-AllStar perform better than BBH in terms of condition coverage up to 43%. Although BHAllStar generates more test cases compared to BBH, we achieve extending search space and obtaining higher condition coverage rates in the same execution time. As a future work, we plan new experiments to compare Multiple Black Hole Approach reported in [9] and our BH-AllStar. We also plan to decrease the number of test cases in our current approach, the selection of best stars for each branch in BH-AllStar can be limited by selection only one among the best stars. We also intend to conduct further research on every condition in a decision to be covered of the SUT, rather than having higher condition coverage, which is known as MC/DC (Modified Conditon/Decision Coverage). We think that our proposed approach can be applied to other problems, such as testing algorithms with different level of complexity, nested conditions and line of codes. Initialization of the population, which is the first step of BBH can also be optimized to start with a better population rather than a random start as in its current setting. 7. References