The Conversion of Dynamic Fault Trees to Stochastic Petri Nets, as a case of Graph Transformation

A model-to-model transformation from Dynamic Fault Trees to Stochastic Petri Nets, by means of graph transformation rules, is presented in this paper. Dynamic Fault Trees (DFT) are used for the reliability analysis of complex and large systems and represent by means of gates, how combinations or sequences of component failure events, lead to the failure of the system. DFTs need the state space solution which can be obtained by converting a DFT to a Stochastic Petri Net: this task is expressed by means of graph transformation rules, and is applied to a case of system.     

基于指针映射集的动态内存故障测试方法研究

动态内存故障在使用指针的程序中是普遍存在的,采用动态测试方法进行测试难以准确定位故障源.而现有的静态分析方法主要存在漏报和误报过多的情况.针对这些问题,提出了指针映射代数系统的概念,全面地反映了指针与内存之间的映射关系,并给出了面向不同故障的指针映射集的构造规则,以此为基础建立了动态内存故障模型.通过指针映射集和故障模型,可以自动检测内存释放异常、内存泄露和空指针引用等动态内存故障,提高了测试效率.在分析过程中,还综合应用了控制流图和路径条件,提高了测试结果的精度.实验结果表明,该方法能够有效检测动态内存故障,而且出于规则定义较为全面,漏报和误报率也较低.     

A minimization algorithm for automata generated fault trees with priority gates

Fault tree analysis is still widely practiced in high-hazard industries. We propose in this article an algorithm for the reduction of fault tree expressions that are generated from automata representations of failure behaviors. Automata formalisms are increasingly being used to describe systems exhibiting sequence-dependent failures—i.e., the overall outcome like a total failure of the system can depend on the order in which events occur. A set of paths leading to a safety-relevant state is encoded as a standard sum of product canonical form, and without any loss of the significance of the sequencing of events. That is, the corresponding fault tree expression is basically a Boolean formula which is extended with the necessary temporal features (event occurrence priority). Such expressions can then be reduced into minimal canonical forms by using the Boolean methods together with the required temporal logic calculus. Since minimal failure sequences can be determined from the obtained reduced models, the proposed approach can improve the analysis of the dynamic effects of the sequencing of faults and propagated errors in such models. As a consequence, it can have a positive impact on the design of failure prevention measures. A fault tolerant example system exhibiting dynamic behavior is used to highlight the benefits of the approach.

     

Fault diagnosis in dynamical systems: a graph theoretic approach

Fault diagnosis is a vital aspect in the design of operational control systems for large-scale systems with stringent requirements on safety and reliability. In this paper, we develop graph representations for the failure propagation in large-scale systems. Using this model, we present efficient algorithms for failure source identification for single and multiple faults, for diagnosis of faulty alarms, and for forewarning and fault simulation. All these algorithms are analysed for their worst-case complexities. The treatment is algorithmic and graph theoretic and no reference is made to the underlying physical systems.     

一种基于数据流分析的故障序列生成方法

故障注入是一种测评容错机制的有效方法,它通过有意识地向目标系统引入故障来加速测试容错机制的试验过程.目前大多数故障注入实验中采用的故障序列都是通过随机抽样获取的,容易造成故障潜伏,从而导致容错机制的评测结果不准确.本文提出一种基于数据流分析的故障序列生成方法.提出<故障注入位置,故障注入时间,故障类型,故障掩码>的单粒子故障模型.在此基础上,通过数据流活跃变量分析计算得出故障注入位置属性,以及定值-引用分析确定了故障注入时间属性.并以PowerPC8548处理器和它对应的Trace模拟器为实验平台,验证了该故障序列生成方法具有90%以上的失效加速比,较好地解决了故障潜伏问题.     

XSDyM: An XML graphical conceptual model for static and dynamic constraints

Data modelling is not only important to visualise the structural schema of data, but also to show the intended integrity constraints. In this paper, we propose a modelling approach called XML Static Dynamic Modelling (XSDyM). While a text-based schema definition is often the most common method used to describe XML, graphical modelling is more accepted as it is capable of visualising the schema definition more effectively for the reader. Conveying the dynamic constraints on XML graphical model requires a special treatment as the constraints basically comprehend the state transitions. It is important for an XML modelling to keep the basis as precise as possible to satisfy the nature of XML and at the same time be able to represent the constraints in an effective way. Using the XML tree-based modelling as the basis of the work, we proposed our own approach to convey the state transitions of the constraints, where it is inspired from the well-known state diagram and adopt some useful features of ORM modelling. We evaluate the correctness of our proposed modelling using a model which involves the checking of model transformations between the modelling and the equivalent XML schema languages.     

FINE: A fault injection and monitoring environment for tracing theUNIX system behavior under faults

The authors present a fault injection and monitoring environment (FINE) as a tool to study fault propagation in the UNIX kernel. FINE injects hardware-induced software errors and software faults into the UNIX kernel and traces the execution flow and key variables of the kernel. FINE consists of a fault injector, a software monitor, a workload generator, a controller, and several analysis utilities. Experiments on SunOS 4.1.2 are conducted by applying FINE to investigate fault propagation and to evaluate the impact of various types of faults. Fault propagation models are built for both hardware and software faults. Transient Markov reward analysis is performed to evaluate the loss of performance due to an injected fault. Experimental results show that memory and software faults usually have a very long latency, while bus and CPU faults tend to crash the system immediately. About half of the detected errors are data faults, which are detected when the system is tries to access an unauthorized memory location. Only about 8% of faults propagate to other UNIX subsystems. Markov reward analysis shows that the performance loss incurred by bus faults and CPU faults is much higher than that incurred by software and memory faults. Among software faults, the impact of pointer faults is higher than that of nonpointer faults     

Improved code defect detection with fault links

Fault links represent relationships between the types of code faults, or defects, and the types of components in which faults are detected. For example, our prior work validated that a fault link exists between Controller components and Control/Logic faults (such as unreachable code). Fault link information can guide code reviews, walkthroughs, testing, maintenance, and can advise fault seeding. In this paper, we use fault links to augment code reviews. Two experiments were undertaken to evaluate the usefulness of fault links, one with 26 Computer Science students and another with 24 software engineering professionals. The first experiment showed that fault link information assisted in finding more total defects and more ‘hard to detect’ defects, in the same amount of time, in a Java component of an online course management application. The experiment was repeated with professionals, adding a second Java component from the same application. For the second experiment, more total defects were found by the participants using fault link information for one of the two components and more hard to detect defects were found, in the same amount of time, in both Java components. The group using fault link information for code walkthroughs found, on average, 1.7–2 times more faults and 2–3 times more hard faults than the control group. Copyright © 2010 John Wiley & Sons, Ltd.     

基于故障传播的模块化BP神经网络电路故障诊断

大规模的数模混合电路所含故障模式众多,电路故障状态复杂,且易发生传播,因而电路故障诊断难度较大。针对大规模电路发生故障时存在故障传播的问题,提出一种基于故障传播的模块化BP神经网络（MBPFP）故障诊断方法。首先,在电路模块划分的基础上分析子电路间的故障传播,并将故障源和故障传播源"模块化";然后,通过子电路的异常检测模型进行一级定位,缩小故障原因集合,确定故障模块;最后,利用目标模块的BP神经网络模型进行二级定位,实现故障诊断并识别故障模式。与传统BP神经网络等方法进行比较的实验结果表明,MBPFP故障诊断方法具有较高的故障覆盖率,在定位准确率方面提高了至少8个百分点,其性能优于传统BP神经网络等方法。     

Common Trends in Software Fault and Failure Data

The benefits of the analysis of software faults and failures have been widely recognized. However, detailed studies based on empirical data are rare. In this paper, we analyze the fault and failure data from two large, real-world case studies. Specifically, we explore: 1) the localization of faults that lead to individual software failures and 2) the distribution of different types of software faults. Our results show that individual failures are often caused by multiple faults spread throughout the system. This observation is important since it does not support several heuristics and assumptions used in the past. In addition, it clearly indicates that finding and fixing faults that lead to such software failures in large, complex systems are often difficult and challenging tasks despite the advances in software development. Our results also show that requirement faults, coding faults, and data problems are the three most common types of software faults. Furthermore, these results show that contrary to the popular belief, a significant percentage of failures are linked to late life cycle activities. Another important aspect of our work is that we conduct intra- and interproject comparisons, as well as comparisons with the findings from related studies. The consistency of several main trends across software systems in this paper and several related research efforts suggests that these trends are likely to be intrinsic characteristics of software faults and failures rather than project specific.     

Software faults: A quantifiable definition

An important aspect of developing models relating the number and type of faults in a software system to a set of structural measurement is defining what constitutes a fault. By definition, a fault is a structural imperfection in a software system that may lead to the system's eventually failing. A measurable and precise definition of what faults are makes it possible to accurately identify and count them, which in turn allows the formulation of models relating fault counts and types to other measurable attributes of a software system. Unfortunately, the most widely used definitions are not measurable—there is no guarantee that two different individuals looking at the same set of failure reports and the same set of fault definitions will count the same number of underlying faults. The incomplete and ambiguous nature of current fault definitions adds a noise component to the inputs used in modeling fault content. If this noise component is sufficiently large, any attempt to develop a fault model will produce invalid results. In this paper, we base our recognition and enumeration of software faults on the grammar of the language of the software system. By tokenizing the differences between a version of the system exhibiting a particular failure behavior, and the version in which changes were made to eliminate that behavior, we are able to unambiguously count the number of faults associated with that failure. With modern configuration management tools, the identification and counting of software faults can be automated.     

Automatic modeling and fault diagnosis of car production lines based on first-principle qualitative mechanics and semantic web technology

Fault diagnosis is critical for intelligent manufacturing by monitoring the status of a production line and preventing financial loss. Model-based fault diagnosis has the advantage of being able to explain the cause and propagation of faults over model-free diagnosis, but would need knowledge about the configuration model and context-specific information of the production line. Ontology modelling can provide context-specific information on top of a configuration model to benefit fault diagnosis. Typically ontologies are manually constructed and then used by a reasoner based on a set of predefined rules. From the perspective of fault diagnosis, this approach works as an expert system where both the ontology models and predefined rules are specific to a given system. Once the system has changed which happens from time to time as repairs and updates in a production line, or in the case of a different system, the ontology models and predefined rules would need to be manually modified or reconstructed. Here a model-based method is proposed to automate generation of configuration models with context-specific information using semantic web technology when a production line is healthy, and to use the generated configuration model and information for diagnosis when the production line has a fault. The method does not rely on predefined rules and reasoners, but rather uses dynamics models that are based on first-principle qualitative mechanics. It uses numerical optimization to minimize the discrepancy between sensor data from the production line and from simulation running the dynamics model to achieve automatic configuration modelling and fault diagnosis. With three use cases commonly found for a production line, i.e. automatic sensor placement modeling or misplacement diagnosis, motor fault diagnosis with single sensor modality, and motor fault diagnosis with sensory substitution, the feasibility of the proposed method is demonstrated. The method’s faster computational speed and comparable accuracy to a quantitative model-based approach suggests it may complement and accelerate the latter with early-stage selection of candidate models for both modelling and fault diagnosis.     

FPGA互连测试中的反馈桥接故障覆盖问题

现场可编程门阵列(FPGA)内部资源众多,其中互连资源出现故障的概率远远高于片内其他资源,而在以往许多互连测试研究中,所生成的测试配置存在无法覆盖反馈桥接故障的难题,所以较难有测试配置实现故障列表的100%覆盖。因此通过约束桥接故障只发生在单个查找表(LUT)内的信号线上,并结合单项函数,对反馈桥接故障模型进行优化改进,从根本上解决难题；然后对优化后的反馈桥接故障设置相应的约束条件,再使用布尔可满足性理论(SAT)生成满足约束条件的测试配置。采用优化后的故障模型对ISCAS"89基准电路进行了测试配置生成实验,结果表明生成的测试向量解决了反馈桥接故障的覆盖难题,并且在实现故障列表的100%覆盖下,优化后的故障模型所需要的测试配置数最少。     

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     

综合故障树分析方法在容错计算机系统中的应用

该文运用二元决策图（Binary Decision Diagram）分析传统的静态故障树，运用Markov链分析新兴的动态故障树，由此形成一种创新性的故障诊断方法：综合故障树（Integrated Fault Tree）分析法。综合故障树分析法运用分而治之的策略处理各种故障，不仅加深了故障诊断、分析的精度，同时也拓展了故障树分析法的运用领域。该文结合实例，运用综合故障树分析法解决容错计算机系统中动态时序特性的建模困难问题；分析结果表明，在容错计算机系统中运用此方法，可以有效地对系统建模和分析系统可靠性。     

Fault Prediction and Compensation Functions in a Diagnostic Knowledge-Based System for Hydraulic Systems

Fault prediction and fault compensation are beneficial for the production technology and give a new dimension to fault diagnosis in technical systems. The overall goal of this paper is the presentation of fault prediction and fault compensation procedures as they are studied, implemented and embedded in a real time expert system. This expert system detects and diagnoses faults in hydraulic systems. For this purpose dynamic modelling information, on-line sensor information, special features of the domain of hydraulic systems and expert systems technology are used co-operatively.     

基于DFT的飞机电源网络化故障诊断方法

针对目前飞机恒速恒频交流(CSCF-AC)电源系统故障诊断方法中存在的虚警率高、信息不能共享等问题,提出一种基于动态故障树(DFT)的CSCF-AC电源系统网络化故障诊断方法。通过在普通布尔算子中引入BEFORE算子,对CSCF-AC电源系统动态故障树进行定性分析,得到系统的失效模式,在此基础上建立一个包括机内自检、地面诊断和远程专家诊断在内具有三层结构的网络化故障诊断系统。实验结果表明,该方法有效可靠,具有一定的工程实用性。     

一种软件故障诊断过程框架

软件在国民经济和社会生活中发挥着重要作用.软件出现故障给人们的工作、生活带来不便,甚至造成严重危害.但是当前所进行的多为软件故障诊断中单项活动的研究,较少有对各项诊断活动及其相应方法进行有效集成的研究.文中分析软件失效机理和软件故障产生原因,讨论软件故障模型,提出一种由故障检测、故障定位、故障排除、交付等组成的集成化的...     

基于SAT求解器的故障树最小割集求解算法

故障树分析广泛应用于核工业、航空航天和交通控制等安全攸关领域的安全性分析。求解故障树的最小割集是故障树分析的关键步骤。目前,对于大规模故障树的最小割集的求解方法主要是将故障树转化为二元决策图之后求解,其主要缺点在于算法在时间和空间上的消耗严重依赖良好的变量顺序。为了减少存储资源并加快求解速度,提出了一种基于可满足性问题的故障树最小割集求解算法。首先,将求解故障树最小割集问题转化为求解布尔可满足性问题。然后,利用可满足性问题求解器,通过迭代分析求得最小可满足解集合,即为对应故障树的最小割集。实验表明,本文算法求得的最小割集准确、有效并且在空间和时间上的消耗均要优于传统的基于二元决策图的故障树最小割集求解算法。