Path-oriented Automatic Test Data Generation Driven By Component Linear Fitting Functions

Software testing is one of the most important and effective methods that can guar-antee software quality, it also has been the most principal mean used by industry to guarantee software correctness. Limited dy computing power, time and space re-sources, testing is not able to try all possible execution for a program. In practise, test adequacy criterions are applied to drive and evaluate test processes. For a given test adequacy criterion, how to generate a test data set which can drive the execution of a program to cover relevant program architectures is the most critical progress in software testing. At present, test data generation is usually completed manually, which is not only time consuming, but also difficulty to guarantee the validity of test data. How to automatically generate effective test data for a test adequacy criterion is one of the hot issues in researches of software testing.Path-oriented coverage test criterion is a white-box test adequacy criterion which is used wildly, it requires test data driving a program executing along a given path. It has been proved in theory that there is no effective numerical method that can gener-ate test data for any path in a program. Existing approaches for this problem can be categorized into static analysis approaches and program execution based approaches. Static analysis approaches have difficulty in handling nonlinear path constraints. Pro-gram execution based approaches are likely to trap in local optima so that feasible test data can’t be found. Both categories of these approaches have limitations in practice.Aim at effectively generating test data for path-oriented test adequacy criterion, this thesis propose a novel path-oriented test data approach technique based on program execution. By tracking program execution, runtime values evaluated by input data on decision nodes are collected and component linear fitting functions with these values are constructed to approximate constraints on decision nodes. Further more, feasible solutions for path constraint system are searched based on the component linear fitting functions so that feasible input data for a given path is generated. The approach in this thesis can handle simple conditions and complex conditions effectively. A prototype tool for C language program is developed with Java language adopting this approach and experiments are studied with the tool. The details of the research in this thesis are as follows:·Research on constructing component linear fitting functions based on program execution and then approximating constraints on decision nodes in a given path. Firstly, the normal form of a constraint on a decision node is discussed, then branch function is introduced to be the normal express of the numerical expres-sion in the normal form on a decision node. With program instrumentation, values of branch functions on decision nodes evaluated by test input vector are derived. Two vector are entered at one time and they are only different at values of one component variable. The component linear fitting function on the interval is derived by computing a line which passes through these two points.·Research on automatically generating test data for pathes with only simple con-ditional decision nodes driven by component linear fitting functions. Component linear fitting functions on decision points are used to construct constraint system for the relevant path. A solution of the constraint system is a possible input for the path. Then the program execute on the input, either the path is covered, or the component linear fitting functions on decision nodes are revised base on re-sult of the execution and a new constraint system is derived to compute a new feasible solution. Component variable input domain enlargement is drawn into the progress in case of trapping in local optima.·Research on automatically generating test data for pathes with complex condi-tional decision nodes driven by component linear fitting functions. Simple con-ditions in a complex condition which are unsatisfied are added into constraint system one by one for a solution until a solution of the constraint system can satisfy the whole complex condition. ·A tool for path-oriented automated test data generation is developed by adopting the approach in this thesis. Several programs from a numerical computing pack-age NRC++is studied by experiments and compared to random test generation approach. The study indicates that the approach in this thesis is more effective in handling nonlinear constraints and local optima.