Research Of Automatic Test Case Generation For Complicated Programs

Software testing is the process of verifying program features during software development,which is the most important method to protect the quality of softwares.In the field of software engineering,an important research direction is the automated software testing.Automated test case generation is one of the key issues of automated testing.The growing scale and complexity of the programs has hindered the generation of test cases that meets the requirement of a high coverage.Therefore,it is necessary to study the automated test case generation techniques according to the characteristics of the program itself.A program structure consists of two aspects:the control structure and the data structure.The loop structure is a basic control structure that can lead to the explosion of the program path,which brings about two difficulties in the automated test cases generation:there are too many program paths to produce sufficient test cases in limited time;and the infeasible paths will affect the efficiency of test case generation.Data structure can be divided into basic data structure and complex data structure.During the process of program execution,basic data structure will not change its structure,only to change the value;in contrast,the complex data structure will not only change its structure,but also change the value.Therefore,the test case generation of the basic data structure only needs to analyze the value;the test case generation of the complex data structure needs to consider the structure and value at the same time.Character string is a commonly used data structure;the test case of the string can not be generated by traditional numerical test case generation tools because of its structured data model and functional operation manner.This thesis presents studies on the characteristics of complex programs,and proposes several techniques for the key issues of automated test case generation.The main work includes the following aspects:1)Heuristic guided hybrid path generation for program containing loops.The path explosion problem caused by program containing loops structure can lead to the difficulty of selecting a program path during automated test case generation.This thesis proposes a combinatorial strategy to alleviate the path explosion problem:classifying loops into different classes according to their relative positions to the target,combing static analysis and dynamic execution to perform path selection for different loop structures,and utilizing an objective function on offering guidance for the path exploration.This method solves the problem of path selection in the program that contains the loop structure in the automatic test case generation.2)Infeasible path detection based on code pattern and backward symbolic execution.Lots of program paths are proved to be infeasible,which leads to imprecision and low efficiency of program analysis.The loops in a program bring about large amount of infeasible paths which hinder the automated testcase generation.The immediate cause of path infeasibility is the contradiction of path constraints,whose distribution will affect the performance of different program analysis techniques.But there is lack of research on the distribution of contradict constraints currently.This thesis proposes a code pattern based on the empirical study of infeasible paths,the statistical result proves the correlation of the pattern with contradict constraints,and then develop a path feasibility detection method based on backward symbolic execution.The experimental results show that utilizing backward path feasibility analysis on such programs is more efficient than forward analysis.This work provides a significant improvement to infeasible path detection by applying the proposed approach on coverage testing as an auxiliary.3)Research on automatic test generation for string data type.Most object-oriented languages treat a character string as a primitive data type which is manipulated by string library functions.Most constraint solvers have limitations on their input constraints,such as strong restrictions on the expressiveness of constraints or lack of the ability to solve hybrid constraints.These limitations hinder applying automated constraint solvers on program analysis techniques for programs containing strings and string functions.This thesis proposes a constraint language which contains several primitive operations to precisely describe the constraints of commonly used string functions based on the character array model.The translated string constraints together with numeric constraints are then solved by a two-phase test generation procedure:firstly,a partial solution is obtained to satisfy the arithmetic constraints of the position variables,the solution is utilized to eliminate the string constraints to pure character array constraints;secondly,the pure array constraints are solved by an off-the-shelf Satisfaction Module Theory(SMT)solver for array-specific theory.The experimental results show that the integration of the proposed approach promotes the testing coverage of an existing testing tool.4)These techniques are implemented in a code test system called CTS and are evaluated by experiments.The experimental results verify the effect of the proposed methods on the improvement for automated test case generation.