A Random Walk Based Algorithm for Structural Test Case Generation
This work addresses the expensive process of structural testing in software development, offering an incremental improvement over existing methods.
The authors tackled structural test case generation by proposing WalkTest, a random walk-based algorithm that sorts test goals by solution costs, achieving better running time and coverage rates than random test and tabu search in experiments on condition-decision coverage.
Structural testing is a significant and expensive process in software development. By converting test data generation into an optimization problem, search-based software testing is one of the key technologies of automated test case generation. Motivated by the success of random walk in solving the satisfiability problem (SAT), we proposed a random walk based algorithm (WalkTest) to solve structural test case generation problem. WalkTest provides a framework, which iteratively calls random walk operator to search the optimal solutions. In order to improve search efficiency, we sorted the test goals with the costs of solutions completely instead of traditional dependence analysis from control flow graph. Experimental results on the condition-decision coverage demonstrated that WalkTest achieves better performance than existing algorithms (random test and tabu search) in terms of running time and coverage rate.