Fault masking by multiple timing faults in timed EFSM models

Detection of multiple timing faults is a challenging task because these faults, although may be detectable individually, can mask each other’s faulty behavior, making a faulty implementation under test (IUT) indistinguishable from a non-faulty one during testing. This phenomenon, called fault masking, is formally defined in this paper. It is proven that graph augmentation algorithms proposed for timed Extended Finite State Machines (EFSMs) with multiple timers can detect pairwise occurrences of classes of timing faults in an IUT and, hence, detects fault masking.     

基于故障特征信息熵的故障诊断策略优化方法

针对复杂电子设备的顺序故障诊断策略问题,为实现快速的故障检测与隔离,提出了一种基于故障特征信息熵的故障诊断策略树生成算法。该算法综合考虑测试费用和故障概率因素,依据故障特征信息熵的大小依次选择测试点来生成优化的故障诊断策略树。实例表明该算法可行,能以较低的测试费用和较少的测试步骤实现复杂电子设备的故障检测和隔离。     

Testing Conformance to a Quasi-Non-Deterministic Stream X-Machine

Stream X-machines have been used in order to specify a range of systems. One of the strengths of this approach is that, under certain well-defined conditions, it is possible to produce a finite test that is guaranteed to determine the correctness of the implementation under test (IUT). Initially only deterministic stream X-machines were considered in the literature. This is largely because the standard test algorithm relies on the stream X-machine being deterministic. More recently the problem of testing to determine whether the IUT is equivalent to a non-deterministic stream X-machine specification has been tackled. Since non-determinism can be important for specifications, this is an extremely useful extension. In many cases, however, we wish to test for a weaker notion of correctness called conformance. This paper considers a particular form of non-determinism, within stream X-machines, that will be called quasi-non-determinism. It then investigates the generation of tests that are guaranteed to determine whether the IUT conforms to a quasi-non-deterministic stream X-machine specification. The test generation algorithm given is a generalisation of that used for testing from a deterministic stream X-machine. Received November 1999 / Accepted in revised form December 2000     

Scalable and Effective Test Generation for Role-Based Access Control Systems

Conformance testing procedures for generating tests from the finite state model representation of Role-Based Access Control (RBAC) policies are proposed and evaluated. A test suite generated using one of these procedures has excellent fault detection ability but is astronomically large. Two approaches to reduce the size of the generated test suite were investigated. One is based on a set of six heuristics and the other directly generates a test suite from the finite state model using random selection of paths in the policy model. Empirical studies revealed that the second approach to test suite generation, combined with one or more heuristics, is most effective in the detection of both first-order mutation and malicious faults and generates a significantly smaller test suite than the one generated directly from the finite state models.     

Test suite minimization for testing in context

Testing a component embedded into a complex system, in which all other components are assumed fault‐free, is known as embedded testing. This paper proposes a method for minimizing a test suite to perform embedded testing. The minimized test suite maintains the fault coverage of the original test suite with respect to faults within the embedded component. The minimization uses the fact that the system is composed of a fault‐free context and a component under test, specified as communicating, possibly non‐deterministic finite state machines (FSMs). The method is illustrated using an example of telephone services on an intelligent network architecture. Other applications of the proposed approach for testing a system of communicating FSMs are also discussed. Copyright © 2003 John Wiley & Sons, Ltd.     

Checking experiments for stream X-machines

Stream X-machines are a state based formalism that has associated with it a particular development process in which a system is built from trusted components. Testing thus essentially checks that these components have been combined in a correct manner and that the orders in which they can occur are consistent with the specification. Importantly, there are test generation methods that return a checking experiment: a test that is guaranteed to determine correctness as long as the implementation under test (IUT) is functionally equivalent to an unknown element of a given fault domain Ψ. Previous work has show how three methods for generating checking experiments from a finite state machine (FSM) can be adapted to testing from a stream X-machine. However, there are many other methods for generating checking experiments from an FSM and these have a variety of benefits that correspond to different testing scenarios. This paper shows how any method for generating a checking experiment from an FSM can be adapted to generate a checking experiment for testing an implementation against a stream X-machine. This is the case whether we are testing to check that the IUT is functionally equivalent to a specification or we are testing to check that every trace (input/output sequence) of the IUT is also a trace of a nondeterministic specification. Interestingly, this holds even if the fault domain Ψ used is not that traditionally associated with testing from a stream X-machine. The results also apply for both deterministic and nondeterministic implementations.     

Software testing based on SDL specifications with save

The signal save construct is one of the features distinguishing SDL from traditional high-level specification and programming languages. However, this feature increases the difficulties of testing SDL-specified software. We present a testing approach consisting of the following three phases: SDL specifications are first abstracted into finite state machines with save constructs, called SDL-machines; the resulting SDL-machines are then transformed into equivalent finite state machines without save constructs if this is possible; and, finally, test cases are selected from the resulting finite state machines. Since there are many existing methods for the first and third phases, we mainly concentrate upon the second phase and come up with a method of transforming SDL-machines into equivalent finite state machines, which preserve the same input/output relationship as in the original SDL-machines. The transformation method is useful not only for testing but also for verifying SDL-specified software     

Formally verified on-line diagnosis

A reconfigurable fault tolerant system achieves the attributes of dependability of operations through fault detection, fault isolation and reconfiguration, typically referred to as the FDIR paradigm. Fault diagnosis is a key component of this approach, requiring an accurate determination of the health and state of the system. An imprecise state assessment can lead to catastrophic failure due to an optimistic diagnosis, or conversely, result in underutilization of resources because of a pessimistic diagnosis. Differing from classical testing and other off-line diagnostic approaches, we develop procedures for maximal utilization of the system state information to provide for continual, on-line diagnosis and reconfiguration capabilities as an integral part of the system operations. Our diagnosis approach, unlike existing techniques, does not require administered testing to gather syndrome information but is based on monitoring the system message traffic among redundant system functions. We present comprehensive on-line diagnosis algorithms capable of handling a continuum of faults of varying severity at the node and link level. Not only are the proposed algorithms on-line in nature, but are themselves tolerant to faults in the diagnostic process. Formal analysis is presented for all proposed algorithms. These proofs offer both insight into the algorithm operations and facilitate a rigorous formal verification of the developed algorithms     

Extended robust observation approach for failure isolation

A new failure isolation scheme is proposed using an extended robust observation approach. A systematic procedure is developed for designing fault detection observers. This new failure isolation scheme can isolate a much larger class of failure modes than previous failure isolation schemes in the relevant literature, so that failure diagnosing precision may be greatly improved.     

多模式系统的测试顺序优化

研究了多模式系统的测试顺序优化问题。基于不同模式下测试与故障之间的依赖关系,结合系统故障的先验概率、可用测试的成本以及不同模式的转换费用,构造了该问题的数学描述模型。基于已有的搜索算法提出了一种准多步前向搜索算法,该算法以信息增益为启发策略,可自动获取平均测试费用最少、且能快速实现系统故障检测与隔离的优化测试顺序。最后实例验证了该算法的正确性,证明该算法可解决实际问题。     

Structured residual vector-based approach to sensor fault detection and isolation

This paper proposes a novel approach to detection and isolation of faulty sensors in multivariate dynamic systems. After formulating the problem of sensor fault detection and isolation in a dynamic system represented by a state space model, we develop the optimal design of a primary residual vector for fault detection and a set of structured residual vectors for fault isolation using an extended observability matrix and a lower triangular block Toeplitz matrix of the system. This work is, therefore, a vector extension to the earlier scalar-based approach to fault detection and isolation. Besides proposing a new algorithm for consistent identification of the Toeplitz matrix from noisy input and output observations without identifying the state space matrices {A, B, C, D} of the system, the main contributions of this newly proposed fault detection and isolation scheme are: (1) a set of structured residual vectors is employed for fault isolation; (2) after determination of the maximum number of multiple sensors that are most likely to fail simultaneously, a unified scheme for isolation of single and multiple faulty sensors is proposed; and (3) the optimality of the primary residual vector and the structured residual vectors is proven. We prove the advantage of our newly proposed vector-based scheme over the existing scalar element-based approach for fault isolation and illustrate its practicality by simulated and experimental evaluation on a multivariate pilot scale, computer interfaced system.     

Performance bounds for binary testing with arbitrary weights

Summary Binary testing concerns finding good algorithms to solve the class of binary identification problems. A binary identification problem has as input a set of objects, including one regarded as distinguished (e.g., faulty), for each object an a priori estimate that it is the distinguished object, and a set of tests. Output is a testing procedure to isolate the distinguished object. One seeks minimal cost testing procedures where cost is the average cost of isolation, summed over all objects. This is a problem schema for the diagnosis problem: applications occur in medicine, systematic biology, machine fault location, quality control and elsewhere.In this paper we extend work of Garey and Graham to assess the capability of a fast approximation rule, the binary splitting rule, to give near optimal testing procedures when the a priori estimates are arbitrary. We find conditions on the test set such that the approximation error reduces nearly to that of the equally likely a priori estimate case of Garey and Graham and find another upper bound on approximation error for the same test set conditions which works very well under a priori estimate assumptions where the first result is poor.This research has been partially supported by AFOSR, Air Force Command, AFOSR-81-0221 and by the Rockland Research Center, Rockland, NY, USA     

A data mining approach for machine fault diagnosis based on associated frequency patterns

Bearings play a crucial role in rotational machines and their failure is one of the foremost causes of breakdowns in rotary machinery. Their functionality is directly relevant to the operational performance, service life and efficiency of these machines. Therefore, bearing fault identification is very significant. The accuracy of fault or anomaly detection by the current techniques is not adequate. We propose a data mining-based framework for fault identification and anomaly detection from machine vibration data. In this framework, to capture the useful knowledge from the vibration data stream (VDS), we first pre-process the data using Fast Fourier Transform (FFT) to extract the frequency signature and then build a compact tree called SAFP-tree (sliding window associated frequency pattern tree), and propose a mining algorithm called SAFP. Our SAFP algorithm can mine associated frequency patterns (i.e., fault frequency signatures) in the current window of VDS and use them to identify faults in the bearing data. Finally, SAFP is further enhanced to SAFP-AD for anomaly detection by determining the normal behavior measure (NBM) from the extracted frequency patterns. The results show that our technique is very efficient in identifying faults and detecting anomalies over VDS and can be used for remote machine health diagnosis.     

Generating Conformance Tests for Nondeterministic Protocol Machines

We present a method of generating test cases from the software specifications which are modeled by nondeterministic finite state machines.It is applicable to both nondeterministic and deterministic finite state machines.When applied to deterministic machines,this method yields usually smaller test suites with full fault coverage than the existing methods that also assure full fault coverage.In particular,the proposed method can be used to test the control portion of software specified in the formal specification languages SDL or ESTELLE.     

Synthesis of distinguishing test cases for timed finite state machines

This paper is devoted to the generation of distinguishing experiments with completely specified timed finite state machines. It is shown, in particular, that two completely specified nondeterministic finite state machines can be distinguished by a multiple preset experiment if and only if these finite state machines are not equivalent. Two finite state machines can be distinguished by a simple adaptive experiment if and only if they are r-distinguishable, i.e., have no common completely specified reduction. The corresponding adaptive experiment is described by a special timed finite state machine. The procedure for constructing such an r-distinguishing timed finite state machine is proposed.     

Fault diagnosis based on identified discrete-event models

Fault diagnosis of Discrete-Event Systems consists of detecting and isolating the occurrence of faults within a bounded number of event occurrences. Recently, a new model for discrete-event system identification with the aim of fault detection, called Deterministic Automaton with Outputs and Conditional Transitions (DAOCT), has been proposed in the literature. The model is computed from observed fault-free paths, and represents the fault-free system behavior. In order to obtain compact models, loops are introduced in the model, which implies that sequences that are not observed can be generated leading to an exceeding language. This exceeding language is associated with possible non-detectable faults, and must be reduced in order to use the model for fault detection. After detecting the fault occurrence, its isolation is carried out by analyzing residuals. In this paper, we present a fault diagnosis scheme based on the DAOCT model. We show that the proposed fault diagnosis scheme is more efficient than other approaches proposed in the literature, in the sense that the exceeding language can be drastically reduced, reducing the number of non-detectable fault occurrences, and, in some cases, reducing also the delay for fault diagnosis. A practical example, consisting of a plant simulated by using a 3D simulation software controlled by a Programmable Logic Controller, is used to illustrate the results of the paper.     

Robust fault isolation for a class of non-linear input?output systems

The design and analysis of fault diagnosis methodologies for non-linear systems has received significant attention recently. This paper presents a robust fault isolation scheme for a class of non-linear systems with unstructured modelling uncertainty and partial state measurement. The proposed fault diagnosis architecture consists of a fault detection and approximation estimator and a bank of isolation estimators. Each isolation estimator corresponds to a particular type of fault in the fault class. A fault isolation decision scheme is presented with guaranteed performance. If at least one component of the output estimation error of a particular fault isolation estimator exceeds the corresponding adaptive threshold at some finite time, then the occurrence of that type of fault can be excluded. Fault isolation is achieved if this is valid for all but one isolation estimator. Based on the class of non-linear systems under consideration, fault isolability conditions are rigorously investigated, characterizing the class of non-linear faults that are isolable by the proposed scheme. Moreover, the non-conservativeness of the fault isolability conditions is illustrated by deriving a subclass of nonlinear systems and faults for which this condition is also necessary for fault isolability. A simulation example of a simple robotic system is used to show the effectiveness of the robust fault isolation methodology.     

Eliminating synchronization faults in air traffic control software via design for verification with concurrency controllers

The increasing level of automation in critical infrastructures requires development of effective ways for finding faults in safety critical software components. Synchronization in concurrent components is especially prone to errors and, due to difficulty of exploring all thread interleavings, it is difficult to find synchronization faults. In this paper we present an experimental study demonstrating the effectiveness of model checking techniques in finding synchronization faults in safety critical software when they are combined with a design for verification approach. We based our experiments on an automated air traffic control software component called the Tactical Separation Assisted Flight Environment (TSAFE). We first reengineered TSAFE using the concurrency controller design pattern. The concurrency controller design pattern enables a modular verification strategy by decoupling the behaviors of the concurrency controllers from the behaviors of the threads that use them using interfaces specified as finite state machines. The behavior of a concurrency controller is verified with respect to arbitrary numbers of threads using the infinite state model checking techniques implemented in the Action Language Verifier (ALV). The threads which use the controller classes are checked for interface violations using the finite state model checking techniques implemented in the Java Path Finder (JPF). We present techniques for thread isolation which enables us to analyze each thread in the program separately during interface verification. We conducted two sets of experiments using these verification techniques. First, we created 40 faulty versions of TSAFE using manual fault seeding. During this exercise we also developed a classification of faults that can be found using the presented design for verification approach. Next, we generated another 100 faulty versions of TSAFE using randomly seeded faults that were created automatically based on this fault classification. We used both infinite and finite state verification techniques for finding the seeded faults. The results of our experiments demonstrate the effectiveness of the presented design for verification approach in eliminating synchronization faults.     

Probabilistic and reactive fault diagnosis for dynamic overlay networks

Overlay networks have emerged as a powerful and flexible platform for developing new disruptive network applications. The attractive characteristics of overlay networks such as routing flexibility and overlay topology dynamics bring to overlay fault diagnosis new challenges, which include the dynamical overlay symptom-fault correlation, multi-layer (i.e., underlay vs. overlay) abstraction, and unregulated overlay symptoms. To address these challenges, we propose a novel user-level probabilistic and reactive fault diagnosis technique, called ProFis for overlay networks, which can seamlessly integrate passive and active fault reasoning to develop an optimal fault diagnosis framework. ProFis uses observable overlay symptoms as reported by overlay applications to dynamically correlate overlay symptoms and faults. ProFis diagnoses overlay faults passively and selects optimal actions (i.e., with the least cost) to enhance the passive diagnosis whenever necessary. Our evaluation study shows that ProFis can efficiently (i.e., low latency) and accurately localize the root causes of overlay faults, even when symptom loss rate is high.