Research On Improvement And Extension Of The Linear Fitting Functions Based Solving Method For Complex Path Constraints

Path-oriented testing is an important testing technology. Acting as a core sup-porting technology, it is widely used in many test scenarios e.g. containing of fault localization, goal-oriented testing, memory leak detection and etc. Path-oriented test data generation focuses on generating test inputs that can drive the program to execute along a given path. Automatic test data generation can effectively reduce testing costs and enhance testing efficiency. In recent years, it is one of the most hot research topics in the field of software testing.The difficulty of the automatic test data generation lies in how to handle complex path constraints with non-linear constraints and floating-point computation. Currently, methods based on meta-heuristic search or dynamic symbolic execution have shown to be the most effective solutions. Facing with of a specific problem, the effectiveness of meta-heuristic search based methods is determined by parameter configurations while the randomness of initial values and search process can also bring uncertainty to the search result. The key issue in these methods is, how to set reasonable parameters to balance search accuracy and search time. When solving complex path constraints, dynamic symbolic execution based methods either replace symbolic terms with their concrete values or rely on domain-specific strong solvers. However, such simplification brings blindness and restricts the search space. The capability of constraint solvers is still not strong enough to solve real programs.The linear fitting functions driven method is based on dynamic program execu-tion, and can generate test data for programs with complex no-linear constraints. This method generates linear fitting functions using program inputs and the values collected at each branch function of a relational expression at the run time, and then derives fea-sible input intervals which can produce desired test inputs. The existing method driven by linear fitting functions still has some limitations, for example, search is insufficiency and the process of building fitting functions is relatively imprecise. The efficiency of existing method is not good enough to treat with big programs. In addition, paths with array inputs or cross module function calls cannot be treated by the existing method. To deal with the shortcomings and limitations above, this paper presents an improved linear fitting functions-based approach, which searches target input data more effec-tively, and can generate path-oriented test data for programs with array inputs or cross modular function calls. In detail, the primary contributions of this paper are the fol-lowing:· Propose an automatic path-oriented test data generation algorithm driven by im-proved linear fitting functions driven method. To overcome the shortcomings of the search strategy in existing method, this paper tries to search on more directions (input variables), and proposes a crossing search strategy on direc-tions of multi-variables. Furthermore, to take the advantage of multi-processors technology, this paper implements the above method using a parallel scheduler-workers model, and then gives an optimization strategy combined with program dependence analysis technology to reduce the time consumption. Considering the shortcomings in the process of building fitting functions, this paper firstly, discusses the predictive effect of existing fitting curves on neighbouring fitting intervals when there is no feasible interval in fitting intervals and then proposes some extension and refinement rules for the fitting intervals of a branch function of a relational expression. Finally, this paper presents an adaptive extension and refinement method for the search space of a path.· Extend the linear fitting functions based method for supporting array inputs and function calls. When generating test data for programs with array inputs, this paper obtains all of the array variable subscripts related to a target path under a specific program input using program instrumentation to avoid redundant search on a large amount of irrelevant array elements. The number of program path-s would increase rapidly when nesting some multi-layered function calls. This paper obtains the relevant path set for a target program position needed to be cov-ered, through separating compound expressions and ignoring irrelevant control flow structure. This method reduces the size of path space and the probability of infeasible paths, so as to improve the efficiency of generating test data set.· Develop a prototype tool implementing the proposed method, and carry out three experiments. Experimental evaluation on the 15 scientific computing programs indicates that these strategies proposed in this paper improve the covering effect with respect to path coverage criterion using linear fitting functions. Concol-ic Walk algorithm is one of the most effective test data generation methods for solving complex path constraints at present. On a corpus of 11 programs, com-pared to Concolic Walk method, the method proposed in this paper gains better covering effect at the cost of less time. Meanwhile, this method improves the coverage of two state-of-the-art test generators based on strong solvers signifi-cantly. This suggests that this paper’s method and other methods complement each other. By integrating our tool, other test generators can improve their a-bilities to solve complex path constraints. Experiment on the influence of three main parameters of the algorithm in this paper shows that, because of adopting an adaptive extension and refinement method, the search effect of this algorith-m is not restricted to the selection of initial values. The cross search strategy can improve the covering ability of this algorithm, and our tool can gain good coverage with rather small threshold.