# Automatic Test Data Generation Using the Activity Diagram and Search-Based Technique
## 3 AutoTDGen Approach
### Automatic Data Flow Analysis and Test Data Generation
#### 3.3.2 Test Data Generation  
After the def-use pairs are automatically identified from the ADs of the SUT, the GA is used as a search algorithm to generate an optimized set of test data for satisfying the data flow coverage criterion. **Genetic Algorithms**: A basic GA starts with randomly initializing the population, which is a set of solutions. A fitness function is used to evaluate the fitness of an individual. The individuals are chosen based on their measured fitness scores. Then the selected individuals are going throw the process of crossover and mutation for mating and altering the offspring. The fitness evaluation, selection, crossover, and mutation steps are repeated until the stopping criterion is met or the maximum resources are spent [40]. A key aspect of generating test data using GA is designing a fitness function to determine how the test data generated by the GA fit the desired solution (the target def-use pairs). Thus, designing an appropriate fitness function to guide the search is the key to the entire search-based test data optimization technique. **Fitness Function**: In this paper, we focus on data flow coverage as the test coverage criterion, but our proposed technique is not limited to a certain test criterion. It can be generalized to any test criterion. In data flow-based testing, an individual test datum can satisfy more than one def-use pair (Table 1). Thus, to guide parent selection and evaluate how the test data generated by the GA cover the target def-use pairs, we designed a fitness function that rewards maximum coverage of def-use pairs. For example, if more than one def-use pair is reachable and subsumed by another def-use pair, the prefix guides the algorithm to reward the one that is not subsumed or dominated. To guide the search toward the target def-use pairs, we use the def-use pair coverage level (\(DUP_{CL}\)) and the guard condition distance (\(GC_{D}\)) for the fitness function. The \(DUP_{CL}\) is calculated based on the number of def-use pairs covered by an individual test datum, and the \(GC_{D}\) is calculated using the guard condition in the activity \(D_{N}\) (Definition 1). The guard conditions are value specifications that are commonly used in \(D_{N}\). The \(GC_{D}\) heuristic is used for test data generation and evaluates how close a decision in an activity is to being estimated as satisfied or not satisfied. For instance, if we consider a guard condition [id \(\geq\) 6], in a decision clause \"id\" with the value id = 2, the guard condition distance will be calculated as \(6-2+n\), with the number n \(>\) 0. The \(GC_{D}\) is normalized to guarantee \begin{table}
\begin{tabular}{c c c c} \hline \hline _Variable_ & _Def-Use Path Set_ & _Def-Use Pair Paths_ & _Prefix_ \\ \hline \multirow{4}{*}{Locks} & (1, locks) & [1, locks \(\geq\) 1, 3, 4, 5] & N \\  & (5, locks) & [5, 1 \(<\) locks \(\leq\) 70] & Y \\  & & [5, 1 \(<\) locks \(\leq\) 70, 7] & N \\ \multirow{4}{*}{Stocks} & (3, stocks) & [3, stocks \(\geq\) 1] & Y \\  & & [3, stocks \(\geq\) 1, 5, 6, 7] & N \\ \multirow{4}{*}{Barrels} & (3, barrels) & [3, barrels \(\geq\) 1] & Y \\  & & [3, barrels \(\geq\) 1, 5, 6, 7] & N \\ \multirow{4}{*}{Commissions} & (14, commissions) & [14, 312 commissions \&\& \\  & & commissions \(>\)15, 16] & N \\ \multirow{4}{*}{Sales} & & [7, sales \(\geq\) 1800] & Y \\  & & [7, sales \(\geq\) 1800, 9] & Y \\ \multirow{4}{*}{Sales} & (7, sales) & [7, sales \(\geq\) 1800, 9, 13, 14] & N \\  & & [7, 9, sales \(\geq\) 1000] & Y \\ \cline{1-1}  & & [7, 8, sales \(\geq\) 1000, 11, 13, 14] & N \\ \cline{1-1} \cline{2-4}  & & [7, 8, 10, sales \(\geq\) 999, 12, 13, 14] & N \\ \hline \hline \end{tabular}
\end{table} 
Table 1: An example of generated def-use pair paths. to maximize the def-use pair coverage as well as to ensure that all the def-use pairs are adequately covered. Some of the common normalization techniques for structural criteria like branch distance and their importance is discussed by [41].