Software testing is a critical task in the software development life cycle. It is an expensive and laborious activity that is often considered time-consuming in any software development life cycle model
Test data generation is a central objective in software testing
Many researchers have proposed several automatic generations of test data set for path testing, such as random, symbolic, dynamic, and search-based testing. All three approaches to test data generation are inadequate to sustain enough appropriate test data. As a result, search-based testing is the day’s trend for generating test data
In this paper we utilized the application of Negative Selectin Algorithm in Ant Colony optimization (ACO). Marco Dorigo introduces the ACO algorithm by studying the foraging behaviour of the ant colony
In an ant colony system (ACS), searching for an optimal path generates solutions referred to as a path on the construction graph G = (V, E). The set of solutions can be linked to either the graph G node set V or the graph G edge set E. The quantity of pheromone trail associated with an edge (i,j) indicates the learnt desirability of selecting node j when the ant is on node I and m ants are utilised to build a tour in the network given a graph with n nodes. If the kth ant is still on node I, the current position (i.e., the node I set of neighbourhood nodes for such an ant) can be written as
Once all ants have finished their tour, the pheromone on all edges is updated using the equation below. Pheromone updating aims to raise pheromone values associated with good or promising solutions while lowering those associated with negative ones
The pheromone decay parameter
Ant k has deposited pheromone on edge (i,j). It's commonly defined as
Tk denotes the route taken by ant k, while Lk denotes the duration of the tour. It is clear from the definition of
In Dorigo's modified ant colony system (ACS),
The Negative Selection Algorithm (NSA) is possibly the most critical strategy (AIS)
The following are some related works on test data generation fields: Hussein Almulla and Gregory Gay proposed a feedback-based test data generation approach using multiple fitness functions. The method is guided by the choice of fitness function to produce more effective results
The majority of work in the field of test data generation has focused on structured oriented methodologies; however, in this study, we proposed a methodology based on object oriented techniques. The majority of the work in the domain of test data generation is done using search-based approaches and artificial immune algorithms. These approaches are unable to fully locate the search space, limiting efficacy and efficiency. In this paper, we propose a hybrid approach based on ant colony optimization (ACO) and negative selective algorithm (NSA) that is more competent than other approaches in the same discipline and is fully practised to locate the search space, guiding to complete path coverage with a higher efficacy rate.
In the proposed methodology, the test procedures and both techniques must work in an aligned manner to produce an optimal outcome.
The primary objective of the ACO and NSA algorithm is to solve computational problems. We propose a hybrid strategy based on Ant Colony Optimization (ACO) and apply the Negative Selection Algorithm (NSA). Therefore that it can produce a high-coverage test data set with significant efficacy. The following is a formal definition of the data creation problem by combining the applications of both ACO and NSA technologies. Let a programme under test P have a test data set as input, i.e.,
The search domain in the approach is a topology structure graph. An ant's neighbour region is a set of nodes adjacent to its current location in a graph. Each ant's position can be considered a test case in the test data generation process, and it's usually represented as a vector in the input domain. In this case, the domain is a continuous Euclidean space. Initially, m ants are placed randomly over the search domain. For every ant
Each ant seeks a better solution in its immediate area during the scan. The local search is aligned with the shifting of ant positions. Its purpose is for each ant to randomly travel the solution in the proximity of the maximum radius rmax. Generally, we set the initial value of the parameter rmax to a constant based on the characteristics of the problem. However, as the number of iteration times in searching increases, it will eventually decrease the value of rmax. Ant's local shifting can be well defined when ant k walks to a new neighbour position Xk, and if Xk>f(Xk), then the ant can be transferred to a new position. Otherwise, it will have to remain in its existing place. Here f(Xk) is the fitness value of the solution Xk. Global search is applied when the fitness of any node has a higher value than the average fitness. i.e. f(Xk)> favg(Xk). In that case, Hamming distance is computed among the nodes to attain the global best solution
The application of the Negative Selection Algorithm is used in the next step of the proposed strategy. After finding the new test data sets through Ant Colony Optimization, NSA is applied to those data sets. NSA not only identifies the replication of test data generated through ACO but also supports complete path coverage and reduces the size of the test suite to elevate the performance and speed of the algorithm. Let us consider the test data Td. If it already exists in the newly generated test data set, discard it from Td. Otherwise, the Hamming distance between the new detector Td1 from the est data set Td and all detectors Tdi in the set and the smallest distance obtained will be compared with a threshold value. If the distance is lesser than the threshold value, then the test data will be removed from the test data set Td, or else it is included in the refined set of test data. This approach aids in the coverage of the search area as far as possible. It could cover more paths with a smaller amount of test data for the program under test. Subsequently, go for the nearest test data from the set, i.e., Td2 and calculate the new detector Td1 and Td2. If the fitness value of Td1 is greater than Td2, interchange the test data Td2 with the test data Td1. The following method is used to find the distance between test data.
1.
2.
The fitness function has a significant impact on test data validity. The fitness function preferably applies for the refinement of test cases. In this study, we have used a path-based coverage criterion to validate the code's fitness. Path-based fitness can be calculated as:
where α and β are the set of nodes in the targeted and executed paths, respectively
A comparison of real-world benchmark programs from the literature has been made to determine the performance of the proposed technique. These benchmark programs have been extensively applied in search-based testing by researchers. The program codes are being written in object-oriented programming languages such as Java. All these programs are designed using complex programming structure syntax such as relational operators, logical operator's conditional statement, control statements, modularity, the structure of classes, etc. This made these programs suitable for analysing various test data generation techniques. These programs often provide a complex data structure with various types, such as integers, floats, characters, and strings.
|
|
|
|
|
|
|
Triangle Type |
3 |
50 |
16 |
13 |
9 |
|
DayFinder |
3 |
168 |
24 |
24 |
16 |
|
MinMax |
1: N |
83 |
6 |
12 |
4 |
|
Isprime |
1 |
34 |
6 |
11 |
4 |
|
BubbleSort |
1: N |
81 |
8 |
15 |
5 |
|
MidValues |
3 |
37 |
16 |
9 |
9 |
|
LinearSearch |
1: N |
48 |
4 |
10 |
3 |
|
BinarySearch |
1: N |
69 |
6 |
14 |
4 |
|
SqRoot |
1 |
27 |
6 |
8 |
4 |
|
Student Grades |
1 |
53 |
18 |
19 |
10 |
|
Greater |
3 |
25 |
6 |
12 |
4 |
|
To prove whether the ACO-NSA based test data generation approach is practical or not, the following test metrics are considered while evaluating the code such as:
1. Average Coverage (AC), i.e., the average of all test input path coverage throughout multiple runs.
2. Average Generation (AG), i.e., the average evolutionary generation in which all paths are covered.
3. Average Time (AT), i.e., the average execution time for all paths in seconds.
4. Success Rate (SR), i.e., the probability of coverage of all paths.
A different number of tests have been done for the above metrics, such as for AC, AG, and AT, the value of the test has been set to 1000, and for SR, it was set to 200 to achieve the full coverage of the source program. The experimental findings of the four algorithms are presented in response to eleven programmes in
|
|
|
|
|
1 |
1→2→3→4→5→12→14→15 |
9 |
2,3,4 |
Scalene |
2 |
1→2→3→4→5→6→8→11→-14→15 |
9 |
4,4,3 |
Isosceles |
3 |
1→2→3→4→5→6→7→14→15 |
9 |
2,2,2 |
Equilateral |
4 |
1→2→13→14→15 |
9 |
1,2,3 |
Not a triangle |
5 |
1→2→3→13→14→15 |
9 |
2,1,0 |
Not a triangle |
6 |
1→2→3→4→13→14→15 |
9 |
1,0,2 |
Not a triangle |
7 |
1→2→3→4→5→6→8→9→11→14→15 |
9 |
5,4,5 |
Isosceles |
8 |
1→2→3→4→5→8→9→10→11→14→15 |
9 |
2,6,6 |
Isosceles |
9 |
1→2→3→4→5→8→11→14→15 |
9 |
9,9,7 |
Isosceles |
The comparison of 11 different bench mark programs for metric average coverage using three different approaches—random testing, ant colony optimization, and negative selection algorithm is shown in the
The comparison of 11 different bench mark programmes for metric average generation using three different approaches—random testing, ant colony optimization, and negative selection algorithm is shown in the
The comparison of 11 different bench mark programmes for metric average time using three different approaches—random testing, ant colony optimization, and negative selection algorithm is shown in the
The comparison of 11 different bench mark programmes for metric success rate using three different approaches—random testing, ant colony optimization, and negative selection algorithm is shown in the
This section of the paper presents the results of the experiments conducted to evaluate the performance of the proposed method, i.e., ACO-NSA test data generation for path coverage. At the beginning, the program's source code is converted into a control flow graph, and then ACO-NSA is applied to generate automated test data. The finding represents that the proposed approach generates the least amount of test data in limited generations and has high coverage ratio. The results are compared with random testing, ant colony optimization, and negative selection algorithm to evaluate the performance of the projected approach. The performance is measured in terms of average Coverage (AC), average generation (AG), success rate (SR), and average time (AT). The researchers widely applied benchmark programs for test data generation is being applied for comparison. These benchmark programs' design flow structure suited them for testing various test data generation techniques. All such programs have different data structures, codes (LOC), arithmetic, relational and logical operators, loops and nested loops, conditional statements, arrays, functions and classes and complexity levels.
Among 11 distinct benchmark programs "triangle type classifier (Tritype)" is a highly recognized programming application for testing. It seems to be a simple application for the testing process, but it has all requirements suitable for testing, such as data structures, conditional and logical operators, conditional and logical statements, functions, and arrays. It uses three input variables to decide the triangle type (scalene, isosceles, equilateral, and not a triangle). The size of the search space is proportional to the data type. If it is assumed to be an integer of type, it may consume two bytes of memory for an individual variable declared. It is challenging to design test cases corresponding to such an extensive range of data from the appropriate domain corresponding to the variable's data type. The proposed approach guides the method to generate appropriate test data from the domain to achieve the full path coverage. Path fitness is applied along with the proposed method to achieve quality data. The probability of finding the accurate value for all three variables that execute the critical path, such as the isosceles triangle, depends upon the three variables, i.e., having any type of triangle will be 1/3rd of all. The analysis reveals that the ACO-NSA is more efficient than random testing, ACO and NSA using the triangle type classifier program for test data generation. The number of generations required in ACO-NSA is comparatively much more minor than random testing, ACO, NSA, and hybrid NSA-GA. Its concluded from the results (
This paper suggested a hybrid ACO-NSA test data generation algorithm for basis path testing, the fitness of the approach is accessed using path fitness. To assess the effectiveness of a strategy, four separate metrics —average coverage, average generations, average time, and success rate have been taken into account. All metrics are analyzed using 11 distinct benchmark programmes with varying numbers of iterations, including 200 for success rate, 1000 for average coverage, average generation, and average time. The proposed approach has been compared to negative selection, ant colony optimization, and random testing approaches . For the aforesaid metrics, the proposed technique performs better than the other three. For all 11 tests, the total number of generations is quite modest in the technique, ranging from 1 to 8%, average execution time ranges from 0.026 to 0.157 ns, success rate ranges from 99.4 to 100%, and average coverage is strong with a range of 95.55 to 100%.