Methodology of Test Case Minimization Using Firefly Algorithm

One of the main challenges in software testing is to design and execute an effective test suite, which can detect the faults in the software system. An effective test suite should have high coverage, which means that it can exercise a large proportion of code statements and branches. High coverage can increase the likelihood of finding faults and improve confidence in software quality. However, achieving high coverage is not easy, as it may require a large number of test cases, which can be costly and time-consuming to generate and execute.

Test case minimization is a technique that aims to reduce the size of a test suite while preserving its fault detection capability. Various techniques have been proposed for test case minimization, such as greedy algorithms, heuristic algorithms and metaheuristic algorithms. Metaheuristic algorithms are general-purpose optimization algorithms that can explore a large and complex search space by using stochastic or probabilistic rules. These algorithms have been widely applied to test case minimization problems, as they can find near-optimal solutions within reasonable time and avoid being trapped in local optima.

Let’s review a test case minimization technique based on a swarm intelligence algorithm called Firefly Algorithm (FA) and Unified Modeling Language (UML) state chart diagrams. UML state chart diagrams – a type of diagram that shows the behavior of an object or a system using finite state transitions. It represents the different states of an object or a system and how they change in response to internal or external events.

Firefly Algorithm

Firefly algorithm (FA) is an algorithm inspired by the flashing behavior of fireflies, which can attract each other and move towards brighter fireflies. FA was proposed in 2009 as a general-purpose optimization algorithm that can solve various types of problems, such as continuous, discrete, constrained, unconstrained, single-objective or multi-objective problems.

FA simulates the movement of fireflies in a multidimensional search space, where each firefly represents a potential solution to the optimization problem. FA uses two operators: attractiveness operator (AO) and brightness operator (BO). AO determines the attraction force between two fireflies based on their brightness and distance. BO determines the brightness of a firefly based on its fitness value and randomness. FA can converge quickly to the optimal or near-optimal solutions by using these two operators.

The AO is based on the assumption that fireflies are attracted to each other by their flashing lights, which vary in intensity and frequency. The attraction force between two fireflies depends on their brightness and distance. The brighter firefly attracts the dimmer firefly and moves towards it. The farther firefly attracts the nearer firefly less and moves towards it less. The attraction force decreases exponentially with the increase of distance.

The BO is based on the assumption that fireflies have different levels of brightness, which reflect their quality or fitness. The brightness of a firefly depends on its fitness value and randomness. The higher fitness value leads to higher brightness and vice versa. The randomness adds some variation to the brightness and prevents premature convergence.

The termination criterion can be based on some factors, such as the maximum number of iterations, the maximum number of function evaluations, the minimum fitness value or the minimum fitness improvement.

Algorithm Design and Implementation

To apply FA on UML state chart diagrams for test case minimization, we need to complete four main steps: make test cases, give weight to paths, calculate path coverage, and reduce test cases.

Make Test Cases

The first step is to make a set of test cases from the UML state chart diagram of the software we want to test. A test case is a set of steps that we do on the software and check the results. A step is a change from one state to another because of an event. To make test cases, we use an algorithm that goes through the state chart diagram and records all possible sets of steps. Let’s assume that the state chart diagram is clear, complete, and consistent. This means that there is only one step for each event in each state, there is at least one step for each event in each state, and there are no wrong or conflicting conditions or actions.

Give Weight to Paths

The second step is to give a weight to each set of steps in the state chart diagram based on how important or relevant it is for testing. The weight of a set of steps shows how likely it is to show bugs or errors in the software. Let’s use a method to give weights based on these things:

• The number of steps in the set of steps. A longer set of steps has a higher weight than a shorter set of steps, because it covers more software behavior and interactions.
• The number of actions in the set of steps. An action is something that the software does when a step happens. A set of steps with more actions has a higher weight than a set of steps with fewer actions, because it involves more software functionality and complexity.
• The number of guards in the set of steps. A guard is a condition that must be true for a step to happen. A set of steps with more guards has a higher weight than a set of steps with fewer guards, because it needs more specific inputs and conditions to be met.
• The number of loops in the set of steps. A loop is a set of steps that goes back to the same state. A set of steps with more loops has a higher weight than a set of steps with fewer loops, because it shows more repeated or iterative behavior.

Let’s use the following formula to calculate the weight of a set of steps:

w = (0,25 * S) + (0,5 * A) + (0,75 * G) + (1 * C) where w – weight; S – number of steps; A – number of actions; G – number of guards; C – number of loops.

Calculate Path Coverage

The third step is to calculate the path coverage for each test case based on how well it covers the sets of steps in the state chart diagram. Path coverage is a measure of how much a test case covers the sets of steps in the state chart diagram. Let’s use four types of things to calculate path coverage:

• All-state coverage (ASC) means that every state in the state chart diagram is visited by at least one test case.
• All-transition coverage (ATC) means that every step in the state chart diagram is done by at least one test case.
• All-transition-pairs coverage (ATPC) means that every pair of next steps in the state chart diagram is done by at least one test case.
• All-one-loop coverage (AOLC) means that every loop in the state chart diagram is done by at least one test case.

Let’s use the following formula to calculate the path coverage for each test case:

P = w * n where P – path coverage; w – weights of a set of steps; n – number of sets of steps.

Reduce Test Cases

The final step is to reduce the number of test cases using FA. Using FA let’s find a smaller group of test cases that has the highest total path coverage while having the lowest number of test cases:

• Each firefly represents a group of test cases.
• The position of each firefly is shown as a list of zeros and ones, where each number corresponds to a test case and its value shows whether it is chosen or not.
• The brightness or fitness of each firefly is calculated like this: the fitness is equal to the total path coverage of the group of test cases minus 0.1 times the number of test cases in the group.
• The initial group size of fireflies is 50, and the maximum number of steps is 100.

FA starts by randomly making a group of fireflies with different groups of test cases, then repeats these steps:

• For each firefly, find another firefly that has higher quality or fitness, or none if there is no such firefly.
• Move each firefly towards the other firefly that has higher quality or fitness, or move randomly if there is no such firefly.
• The movement of each firefly is done by changing one or more numbers in the list according to how much they like each other. It’s based on their distance, how fast their brightness gets weaker with distance, and how much randomness they have in their movement.

FA stops when it reaches the maximum number of steps or when it finds a good enough solution. The best solution among all fireflies is returned as the final result.