A Reinforcement Learning-based Approach to Partition Testing

Partition testing is one of the most fundamental and popularly used software testing techniques. It first divides the input domain of the program under test into a set of disjoint partitions, and then creates test cases from these partitions. Motivated by the theory of software cybernetics, some strategies have been proposed to dynamically select partitions based on the feedback information gained during testing. The basic intuition of these strategies is to assign higher probabilities to those partitions with higher fault-detection potentials, which are judged and updated mainly according to the previous test results. Such a feedback-driven mechanism can be considered as a learning process --- it makes decisions based on the observations acquired in the test execution. Accordingly, advanced learning techniques could be leveraged to empower the smart partition selection, with the purpose of further improving the effectiveness and efficiency of partition testing. In this paper, we particularly leverage reinforcement learning to enhance the state-of-the-art adaptive partition testing techniques. Two algorithms, namely RLAPT Q and RLAPT S, have been developed to implement the proposed approach. Empirical studies have been conducted to evaluate the performance of the proposed approach based on seven object programs with 26 faults. The experimental results show that our approach outperforms the existing partition testing techniques in terms of the fault-detection capability as well as the overall testing time. Our study demonstrates the applicability and effectiveness of reinforcement learning in advancing the performance of software testing.