Research On The Algorithms And Experiments Of Automatic Test Case Generation Based On Branch And Bound

As a basic problem in software testing (including white-box testing and black-box testing), path-wise test case generation (denoted as Q) is of special importance, because the control-flow testing and data-flow testing in white-box testing as well as some problems in black-box testing can all be summarized as Q. Q is described as:given a program P and a path W, if the input space of P is D, it is required to solve out x, x∈D, to make sure that when executing P with x as an input, the path traversed is W. The essence of Q is constructing and solving the constraint system.Constraint solving is a traditional research topic in artificial intelligence. Many problems, including Q, can be summarized a constraint-solving problem. But Plenty of problems in testing is NP-hard, and even undecidable, making it a tough job to solve the problem within acceptable time limit. Therefore, path-wise test case generation is transformed into such a problem: how to transplant the methods in constraint solving into testing and make testing more efficient.Funded by the National Grand Fundamental Research863Program of China (No.2012AA011201), the National Natural Science Foundation of China (No.61202080), the Major Program of the National Natural Science Foundation of China (No.91318301), and the Open Funding of State Key Laboratory of Computer Architecture (No. CARCH201201), and based on the abstract memory model in CTS (Code Testing System), this paper studies the problem of path-wise test case generation by constructing an efficient constraint solving engine. The work of this paper includes the following aspects. (1)The constraint solving framework based on branch and boundPath-wise test case generation is in essence a constraint satisfaction problem, which is solved by a proper search or optimization algorithm. As the global search algorithm, branch and bound provides flexible backtracking mechanism, able to reach the higher level of the search tree when no more local solution can be found, making the visited nodes as few as possible. But the backtracking operation increases the complexity of the algorithm, so the extended leave nodes should be determined by a proper ordering rule. It is also required to find a feasible solution or determine the infeasibility as soon as possible, and to prune branches as many as possible after finding a solution. State space search is also introduced to facilitate the implementation of the search algorithms.(2) The initial domain reduction and irrelevant variable removal based on program slicingAccording to the characteristics of symbolic execution, control flow graph and interval arithmetic, the slicing is accomplished from two aspects: the set of related variables and the path condition. The values of variables in the same expression influence each other for the satisfaction of the expression. Path condition is the data flow value of the path branches in the process of interval arithmetic. The information about the expressions related to each variable can be obtained through program slicing, and then a mapping dictionary between variable and the initial domain value is established. By retrieving this dictionary, the initial domains of variables can be reduced without eliminating part of the feasible solutions. To the path to be traversed, not every variable will be responsible whether it is traversed or not. Using program slicing, the variables related to the path to be traversed can be abstracted before state space search, and those irrelevant can be removed out of the search space, thus reducing the complexity of the algorithm greatly.(3)Identification of infeasibility and search tree pruning based on iterative interval arithmeticBecause interval arithmetic is iteratively descendent, the initial condition for each round of interval arithmetic is just the result of last round of interval arithmetic. So in the current round of interval arithmetic, the initial condition contains the result of last round of interval arithmetic and it serves as the constraint in this round. If at a certain step, the result reaches beyond the initial condition, the result will be eliminated. The iteration finally goes stable, and reaches the fix points between two rounds of interval arithmetic. Besides, iterative interval arithmetic identifies infeasible paths in advance before the search begins, saving the labor that will be consumed in the following search steps.(4) The permutating mechanism for free variables based on the ranks of variablesA sequence of free variables is first determined by remaining domain sizes, because this can minimize the search tree. But when there are variables that are of the same domain size, this rule will lose effect and a complementary strategy is required to break the tie, namely, the variables with the same domain size should be permutated by ranks. Ranks are determined by the heuristics of interval arithmetic that the earlier a variable appears on a path, the greater influence it has on the result of interval arithmetic along the path. Quicksort is utilized when permutating variables according to remaining domain size and returns a sequence as the result. If there are variables whose domain sizes are the same as that of the head of the sequence, then the ordering by rank is under way, which will terminate as soon as different ranks appear.(5) Heuristic initial value selection strategyFor the sake of both the diversity of test cases and efficiency, the initial values of variables are selected after the domains where they are selected are reduced heuristically. Based on symbolic execution and interval arithmetic, the expressions related to each variable can be abstracted, and then the properties of the variables can be analyzed. From the aspect of satisfying constraints, the variables in each expression are divided into three groups: positive variable, negative variable, and neutral variable. And from the aspect of satisfying constraints, the variables along the path are also divided into three groups:positive variable, negative variable, and neutral variable. The properties of variables along the path are based on the statistical information of each expression along the path. After determining the properties of variables along the path, the domains where their initial values are selected can be reduced accordingly.(6) The hill climbing strategyAs a local search algorithm, hill climbing is fast-converging and easy-to-implement, however it is apt to be trapped into local optima. Test case generation does not demand a global optimal solution, so hill climbing is introduced for searching the local solution. The objective function is properly defined to make fast-convergence when there are solutions and quit quickly when there are no solutions. Hill climbing exploits its advantage under the branch and bound framework.The branch and bound framework and the acceleration strategies proposed in this paper reach high coverage when testing typical benchmarks and some real projects. To linear programs, the search is basically backtrack-free. Hill climbing functions well for strict constraints even equations.