A Method Of Automatic Test Case Generation For CDC/MCDC Coverage Criteria Using Linear Fitting Technique

Testing is an important activity in software development,which is one of the frequently used approaches to assuring software quality.To meet the requirement of adequate testing coverage,testers need to spend a large amount of time and efforts in designing test cases.Automatic test case generation can automatically generate effective test cases for a given test coverage criterion,which can cut down the workload of testers and reduce the cost of software development.It is an important aspect of research on automatic testing techniques.The Condition Decision Coverage(CDC)and Modified Decision Condition Coverage(MCDC)are two frequently used white-box coverage criteria when testing safety-critical software.Due to the existence of nonlinear computation,the problem of test case generation of this kind has been proved to be an NP problem.Existing work mainly relies on Symbolic Execution and heuristic search based technology to explore the solutions which satisfy the constraints of the program.Symbolic Execution is limited to the ability of current constraint solvers which can't solve non-linear constraint effectively;the main problem of heuristic search based technology(e.g.,genetic algorithm and simulated annealing algorithm)is that their search interval is not extensible and the search effectiveness is affected by multiple parameters.Hence,finding the optimal parameter set for a given program is very difficult.The Component Linear Fitting method is also a heuristic search based method.Unlike symbolic execution and heuristic search based technology,it does not use fitness functions,but uses the characteristic that the condition in a program is a function of the program inputs.As a result,it can predict the solution of the problem in terms of the linear fitting functions about each input variable.The Component Linear Fitting method is capable of extending search space,handling non-linear constraints and solving floating point computations,while its parameters are easy to be set.Now it has been adopted in test case generation towards path-oriented coverage.The paper studies the test case generation technology for CDC and MCDC coverage criteria based on Component Linear Fitting methods,its main work includes the following aspects:· Towards the CDC and MCDC coverage criteria,we propose an interval extending method based on fitting functions on boundary intervals and a search mechanism based on variable intervals.Adopting these two technologies,we propose a test case generation algorithm towards CDC/MCDC test criteria,which is able to handle complex constraints,nonlinear conditions and floating-point conditions.It first sets a component of input vector as independent variable,then generates a group of inputs randomly to execute program under test.If the target condition statement is passed during an execution,then it records the corresponding points.These points recorded acting as samples are used to calculate the Component Linear Fitting function of the condition about the independent variable.The CLF uses the Component Linear Fitting function to profile a condition and predict the feasible inputs.The algorithm repeats executing the program under test,constructing Component Linear Fitting functions and predicting feasible inputs until solutions are found or the searching threshold is reached.· Design and implement a prototype tool-CLF-CDC,an Eclipse plug-in which can automatically generate test cases for C functions with respect to CDC coverage criterion.To evaluate the effectiveness and performance of CLF,we select 25 C functions as benchmarks which come from the math package:Numerical Recipes and other open source websites,and chose GA as the comparison algorithm.In addition,we use statistical methods to check whether the effectiveness and performance of two methods have significant difference.Experimental results show that the CLF is better than GA in effect;in particular,CLF can cover more "extreme conditions".Besides,for the performance,CLF is the same as the optimized GA,but CLF does not need the searching of optimal parameters.