Dynamic Multiple Fault Diagnosis: Mathematical Formulations and Solution Techniques

Imperfect test outcomes, due to factors such as unreliable sensors, electromagnetic interference, and environmental conditions, manifest themselves as missed detections and false alarms. This paper develops near-optimal algorithms for dynamic multiple fault diagnosis (DMFD) problems in the presence of imperfect test outcomes. The DMFD problem is to determine the most likely evolution of component states, the one that best explains the observed test outcomes. Here, we discuss four formulations of the DMFD problem. These include the deterministic situation corresponding to perfectly observed coupled Markov decision processes to several partially observed factorial hidden Markov models ranging from the case where the imperfect test outcomes are functions of tests only to the case where the test outcomes are functions of faults and tests, as well as the case where the false alarms are associated with the nominal (fault free) case only. All these formulations are intractable NP-hard combinatorial optimization problems. Our solution scheme can be viewed as a two-level coordinated solution framework for the DMFD problem. At the top (coordination) level, we update the Lagrange multipliers (coordination variables, dual variables) using the subgradient method. At the bottom level, we use a dynamic programming technique (specifically, the Viterbi decoding or Max-sum algorithm) to solve each of the subproblems, one for each component state sequence. The key advantage of our approach is that it provides an approximate duality gap, which is a measure of the suboptimality of the DMFD solution. Computational results on real-world problems are presented. A detailed performance analysis of the proposed algorithm is also discussed.      

针对动态系统的多故障诊断模型与优化算法

一般的静态故障诊断模型无法描述状态随时间变化的系统,为此用隐马尔可夫模型对动态变化的系统状态进行建模,给出了动态多故障诊断问题的形式化描述;该问题的目标函数是典型的集合覆盖问题,属于NP难解问题。通过将原始目标函数转化为若干个独立的子问题,并分别用动态规划算法进行求解,有效实现了动态系统的多故障诊断;与现有的方法相比,该方法在不影响检测率和隔离率的前提下,执行时间短,计算复杂度低,优化效果明显。     

Test sequencing algorithms with unreliable tests

In this paper, we consider imperfect test sequencing problems under a single fault assumption. This is a partially observed Markov decision problem (POMDP), a sequential multistage decision problem wherein a failure source must be identified using the results of imperfect tests at each stage. The optimal solution for this problem can be obtained by applying a continuous-state dynamic programming (DP) recursion. However, the DP recursion is computationally very expensive owing to the continuous nature of the state vector comprising the probabilities of faults. In order to alleviate this computational explosion, we present an efficient implementation of the DP recursion. We also consider various problems with special structure (parallel systems) and derive closed form solutions/index-rules without having to resort to DP. Finally, we present various top-down graph search algorithms for problems with no special structure, including multistep DP, multistep information heuristics, and certainty equivalence algorithms     

Fault coupling in finite bijective functions

Fault-based testing attempts to show that particular faults cannot exist in software by using test sets that differentiate between the original program (hypothesized to be correct) and faulty alternate programs. The success of this approach depends on a number of assumptions, notably that programmers are competent insofar as they only commit relatively trivial faults, and that faults only couple infrequently. Fault coupling occurs when test sets are able to differentiate between the original program and faulty alternate programs when faults occur in isolation, but not when they occur in combination; it is a complicating factor in fault-based testing. Fault coupling is studied here within the context of finite bijective functions. A complete mathematical solution of the problem is possible in this simplified case; the results indicate that fault coupling does indeed occur infrequently, and are thus in agreement with the empirical results obtained by others in the field. One surprising result is that certain kinds of test set are able to avoid fault coupling altogether.     

The effect of the specification model on the complexity of adding masking fault tolerance

In this paper, we investigate the effect of the representation of safety specification on the complexity of adding masking fault tolerance to programs - where, in the presence of faults, the program 1) recovers to states from where it satisfies its (safety and liveness) specification and 2) preserves its safety specification during recovery. Specifically, we concentrate on two approaches for modeling the safety specifications: 1) the bad transition (BT) model, where safety is modeled as a set of bad transitions that should not be executed by the program, and 2) the bad pair (BP) model, where safety is modeled as a set of finite sequences consisting of at most two successive transitions. If the safety specification is specified in the BT model, then it is known that the complexity of automatic addition of masking fault tolerance to high atomicity programs - where processes can read/write all program variables in an atomic step) - is polynomial in the state space of the program. However, for the case where one uses the BP model to specify safety specification, we show that the problem of adding masking fault tolerance to high atomicity programs is NP-complete. Therefore, we argue that automated synthesis of fault-tolerant programs is likely to be more successful if one focuses on problems where safety can be represented in the BT model.     

Test generation in combinational networks by decomposition

Hierarchical Systems Theory attempts to analyze complex systems by decomposition. The computational benefit of decomposition is a substantial reduction in both computer memory and processing time.

This paper investigates the application of the theory to the problem of generating tests for the detection of digital faults. The digital network is decomposed into two or more loosely coupled subnetworks. For each subnetwork, a parametric test is derived. An optimal test for the entire network is then obtained from these parametric tests by selecting appropriate values for the parameters.

A complete and near-minimal test set can be constructed by repeated use of the above procedure. In each iteration, an optimal test is selected and the faults detected by this test are excluded from further consideration. The process is then repeated on the remaining undetected faults. The algorithm terminates when all faults in the original fault set have been excluded.

It is shown that as a result of decomposition, a reduction in the required amount of memory space of as much as 50% can be realized.     

FSM-based testing from user defined faults adapted to incremental and mutation testing

We study the problem of deriving a test suite with guaranteed fault coverage from a given finite state machine specification with respect to some given user defined faults. We consider the case when an implementation under test can have more states than its specification while user defined faults are implemented in an arbitrary way. We show that our approach can be used for FSM-based incremental and mutation testing and correspondingly we investigate cases that can be used for reducing length of obtained test suites. In some cases, worst-case length of obtained test suite becomes polynomial. Experiments show significant gains is using our approach in comparison to testing the whole specification.     

副版本不可抢占的全局容错调度算法

容错是硬实时系统的关键能力,容错调度算法可以在有错误发生的情况下满足任务的实时性需求.在主副版本机制的容错调度算法中,主版本出错后留给副版本运行的时间窗口小,副版本容易错失截止期.针对副版本需要快速响应的问题,提出副版本不可抢占的全局容错调度算法FTGS-NPB（fault-tolerant global scheduling with non-preemptive backups）,赋予副版本全局最高优先级,使副版本在主版本出错后可以立刻获得处理器资源,并且在运行过程中不会被其他任务抢占.这样,副版本可以在最短时间内响应.分别基于截止期分析和响应时间分析建立了FTGS-NPB的可调度性测试,并分析了两种可调度性测试分别适用于不同的优先级分配算法.仿真实验结果表明,FTGS-NPB可以有效地减少实现容错的代价.     

基于有限状态机的电梯控制系统故障诊断方法

针对电梯控制系统软故障样本获取困难及产生时间短暂的问题,提出一种基于状态机的故障诊断方法。利用电梯控制开关量和电梯运行模拟量作为状态机的状态特征,在电梯正常运行过程中收集各状态并记录状态转换,以此建立电梯控制系统的规范模型;改进基于有限状态机的被动测试错误检测算法,对待诊断的电梯控制系统进行故障检测/诊断;并不断地确认新的故障情况,完善规范模型。实验结果表明,该方法可以及时检测出未知情况,也可以有效地诊断已知故障,对电梯控制系统瞬间出现的软故障有很好的监督作用。     

Design of exclusive or sum-of-products (ESP) logic arrays with universal tests for detecting stuck-at and bridging faults

The detection problem of bridging faults in AND-EXOR arrays is considered in this paper in a new framework. These AND-EXOR arrays are different from the arrays based on the so-called Reed-Muller canonic (RMC) expansion of functions. The multiple stuck-at fault detection test set in such arrays as already derived by Pradhan[1] has been utilized to detect bridging faults. One most important advantage of this test set is that it is independent of the function realized and it has a simple algebraic structure and hence can be generated easily. As this conventional test set is insufficient to detect all bridging faults, we propose a technique of augmenting the network with some additional observation points which take care of otherwise undetectable bridging faults.     

基于多目标约束的鲁棒故障检测滤波器设计

针对包含未知输入的线性时不变系统,研究了其鲁棒故障检测滤波器设计问题。由于故障信号往往分布在有限频域段内,设计的目标包括使特定有限频域段上的复合性能指标最小化以及满足区域极点配置的要求。一个基于LMI的方法被提出用于解决该设计问题。该方法的优点在于求解过程中可以获取给定有限频域段上的频域指标的真实值,并可求得满足目标的最优解。因此,设计的故障检测滤波器可以获得良好的故障检测性能。一个基于某国产歼击机的设计实例验证了该方法的有效性。     

IPSETFUL: an iterative process of selecting test cases for effective fault localization by exploring concept lattice of program spectra

Fault localization is an important and challenging task during software testing. Among techniques studied in this field, program spectrum based fault localization is a promising approach. To perform spectrum based fault localization, a set of test oracles should be provided, and the effectiveness of fault localization depends highly on the quality of test oracles. Moreover, their effectiveness is usually affected when multiple simultaneous faults are present. Faced with multiple faults it is difficult for developers to determine when to stop the fault localization process. To address these issues, we propose an iterative fault localization process, i.e., an iterative process of selecting test cases for effective fault localization (IPSETFUL), to identify as many faults as possible in the program until the stopping criterion is satisfied. It is performed based on a concept lattice of program spectrum (CLPS) proposed in our previous work. Based on the labeling approach of CLPS, program statements are categorized as dangerous statements, safe statements, and sensitive statements. To identify the faults, developers need to check the dangerous statements. Meantime, developers need to select a set of test cases covering the dangerous or sensitive statements from the original test suite, and a new CLPS is generated for the next iteration. The same process is proceeded in the same way. This iterative process ends until there are no failing tests in the test suite and all statements on the CLPS become safe statements. We conduct an empirical study on several subject programs, and the results show that IPSETFUL can help identifymost of the faults in the program with the given test suite. Moreover, it can save much effort in inspecting unfaulty program statements compared with the existing spectrum based fault localization techniques and the relevant state of the art technique.     

Sensor fault detection and isolation: a game theoretic approach

This paper studies sensor fault detection using a game theoretic approach. Sensor fault detection is considered as change point analysis in the coefficients of a regression model. A new method for detecting faults, referred to as two-way fault detection, is introduced which defines a game between two players, i.e. the fault detectors. In this new strategic environment, assuming that the independent states of the regression model are known, the test statistics are derived and their finite sample distributions under the null hypothesis of no change are derived. These test statistics are useful for testing the fault existence, as well as, the pure and mixed Nash equilibriums are derived for at-most-one-change and epidemic change models. A differential game is also proposed and solved using the Pontryagin maximum principle. This solution is useful for studying the fault detection problem in unknown state cases. Kalman filter and linear matrix inequality methods are used in finding the Nash equilibrium for the case of unknown states. Illustrative examples are presented to show the existence of the Nash equilibriums. Also, the proposed fault detection scheme is numerically evaluated via its application on a practical system and its performance is compared with the cumulative sum method.     

Finite‐horizon fault estimation under imperfect measurements and stochastic communication protocol: Dealing with finite‐time boundedness

In this paper, we analyze the finite‐horizon fault estimation issue for a kind of time‐varying nonlinear systems with imperfect measurement signals under the stochastic communication protocol (SCP). The imperfect measurements result from randomly occurring sensor nonlinearities obeying sensor‐wise Bernoulli distributions. The Markov‐chain‐driven SCP is introduced to regulate the signal transmission to alleviate the communication congestion. The aim of the considered issue is to propose the design algorithm of a group of time‐varying fault estimators such that the estimation error dynamics satisfies both the H_∞ and the finite‐time boundedness (FTB) performance requirements. First, sufficient conditions are set up to guarantee the existence of the satisfactory H_∞ FTB fault estimators through intensive stochastic analyses and matrix operations. Then, the gains of such fault estimators are explicitly parameterized by resorting to the solution to recursive linear matrix inequalities. Finally, the correctness of the devised fault estimation approach is demonstrated by a numerical example.     

计算系统自诊断模型与建模方法的研究

自诊断(Self-Diagnostic)技术旨在使计算系统具备在无需人为干涉的情况下监控自身状态、识别并定位故障的能力,是提高计算系统可靠性和可维护性的重要方法;基于有限状态机模型和故障模型,提出了一种新的系统自诊断模型及其建模方法,利用系统关键点检测单元和故障特征向量的方法分别描述系统状态和故障类型,分析不同故障类型间的关联属性并建立相应的故障模型,使得系统能够准确识别自身正/异常状态,对可能出现的故障进行准确识别和定位,在复杂故障环境下同样具备良好的诊断能力;对于提高系统可靠性、建立具备较高自诊断能力的计算系统具有重要意义。     

A Nitsche-extended finite element method for earthquake rupture on complex fault systems

The extended finite element method (XFEM) provides a natural way to incorporate strong and weak discontinuities into discretizations. It alleviates the need to mesh discontinuities, allowing simulation meshes to be nearly independent of discontinuity geometry. Currently, both quasistatic deformation and dynamic earthquake rupture simulations under standard FEM are limited to simplified fault networks, as generating meshes that both conform with the faults and have appropriate properties for accurate simulation is a difficult problem. In addition, fault geometry is not well known; robustness of solution to fault geometry must be determined. Remeshing with varying geometry would make such tests computationally unfeasible. The XFEM makes a natural choice for discretization in these crustal deformation simulations on complex fault systems. Here, we develop a method based upon the XFEM using Nitsche’s method to apply boundary conditions, enabling the solution of static deformation and dynamic earthquake models. We compare several approaches to calculating and applying frictional tractions. Finally, we demonstrate the method with two problems: an earthquake community dynamic code verification benchmark and a quasistatic problem on a fault system model of southern California.     

长期在轨推进系统故障诊断实时仿真技术研究

为了解决长期在轨航天器易出现故障的推进系统故障常规地面检测费时费力且无法完全包络全部故障模式的问题,提出了长期在轨推进系统故障诊断实时仿真技术方案,建立了长期在轨推进系统故障诊断实时测试平台。通过建立推进系统实时仿真模型,实现对长期在轨推进系统的实时仿真;依托实时测试平台对推进系统故障诊断策略进行仿真优化、对在轨飞行器故障进行诊断、并对处置预案进行验证支持故障处置决策。长期在轨推进系统故障诊断实时测试平台有效缩短了器上故障诊断策略的优化迭代周期,同时节省了大量原本用来进行试车的经费。     

Formal Analysis of Coupling Hypothesis for Logical Faults

Fault-based testing focuses on detecting faults in a software. Test data is typically generated considering the presence of a single fault at a time, under the assumption of coupling hypothesis. Fault-based testing approach, in particular mutation testing, assumes that the coupling hypothesis holds. According to the hypothesis, a test set that can detect presence of single faults in an implementation, is also likely to detect presence of multiple faults. In this paper it is formally shown that the hypothesis is guaranteed to hold for a large number of logical fault classes.     

Computationally efficient algorithms for multiple fault diagnosis in large graph-based systems

Graph-based systems are models wherein the nodes represent the components and the edges represent the fault propagation between the components. For critical systems, some components are equipped with smart sensors for on-board system health management. When an abnormal situation occurs, alarms will be triggered from these sensors. This paper considers the problem of identifying the set of potential failure sources from the set of ringing alarms in graph-based systems. However, the computational complexity of solving the optimal multiple fault diagnosis (MFD) problem is exponential. Based on Lagrangian relaxation and subgradient optimization, we present a heuristic algorithm to find approximately the most likely candidate fault set. A computationally cheaper heuristic algorithm - primal heuristic - has also been applied to the problem so that real-time MFD in systems with several thousand failure sources becomes feasible in a fraction of a second. This paper also considers systems with asymmetric and multivalued alarms (tests).     

Maxx: Test Pattern Optimisation with Local Search Over an Extended Logic

In the electronic computer-aided design area, the test generation problem consists in finding an input vector test for some possible diagnosis (a set of faults) of a digital circuit. Such tests may have some unspecified Primary Inputs (i.e. bits are assigned neither 0 nor 1). In fact, for many purposes, minimally specified tests (or patterns) are preferred. Hence, we have the test pattern optimisation (TPO) problem where the goal is to obtain a test with the maximum number of unspecified bits. In this paper we discuss different modelling approaches and present a TPO tool (Maxx) that substantially outperforms others by combining Branch-and-Bound and local search over distinct models. We apply the usual branch-and-bound search on CLP(FD) over a simple, yet incomplete, logic. A complementary Local Search is performed over an extended model, trying to improve an already computed solution by exploring an extended solution space thanks to the use of an extended logic (too complex for constraint solving). Such extended logic considers sets of dependencies on specified input values, keeping track of sources of unspecified values and their inversion parities. This allows modelling a number of alternative test vectors by unspecification of each possible input bit, thus being able to obtain an improved test vector in linear time. This paper shows, for TPO, that adapting constraint propagation with results obtained from local search outperforms the use of each of these techniques alone, obtaining significantly better results than those obtained with a highly efficient tool based on an integer linear programming formulation on a propositional satisfiability model.