Research On Test Data Generation And Input Interval Prediction Driven By Linear Fitting Functions

Ensuring correctness is base of high quality software.Testing is the most important technical means to ensure so:ftware correctness.Path-oriented testing focuses on path-oriented coverage criteria,generates test input to drive the program to execute along the target path,which can efficiently detect errors in the program.Automatic path-oriented testing can greatly improve testing efficiency and reduce its costs.One of the difficulties for path-oriented testing lies in how to solve non-linear and floating-point path constraints.The existing linear fitting functions driven method is based on dynamic program execution,which updates the linear fitting functions of in-put variables by dynamic execution information,then calculates the prediction interval,and finally suggests the input data for path constraints.Related work has shown that it can solve complex path constraints.However,constrained by the dynamic program execution method,there are some limitations,such as insufficient linear fitting func-tions information caused by code short circuit,influence of constraints order on solving efficiency,and massive IO overhead.This paper studies the parallel solving method driven by linear fitting functions,which is built on symbolic execution.The method first extracts path constraints using symbolic execution,then makes full use of the potential parallelism of linear fitting functions based solving method,and finally solves path constraints in parallel on the CUDA platform.At the same time,interval prediction method can be used to simplify and solve complex constraints.Based on existing linear fitting functions driven method,this paper studies the input interval prediction problem,and designs an input interval prediction method based on linear fitting functions.Specifically,the main contributions of this paper are as follows:· This paper proposes a path-oriented test data generation method driven by parallel linear fitting function approximation and solving.This method assigns independent CUDA threads with individual sample point,and realizes parallel runtime value cal-culation using the fact that runtime value can be computed independently.Taking the advantage of the independence of calculating linear fitting functions between any two adjacent points,the method allocates independent CUDA threads to real-ize computation in parallel.Considering the problem of thread waiting caused by branch differentiation in fitting function calculation,this method analyses the rea-son for branch differentiation caused by different fitting situations,and designs an optimization strategy to reduce branch by calculating the classification matrix.Ac-cording to the independence of predictive interval calculation,independent threads are allocated to perform parallel computation.Aiming at the independence of pre-dictive vector calculation,this method distributes independent threads to realize its parallelization.Meanwhile,in order to make full use of the parallel computing power,this method analyses the SIMT mechanism of CUDA,and proposes a thread scheduling strategy to dynamically adjust the predictive vector size.Based on the above technologies,a parallel solving method driven by linear fitting functions us-ing the CUDA platform is proposed.· This paper proposes an input interval prediction method based on linear fitting func-tions.Firstly,linear fitting functions can produce a large number of candidates.When a candidate interval is good enough and both ends of the interval satisfy the constraints,the predicted interval has enough precision.A prediction technique for generating input interval of a single variable from linear fitting functions is pro-posed.Next,according to the continuity of constraint functions,there are feasible input intervals in the input interval sequence.A multi-variable input interval pre-diction technique is proposed to refine the intervals by a large number of random sampling.Based on the above technologies,an input interval prediction method based on linear fitting functions is proposed.· This paper has implemented a prototype tool based on the proposed methods,and carries out three experiments.The PLFF Solver and the IIP Solver are implemented according to the parallel solving method and input interval prediction method.Firstly,the experimental results of10 benchmark programs from NRC and coral show that our parallel solving method covers 60%more paths and five times more cover-age efficiency than the existing linear fitting function method based on dynamic program execution.Then,this paper uses Concolic Walk,the best state of the art tool for concolic execution methods.The experimental results of 11 benchmark programs from CW show that our parallel solving method has a 9.8%coverage and three times coverage efficiency increase over the CW method.At the same time,the experiment shows that our method is complementary to the CW method.Combining the two methods,the path coverage of CW method can be improved by 12.7%.Finally,for the input interval prediction experiment,the experimental results of14 benchmark programs from GSL show that the input interval prediction method based on linear fitting functions can effectively generate the input intervals.