Model Based Testing Using Genetic Algorithm

This Tutorial Explains what is Model-Based Testing, What is a Genetic Algorithm and how Genetic Algorithms can be applied to Model-Based Testing:

Testing applications is a very important task for all applications. During the last decade, various techniques for testing applications were proposed to be sure that we are delivering high-quality applications by fulfilling all the requirements coming from the customer.

Model-based testing (MBT) is a very important topic in the field of test automation which is based on the generation of the test cases from models of the tested applications.

Currently, there are various techniques based on model-based testing. Here, we will present two techniques using genetic algorithms for model-based testing. Application of genetic algorithms for model-based testing is a very important topic and there are many articles and comparisons of existing approaches.

Model-Based Testing

Model-based testing (MBT) is an important part of test automation. As the name suggests, used test cases are generated all or partly from a model. The model used describes some functional aspects of the tested system. The models are the expected behavior of the system under test.

Models are used to represent the testing strategy. We have to mention that for model-based testing, there are two main approaches i.e. Online MBT and Offline MBT.

Online MBT constantly executes the tests as they are generated.

Offline MBT creates a set of tests based on the requirements and executes the tests later. This approach permits the execution of the test cases in a third party system.

The fundamental MBT process comprises five major steps:

1. Modeling
2. Test planning
3. Test design
4. Test generation
5. Test execution

#1) Modeling is the stage in which we have to describe the system requirements. This description will be used for the test generator.

The model has to contain the expected output of the tested system as well. In this step, two aspects are really important i.e. Design Model and Test Model.

When we are selecting the model, some important criteria’s should be taken into account:

In most cases, the model is translated into a finite state machine system or a state transition system. The finite state machine system represents the possible configurations of the system under test.

To find test cases, the system is searched for executable paths. The test case will be created from a possible execution path. This method can be used if the model is deterministic or if can the model can be transformed into a deterministic one.

#2) Test Planning: It means the definition of test selection criteria and metrics. This allows the formal representation of test case specifications, guiding the mapping of feasible test suites, etc.

#3) Test Design: It means formalization of test cases by applying the previous test selection criteria.

#4) Test Generation: Means design as many tests as possible.

OFFLINE

• Searching algorithms
• Tests are written in a determined format.

ONLINE

• Walking algorithms or light searching algorithms.
• The next step is decided after the previous one execution and output value is received.
• Algorithms have to be fast.

#5) Test Execution: Execute the tests and identify the differences between the existing output and expected output.

Evolutionary Algorithms

Evolutionary algorithms are using concepts from biology such as selection, reproduction, and mutation.

Here, we are mentioning three basic types of  evolutionary algorithms:

• Genetic algorithms
• Evolutionary programming
• Evolutionary strategies

Genetic Algorithms (GA)

Genetic algorithms are a part of evolutionary computation. Evolutionary computation is an area of artificial intelligence.

Darwin’s theory about evolution is the basis for Genetic algorithms. We can also say that the solution to a problem solved by genetic algorithms is evolved.

For Genetic algorithms, we are using four important terms from the natural selection i.e. gene, chromosome (individual), population and natural selection

The natural selection includes the following steps:

• The fittest individuals from the population will be selected.
• The individuals will produce offspring which inherit the characteristics of the parents.
• The offspring will be added to the next generation.
• The offspring of parents with better fitness will be better than parents and will have a better chance of surviving.
• This is an iterative process and in the end, a generation with the fittest individuals will be created.

Usually, the simplest way to explain Genetic algorithms is to think that we have to solve a problem and we can consider a set of solutions for that problem. Using evolution theory and natural selection, we will have to find the best solution for the problem to be solved.

Genetic Algorithms use the following terms:

#1) Initial population: The problem starts with a set of solutions (individuals) for the problem to be solved. The population is formed by a specified number of individuals. Each individual is a solution to the problem we would like to solve.

An individual is formed by a set of parameters (variables). We are calling these parameters as genes. Genes are joined into a string to form a Chromosome (solution/individual). Usually, binary values are used (a string of 1s and 0s) to encoded genes in a chromosome.

#2) Fitness function: Determines the ability of an individual to compete with the other individuals. For each individual (chromosome/ solution), we will calculate a fitness score based on the fitness function. The fitness score will ensure the probability that an individual will be selected for reproduction.

#3) Selection: The fittest individuals will be selected and will pass their genes to the next generation. How does it work? The algorithm will select 2 pairs of individuals (parents) based on their fitness scores. Individuals with high fitness scores will be selected for reproduction. There are various algorithms for selection.

#4) Crossover (Recombination): It is the most significant phase in a genetic algorithm. There are various types of crossover.

Generally, to obtain new offspring and insert them in the population, a crossover point is chosen at random from within the genes for each pair of parents to be mated. Based on that, 2 offspring will be generated from the 2 parents.

#5) Mutation: This is a genetic operator that is applied on a part of the new offspring formed, with a low random probability. This implies that the number of the bits within the bit string is often flipped.

#6) Termination: If the population will not produce offspring that are significantly different from the previous generation then the algorithm terminates. At this moment, we can say that the genetic algorithm has provided a set of solutions to our problem.

Genetic Algorithm And Model-Based Testing

The most important part of this text is to understand how genetic algorithms may be applied to model-based testing. Let’s analyze two applications of the genetic algorithms in model-based testing.

We are now using all the terms from genetic algorithms and we are presenting how those are used in various applications of GA for model-based testing.

Using GA For Test Data Generation From UML State Diagram

Model-based testing can take a UML (Unified Modelling Language) model view of the tested application and generates test cases and executable test scripts.

Genetic algorithms can be used to generate the test data using the Unified Modelling Language (UML) statechart diagram.

To use the UML statechart diagram, let’s keep some useful terms in mind:

• State diagrams (state chart diagrams) are used to model any complex functionality or describe the dynamic behavior of the entire system, or a sub-system, or even a single object in a system.
• Model-based testing is employed to get test cases from UML statechart diagram before coding. Thus, we can generate a test suit for any specification of the software. Specifications are often within the sort of UML diagrams, formal language specifications.
• A trigger like an occasion that initiates a transition from one state to another.
• A guard condition may be a Boolean condition that has got to be satisfied for a transition to occur.
• An impact is that action (activity) that happens when a transition occurs.

As we said, to apply a genetic algorithm we have to define the initial population formed by the individuals (chromosome). This initial population will represent a set of solutions for our problem.

Problem definition: Generate test data set which covers maximum states and transitions.

Apply a genetic algorithm:

• The state diagram acts as test cases for a software application to be tested.
• The chromosome is a sequence of triggers for the UML state diagram.
• We will consider the sequence of triggers as an input for the UML state diagram.
• Each trigger is examined to find the transitions that cause a replacement state. The trigger is responsible for state and transition coverage.

Let’s see how the transition coverage will work in this approach:

If (the trigger can generate new state from the present state) then

Next trigger is checked

else

Tracing for the state coverage is stopped and the state and the transition coverage are recorded without taking the rest of the sequence to consider.

Based on each traced trigger, new states and transitions are recorded. The process continues until all the states and transitions are covered.

We have to evaluate each chromosome.

The objective function used for evaluation is:

f(c)=aW+bX+Z

Where:

• a, b, c are constants.
• a = 0 when there is no guard condition in the selected transition.
• W represents the number of states in test cases with attributes with the guard condition true.
• X represents the number of transitions that are covered by the current test but not covered by the previous test set.
• Y represents the number of states that can be extended by the test case to the attainable transition source.
• Z represents the number of state and path coverage for the test case.

The algorithm can be summarized as follows:

• For each chromosome/test case, the fitness function is calculated.
• A test case with the best fitness value will be selected as the parent.
• The selection operator will be used to apply the crossover and mutation operator to the selected test cases.
• The crossover operator will be applied to the sequence of triggers. The crossover will help new states and transitions.
• UML state diagram executed for checking new chromosomes.

The successful tests are done with a population size 6, crossover probability 0.4 and mutation probability 0.3.

Using GA For Prioritization Of Test Case Scenarios Derived From UML Diagrams

One important aspect of model-based testing tasks is the prioritization of test case scenarios derived from an activity diagram and state chart diagram of UML. This can be done using the concept of basic information flow (IF) metric, stack, and GA.

Let’s take a look at the technique for generating test cases from state chart diagrams and nested activity diagrams.

The nested activity diagrams and statechart diagrams are used for creating test case scenarios.

An activity diagram is the functional view of the system. In the activity diagram, we can find the flow of control from one activity to another. Each node in the activity diagram represents activities. An activity is an action performed by the system.

To use an activity diagram for the test case generation, we need a different representation of the activity diagram. Thus, the diagram will be converted into a control flow graph (CFG).

In a CFG each node represents an activity and the edges of the flow graph describe the control flow of the activities.

To use the statechart diagram, we need a graph representation. The statechart diagram is converted into an intermediate graph, State Dependency Graph (SDG).

Each node in the CFG and SDG will have assigned a weight w. For the assigned weight w, a stack memory allocation technique is used. w is based on the number of operations to access the element in the stack.

To define the initial population the encoding of the chromosome is performed. A chromosome or test data is a binary string. We can use a single bit in a string for a decision node of the graph. We can use also multiple bits for a decision node of the graph.

The length of the chromosome will depend on the number of decision nodes and the type of graph being used.

If we have CFG with four decision nodes then the chromosome will be formed by a four-bit binary string. This chromosome will be an individual in the population.

If the chromosomes have a high fitness value then they will be selected as the parents for the reproduction.

The fitness function is the following:

Where:

• w_i represents the weight of the i-th node in the path.
• n represents the number of nodes in the current path.

The crossover is used and the probability of crossover is taken as 80%. Crossover is done if r < 0.8. The probability of mutation used is 20%.

FAQs

Q #1) Which is the difference between Model-based testing and other forms of testing?

Answer: MBT is a part of the software development process and not part of the independent scripting tasks.

Q #2) How will MBT facilitate work between Software Developers and Testers?

Answer: The team should think about the models. Based on the requirements they have to think about how to model the system behavior. That model will be used for testing.

Q #3) Why are we using Genetic Algorithms for Model-based testing?

Answer: Genetic algorithms are used for the optimization of the number of test cases. Genetic algorithms are useful optimization techniques.

Conclusion

We have presented two ways of using GAs in model-based testing. One of the key points in genetic algorithms is solution encoding. Both approaches offer a different solution encoding.

Some improvement techniques are applied for test case generation. No improvement technique can attain the best performance for every piece of code.

Applications of MBT:

The MBT is applied in various approaches of testing:

• Load testing
• Performance Testing
• Security testing
• Verification & Validation Testing
• Conformance testing

MBT and GA can be used for successfully testing web application (login, enrolment system, payment system, e-commerce system). The model is created based on the requirements and various models can be used.

Happy Reading!!