Finite-state machine embeddings for nonconcurrent error detection and identification

In digital sequential systems that operate over several time steps, a state-transition fault at any time step during the operation of the system can corrupt its state and render its future functionality useless. Such state-transition faults are usually handled by embedding the given sequential system into a larger one, in a way that preserves the state evolution and properties of the original system while enabling an external mechanism to perform checks to detect, identify and correct errors in the encoded state of this redundant system. Checking is typically performed concurrently (i.e., at the end of each time step) and can potentially cause high power consumption or an overall slowdown in the system; more importantly, concurrent checking imposes significant reliability requirements on the error-detection/identification mechanism. We develop a methodology for systematically constructing embeddings of finite-state machines so that the external mechanism can capture transient state-transition faults via checks that are performed in a nonconcurrent manner (e.g., periodically instead of every time step). More specifically, by characterizing nonconcurrent error-detecting/identifying capabilities in terms of state encoding constraints and redundant dynamics, the proposed approach can be used to construct a redundant version of the given finite-state machine (FSM) that allows the external mechanism to detect and identify errors due to past state-transition faults based on an analysis of the current, possibly corrupted FSM state. As a result, the checker in such designs can operate at a slower speed than the rest of the system which relaxes the stringent requirements on its reliability.     

Error detection and correction in switched linear controllers via periodic and non-concurrent checks

Control systems that utilize switched linear controllers have proven to be useful (and, in some cases, essential) for accomplishing certain control objectives in particular classes of plants. These controllers are often digital in nature and, as such, are subject to internal hardware malfunctions (faults). In this paper, we present a systematic methodology for constructing embeddings to protect switched linear controllers against hardware faults that corrupt their internal state. Our methodology is based on replacing the original controller with a redundant (higher dimensional) controller that preserves the functionality of the original controller while enabling error detection and correction. More importantly, this methodology allows an external mechanism to detect and identify transient state-transition faults through non-concurrent (e.g. periodic) parity checks. The resulting error detection and correction procedures can then be performed periodically, thereby relaxing the reliability requirements and overhead associated with the checking mechanism.     

Probabilistic detection of FSM single state-transition faults based on state occupancy measurements

This note discusses a probabilistic methodology for detecting single permanent or transient functional changes in the state-transition mechanism of a deterministic finite-state machine (FSM). The associated probabilistic detector observes the empirical frequencies with which different states are occupied and detects faults by analyzing the discrepancy between the observed state occupancy measurements and the expected frequencies. In addition to state occupancy measurements, the detector requires a statistical characterization of the input, but does not need to know the order with which states appear or the exact input sequence that is applied to the FSM. These features can be useful in settings where the input/state order may not be known due to synchronization, communication or other constraints.     

Nonconcurrent error detection and correction in fault-tolerant linear finite-state machines

In this paper, we construct fault-tolerant linear finite-state machines (LFSMs) in which error detection and correction can be performed nonconcurrently (e.g., periodically). More specifically, by jointly choosing the state encoding constraints and the redundant dynamics of the fault-tolerant LFSM, we enable an external checker to detect and identify errors due to past faults based on the current, possibly corrupted state of the LFSM. The paper presents systematic constructions of fault-tolerant LFSMs based on a characterization of nonconcurrent error detection/correction in terms of state encoding constraints and redundant dynamics. In particular, we develop a scheme that uses Bose-Chaudhuri-Hocquenghem (BCH) coding and obtains fault-tolerant LFSMs that require 2D additional state variables and have the ability to correct up to D errors in any state variable at any time step in the time interval consisting of the latest N time steps of operation. The construction uses the minimum possible number of additional state variables and requires an error detecting/correcting mechanism with computational complexity that is only linear in N.     

椭圆曲线点乘的抗故障攻击FSM控制器设计

为提高有限状态机(FSM)控制器的抗故障攻击能力,提出一种非并发故障检测方案。方案利用线性码的故障检错特性,通过在状态机电路中建立故障传播路径来实现。设计了基于NAF编码的从左至右扫描点乘算法的安全有限状态机电路,并对该电路进行了仿真验证与分析。通过仿真验证,与并发故障检测方案相比,该设计能够在减少状态机频繁译码工作量的情况下,正确检测错误并报警,提高了抗故障攻击能力。     

Designs of Bisimilar Petri Net Controllers With Fault Tolerance Capabilities

This paper proposes an approach for providing tolerance against faults that may compromise the functionality of a given controller modeled by a Petri net. The method is based on embedding the given Petri net controller into a larger (redundant) Petri net controller that retains the original functionality and properties, and uses additional places, connections, and tokens to impose invariant conditions that allow the systematic detection and identification of faults via linear parity checks. In particular, this paper considers two types of redundant Petri net controllers: 1) nonseparate redundant Petri net controllers have the same functionality as the given Petri net controller and allow for fault detection and identification, but do not necessarily retain the given controller intact; and 2) separate redundant Petri net controllers are a special case of the nonseparate redundant controllers that retain the given Petri net controller intact but enhance it with additional places to enable fault detection and identification. The work in this paper obtains complete characterizations of both types of redundant controllers along with necessary and sufficient conditions for them to be bisimulation equivalent to the given original Petri net controller. In addition, this paper discusses how each type of redundant controllers can be designed to have desirable fault detection and identification capabilities. When the bisimulation equivalence requirement is not directly enforced, nonseparate redundant controllers can potentially have advantages over separate ones (e.g., they can use fewer connections to detect and identify the same number of faults). An example of a Petri net controller for a production cell and its fault tolerance capabilities using separate and nonseparate embeddings is used to illustrate the approach.     

The use of self checks and voting in software error detection: anempirical study

The results of an empirical study of software error detection using self checks and N-version voting are presented. Working independently, each of 24 programmers first prepared a set of self checks using just the requirements specification of an aerospace application, and then each added self checks to an existing implementation of that specification. The modified programs were executed to measure the error-detection performance of the checks and to compare this with error detection using simple voting among multiple versions. The analysis of the checks revealed that there are great differences in the ability of individual programmers to design effective checks. It was found that some checks that might have been effective failed to detect an error because they were badly placed, and there were numerous instances of checks signaling nonexistent errors. In general, specification-based checks alone were not as effective as specification-based checks combined with code-based checks. Self checks made it possible to identify faults that had not been detected previously by voting 28 versions of the program over a million randomly generated inputs. This appeared to result from the fact that the self checks could examine the internal state of the executing program, whereas voting examines only final results of computations. If internal states had to be identical in N-version voting systems, then there would be no reason to write multiple versions     

Deriving Test Suites with the Guaranteed Fault Coverage for Extended Finite State Machines

Extended finite state machines (EFSMs) are widely used when deriving tests for checking the functional requirements for software implementations. However, the fault coverage of EFSMbased tests covering appropriate paths, variables, etc., remains rather obscure. Furthermore, these tests are known be incapable of detecting many functional faults frequently occurring in EFSM-based implementations. In this paper, an approach is proposed for deriving complete tests with the help of a proper Java EFSM implementation. Since the software is based on a template, the faults turn directly into EFSM faults. The method proposed here makes it possible to derive test suites that can detect functional faults. In the first step, the EFSM-based test suite derived by a well-known method is checked for completeness with respect to the faults generated by the μJava tool. Then, each undetected fault is easily mapped into an EFSM mutant. In the next step, some FSM abstraction is used to derive a distinguishing sequence for two finite-state machines (if such a sequence exists), which is added to the current test suite. The test derived in this way is complete with respect to the faults generated by μJava. If the corresponding FSM derived by EFSM modeling is too complex or no such FSM can be derived, the resulting test suite can be incomplete. However, the experiments performed by us clearly show that the original test suite extended by distinguishing sequences can detect many functional faults in software implementations when the given EFSM is used as a specification for the system.     

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

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

Interprocedural and Flow-Sensitive Type Analysis for Memory and Type Safety of C Code

The explicit memory management and type conversion endow the C language with flexibility and performance that render it the de facto language for system programming. However, these appealing features come at the cost of programs’ safety. Due to the C language permissiveness, highly skilled but inadvertent programmers often spawn insidious programming errors that yield exploitable code. In this paper, we present a novel type and effect analysis for detecting memory and type errors in C source code. We extend the standard C type system with effect, region, and host annotations that hold valuable safety information. We also define static safety checks to detect safety errors using the aforementioned annotations. Our analysis performs in an intraprocedural phase and an interprocedural phase. The flow-sensitive and alias-sensitive intraprocedural phase propagates type annotations and applies safety checks at each program point. The interprocedural phase generates and propagates unification constraints on type annotations across function boundaries. We present an inference algorithm that automatically infers type annotations and applies safety checks to programs without programmers’ interaction.     

不确定规划中非循环可达关系的求解方法

对一个不确定状态转移系统求多个规划问题,那么获得不确定状态转移系统的状态可达关系可以方便求解规划问题,减少冗余计算,建立系统的引导信息。提出一个关于矩阵求不确定领域的状态可达性关系的方法,主要思想是以矩阵乘法来模拟状态转移系统中状态转移,对不确定动作带来的扩散和确定关系带来的聚合进行了统计和处理,从而获得状态可达信息。证明了方法的正确性和有效性。在不确定规划中确定了状态之间的可达性关系,可以在求规划解时删除对规划没有用的状态节点和状态动作序偶;选择能到达目标节点的状态节点和状态动作序偶;进行启发式正向搜索;减少大量冗余计算;提高求解效率。     

An empirical, path-oriented approach to software analysis and testing

Error flow analysis and testing techniques focus on the introduction of errors through code faults into data states of an executing program, and their subsequent cancellation or propagation to output. The goals and limitations of several error flow techniques are discussed, including mutation analysis, fault-based testing, PIE analysis, and dynamic impact analysis. The attributes desired of a good error flow technique are proposed, and a model called dynamic error flow analysis (DEFA) is described that embodies many of these attributes. A testing strategy is proposed that uses DEFA information to select an optimal set of test paths and to quantify the results of successful testing. An experiment is presented that illustrates this testing strategy. In this experiment, the proposed testing strategy outperforms mutation testing in catching arbitrary data state errors.     

SpaceWire冗余网络故障检测恢复技术实现

为提高SapceWire网络可靠性,基于SpaceWire-D提出了一种应用于SpaceWire冗余网络的故障检测恢复技术。网络节点通过比较主、备份端口收到的时间码来判断链路故障状态,在确认主链路发生故障后,节点自动启用备份端口工作。通过引入时间码抖动容限参数,提高了节点对故障判断的准确性,避免了故障误判。测试结果表明,即使故障链路未与节点直接连接,节点也能够在一个时间槽长度内检测到链路故障并自动切换至备份链路。此技术保证了网络故障情况下的数据正确传输,提高了SpaceWire网络的可靠性,是一种稳定可靠的故障检测恢复技术。     

基于故障观测器的多无人机姿态一致性控制

在多个固定翼无人机姿态主从式一致性控制过程中,给出单个固定翼无人机在理想情况下的姿态动力学模型,即名义模型。考虑到无人机在实际运行过程中存在的外部干扰、状态测量误差、控制器微小故障以及无人机实际模型与名义模型之间的偏移,提出一种基于观测器和神经网络的故障检测方法,以实时检测出无人机中存在的故障、模型不确定以及干扰情况。基于无人机名义模型和检测出的故障及干扰,设计主从式多无人机姿态一致性控制器,以实现多无人机姿态的一致性准确跟踪。仿真结果表明,在外部干扰、状态测量误差与控制器微小故障下,与基于神经网络的直接姿态一致性控制器相比,该控制器能够使得无人机的姿态运动状态更接近于期望状态。     

Algebraic approaches for fault identification in discrete-event systems

In this note, we develop algebraic approaches for fault identification in discrete-event systems that are described by Petri nets. We consider faults in both Petri net transitions and places, and assume that system events are not directly observable but that the system state is periodically observable. The particular methodology we explore incorporates redundancy into a given Petri net in a way that enables fault detection and identification to be performed efficiently using algebraic decoding techniques. The guiding principle in adding redundancy is to keep the number of additional Petri net places small while retaining enough information to be able to systematically detect and identify faults when the system state becomes available. The end result is a redundant Petri net embedding that uses 2k additional places and enables the simultaneous identification of 2k-1 transition faults and k place faults (that may occur at various instants during the operation of the Petri net). The proposed identification scheme has worst-case complexity of O(k(m+n)) operations where m and n are respectively the number of transitions and places in the given Petri net.     

An unsupervised artificial neural network versus a rule-based approach for fault detection and identification in an automated assembly machine

Artificial neural networks (ANNs) are suitable for fault detection and identification (FDI) applications because of their pattern recognition abilities. In this study, an unsupervised ANN based on Adaptive Resonance Theory (ART) is tested for FDI on an automated O-ring assembly machine testbed, and its performance and practicality are compared to a conventional rule-based method. Three greyscale sensors and two redundant limit switches are used as cost-effective sensors to monitor the machine’s assembly process. Sensor data are collected while the machine is operated under normal condition, as well as 10 fault conditions. Features are selected from the raw sensor data, and data sets are created for training and testing the ANN. The performance of the ANN for detecting and identifying known, unknown and multiple faults is evaluated; the performance is compared to a conventional rule-based method using the same data sets. Results show that the ART ANN is able to achieve excellent fault detection performance with minimal modeling requirements; however, the performance depends on careful tuning of its vigilance parameter. Although the rule-based system requires more effort to set up, it is judged to be more useful when unknown or multiple faults are present. The ART network creates new outputs for unknown and multiple fault conditions, but it does not give any more information as to what the new fault is. By contrast, the rule-based method is able to generate symptoms that clearly identify the unknown and multiple fault conditions. Thus, the rule-based method is judged to be the most feasible method for FDI applications.     

Minimization of mealy finite-state machines by using the values of the output variables for state assignment

Structural models of finite-state machines (FSMs) that make it possible to use the values of the output variables for encoding the internal states are studied. To minimize the area (the parameter area is used to denote cost in the context of this paper) of FSM implementation, it is proposed to use the structural model of the class D FSM. A method for the design of the class D FSM in FPGA is proposed. This method involves two phases—splitting the internal states of the FSM (to satisfy the necessary conditions for the construction of the class D FSM) and encoding the internal states (to ensure that the codes are mutually orthogonal). It is shown that the proposed method reduces the area of FSM implementation for all families of FPGAs of various manufacturers by a factor of 1.41–1.72 on average and by a factor of two for certain families. Practical issues concerning the method and the specific features of its use are discussed, and possible directions of the elaboration of this approach are proposed.     

一种逆向分析协议状态机模型的有效方法

网络协议的逆向分析技术无论对可信软件的验证、保护还是对恶意软件机理的分析都具有重要用途。由于协议的内在复杂性,重构与其源程序一致的高级模型对分析尤为有益,其中又以有限状态机模型最为典型。建立一种重构网络协议状态机模型的有效方法,主要依据所记录的协议会话的消息流及协议软件实际执行的指令流,通过对指令流反编译并应用改进的形式分析及验证技术构建出状态对象、转移关系及状态转移条件。该方法从协议的会话实例重构出充分一般的状态机模型,效率可行并具有逻辑上可证明的精确性。在详细阐述理论基础之后,也讨论了该方法的实现和应用。     

不确定规划中状态循环可达关系的求解方法

在不确定规划领域中, 不确定状态转移系统求规划解常常会搜索大量无用的状态和动作, 造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算, 为系统提供引导信息。以非循环可达关系为基础, 定义矩阵的计算规则, 使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等, 并设计了求循环可达关系的算法, 且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系, 在求规划解的过程中可以删除大量无用的状态动作序偶, 降低问题规模, 提高求解规划问题的效率。     

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.