In previous work we described Diagnostic Tree for Verification (DTV), a partially automated software engineering technique by which diagnostic trees generated from system models are used to help check out diagnostic procedures. Diagnostic procedures are instructions used to isolate failures during operations. Assuring such procedures manually is time-consuming and costly. This paper reports our recent experience in applying DTV to diagnostic procedures for lighting failures in NASA's Habitat Demonstration Unit (HDU), a prototype for astronauts' living quarters. DTV identified missing and inconsistent instructions, as well as more-efficient sequences of diagnostic steps. Unexpectedly, the most significant benefit was finding assumptions that will not remain true as the system evolves. We describe both the challenges faced in applying DTV and how its independent perspective helped in assuring the procedures' adequacy and quality. Finally, the paper discusses more generally how software systems that are model-based, rapidly evolving and safety-critical appear most likely to benefit from this approach.

The application of model-based diagnosis schemes to real systems introduces many significant challenges, such as building accurate system models for heterogeneous systems with complex behaviors, dealing with noisy measurements and disturbances, and producing valuable results in a timely manner with limited information and computational resources. The Advanced Diagnostics and Prognostics Testbed (ADAPT), which was deployed at the NASA Ames Research Center, is a representative spacecraft electrical power distribution system that embodies a number of these challenges. ADAPT contains a large number of interconnected components, and a set of circuit breakers and relays that enable a number of distinct power distribution configurations. The system includes electrical dc and ac loads, mechanical subsystems (such as motors), and fluid systems (such as pumps). The system components are susceptible to different types of faults, i.e., unexpected changes in parameter values, discrete faults in switching elements, and sensor faults. This paper presents Hybrid Transcend, which is a comprehensive model-based diagnosis scheme to address these challenges. The scheme uses the hybrid bond graph modeling language to systematically develop computational models and algorithms for hybrid state estimation, robust fault detection, and efficient fault isolation. The computational methods are implemented as a suite of software tools that enable diagnostic analysis and testing through simulation, diagnosability studies, and deployment on the experimental testbed. Simulation and experimental results demonstrate the effectiveness of the methodology.

In this paper, we consider a model for the dynamic multiple-fault diagnosis (DMFD) problem arising in online monitoring of complex systems and present a solution. This problem involves real-time inference of the most likely set of faults and their time-evolution based on blocks of unreliable test outcomes over time. In the DMFD problem, there is a finite set of mutually independent fault states, and a finite set of sensors (tests) is used to monitor their status. We model the dependence of test outcomes on the fault states via the traditional D-matrix (fault dictionary). The tests are imperfect in the sense that they can have missed detections, false alarms, or may be available asynchronously. Based on the imperfect observations over time, the problem is to identify the most likely evolution of fault states over time. The DMFD problem is an intractable NP-hard combinatorial optimization problem. Consequently, we decompose the DMFD problem into a series of decoupled subproblems, one for each sample epoch. For a single-epoch MFD, we develop a fast and high-quality deterministic simulated annealing method. Based on the sequential inferences, a local search-and-update scheme is applied to further improve the solution. Finally, we discuss how the method can be extended to dependent faults.

For many safety-critical systems a safety case is built as part of the certification or acceptance process. The safety case assembles evidence to justify that the design and implementation of a system avoid hazardous software behavior. Fault modeling and analysis can provide a rich source of evidence that the design meets safety goals. However, there is currently little guidance available to bridge the gap between the fault modeling that developers perform and the mandated safety case. In this experience report we describe results and open issues from an investigation of how evidence from software tool supported fault modeling and analysis of a spacecraft power system could assist in safety-case construction. The ways in which the software fault models can provide evidence for the safety case appears to be applicable to other critical systems.

Advances in software autonomy can support system robustness to a broader range of operational anomalies, called contingencies, than ever before. Contingency management includes, but goes beyond, traditional fault protection. Increased autonomy to achieve contingency management brings with it the challenge of how to verify that the software can detect and diagnose contingencies when they occur. The approach used in this work to investigate the verification was two-fold: (1) to integrate in a single model the representation of the contingencies and of the data signals and software monitors required to identify those contingencies, and (2) to use tool-supported verification of the diagnostics design to identify gaps in coverage of the contingencies. Results presented here indicate that tool-supported verification of the adequacy and correct behavior of such diagnostic software for contingency management can improve on-going contingency analysis, thereby reducing the risk that change has introduced gaps in the contingency software

This paper describes the use of obstacle analysis to identify anomaly-handling requirements for a safety-critical, autonomous system. The software requirements for the system evolved during operations due to an on-going effort to increase the autonomous system's robustness. The resulting increase in autonomy also increased system complexity. This investigation used obstacle analysis to identify and to reason incrementally about new requirements for handling failures and other anomalous events. Results reported in the paper show that obstacle analysis complemented standard safety-analysis techniques in identifying undesirable behaviors and ways to resolve them. The step-by-step use of obstacle analysis identified potential side effects and missing monitoring and control requirements. Adding an availability indicator and feature-interaction patterns proved useful for the analysis of obstacle resolutions. The paper discusses the consequences of these results in terms of the adoption of obstacle analysis to analyze anomaly-handling requirements in evolving systems.

Test sequencing is a binary identification problem wherein one needs to develop a minimal expected cost test procedure to determine which one of a finite number of possible failure states, if any, is present. In this paper, we consider a multimode test sequencing (MMTS) problem, in which tests are distributed among multiple modes and additional transition costs will be incurred if a test sequence involves mode changes. The multimode test sequencing problem can be solved optimally via dynamic programming or AND/OR graph search methods. However, for large systems, the associated computation with dynamic programming or AND/OR graph search methods is substantial due to the rapidly increasing number of OR nodes (denoting ambiguity states and current modes) and AND nodes (denoting next modes and tests) in the search graph. In order to overcome the computational explosion, we propose to apply three heuristic algorithms based on information gain: information gain heuristic (IG), mode capability evaluation (MC), and mode capability evaluation with limited exploration of depth and degree of mode Isolation (MCLEI). We also propose to apply rollout strategies, which are guaranteed to improve the performance of heuristics, as long as the heuristics are sequentially improving. We show computational results, which suggest that the information-heuristic based rollout policies are significantly better than traditional information gain heuristic. We also show that among the three information heuristics proposed, MCLEI achieves the best tradeoff between optimality and computational complexity.

We consider the problem of constructing optimal and near-optimal test sequences for multiple fault diagnosis. The computational complexity of solving the optimal multiple-fault isolation problem is super exponential, that is, it is much more difficult than the single-fault isolation problem, which, by itself, is NP-hard. By employing concepts from information theory and AND/OR graph search and by exploiting the single fault testing strategies of Pattipati et al. (1990), we present several test sequencing algorithms for the multiple fault isolation problem. These algorithms provide a trade-off between the degree of suboptimality and computational complexity. Furthermore, we present novel diagnostic strategies that generate a diagnostic directed graph, instead of a traditional diagnostic tree, for multiple fault diagnosis. Using this approach, the storage complexity of the overall diagnostic strategy reduces substantially. The algorithms developed herein have been successfully applied to several real-world systems.

We present a hidden Markov model (HMM) based algorithm for fault diagnosis in systems with partial and imperfect tests. The HMM-based algorithm finds the most likely state evolution, given a sequence of uncertain test outcomes over time. We also present a method to estimate online the HMM parameters, namely, the state transition probabilities, the instantaneous probabilities of test outcomes given the system state and the initial state distribution, that are fundamental to HMM-based adaptive fault diagnosis. The efficacy of the parameter estimation method is demonstrated by comparing the diagnostic accuracies of an algorithm with complete knowledge of HMM parameters with those of an adaptive one. In addition, the advantages of using the HMM approach over a Hamming-distance based fault diagnosis technique are quantified. Tradeoffs in computational complexity versus performance of the diagnostic algorithm are also discussed.

Presents a comprehensive methodology for validating automatically generated software. The process consists of developing a fault-effect dependency model for the software, designing input stimuli to make the bugs manifest, designing tests to detect the incompatibilities from the intended behavior, and identifying the faulty code segment. A key feature of the methodology is the application of functional dependency modeling concepts, that have been proven to be robust in the testability analysis and fault diagnosis of large, complex hardware systems, to software verification and validation.

We consider the problem of constructing optimal and near-optimal multiple fault diagnosis (MFD) in bipartite systems with unreliable (imperfect) tests. It is known that exact computation of conditional probabilities for MFD is NP hard. The novel feature of our diagnostic algorithms is the use of Lagrangian relaxation and subgradient optimization methods to provide: 1) near optimal solutions for the MFD problem and 2) upper bounds for an optimal branch and bound algorithm. The proposed method is illustrated using several examples. Computational results indicate the following: 1) our algorithm has superior computational performance to the existing algorithms (approximately three orders of magnitude improvement over the algorithm by Z. Binglin et al. (1993)); 2) near optimal algorithm generates the most likely candidates with a very high accuracy; 3) our algorithm can find the most likely candidates in systems with as many as 1000 faults.