An Automatic Test Sequence Generation Method Based on Markov Chain Model

Software statistical testing, which draws test sequences based on the Markov chain usage, has been proved to be an effective strategy in improving software reliability. There are two main concerns while constructing test Markov chain in statistical testing of software, how to define a reasonable test adequacy criteria and how to generate test sequences both automatically and efficiently. Several strategies have been proposed in literatures to address these problems. However they are not as efficient as desired because of a couple of reasons upon our investigation. First of all, the existing test adequacy criteria are not able to guarantee the full path coverage for the Markov chain usage. Second, the current strategies on generating test sequences are lack of efficiency. Third, they are limited to deal with relatively small size of the Markov chain usage. In this paper, we resolve two main problems in statistical testing of software to meet high software reliability. We address an optimized test adequacy criteria with corresponding proof to guarantee the generated test sequences to cover the full path for the Markov usage Chain. Furthermore, we propose a novel deterministic greedy algorithm with faster convergence speed for constructing test sequences. We then explore applications of simulated annealing (SA), roulette as well as our greedy algorithm based on the optimized test adequacy criteria. Our experimental results show the advantages of our method in generating reasonable size of test sequences, and the ability of generating test sequences for cases with larger scale.