This paper demonstrates an approach to optimize software testing by minimizing the expected cost with given software parameters of concern. Taking software testing process as a Markov decision process, a Markov decision model of software testing is proposed in this paper, and by using a learning strategy based on the cross-entropy method to optimize the software testing, this paper obtains the optimal testing profile. Simulation results show that the testing profile with the learning strategy performs significantly better than the random testing strategy with respect to the expected cost. Moreover, this learning strategy is more feasible and can significantly reduce the number of test cases required to detect and remove a certain number of software defects in comparison with the random testing strategy.