A Stochastic Combinatorial Optimization Model for Test Sequence Optimization

Abstract

Traditional FSM (finite state machine) based test sequence generation methods have three problems: 1) fake test results may occur; 2) unnecessary repetitive tests may exist; 3) actual test coverage rate could be low. These problems are mainly because of the dependences existing between transitions of test sequences. In this paper, to solve these problems, we defined a stochastic combinatorial optimization model to describe the test sequence generation problem from the dynamic viewpoint. Meanwhile, a recursive algorithm is proposed to give one optimal solution for the test sequence generation. This algorithm uses the weighted finite state machine model for the software being tested. At each test decision time, a test sequence will be generated from this model. After the execution of one test sequence and fault detecting, the weight value of this model will be updated. Simulation results show that the effective test efficiency and test coverage rate are evidently increased using our method. Especially, the fake test results are much less than transitional methods.