Optimal software testing in the setting of controlled Markov chains

The controlled Markov chains (CMC) approach to software testing treats software testing as a control problem, where the software under test serves as a controlled object that is modeled as controlled Markov chain, and the software testing strategy serves as the corresponding controller. In this paper we extend the CMC approach to software testing to the case that the number of tests that can be applied to the software under test is limited. The optimal testing strategy is derived if the true values of all the software parameters of concern are known a priori. An adaptive testing strategy is employed if the true values of the software parameters of concern are not known a priori and need to be estimated on-line during software testing by using testing data. A random testing strategy ignores all the related information (true values or estimates) of the software parameters of concern and follows a uniform probability distribution to select a possible test case. Simulation results show that the performance of an adaptive testing strategy cannot compete that of the optimal testing strategy, but should be better than that of a random testing strategy. This paper further justifies the idea of software cybernetics that is aimed to explore the interplay between software theory/engineering and control theory/engineering.