On Path-wise Automated Test Data Generation

Software testing is one of the most important techniques used to assure the qualityof software products at present. Many problems in software testing, such as statementcoverage and patl1 coverage, can be reduced to tlle path-wise test data generating problem,which will be referred to as Problem Q in this thesis and can be described ast given aprogram P and a path W in P, let the input space of P be D, compute x E D, suchthat when P executes on x, path W wiIl be traversed. It will improve the efficiency andqua1ity of software testing to so1ve Problem Q automatically.The essence of this problem lies in the deriving and solving of system of constraints.The obstacles ifl deriving system of constraints aIe how to analyze and reduce the state-ment components and data types of variables on W, and derive system of con8traints asconcise as possibIe. And the primary obstacle in solving system of constraints is how toprocess the nonlinear constraint(s) among them. Matiyasevie and E. J. Weyuker provedthat there is no general and effective algorithm to generate x for arbitrary P and W. Buturged by the practical applications, one proposed several category approaches to addressthis probIem.The progress of the studies on Problem Q is introduced in this thesis. The existingapproaches to address this problem are classified into fOur categories f random, static,dynamic, and heuristic. The representative methods in each category are introduced andanalyzed. The direction of research is also explored.Neelam Gupta et al proposed a method, which is referred to as the Iterative Relax-ation Method in this thesis, to address the above problem. By means of analyzing thestatic and dynamic data dependencies between the statements on [V, and constructingpredicate slices and input dependency sets, this method linearizes the predicate functionswith linear arithmetic representations. TherefOre it can only be used to generate test datafOr white--box testing.Neelam Gupta et al developed a constraint solving technique by using the LeastSquare Error Solution. Jon Edvardsson et al pointed out that the technique developedby Neelam Gllpta et al is neither complete nor terminationaI fOr W on which all of thepredicate functions with respect to the input variables are linear, and suggested usinglinear programming and linear (mixed) integer programming methods instead.The Iterative Relaxation Method is improved in this thesis by omitting the con-structions of predicate slices and input dependency sets. Furthermore, when the dividedII1differences are used to approximate to the derivatives that are coefficients in linear arithmetic representations, computing linear arithmetic representations is converted to compute predicate residuals completely, which needs to analyze neither static nor dynamic data dependencies between the statements on W. At this time, the improved method is more powerful to generate test data, and can be used for black-box testing. The improved method is more efficient to derive linear constraints.This thesis gives a model language and a moderately complete formal description which can be used to prove the properties of static and dynamic data dependencies , and defines the notions in the Iterative Relaxation Method formally. The program theories about the Iterative Relaxation Method and its improvement are investigated, whose results include: the generalization of the predicate slices proposed by Neelam Gupta et al to path-wise static slices, and the proofs of the soundness of the construction algorithm of path-wise static slices and the soundness of the improvement.A path-wise test data generation framework is proposed in this thesis, whose fundamental algorithm is the improved method. This framework adopts a constraint solver using linear programming and linear (mixed) integer programming methods for W on which all of the predicate functions with respect to the input variables are linear. For W on which there is nonlinear function(...