Optimized Branch and Bound for Path-wise Test Data Generation
Yawen Wang, Ying Xing, Yunzhan Gong, Xu-Zhou Zhang · International Journal of Computers Communications & Control · 2014
The increasing complexity of real-world programs necessitates the automationof software testing. As a basic problem in software testing, the automationof path-wise test data generation is especially important, which is in essence a constraintsatisfaction problem solved by search strategies. In this paper, the searchalgorithm branch and bound is introduced and optimized to tackle the problem ofpath-wise test data generation. The optimized branching operation is fulfilled by adynamic variable ordering algorithm with a heuristic rule to break ties. The optimizedbounding operation is accomplished by analyzing the results of interval arithmetic.In order to facilitate the search methods, the solution space is represented as statespace. Experimental results prove the effectiveness of the optimized branching andbounding operations, and show that the proposed method outperformed some othermethods used in test data generation. The results also demonstrate that the proposedmethod is applicable in engineering.