A MUTATION-BASED FRAMEWORK FOR AUTOMATED TESTING OF TIMELINESS

Diploma

Abstract

A problem when testing timeliness of event-triggered real-time systems is that response times depend on the execution order of concurrent tasks. Conventional testing methods ignore task interleaving and timing and thus do not help determine which execution orders need to be exercised to gain confidence in temporal correctness. This thesis presents and evaluates a framework for testing of timeliness that is based on mutation testing theory. The framework includes two complementary approaches for mutation-based test case generation, testing criteria for timeliness, and tools for automating the test case generation process. A scheme for automated test case execution is also defined. The testing framework assumes that a structured notation is used to model the real-time applications and their execution environment. This real-time system model is subsequently mutated by operators that mimic potential errors that may lead to timeliness failures. Each mutated model is automatically analyzed to generate test cases that target execution orders that are likely to lead to timeliness failures. The validation of the theory and methods in the proposed testing framework is done iteratively through case-studies, experiments and proof-of-concept implementations. This research indicates that an adapted form of mutation-based testing can be used for effective and automated testing of timeliness and, thus, for increasing the confidence level in real-time systems that are designed according to the event-triggered paradigm.


Overview

Real-time systems must be dependable as they often operate in tight interaction with human operators and valuable equipment. A trend is to increase the flexibility of such systems so that they can support more features while running on “off-theshelf” hardware platforms. However, with the flexibility comes increased software complexity and non-deterministic temporal behavior. There is a need for verification methods to detect errors arising from temporal faults so that confidence can still be placed in the safety and reliability of such systems.

A problem associated with the testing of real-time applications is that their timeliness depends on the execution order of tasks. This is particularly problematic for event-triggered and dynamically scheduled real-time systems, in which events may influence the execution order at any time (Schutz 1994). Furthermore, tasks¨ in real-time systems behave differently from one execution to the next, depending not only on the implementation of real-time kernels and program logic, but also on efficiency of acceleration hardware such as caches and branch-predicting pipelines. Non-deterministic temporal behavior necessitates methods and tools for effectively detecting the situations when errors in temporal estimations can cause the failure of dependable applications.

The timeliness of embedded real-time systems is traditionally analyzed and maintained using scheduling analysis techniques or regulated online through admission control and contingency schemes (Burns & Wellings 2001). These techniques use assumptions about the tasks and load patterns that must be correct for timeliness to be maintained. Doing schedulability analysis of non-trivial system models is complicated and requires specific rules to be followed by the run-time support system. In contrast, timeliness testing is general in the sense that it applies to all system architectures and can be used to gain confidence in assumptions by systematically sampling among the execution orders that can lead to missed deadlines. Hence, from a real-time perspective, timeliness testing is a necessary complement to analysis.

It is difficult to construct effective sequences of test inputs for testing timeliness without considering the effect on the current set of active tasks and real-time protocols. However, existing testing techniques seldom use such information and they do not predict which execution orders may lead to timeliness failures (Nilsson, Andler & Mellin 2002).

In summary, problems with testing of timeliness arise from a dynamic environment and the vast number of potential execution orders of event-triggered real-time systems. Therefore, we need to be able to produce test inputs that exercise a meaningful subset of these execution orders. Within the field of software testing, several methods have been suggested for model-based test case generation but few of them capture the behavior that is relevant to generate effective timeliness test cases.

This thesis presents a mutation-based method for testing of timeliness that takes internal behaviors into consideration. The thesis also describes experiments for evaluating the effectiveness of this method.


Real-time System Preliminaries

Real-time systems denote information processing systems which must respond to externally generated input stimuli within a finite and specified period (Young 1982). Typically, these kinds of systems are also embedded and operate in the context of a larger engineering system – designed for a dedicated platform and application.

Real-time systems typically interact with other sub-systems and processes in the physical world. This is called the environment of the real-time system. For example, the environment of a real-time system that controls a robot arm includes items coming down a conveyor belt and messages from other robot control systems along the same production line. Typically, there are explicit time constraints, associated with the response time and temporal behavior of real-time systems. For example, a time constraint for a flight monitoring system can be that once landing permission is requested, a response must be provided within 30 seconds (Ramamritham 1995). A time constraint on the response time of a request is called a deadline. Time constraints come from the dynamic characteristics of the environment (movement, acceleration, etc.) or from design and safety decisions imposed by a system developer. Timeliness refers to the ability of software to meet time

Real-time systems are sometimes called reactive since they react to changes in their environment, which is perceived through sensors, and influence it through different actuators. Dependable systems are computer systems where people’s lives, environmental or economical value may depend on the continued service of the system (Laprie 1994). Since real-time systems control hardware that interacts closely with entities and people in the real world, they often need to be dependable.