Search Based Software Testing Article 2022

Running head: SEARCH-BASED SOFTWARE TESTING
SEARCH-BASED SOFTWARE TESTING
Name of Student
Name of University
Author Note

SEARCH-BASED SOFTWARE TESTING
Table of Contents
Introduction:...............................................................................................................................2
Discussion:.................................................................................................................................3
Main Optimization Algorithms:.............................................................................................4
Application areas with fitness functions:...............................................................................4
Highlighted Issues and solutions:...........................................................................................6
Reducing the human oracle cost:...........................................................................................7
Conclusion:................................................................................................................................8
References:.................................................................................................................................9
Student Id Student Name pg. 1

SEARCH-BASED SOFTWARE TESTING
Introduction:
The selected article is about the Optimization method of problems, Search-based
Software Testing in which different researchers have applied various optimization method to
solve the problems of high-level. Search-based Software Testing includes various algorithms
to test the tasks for analysing [4]. This article has helped to know various optimization
processes which serves functions for specific problems. Here the role of fitness function have
been mentioned which assists in finding better solutions for problems to complete within the
time limit [3].
The first objective for reviewing is to locate the body of the literature so that the
identification of different functions can be done. As there are many segments in the article of
the algorithms, every segment requires thorough study to identify the optimization methods.
Earlier which methods were used, how the optimization methods have been improved by
other researchers, will be analysed. This article is written by Phil McMinn and the content of
the article is methods that have been used in software testing and the approaches made by the
various researchers. The researchers have faced various issues while executing the testability
functions to find out the automated oracles, while optimizing and while aiming to reduce the
associated costs.
Discussion:
The purpose of the article is to focus on the automated software testing to find the
solutions. The concept of Search-based Software Testing was approached by Webb Miller
and Spooner, in which test data generation was involved. Various open problems have also
discussed in the article which will form the scope to work more to find optimization methods.
The important algorithms used for the optimization are, Simulated Annealing, Hill Climbing
and Genetic algorithms, these are based on random search methods [6]. Proper guidance has
been maintained to search for better solutions which can be termed as ‘Fitness function’, it
provides the way to evaluate the problems clearly and if the fitness function is followed then
optimization solution can be applied efficiently within correct time.
Student Id Student Name pg. 2

SEARCH-BASED SOFTWARE TESTING
The search-based algorithm follows the method of doing random search until the best
solution is achieved [8]. Although random search algorithms is not a good idea to implement
on bigger problems but if the number of inputs for test generation are less, then with the help
of fitness function solution can be achieved faster [12]. The two most important
requirements of the search-based algorithm is Representation, which involves the criteria of
the solution to be capable of being controlled by the algorithm. And another requirement is
Fitness function, which acts as a guidance to the problems [9]. For different problems
different fitness functions exist.
Main Optimization Algorithms:
The difference between the various random search algorithms, are: in Hill Climbing
algorithm random searches are done by following the local optimum solution whereas in
Simulated Annealing probability of finding solutions is determined. If the randomly chosen
algorithm does provide better optimization then it is accepted otherwise have to proceed
towards other random algorithm [2]. And the Genetic algorithm, global search method is
applied regardless of the local or neighbour solution, after implementing the global search
whatever best fitted solution is found is accepted [5].
Application areas with fitness functions:
The testing functions that have been applied with the help of fitness function in the
appropriate problem areas such as:
 Airbag used in cars which works with the help of sensors to detect the crucial
situations and inflate within seconds. In the sensors, electronic controller unit is
used which requires fitness function to find the execution time for the software
either of best-case or worst-case and this approach is known as Temporal Testing.
 Another application area is the parking controller which searches for appropriate
parking space and automatically controls the car to get parked without striking the
other objects [10]. For this functional testing, fitness function that is used is to find
the shortest distance to park but while evaluating the function faults got revealed
which could have led to collision but fitness function assisted in avoiding that,
Student Id Student Name pg. 3

SEARCH-BASED SOFTWARE TESTING
 Structural testing has been considered as the best option to apply in Search-based
algorithm, a structural test data can be generated in checksum routine for registry
numbers [7]. As a structural testing, a fitness function was approached by
Wegener with two metrics, first one was approach level and another one was
branch distance. In the approach level the targets are found and in the branch
distance metrics the input is scaled on basis of the satisfaction level favouring the
condition.
Fitness function seeks for optimal point for a problem, which helps the software
engineers to evaluate the optimization technique.
Highlighted Issues and solutions:
The techniques that were used in Search-based software testing have been interrupted
by some issues such as, lack of monitoring the execution environment of the software. If the
interactions with the associated operating system, file system is not given attention then the
execution may not work properly. These issues can be handled by generating test data after
which proper storing of the file is done to be read by the program that has been implemented
for the test. Since, fitness functions are based on random approaches this might happen that
proper guidance is not provided as an instance, ‘flag’ problem whose value is returned either
as false or true. And for this problem, testability transformation was applied in which various
versions of the program is tested and transformation is implemented accordingly. Moreover,
even the transformed functions can fail to provide solution for which pseudo-oracle
transformation have been proposed which helps in ensuring the outcomes to be identical of
both the transformed and original codes. McMinn introduced a transformation method to test
the reliability of the code.
Student Id Student Name pg. 4

SEARCH-BASED SOFTWARE TESTING
Reducing the human oracle cost:
To reduce the quantity of involved test cases in which the human evaluation is
required various fitness functions have been proposed to focus on the structural coverage and
also ‘whole coverage’ approach. Delta debugging was the best approach to identify the
statements in the code that causes inefficiency during the test case hence, the unit tests got
minimized and this one the quantitative angle of cost [1]. The quantitative cost also depends
on the size of the test cases such as, those are relevant to object oriented programs consisting
of many statements for which each statement necessary test cases are required.
The qualitative aspects were also focused, in which the test case are examined or
checked whether the test cases can would successfully do the comparison between the
transformed code and the original code. For handling the qualitative costs, initial point of the
search-based approach is checked on the basis of the domain knowledge. While working with
the domain knowledge is performed then the biased behaviour can be observed as it is the
recognizable field. To minimize the cost of human oracle, new test cases can be required to
be generated.
The example of calendar can be considered, in which the test cases that are involved
in this type of approach are generally recognisable [11]. Another method that is used in
developing the quantitative cost is extracting the program’s information and final one is
reusing of generated test data in different programs. Once the suitable functions have been
found then same functions can be used at the starting stages of the test data generation.
Search-based software testing offers the application of more than one fitness function.
The multi-objective search helps in finding optimal solutions for the new and complex
problems. The multi-objective search beats the technique of traditional methods to find out
the optimal solutions. Moreover, the traditional techniques have capability of doing only one
task. Other potential applications have also been found to serve best options which has helped
in minimizing the delivery time. As mentioned fitness function helps to get the outcomes
within time frame.
Student Id Student Name pg. 5

SEARCH-BASED SOFTWARE TESTING
Conclusion:
The report includes various searching-based algorithms which provides solution to the
problems. It has been observed that the ‘Fitness function’ is the most important factor to
properly implement the test data generation. For every singular problem relevant fitness
function have been applied to achieve the wanted outcomes. Search-based software testing
follows the random approach for every cases and it is essential that appropriate function is
applied. Fitness function shows the proper way to evaluate any sort of complex problem. To
approach the best method for proper test data generation fitness functions guides in
proceeding.
Various problems have been faced during test data generation of different programs
and proper solution through fitness function has been applied to the algorithms. The vital
algorithms for the random approach are, simulated annealing, hill climbing and genetic
algorithm, each algorithm follows the searching-based approach. According to the author of
the article optimization of the problems need to be searched properly to find the best solution.
To prove that various fitness function have been identified for each problem. With the
guidance of the fitness function the sustainability factor is maintained to solve the problems.
Student Id Student Name pg. 6

SEARCH-BASED SOFTWARE TESTING
References:
[1] Afshan, S., McMinn, P. and Stevenson, M., “Evolving readable string test inputs using a natural
language model to reduce human oracle cost”, In 2013 IEEE Sixth International Conference on
Software Testing, Verification and Validation (pp. 352-361). IEEE, 2013, March.
[2] Aksyonov, K. and Antonova, A., “Multiagent genetic optimisation to solve the project scheduling
problem under uncertainty”, International Journal on Advances in Software, 7(1&2), pp.1-19, 2014.
[3] Dave, M. and Agrawal, R., “Mutation Testing and Test Data Generation Approaches: A Review”, In
International Conference on Smart Trends for Information Technology and Computer
Communications (pp. 373-382). Springer, Singapore, 2016.
[4] Engelbrecht, A.P., “Fitness function evaluations: A fair stopping condition?”, In 2014 IEEE
Symposium on Swarm Intelligence (pp. 1-8). IEEE, 2014, December.
[5] Floudas, C.A. and Pardalos, P.M., “Recent advances in global optimization”, princeton University
press, 2014
[6] Goldenberg, M. “The heuristic search research framework”, Knowledge-Based Systems, 129, pp.1-3,
2017.
[7] Henard, C., Papadakis, M., Perrouin, G., Klein, J. and Traon, Y.L., “Multi-objective test generation for
software product lines”, In Proceedings of the 17th International Software Product Line Conference
(pp. 62-71). ACM, 2013 August.
[8] Kozeny, V., “Genetic algorithms for credit scoring: Alternative fitness function performance
comparison”, Expert Systems with Applications, 42(6), pp.2998-3004, 2015.
[9] Lodha, G.M. and Gaikwad, R.S., “Search based software testing with genetic using fitness function” In
2014 Innovative Applications of Computational Intelligence on Power, Energy and Controls with their
impact on Humanity (CIPECH) (pp. 159-163). IEEE, 2014.
[10] Pitangueira, A.M., “August. Incorporating preferences from multiple stakeholders in software
requirements selection an interactive search-based approach” In 2015 IEEE 23rd International
Requirements Engineering Conference (RE) (pp. 382-387), IEEE, 2015.
[11] Srivatsava, P.R., Mallikarjun, B. and Yang, X.S., “Optimal test sequence generation using firefly
algorithm” Swarm and Evolutionary Computation, 8, pp.44-53, 2013.
[12] Varshney, S. and Mehrotra, M., “Search based software test data generation for structural testing: a
perspective”, ACM SIGSOFT Software Engineering Notes, 38(4), pp.1-6, 2013.
Student Id Student Name pg. 7