The Algorithm to Solve Equation Constraints in Automatic Test Data Generation

This paper proposes the branch and bound algorithm that integrates the method of equation dealing to solve equation constraints in automatic test data generation. Firstly, the method in linear algebra that judges whether a linear equation set is solvable is introduced to the branch and bound test data generation framework. Secondly, branch and bound algorithm that integrates the method of equation dealing is proposed to support various types of variables. Finally, equality constraints are divided into three categories: unsolvable, multiple solutions and single solution that included all conditions. Experimental results show that, the proposed algorithm can not only detect a part of the infeasible path, but also reduce the time consumption of test case generation as well as increase coverage. The testing on large projects and the comparison experiment with the open source constraint solver Choco show that the algorithm can improve the testing efficiency.