Test Automation for Hybrid Systems

Author: Bahareh Badban, Martin Fränzle, Jan Peleska and Tino Teige:

Abstract:
This article presents novel results on automated test generation for hybrid control systems. In contrast to test automation techniques for purely discrete controllers this involves the generation of both discrete and real-valued, potentially time-continuous, input data to the system under test. To this end, the test automation techniques introduced here are allocated in two-layers: The upper layer contains a symbolic test case generator constructing test cases as paths through an abstracted representation of the transition graph specifying the system under test. Different test strategies designed to pursue various quality objectives lead to different selections of symbolic test cases. Symbolic test cases are transformed into feasible, i. e., executable, test cases by constructing concrete sequences of input data, allowing the execution of the pre-planned transition sequence. The input data construction is performed by the lower layer consisting of a constraint solver. This component applies interval analysis techniques identifying the domains from where to pick the appropriate test data. The well known complexity problems of the various paving algorithms used in interval analysis are circumvented by three main concepts: First, sequences of constraints, each element representing a conjunct of a larger global constraint, are processed separately, thereby keeping the dimension of the local constraint problems involved at an acceptable level. Second, interval vectors containing the global solution set are contracted using forward-backward interval constraint propagation. Third, both symbolic test case generator and constraint solver learn to avoid symbolic transition sequences whose prefixes are already known to be infeasible and to avoid interval solutions for local constraints which are known to be in conflict with other local constraints to be satisfied for the same symbolic test case, respectively.

PDF file (262KB) (extended version of the submission published in Proceedings of the SOQUA'06, November 6, 2006, Portland, OR, USA.)