Research On The Technology Of Automatic Test Data Generation For Path-oriented Criteria Using Linear Fitting Functions

Testing is the most essential and effective technique for assuring software quality.The main technical challenges that the testing technique faces with is how to improve the effectiveness of testing and reduce the costs of it when dealing with software sys-tems of large scale and high complexity.Testing automation techniques is the main approach to settling the problem,where the techniques for automated testing input generation can greatly reduce the manual intervene and achieve higher coverage by automatically generating testing inputs for given testing criteria,thus is an important research direction in the literate.The path-oriented test adequacy criteria is one of the most widely used and ef-fective criteria in practice.The problem of generating input for a given path can be transferred to the satisfiability problem of constrained systems,which has been proved in theory as a NP-complete problem.There exists no feasible method that can solve arbitrary constraint systems with non-linear constraints.At present,research on the problem focuses on how to search the input space so as to find the solutions to the constraint system,among which methods based on genetic algorithm and simulated annealing algorithm are proved to be very effective.However,methods of the two kinds have apparent limitations:They both requires the solutions to be included in the initial search domain;the effectiveness of searching heavily depends on the parame-ters of the algorithm;the searching process consumes huge computation.Approaches based on component linear fitting functions can non treat paths associate with com-positive constraints.The algorithm is inadequate for handling real programs and its effectiveness is lack of experimental proof.To solve these problems above,we present a program execution based approach driven by component linear fitting functions,which is effective for nonlinear and com-pound constraints,and is not limited to the initial search domain.This approach dosen't need to encode the inputs,either.Here,component linear fitting functions built on in-puts and values at decision points,are used to approximate constraints.They drive the search to reach constraints' solutions by calculating feasible intervals.In detail,the main contributions of this paper include:· Present a test data generation technology for compound constraints based on component linear fitting functions.We can calculate the approximate feasible intervals of inequalities constructed by branch functions in a path.In particular,when dealing with compound constraints,we need to analyze the logical rela-tions and calculate the feasible intervals gradually.For a target path,a feasible input should satisfy all the constraints at the same time.We constructed the com-ponent linear fitting functions of every branch function at first,and then calculate the approximate feasible intervals step by step based on them.We also proposed a expand strategy of feasible intervals based on boundary intervals.Eventually,we can generate feasible inputs from these intervals..Design a path-oriented test data generation approach driven by component linear fitting functions,which can generate test data for paths with compound con-straints.This approach starts with two random inputs,then modify these in-puts gradually through execution results.Specifically,it will check every input component iteratively using the best inputs generated from previous component.Eventually we will generate a feasible inputs for target path or mark it as infea-sible.· Develop a prototyping tool based on our method and conduct two experiments on 35 real programs selected from the mathematical package Numerical Recipes at the full input space and given input interval respectively,which compares the effectiveness and speed with two methods based on genetic algorithm and sim-ulated annealing algorithm.The experiment demonstrates that our approach is able to generate effective testing inputs for paths with compositive constraints and non-linear constraints.Its algorithm can driver the searching process to ex-pand its search domain very efficiently.It also shows that our method provides better capabilities of testing input generation,as compare the two methods,for the programs of small-scale,it achieves the same efficiency;for the programs of middle-scale,it provides higher path coverage and less execution time;for the programs of large-scale,it can achieve the similar path coverage in less time.