TATOO

Test and Testability of Distributed Real-Time Systems

mrtcbrown_small.gif (2333 bytes)

Namnlös1.gif (2910 bytes)

logo.gif (1698 bytes)

Project Description

This is an ARTES_SMALL.JPG (4314 bytes) project and is being carried out at Mälardalen Real-Time Research Center (MRTC), Mälardalen University College. The project deals with fundamentals for deterministic testing of distributed real-time systems.

The project  is carried out in co-operation with our industrial partners Volvo Construction Equipment Components AB, Datex-Ohmeda AB, and Enator Teknik Mälardalen AB. The research will provide us with insights in concrete, application specific, real-time engineering practices and broaden the scientific foundation for industry.

Summary

The goal of the project is to develop methods, metrics, design rules, and tools for testing of distributed real-time systems (DRTS). Theoretical and practical results with regard to testing and testability of DRTS are next to nonexistent. Research is therefore of significance to both academia and Industry. During the first phase of the project we have developed: Methods for achieving deterministic testing of DRTS, testability metrics, and tools that implements the results. We have specifically addressed task sets with recurring release patterns, executing in a distributed system, where the scheduling on each node is handled by a priority driven preemptive scheduler. This includes statically scheduled systems that are subject to preemption and interrupts, as well as strictly periodic fixed priority systems.

Problem Statement

Achieving deterministic testing of sequential programs is easy because we need only control the sequence of inputs and the start conditions, in order to guarantee reproducibility. That is, given the same initial state and inputs, the sequential program will deterministically produce the same output on repeated executions, even in the presence of systematic faults. Reproducibility is essential when performing regression testing or cyclic debugging, where the same test cases are run repeatedly with the intent to validate that either an error correction had the desired effect, or simply to make it possible to find the error when a failure has been observed. However, trying to directly apply test techniques for sequential programs on distributed real-time systems is bound to lead to non-determinism and non-reproducibility, because control is only forced on the inputs, disregarding the significance of order and timing of the executing and communicating tasks. Any intrusive observation of a DRTS will in addition incur a temporal probe-effect that subsequently will affect the system’s temporal and functional behavior.

In order to achieve systematic testing of DRTS there are three major problems that need to be addressed:

  1. Reproducing the inputs with respect to contents, order, and timing
  2. Deterministically observing or reproducing the order and timing of the execution of the parallel programs as well as their communication with each other and the environment
  3. Eliminating the probe-effect.

In the TATOO project we target problems (2) and (3). For a description of related research regarding these problems see Thane and Hansson [RTSS, RTCSA].

Main Ideas

Facilitate deterministic testing of DRTS by transforming the non-deterministic DRTS testing problem into a set of deterministic sequential programs testing problems. This is can be achieved by deriving all the possible execution orderings of the distributed real-time system and regarding each of them as a sequential program.We intend to specifically addressed task sets with recurring release patterns, executing in a distributed system, where the scheduling on each node is handled by a priority driven preemptive scheduler. This includes statically scheduled systems that are subject to preemption and interrupts, as well as strictly periodic fixed priority systems. Together with an accompanying testing strategy this approach could allow test methods for sequential programs to be used, since each identified ordering can be regarded as a sequential program. We intend to take into account the effects of interrupts, preemption, clock synchronization, and varying start and execution times of the involved tasks.

Develop testability metrics that gives criteria on when to stop testing, and what to test. This is important since any criteria less than exhaustive testing must be justifiable. A metric is also useful for analysis, and comparison between different design solutions and architectures, so that sound design rules can emerge.

Devise monitoring mechanisms that eliminate the probe effect through the allocation of sufficient resources and then letting the probes remain in the target system. This includes allocating resources for the probes’ execution time, memory, communication bus bandwidth and accounting for the probes when designing and scheduling. In order to guarantee consistent observations of the global state in the DRTS we assume that the system is globally scheduled. Which means that the release and execution times can be related to a global synchronized time base with a known precision.

Expected Results

The result will be a set of methods, and tools, for testing distributed real-times systems, addressing what current test methods for sequential programs cannot test. Corresponding to the set of methods there will be a set of testability metrics, and tools, for finding out how many test-cases are necessary in order to find all errors in the code with a certain confidence. In close relation to the testability metrics there will be methods for identification of the actual test-cases that must be executed in order to satisfy the coverage criteria defined by the test methods and testability metrics.The prospects of finding such methods and metrics are quite good when the semantical restrictions on distributed real-time systems, based on static scheduling or fixed priority scheduling, are significantly greater than those for concurrent systems where no notion of real-time exists.There is very little done (next to nothing) in this field, so if the project is fruitful the impact will be considerable both to Academia (potentially opening up a new field of research) and to the Industry where there is a dire need for methods and tools.

 research.gif (1081 bytes)
MRTC conducts research on the design and verification of safety-critical distributed real-time systems .

staff.gif (1055 bytes)
A list with our current members and guest researchers.

publ.gif (381 bytes)
You can download and print papers and thesis from our list of publications.

The project deals with fundamentals for deterministic testing of distributed real-time systems

Project Members

Henrik Thane

Hans Hansson

Some selected publications:

[RTCSA] Thane H, Hansson H. Handling Interrupts in Testing of Distributed Real-Time Systems. To appear in Real-Time Computing Systems and Applications conference (RTCSA’99), Hong Kong, December, 1999. (Review version)

[RTSS] Thane H, Hansson H. Towards Systematic Testing of Distributed Real-Time Systems. To appear in Real-Time Systems Symposium, Phoenix U.S.A, December, 1999. (Review version)

[Tech1] Thane H. Dealing with Interrupts in Testing of Distributed Real-Time Systems. Technical report, Mälardalen Real-Time. Research Centre, Dept. Computer Engineering, Mälardalen University, 1999.In the works

[Tech2] Thane H. Design for Deterministic Monitoring of Distributed Real-Time Systems. Technical report, Mälardalen Real-Time Research Centre, Dept. Computer Engineering, Mälardalen University, 1999.In the works

Related publications:

[SAFE96] Thane, H. Safe and Reliable Computer Control Systems - Concepts and Methods. Research Report TRITA-MMK 1996:13, ISSN 1400-1179, ISRN KTH/MMK/R-96/13-SE. Mechatronics Laboratory/ Department of Machine Design, the Royal Institute of Technology, S-100 44 Stockholm, Sweden,1996.

[an error occurred while processing this directive]
Last modified 1999-10-07 by Henrik Thane