Games and Scenarios for Real-Time System Validation

This thesis presents research on the validation of real-time embedded software systems in the context of model-based development. The thesis proposes scenario-based and game-theoretic approaches to system analysis, verification, synthesis and testing to address the challenges that arise from the system characteristics of environment uncertainties, complex process interactions, quantitative timing constraints, partial observability and combinations thereof.

We make timed extensions to live sequence chart (LSC) such that the inter-process behaviors and scenario-based requirements of concurrent communicating real-time systems can be modeled and specified with LSC. By translating LSC to timed automata (TAs), we reduce scenario-based model consistency checking and property verification to CTL real-time model checking problems, and reduce scenario-based synthesis to a timed game solving problem. By linking our prototype translators with existing model checker Uppaal and game solver Uppaal-Tiga, we show that these methods contribute to the interaction correctness and timeliness of early system designs.

The thesis also shows that testing a real-time reactive system can be viewed as playing a timed game between the tester and the system under test (SUT). We propose methods of using winning strategies as test cases for black-box conformance testing. The methods are generalized to problems where only possibly winning game strategies can be obtained. In this case continued testing requires some early-stage ``cooperations'' from the SUT. Furthermore, we adapt the methods to the partial observability settings where only imperfect information about the SUT is available. All these methods contribute to the improved ability to test for reactivity correctness and timeliness of the systems in question. Experimental evaluations with case studies indicate that the proposed approaches are conceptually, algorithmically and computationally viable.