Abstract: The application of Markov train model in random program testing is discussed in this paper. Having established the Markov usage model and Markov testing model respectively, the algorithms to evaluate testing completeness and to estimate mean failure frequency are proposed. Their availability and correctness have been validated in testing.