## 2 Theoretical Background  
### Basic Concepts  
In this paper, we use a dynamic approach to automatic test data generation, which is based on actual execution of a SUT, dynamic data flow analysis, and fitness function optimization. Test data is developed using actual values of input variables. When the program is executed on some input data, the program execution flow is monitored. A control flow graph (CFG) of the program under testing is a directed graph \(\text{CFG}=(V,\ R,\ v0,\ vE)\), where \(V\) is a set of graph nodes, \(R\) is a subset of cartesian product \(V\times V\) determining a binary relation on \(V\) (a set of graph edges), \(v0\) and \(vE\) are, respectively, unique entry and unique exit nodes \(v0\in V\), \(vE\in V\). For the sake of simplicity, we restrict our analysis to a subset of structured C-like programming language constructs, namely: sequencing statements (for example, assignments), conditional statements (_if-then-else_), cycle statements (_for_ and _while_). A node in \(V\) corresponds to the smallest single-entry, single-exit executable part of a statement in P that cannot be further decomposed. A single node corresponds to an assignment statement, input or output statement, or the <<expression> part of an _if-then-else_ or _while_ statement. An edge \((v_{i},\ v_{j})\in R\) corresponds to a possible transfer of control from the node \(v_{i}\) to the node \(v_{j}\). The edge \((v_{i},\ v_{j})\) is called a branch. Each branch in the CFG can be labeled by a predicate, describing the conditions under which the branch will be traversed. An input variable of SUT is a variable \(var_{i},\ i=\overline{1,N}\), which appears in an input statement, e.g., \(read(var_{i})\), or it is an input parameter of a procedure. Input variables may be of different types, e.g., integer, real, Boolean, etc. Let \((var_{1},\ var_{2},\ \ldots,\ var_{N})\) be a vector of input variables of the SUT. The domain \(D_{i}\) of input variable \(var_{i}\) is a set of all values which \(var_{i}\) can hold. By the domain \(D\) of the SUT we mean a cartesian product \(D=D_{1}\times D_{2}\times\ldots\times D_{N}\), where each \(D_{i}\) is the domain of input variable \(var_{i}\), i.e., a set of all values that \(var_{i}\) can hold. Thus, a SUT input is a single point in the \(N\)-dimensional input space \(D\). A path \(P\) in a CFG is a sequence of nodes \(P=\left\langle v0,\ v_{i_{1}},\ \ldots,\ v_{i_{k}}\ldots,\ vE\right\rangle\), such that \(v0,vE,v_{i_{k}}\in V\), \(\left(v_{i_{k}},\ v_{i_{(k+1)}}\right)\in R\). A path is feasible if there exists a SUT input for which the path is traversed during program execution, otherwise the path is infeasible. The maximum goal of automated test data generation problem is to find the so-called test case, being a set of the SUT inputs \(\left\{x_{1},\ x_{2},\ \ldots,\ x_{m}\right\},\ x_{i}\in D\), on which the whole variety of feasible SUT paths will be traversed. This problem can be solved gradually. One can initially formulate a partial purpose of finding one SUT input on which a given path \(P\) will be traversed. By sequentially choosing all possible SUT paths (or a subset of the most critical paths), one can iteratively find a test case that provides the greatest path coverage. In order to solve the problem of finding a SUT input for a given path \(P\), various optimization methods can be used. For example, in [29], the GA is successfully applied. In this case, as a fitness function it is reasonable to use a weight function that assigns nonzero weights for those nodes or branches of CFG along which the considered path \(P\) passes, and zero values for those nodes or branches along which path does not pass. For example, in [29], to solve the above problem, a function is used of the following form  
\[F(x)=\sum_{j=1}^{n(x)}w_{j}(x), \tag{1}\]  
where \(w_{j}(x)\) are the nonzero weights corresponding to the path of the CFG generated by the input value \(x\in D\); \(n(x)\) is the number of statements (or branches) covered by the path.