Requirement-Based Testing: Enhancing Reinforcement Learning with Game Theory

Abstract

We consider the automatic online synthesis of black-box test cases from functional requirements specified as automata for reactive implementations. The goal of the tester is to reach some given state, to satisfy a coverage criterion, while monitoring the violation of the requirements. We develop an approach based on Monte Carlo Tree Search (MCTS), which is a classical technique in reinforcement learning for computing optimal policies. Seeing the automata requirements as a game between the implementation and the tester, we develop a heuristic by biasing the search towards inputs that are promising in this game. We experimentally show that our heuristic accelerates the convergence of MCTS, thus improving the performance of testing.