Search

To date, no method has explicitly and cost effectively dealt with failure detection in software systems whose specifications are nondeterministic. In such systems, the specification permits multiple outputs for the same input sequence and system state. Nondeterminism in specifications is advantageous because the specification writer can avoid stating irrelevant behavior as mandatory, freeing the software designer to choose a behavioral alternative that would yield a more desirable implementation. Unfortunately, this flexibility comes at a cost to the failure detection mechanism. It must accommodate all the target system's legal behavioral alternatives and avoid favoring one of them. The article describes a hierarchical supervisor whose failure detection mechanism explicitly addresses systems with nondeterministic specifications. The supervisor, a unit separate from the target system, observes the system's external inputs and outputs and reports any failures. Its hierarchical structure results from splitting the task of identifying the behavioral alternative the target system chooses from the task of checking the details of system behavior. This structure makes it possible to efficiently trade off detection accuracy and computational cost. To evaluate their approach, the authors created a prototype supervisor and used it to supervise the execution of the control program of a small telephone exchange. Results indicate that the hierarchical supervisor can significantly reduce the computational cost of considering the target system's behavioral alternatives. However, although the supervisor's computational cost is significantly reduced, it is still higher than that for the target system.

The problem of automatic detection of failures of reactive, session-oriented software programs is described. Detection of failures is carried out by a separate unit, which observes the inputs and outputs of the target program and reports the failures detected.

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 communicating finite state machines. The failure detector described in this paper is called assume-guarantee supervisor. The supervisor simultaneously observes the input/output and stable states of the target system, interprets the specification, and reports the discrepancies between these two as failures. We formalize an assume-guarantee paradigm for supervision, and provide a generic failure detection algorithm. We also describe the architecture and operation of a failure detection tool which employs the above model. This tool can be employed for online software failure detection in the operational stage of a system.

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.

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.

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.

Specification-based software supervision is an approach to the automatic run-time detection of failures. The supervisor is a unit that monitors the inputs and outputs of a target software system and reports discrepancies between specified and observed behaviors as failures. Two fundamental issues arise in supervision. The first is due to specification non-determinisms. The major difficulty being that the supervisor is required to consider all legitimate behavioral alternatives to avoid erroneous failure reports. In some cases, this results in significant supervisor time and space complexities. The second issue deals with continuation of supervision after a failure was detected. The major problem is that after a failure is detected, the supervisor no longer has definite knowledge about the specification state of the target system which can result in in spurious failure reports. This paper describes a software supervisor architecture for target systems whose specifications are expressed in communicating extended finite state machine-based formalisms. The architecture includes several independent mechanisms, each tailored to resolving a specific ambiguity occurring within the software supervisor. Included are mechanisms for resolving specification non-determinism and identifying the state of the target system after a failure is detected.

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 paper describes a software engineering option which has been developed and is being taught jointly by two departments in two faculties: Computer Science (Faculty of Mathematics) and Electrical and Computer Engineering (Faculty of Engineering). The attempt to create a joint option has resulted in certain strengths and weaknesses. The strengths derive from the different approaches to software engineering in the two departments. The weaknesses derive from the constraints of having to deal with two sets of departmental, faculty, and accreditation board constraints, which leaves the option less flexibility. We describe the option, emphasizing three components: the course selection and, in particular the three new courses which were created specifically for the option; the CASE tools which accompany each of the new courses; and the project which spans all three of the new courses. The project is described in detail, emphasizing its bifurcated nature, with a real time embedded system aspect for the computer engineers and an information system aspect for the computer scientists.

With the critical role played by software systems in the operation of telecommunications networks, the ability to detect and report software failures has become of great importance. The paper presents the failure detection approach of real-time supervision based on the belief method. Real-time supervision allows failures in a software system to be detected in real-time based only on boundary signals and a specification of its external behaviour. This feature is of particular benefit when software is purchased from other vendors and there is no direct access to source code. An implementation of real-time supervision has been shown to be capable of failure detection in a small telephone exchange.

Real-time supervision is one technique used to improve the perceived reliability of software systems. A real-time supervisor observes the inputs and outputs of the system and reports failures that occur. The approach presented in this paper uses the specification of external behavior of the system to detect failures. Failures are reported in real-time. In addition, the approach permits the assessment of the erroneous states of the system. Following a failure, the supervisor makes an assumption of the (system) erroneous state. Consequences of the same fault are not reported repeatedly. The supervisor accommodates the nondeterminism permissible under some specification formalism. The formalism considered in this paper is the CCITT SDL. >

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. >

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.

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.

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.

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.

Software supervision is an approach to automatic detection of software failures. A software supervisor observes the inputs and outputs of a target system. It uses a model of correct behavior, derived from the target system's requirements specification. Discrepancies between specified and observed behaviors are reported as failures. The tradeoff between the computational complexity of supervision and the latency of failure reporting is discussed in this paper. Supervisor computational complexity can be significantly reduced at the expense of increased failure reporting latency. For applications such as software testing, this is a practical tradeoff. Such a supervisor is called an out-of-time supervisor. This paper describes the data, flows, algorithms, operation and evaluation of an out-of-time supervisor for communicating finite state machine based requirements specifications. A prototype supervisor was used to monitor the operation a small telephone exchange control program. For a failure reporting latency equal to the worst-case response time of the target system, a reduction in computational complexity of several orders of magnitude was measured.

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.

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.

Software supervision is an approach to the real time detection of failures. A software supervisor is a unit which monitors both the inputs and outputs of a real time system and reports discrepancies between observed and expected behaviors. The major difficulty with software supervision is the running time complexity of the supervisor. A significant source of running time complexity was determined to be the total number of signals at the inputs queues of specification processes for which no ordering information is known. This paper describes an approach to reduce the running time complexity of a software supervisor. The approach makes use of a transformed specification in which several state transitions are grouped into a single transition or aggregate state. This effectively reduces the number of signals at the input queues of processes. The case where the system under supervision is specified in the ITU Specification and Description Language (SDL) is considered. An algorithm to translate SDL processes into aggregate state representations is described. Use of the algorithm is exemplified with the aid of an SDL specification of a small private branch telephone exchange.

Large software systems, such as telecom applications, are often built on reused components. Such systems are often developed using components from previous similar projects, or simply using a reconfiguration of the same set of components from a previous similar project. Performance prediction of such software system architectural design provides a quantified measurement for better design quality. The design is specified in a communicating extended finite state machine model. The model is extended with stochastic information and simulated for performance prediction. The stochastic extension requires performance data for each component and load information of the system environment. This paper addresses the problem of abstracting stochastic performance model of a component to be reused in a software architectural design. We use a software supervision approach to monitor the performance of a deployed component and collect its execution trace, including individual time stamps of the externally observable signals. We then derive a stochastic performance model of the component from the trace. The model can be used later in performance prediction when the component is reused. We applied this method to a control program of a small telephone exchange. We were able to reuse a component and its performance data in a new exchange design.

A real-time supervisor observes the inputs and outputs of a real-time system and reports the failures that occur. Failures are reported in real-time. This paper considers the case when the target system is specified in CCIl'TSDL, a specification language based on communicating extended finite state machines. The paper presents the supervisor model. The model is derived from the specification model of the target system. Its semantic is defined through extension to SDL semantic. A major source of difficulties in the development of supervisor model are the nondeterminisms permissible under SDL. Underlying the models presented is the theory of beliefs, where a belief is a hypothesis about the evolving behavior of a specifrcation process. Consistent beliefs about the behavior of individual specification processes form belief sets. Beliefs (and belief sets) are created whenever an uncertainty about the evolving behavior arises and terminated when an observed output is inconsistent with the hypothesis they represent. The supervisor concludes that a failure has occurred when the last belief is terminated (there is no legitimate explanation for the observed behavior).

No one likes to debug programs, and there is no way to automate the task. However, knowledge-based approaches offer some possibilities for the future.

The adjoint network approach to automated network design as presented by Director and Rohrer is extended for use in gradient calculations for noncommensurate networks. The networks can contain distributed elements such as uniform transmission lines and RC lines. An example investigates gradient computations for a noncommensurate microwave network having 13 variable parameters.

Some current trends in automated network design optimization which, it is believed, will play a significant role in the computer-aided design of lumped-distributed and microwave networks are reviewed and discussed. In particular, the adjoint network approach due to Director and Rohrer for evaluating the gradient vector of suitable objective functions related to network responses that are to be opttilzed is presented in a tutorial manner. The advantage of this method is the ease with which the required partial derivatives with respect to variable parameters, such as electrical quantities or geometrical dimensions, can be obtained using at most two network analyses. Least pth and minimax approximation in the frequency domain are considered. Networks consisting of linear time-invariant elements are treated, including the conventional lumped elements, transmission lines, RC limes, coaxial lines, rectangular waveguides, and coupled lines. To illustrate the application of the adjoint network method, an example is given concerning the optimization in the least pth sense using the Fletcher-Powell method of a transmission-line filter with frequency variable terminations previously considered by Carlin and Gupta.

A theoretical foundation is presented for the efficient computation of first- and second-order sensitivities of networks with respect to network parameters in terms of wave variables. The concept of the adjoint network is used. First-order sensitivity formulas for a wide variety of elements are presented, including lumped and uniformly distributed elements, active and passive elements, and reciprocal and nonreciprocal elements. Parameters include electrical quantities, geometrical dimensions, and frequency. It is shown how gradients related to wave-based least pth and minimax objective functions can be computed. A comparison with a method which avoids the need for analysis of adjoint networks is made. Applications in the computer-aided design of networks using efficient gradient minimization methods are envisaged.

In recent contributions, Director and Rohrer discussed the concept of the adjoint network and its relevance to automated design of networks in the frequency and time domains. Employing Tellegen's theorem they demonstrated how the gradient vector for a least squares type of response objective function with respect to all existing (and nonexisting, if desired) elements could be evaluated from only two complete analyses, one of the given network and one of its topologicalIy equivalent adjoint network. In the frequency domain they considered both reciprocal and nonreciprocal lumped, linear and time invariant elements. More recently, it was shown how their approach could be implemented for least pth and minimax response objective functions.

With current trends towards more complex software system and use of higher level languages, a monitoring technique is of increasing importance for the areas such as performance enhancement, dependability, correctness checking and so on. In this paper, we present a formal specification-based online monitoring technique. The key idea of our technique is to build a linking system, which connects a specification animator and a program debugger. The required information about dynamic behaviors of the formal specification and concrete implementation of a target system is obtained from the animator and the debugger. Based on that information, the judgment on the consistency of the concrete implementation with the formal specification will be provided. Not embedding any instrumentation code into the target system, our monitoring technique will not alter the dynamic behavior of the target system. Animating the formal specification, rather than annotating the target system with extra formal specifications, our monitoring technique separates the implementation-dependent description of the monitored objects and the formal requirement specification of them.

It is shown how the adjoint-network approach to automated design due to Director and Rohrer can be implemented in gradient calculations for least pth and minimax response objective functions. Their formulas, for example, for frequency-domain design of networks consisting of lumped, linear and time invariant elements may be used without change, provided that the adjoint network is appropriately excited.

A method for computing the equivalent wave source at some port of an excited reciprocal or nonreciprocal network using one analysis of the appropriately terminated adjoint network is presented. The procedure should be useful in simplifying the scattering-matrix analysis of complicated networks.

A method is presented for evaluating first- and second-order sensitivities of, in general, a nonreciprocal network described by a scattering matrix. It avoids the analysis of an adjoint network, using only the results of an analysis of the given network.