This paper considers automatic, specification based detection of failures (supervision) of software systems. It is applicable to systems specified in a formalism based on communicating finite state machines. The technique enhances the belief-based approach to supervision to allow its continuation after occurrences of failures. The enhancement adopts the fuzzy set view of the membership of hypotheses in the behavior matched set. The paper first overviews the belief-based approach, presents the fuzzy enhancements and describes an experimental evaluation of the technique and summarizes its results.

The paper considers automatic, specification-based detection of failures (differences between observed and specified behavior) in external behavior of software systems. The external behavior is recorded in traces, which are analyzed for the presence of failures. The paper describes a novel failure detection technique. The technique is applicable to multi-user systems which are reactive, session-oriented and specified in formalisms based on communicating extended finite state machines. It separates the failure detection concerns into two parts, the detection of failures directly noticeable by individual users, and the determination whether the individually correct local behaviors are globally consistent with the specification. An experimental evaluation of the technique on the control program for a small telephone exchange is also presented

Self-protection is an attribute of autonomic computing systems, reflecting the requirement to proactively defend against attackers, and automatically detect and recover from attacks. As demonstrated by increasing numbers of Internet worms, a single previously unknown vulnerability can cause an entire infrastructure to crumble, due to software and hardware monocultures. One defence against complete failures is diversity: by utilizing differing implementations of software and hardware, the potential total damage from a single exploit is lessened. The self-deployment and self-configuration features of an autonomic computing infrastructure make it practical to use diversity as a self-protection mechanism. We explore the idea of using diversity as a factor in resource allocation decisions, showing how it could be used to limit the damage an attacker can inflict.

The benefits of monitoring the internal health of complex systems are recognized in mature engineering disciplines. Such monitoring helps maintain the operational reliability and availability of the system. Recently, research has begun to address the notion of health of complex software systems and its monitoring. This paper outlines a three-layer software health monitoring architecture and presents a collection of design patterns for the bottom two layers of the architecture. The patterns can be implemented with aspect-oriented technologies, which increase system modularity and facilitates retrofitting of monitoring capability onto existing systems. The application of the patterns to a control program of a small telephone exchange is described and the results of its general assessment are summarized.

The paper presents a curriculum for a 4-year undergraduate program in Embedded System Engineering (ESE). The curriculum was developed using a two-step approach. First, a body of education knowledge for Embedded System Engineering was defined. The body consists of sixteen knowledge areas. Each area is composed of several knowledge units, some designated as core and others as electives. The minimum lecture time for the core of each knowledge area is identified. The Body of Knowledge for Computer Engineering, developed by the IEEE-CS/ACM task force for Computing Curricula, was used as a reference. The education knowledge for ESE then served as the base for the development of the program curriculum. The curriculum has a strong mathematics and basic science base, an in-depth exposure to engineering science and design of systems implemented with digital hardware and software, and coverage of two prominent application areas of embedded systems. The curriculum core takes approximately 3 years of the program; the remaining part is elective.

Global predicate evaluation is a fundamental problem in distributed systems. This paper views it from a different perspective, namely that of the signals and systems area of electrical engineering. It adapts a signal processing approach to address this problem in the context of monitoring of 'health' of a software system. The global state of the system is viewed as a 'state' signal which evolves over time. The distributed processes are assumed to possess roughly synchronized clocks. The states of individual processes are periodically sampled and reported to a global monitor. The observed system state constructed by the global monitor is viewed as being composed of two components - the consistent global states and an error signal due to the messages in transit and differences in the local clocks. The global monitor removes the error signal by processing the observed global signal through a low-pass filter. It evaluates the predicates on the filtered signal. The approach presented is applicable to distributed systems which are semi-stationary, i.e. whose internal states of interest remain stable over comparatively long intervals of time. The paper presents the relevant signal processing concepts (p-spectrum and p-filtering), outlines an architecture for global predicate monitoring and describes the signal processing done in the global monitor. The paper then summarizes an evaluation of the approach presented on a small computer aided vehicle dispatch system. The evaluation experiments are described and the results are presented and analyzed.

This paper proposes a specification-based monitoring approach for automatic run-time detection of software errors and failures of distributed systems. The specification is assumed to be expressed in communicating finite state machines based formalism. The monitor observes the external I/O and partial state information of the target distributed system and uses them to interpret the specification. The approach is compositional as it achieves global monitoring by combining the component-level monitoring. The core of the paper describes the architecture and operations of the monitor The monitor includes several independent mechanisms, each tailored to detecting specific kinds of errors or failures. Their operations are described in detail using illustrative examples. Techniques for dealing with nondeterminism and concurrency issues in monitoring a distributed system are also discussed with respect to the considered model and specification. A case study describing the application of the prototype monitor to an embedded system is presented.

In the development of many software systems, the focus was on functionality. When these systems are used in situations requiring higher reliability and availability, such qualities must be retrofitted into the system. This paper considers a way of adding such capability to existing software by taking advantage of aspect-oriented programming, a recently developed technology which supports encapsulation of non-functional concerns. The paper introduces the notion of a system health index as a measure of the internal system well-being, and identifies a number of health indicators, i.e. operational metrics from which a health index could be derived. The paper then discusses an aspect-oriented implementation of health indicators and lists several applicable aspect-oriented design patterns. Experience obtained from the implementation of health indicators in a distributed system whose original development focused only on functionality is then summarized. The experience suggests that time and space overhead and development costs are moderate, and that there is a distinct advantage of aspect-oriented implementation of health indicators.

Despite rigorous use of model checking, testing, and other technological innovations in software development there exists faults which elude those detection efforts and do not surface until the software is operational. These faults may lead to serious software failures (deviation of actual behavior from the desired one). Existing software failure detectors for concurrent systems are not compositional, and hence suffer from the state explosion problem. We present a compositional approach for automatic failure detection of concurrent programs specified as a collection of communi-cating finite state machines. The failure detector described in this paper is called assume-guarantee supervisor. The su-pervisor simultaneously observes the input/output and sta-ble states of the target system, interprets the specification, and reports the discrepancies between these two as failures. We formalize an assume-guarantee paradigm for supervi-sion, and provide a generic failure detection algorithm. We also describe the architecture and operation of a failure de-tection tool which employs the above model. This tool can be employed for online software failure detection in the op-erational stage of a system. 1

The functionality of many real-time systems depends critically on their software. It is important to know whether their software operates correctly or whether failures are occurring. This would help system operators take corrective actions before minor problems escalate into major disruptions. The paper considers one approach to automatic detection of software failures called supervision. In this approach, a separate unit called the supervisor observes the inputs and outputs of the target program. The supervisor knows what the intended behavior of the target program is and reports deviations as failures. The focus is on event-driven, embedded real-time software. The paper first overviews major issues involved in supervision. These include the definition of correct behavior, observability of program inputs and outputs, dealing with specification nondeterminism, tradeoffs between failure detection accuracy and computational cost, and the continuation of supervision after occurrences of failures. The paper then summarizes experience obtained in supervision of a control program of a small telephone exchange. The exchange and its telephones were simulated on a multiprocessor workstation. The summary includes the results obtained for failure detection capability and computational cost.

The large number of test inputs and outputs usually involved in testing of protocols makes automated output checking necessary. An automated oracle in the test environment achieves this automation. It is imperative that the oracle should be tolerant of nondeterminism in the specifications. This paper presents an and-state method to accommodate specification nondeterminism in automated protocol resting oracles. The and-state method generates concurrent system states when encountering nondeterminism. The and-state method reduces the computational cost of an oracle by avoiding running n concurrent copies of the system to generate all n possible behaviors caused by nondeterminism. We illustrate the and-state method using example specifications given in the Specification and Description Language (SDL). We applied this method to an automated oracle of a small protocol in a network system consisting of 60 nodes. The experimental results show that this oracle facilitates random testing of the protocol.

Classical software reliability research has tended to focus on behavioral type failures which typically manifest themselves as incorrect or missing outputs. In real time software, a correct output which is not produced within a specified response time interval may also constitute a failure. As a result, response time failures must also be taken into account when real time software reliability is assessed. The paper considers the case where the detection of response times failures is done by a separate unit which observes the inputs and outputs of the target software. Automatic detection of such failures is complicated by state dependencies which require the unit to track a target's state as well as the elapsed times between specified stimulus and response pairs. A novel black box approach is described for detecting response time failures and quality of service degradations of session oriented, real time software. The behavior of the target software is assumed to be specified in a formalism based on the notion of communicating extended finite state machines. The response time failure detection unit implemented independently of the target software, interprets a formal model derived directly from the target's requirement specifications. The model is used both to track the state of the target and to determine when to start and stop time interval timing measurements. Measurements of multiple response time intervals may occur simultaneously. The approach was evaluated on the call processing program of a small telephone exchange. Some results of the evaluation are presented and discussed.

Software supervision is an approach to the automatic detection of software failures. A supervisor observes the inputs and outputs of a target system. It uses a model of correct behavior, derived from the target system's requirement specification. Discrepancies between specified and observed behaviors are reported as failures. Applications of the supervisor include online failure detection in real time reactive systems, fault localization and automatic collection of failure data. The paper describes a hierarchical approach to supervision. The approach differs from previous approaches in that supervision is split into two sub problems: tracking the behavior of the target system and detailed behavior checking. The architecture of the hierarchical supervisor has two layers: the path detection layer and the base supervisor layer. The hierarchical approach results in a significant reduction in computational cost arising from specification nondeterminism. The approach was evaluated by supervising the call processing software of a small telephone exchange, executed under random telephone traffic at different loads. Several thousand failures were individually seeded into the output generated by the exchange. The supervisor was able to detect the presence of all seeded failures. Reductions in computational cost of several orders of magnitude were measured in comparison with the direct, single layer supervisor.

An approach to automate detection of behavioral failures during system testing is described. A supervisor monitors the inputs and outputs of a system under test. It reports discrepancies between observed and specified behaviors as failures. Failures due to both design and implementation are detectable. The approach presented is able to tolerate legal behavioral alternatives arising out of specification non-determinism.

A real-time supervisor observes the inputs and outputs of the target system and reports failures that occur. Failures are reported in real-time. The approach presented in this paper uses the specification of the external behaviour of the target system to detect failures. It is able to accommodate the non-determinism permissible under some specification formalisms. In addition, the approach permits the assessment of the erroneous states of the system. The supervisor updates its state after a failure has occurred so that it may continue supervision. This involves making an assumption about the erroneous states that led to the observable failure. Furthermore, consequences of the same fault are not reported repeatedly. The focus of the paper is on telecommunication switching software whose external behaviour is specified using the CCITT Specification and Description Language, a specification language based on communicating extended finite state machines. © 1997 by John Wiley & Sons, Ltd.

Failures of a software system are detected by a supervisor, a separate unit which observes the inputs and outputs of the system and reports its failures in real-time. The supervisor determines whether a failure has occurred by comparing the observed and the specified behavior. The specification of behavior is assumed to be expressed in a formalism based on communicating extended finite state machines (specifically, ITU-T SDL). The supervisor must tolerate legal behavioral alternatives resulting from nondeterminisms in the specification. The computational costs of considering such alternatives can be fairly high. The paper presents the Conditional-Belief (CB) theory that reduces the cost of consideration of alternatives by using conditional-beliefs to represent sets of legal behavioral alternatives. The paper reviews belief-based supervision, introduces the CB theory, and outlines an algorithm for conversion of a class of SDL specification to a CB supervisor model. It describes a demonstration system developed to evaluate CB supervision, and summarizes failure detection and computational cost results for the supervisor of the control program of a small telephone exchange.

Real time supervision is a technique for automatically detecting and reporting failures in the external behaviour of real time software systems. Failure detection is achieved by monitoring the target system's external inputs and outputs, in a 'black box' manner and comparing its behaviour with the formally specified behaviour of the system. The paper presents the Optimistic Path Prediction and Rollbacks (OPPR) approach to real time supervision. In this technique, the supervisor predicts a single likely behaviour of the target system and, if the observed behaviour does not match the prediction, rolls back and creates a new prediction of the legal behaviour. A failure is detected when the supervisor has explored all valid behaviours without matching the observed behaviour. The paper opens by introducing the field of real time supervision and examining existing techniques. The core of the paper presents the basic algorithm of the OPPR method, with an example to illustrate its operation. The paper closes by describing an evaluation system, summarizing the experimental results and examining the performance of the OPPR scheme.

The focus of this paper is on an approach to the automatic failure detection of reactive software systems called specification-based supervision. Assumed is that the software is specified in a formalism based on communicating extended finite state machines (CEFSMs). The major difficulty in supervising such systems is that the supervisor must account for all possible behaviors that are permissible under the non-determinism present in the specification. An approach to the automatic detection of failures based on the theory of beliefs is presented. This theory was developed to deal with the nondeterminism present in CEFSM based formalisms. The specification language SDL, standardized by the International Telecommunication Union, is used as a concrete example. In the theory of beliefs, each behavioral alternative is represented as a separate belief of one or more specification CEFSMs. Beliefs are combined into consistent belief sets that represent legitimate external behaviors. A consistent belief set representing a behavior that does not match the actually observed behavior is terminated. If all consistent belief sets have been terminated, the observed behavior is not legitimate and is reported as a failure of the target software system. A prototype implementation of a belief-based supervisor was developed. The implementation was used to monitor execution of a small telephone exchange. Both the supervisor and exchange were emulated on a workstation. Statistics characterizing the number of consistent belief sets are presented.

Numerous software reliability growth models have been proposed. The authors present three metrics which have been helpful in assessing the applicability and predictive validity of these models. These metrics are the relative fitting error metric, the short term predictive validity metric and the long term predictive validity metric. The application of these three metrics is illustrated on estimation of field reliability of telecommunication switching systems.>