Nicolas Markey

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, 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.

@techreport{2407.18994-SJMMN,
  author =              {Sankur, Ocan and J{\'e}ron, Thierry and Markey,
                         Nicolas and Mentr{\'e}, David and Noguchi, Reiya},
  title =               {Online Test Synthesis From Requirements: Enhancing
                         Reinforcement Learning with Game Theory},
  number =              {2407-18994},
  year =                {2024},
  month =               jul,
  doi =                 {10.48550/arXiv.2407-18994},
  institution =         {arXiv},
  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,
                         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.},
}