{'fraction_non_alphanumeric': 0.028318489680550372, 'fraction_numerical': 0.012585995413577942, 'mean_word_length': 4.443251088534107, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Test Case Generation for Data Flow Testing using Cuckoo Search Algorithm

Software testing consumes the major portion of the total efforts required for software development. This activity is very time consuming and labor intensive. It is very hard to do testing in optimal manner. In this paper a new approach is proposed, which uses the nature inspired stochastic algorithm called Cuckoo Search Algorithm (CSA) for the automatic generation of test data for data flow testing. This approach considers all def-use as test adequacy criteria. For assistance to CSA in the state space a new fitness function is also proposed by using the concept of dominator tree and branch distance in a CFG. To validate the proposed approach experiments are carried out on 10 benchmarked programs and findings are contrasted with earlier work done in this domain. Further in order to prove that proposed approach performs better than the above mentioned approaches a statistical difference test (T-test) is also performed.


I. INTRODUCTION
Software testing is one of the most critical steps in the life cycle of product development and consumes the major portion of the total efforts required in the development of software. This phase includes the identification of defect as many as possible. Software testing requires approximately 50% of total efforts. These efforts are time, money and man power. Software testing can be partitioned into two classes: functional and structural testing. Functional testing is also referred to as black box testing whereas structural testing is referred to as white box testing [1] [2]. Structural testing has better defect exposure capability compared to functional testing [3]. Automatic generation of test cases can reduce these efforts. Nature-inspired algorithms were used for this purpose in recent years [4]. The main idea behind this approach is automatic generation of test data, from the program input domain that satisfies the testing adequacy criterion. This testing adequacy criterion is represented in the form of fitness function [5]. In automatic generation of test cases most difficult task is the selection of test adequacy criterion from various criteria available in the literature [6].
This research article presents a new Cuckoo Search algorithm based approach for the automatic generation of test data for data flow testing. For assistance to CSA in the state space a new fitness function is also proposed by using the concept of dominator tree and branch distance in a CFG. The outcomes accomplished utilizing the proposed approach are  [10]. In the following sections, the remaining paper is arranged. Section II provides an overview of certain related work, section III gives background knowledge of the proposed work, section IV discusses the proposed approach, section V discuss the results gain from experiments and last section VI gives conclusive remarks on the work done and the results achieved.

II. RELATED WORK
Automatic test case generation for a program is very challenging task. In last decade various researches worked in this field and used various meta heuristic based search algorithm. Simulated annealing is used by [11] for pair-wise testing , by [12] for automated program flow testing, by [13] for test case generation for path testing. Genetic Algorithm have been used in [14] for test case generation for path testing, in [15] for objected oriented program using UML modeling, in [16] for regression testing. For the prioritization of test cases it is used in [17]. Particle Swarm Optimization is used in [18] [19][20] [21] for data flow testing. Ant Colony Optimization is used [22][23] [24]. Firefly optimization algorithm have been used in [24][25] [26]. A CSA based frame work is also proposed in [27].

A. Control Flow Graph
A control flow graph (CFG) is a graphical depiction of computation flow of a program during the execution of the program. CFG is a directed graph in which node represents the basic blocks of the program and edge denotes the control flow paths. There are two special nodes are also there, these are entry node and exit node. Entry node is used to enter in the CFG and exit node is used to leave the CFG. Fig. 1 shows the CFG for the triangle classification program Fig. 2.

B. Data Flow Testing
Data Flow testing is one of the types of structural testing. A structural testing requires access to internal structure of the program. It center around the definition and uses of the variables defined and used at different places in program. This testing is used to examine the behavior of variables throughout the program and ensure that there is no error causes by the variables. Rapps [28]  In these criteria all uses criteria is most effective. As per Jorgensen [29] there may be following types of anomalies due to improper utilization of variables in the program. First is a variable is defined but never referenced in the program. Second is a variable is referenced but never defined and last is variable is defined multiple times before it is referenced. For data flow testing a program is converted into a CFG. In the CFG following types of nodes and paths are identified. a) Definition Node: For a variable v, a node is called definition node if variable v is is defined in the corresponding node in the CFG. b) Use Node: For a variable v, a node is called use node if variable v is used in the statement corresponding to that node. The use node may be either computation use node (c-use node) or predicate use node (p-use node). c) Definition use Path: For a variable v definition use path (du path) is the path between the definition node v and the use node of v. d) Definition Clear Path: A definition clear path for a variable v is a path where variable v is not defined again on any node on that path.

Fig. 1: CFG for Triangle Program Classifier
For data flow testing, testing adequacy criteria may be testing of all definition, testing of all uses and testing of all du paths. In testing of all definition for a variable v such paths are find out which include at least one use of variable v. In testing of all uses for a variable v , at least one path is find out for every definition of v to every use of v. The test all du path is the most important data flow testing technique. In this all du path for a variable v are tested. Table  1 shows the definition nodes and Table 2 shows the all du paths of the triangle classification program Fig. 2.

C. Dominator Tree
In a CFG a node n1 dominates another node n2 if each path from start to n2 includes n1 node. By using above concept a dominance relationship can be established, which leads to a dominator tree of the CFG [30]. Fig. 4 Shows the example program's dominator tree.

D. Cuckoo Search Algorithm
Cuckoo is one of those species, which used brood parasitism for reproduction. Cuckoo lay its egg in such nests in which host bird laid its egg recently and color and texture of host bird's egg's resembles with cuckoo's egg [31]. The eggs laid by the cuckoo might be distinguished by the host bird, in such case host birds either relinquish the nest and make another nest elsewhere or push out cuckoo's eggs from the nest. In a large portion of the cases, cuckoo eggs develop earlier than host bird's eggs, and once cuckoo chicks emerge from the egg, it forces other eggs out of the nest by following its instinct. This cuckoo chick activity increases the chances of survival and gives the host bird's larger share of food. This behavior of cuckoo species is simulated by the [32] in 2009 and converted into an algorithm which may be used for solution of optimization problems. In this algorithm a cuckoo choose a nest randomly to lay its egg from a pool of nests and lay only single egg at once. The nest which has highest quality of eggs will be used in future generations. There is a probability Pa [0,1] by which egg laid by the cuckoo is identified by the host bird. In this algorithm at any particular time of instance, eggs that are already in the nest represent the solutions of the problem and egg of the cuckoo laid recently represents the new solution. If the cuckoo solution is better than among available solutions in the nest, worst solution from the nest is replaced by the cuckoo solution. Fig. 5 shows the CSA algorithm and Fig. 6 shows its corresponding flow chart. From the above discussion it is clear that CSA is meta heuristic based optimization algorithm. For simplicity in CSA [32] used following three simple rules in the CSA algorithm.
1. In a randomly selected nest, each cuckoo lays only one egg at a time.
2. The nest having best quality of eggs from the set of available nests will be used in future generation.
3. The host bird can identify the cuckoo's egg by probability Pa [0, 1]. In this case, the host bird can leave the nest or may get rid of the cuckoo egg.
X.-S. Yang and S. Deb [32] suggested that CSA quality can be improved with Le vy flight rather than random walking. Le vy flight is more beneficial for the exploration of the state space because it has longer step length in long run [33].
There is a foraging activity for various animals and insects in nature. It can be demonstrate using Le vy flight. Le vy flight is described as a random walk based on a heavily trailed probability distribution. It is an improvement over brawny movement. This behavior of Le vy flight is very beneficial in exploration of the state space of various types of optimization problems [34] [35]. Let us say a new solution is represented by X t 1 by a cuckoo i using Le vy flight using equation 1 can be written.
xi(t+1)= xi(t)+α⊕Le´vy(λ) (1) Here α denotes the step size and its value must be positive and can be scaled as per requirement of the problem of interest. In most of the cases its value is equal to 1. The symbol ⊕ is to represent entry wise multiplication like in PSO and a random walk is given by Le vy flight. The random move is taken using the Le'vy distribution equation 2.

IV. PROPOSED APPROACH
The proposed approach works in two phases. In the primary stage static analysis of the program under test is done, designing of the fitness function, program is then instrumented and finally def-use paths are extracted from the program. In the second stage CSA is used to generate test cases for the program. The designed algorithm accepts the instrumented program in the form of CFG, CFG's dominant tree, def-use paths to be taken as inputs. Fig. 7 shows the proposed algorithm and Fig. 8 shows the corresponding flow chart.

A. Fitness function
In the search based optimization techniques fitness function is very important. It plays a very crucial role in and used to provide the guidance to search based technique and helps in exploration and exploitation of the problem's state space. This function depends upon nature of the problem and technique used and directly affects the performance of the technique used. The proposed fitness function is designed for data flow testing and uses criteria of all uses as the criterion for evaluating the data flow test. A du-path may not has a concrete path between definition node and use node un the CFG so it is considered as node to node function [36], so a du-path coverage is converted into two goals. The first goal is to reach the node of use and the second goal is to reach the node of use. The covered du-path must not contain any killing node. The proposed fitness function uses the concept of dominance tree, branch distance and concept of closeness level (CL).
For a du-path let u denotes the definition node and v denotes node of use, the fitness value of test case (tc) for a variable var is can be calculated using equation number 3 and 4.

B. Branch Distance
Branch distance is used to calculate the real path closeness from the planned path [37]. Branch distance is calculated on that node which has critical branch and it uses values of variable and constants involved in the predicates used at that node. Branch distance is a minimization function it gives the value zero if the target node is reached and in other cases it is calculated as shown in the Table 3 for different types of predicates value [38]. The distance of the branch is usually within the limit [0,1]. Modified branch distance bd(x,tc), where x corresponds the target node and tc denotes the test case in the current population is calculated using equation 5 [39].

V. EXPERIMENTAL SETUP AND ANALYSIS
The proposed approach is compared with the random test data generator, Genetic algorithm based approach proposed by the [7] and [8], and PSO based approach proposed by [9]. For the validation of the proposed approach widely used benchmarked programs [8], [3], [10], [9] are used. Table 4 shows the details of these programs..

A. Performance Evaluation Parameters
For the comparative analysis of efficiency and effectiveness of the CSA based approach are compared with random search technique and [7] [8] [9] following three evaluation parameters have been used and algorithm parameters setting are shown in the table 5. For comparative analysis of the above mentioned approaches, sizes of populations considered are 10, 15, 20 and 30. Table 5

B. Results&Discussion
Experimental results of the proposed work and the approaches used by the [7], [8], [9] are shown in the tables 5-8 and figures 9-12 and following study questions are answered here. RQ1: What is the efficacy of the proposed approach in achieving 100% data flow coverage and generation of test cases?
From the experimental results of all the approaches it can be concluded that CSA performs better than the other approaches by using the new branch distance based fitness function. Although for small size population (size 10) CSA is not achieving 100% data flow coverage, but it gives 100% coverage in rest three population sizes. In other approaches random search's performance is worst.
RQ2: How beneficial is the recommended fitness in CSA?
The CSA-based approach reached 100% data coverage in a minimum of generation compared with other approaches on benchmarked programs. For the calculation of average number of generations 100 experiments are done for each benchmarked program.
RQ3: What is the effectiveness of the proposed approach in generation of optimized test suite?

C. Statistical Analysis
To demonstrate the improved quality of the proposed solution over other approaches used in the [7], [8], [9], a statistical difference test called T-test has been used. In this analysis average number of generation, average percentage of coverage and average success rates are considered after performing 100 repeated trials on each benchmarked programs. For the T-test following three null hypotheses are framed and T-test results are shown in the tables 9-11. H1: The approach based on the CSA is not much different than the random search and the methods used in the [7], [8], [9] with respect to ANG.
H2: The approach based on the CSA is not much different than the random search and the methods used in the [7], [8], [9] with respect to APC.
H3: The approach based on the CSA is not much different than the random search and the methods used in the [7], [8], [9] with respect to ASR.
For the null hypotheses H1, p value is smaller than 0.05 for all programs except than program 4 in the CSA Vs Random Search, so we reject the hypotheses and claims that performance of CSA based approach is better than the random search technique with respect to ANG. For CSA Vs [7] value of p is smaller than 0.05 for eight programs, in this case we can also rejects the hypotheses and claims that performance of CSA based approach is better than the [7] with respect to ANG. For CSA Vs [8] and CSA Vs [9] value of p is smaller than 0.05 for seven programs, in this case we can also rejects the hypotheses and claims that performance of CSA based approach is better than the [8] and [9] with respect to ANG.  For the null hypotheses H2, p value is smaller than 0.05 for all programs, for the CSA Vs Random Search and CSA Vs [7], so we reject the hypotheses and claims that performance of The approach based on CSA is better than random search technique and [7] with respect to average coverage achieved. For CSA Vs [8] value of p is smaller than 0.05 for nine programs, in this case we can also rejects the hypotheses and claims that performance of CSA based approach is better than the [8] with respect average coverage achieved. For CSA Vs [9] value of p is smaller than 0.05 for seven programs, in this case we can also rejects the hypotheses and claims that performance of CSA based approach is better than the [9] with respect to APC. For the null hypotheses H3, p value is smaller than 0.05 for all programs, for the CSA Vs Random Search and CSA Vs [7], so we reject the hypotheses and claims that performance of The approach based on CSA is better than random search technique and [7] with respect to average success rates. For CSA Vs [8] value of p is smaller than 0.05 for eight programs, in this case we can also rejects the hypotheses and claims that performance of CSA based approach is better than the [8] with respect average success rates. For CSA Vs [9] value of p is smaller than 0.05 for six programs, in this case we can also rejects the hypotheses and claims that performance of CSA based approach is better than the [9] in majority of cases with respect to ASR

VI. CONCLUSION
Use of nature inspired algorithms in the field of test case generation for program/software is now getting attention from the researcher community. Various nature inspired algorithms GA, PSO, ACO etc are used for test case generation and prioritization by considering different testing adequacy criterion. Data flow testing received a very little attention from the researchers. This paper uses Cuckoo Search Algorithm to generate optimal set of test suite for data flow testing. The test adequacy criterion selected here is all-uses criterion. For the guidance of the proposed approach in the search space a new objective function is designed which uses concept the dominance path in the CFG and branch distance. Experiments were carried out on 10 benchmarked programs to confirm the proposed approach and results are compared with earlier work done in this domain. For the comparison three performance parameters, average number of generations, average percentage of coverage achieved and average success rates are used. Further in order to prove that proposed approach performs better than the above mentioned approaches a statistical difference test (T-test) is also performed. Results of this test clearly indicate that proposed approach is significantly better than the others. In future this new approach can be applied on some industrial programs.