Verification and Synthesis of Complete Test Generation Algorithms for Finite State Machines

Speaker: Robert Sachtleben, University Bremen, Germany.

Tuesday 25 Oct 2022, 14:00, Room 1Z76

Abstract: Complete test suites are of special interest in the field of model-based testing, as they guarantee high fault detection capabilities. The variety and complexity of proposed strategies, their implementations, and their corresponding completeness arguments, however, impede thorough manual verification and practical employment.

We present a novel approach to the verification and synthesis of such strategies for models specified using finite state machines. First, we unify the presentation of several such strategies into a single framework implemented as a higher order function, which represents their shared high-level behaviour. Next, we model this framework in the interactive theorem prover Isabelle. Completeness proofs over frameworks are decoupled from concrete implementations of their parameters by suitable interfaces. This approach enables the reuse of proofs between similar strategies and simplifies implementations and completeness proofs of new variations on already handled strategies. Finally, we generate provably correct implementations of the considered test strategies. It is shown that these exhibit comparable performance to a manually developed C++ library for certain inputs.