Online Test Synthesis From Requirements: Enhancing Reinforcement Learning with Game Theory
This work addresses automated testing for reactive systems, representing an incremental improvement by combining reinforcement learning with game theory insights.
The paper tackles the problem of automatically generating test cases from functional requirements for reactive systems, using a Monte Carlo Tree Search approach enhanced with game theory heuristics to accelerate convergence and improve testing performance.
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, so as to satisfy a coverage criterion, while monitoring the violation of the requirements. We develop an approach based on Monte Carlo Tree Search, which is a classical technique in reinforcement learning for efficiently selecting promising inputs. 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 the Monte Carlo Tree Search algorithm, thus improving the performance of testing.