  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.
