The Algorithm to Solve Equation Constraints in Automatic Test Data Generation
Zhang Bo1), Xing Ying2), Gong Yunzhan1), and Jia Wei1)
1) (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876) 2) (Automation School, Beijing University of Posts and Telecommunications, Beijing 100876)
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.
constraint satisfaction problem; linear algebra; infeasible path; branch and bound