格值有限状态机的一些性质

讨论格值有限状态机强连通性、循环性、完全性以及交换性等一些代数性质,证明若两个格值有限状态机之间存在满足一定条件的同态映射时,它们之间的这些性质之间的关系,还给出了格值有限状态机的一些积的定义,以及对积的一些性质进行了讨论,也得到了一些结果。     

Mizumoto格值有限自动机及其最小化

提出取值为格半群的Mizumoto格值有限自动机的概念,得到基于模糊字符串的Mizumoto格值有限自动机的扩张模型,并详细讨论了其性质。同时建立了扩张Mizumoto格值有限自动机与标准扩张Mizumoto格值有限自动机的等价性,在此基础上给出了其最小化算法。     

格值有限自动机等价判定算法

引入了完备L-Fuzzy矩阵的概念,给出了基于格半群的模糊有限自动机的形式化定义,即完备格值有限自动机,研究了它的主要性质;给出了完备格值有限自动机的行为矩阵,从行为矩阵出发,给出了自动机状态等价和自动机等价的定义。最后,得到了该类自动机等价的判定算法。     

FSM状态间逻辑条件检验的算法研究

有限状态机(FSM)是VLSI控制结构的一种映射,它的自动综合成为设计自动化的一个十分重要的环节和途径。本文讨论在FSM自动综合中输入阶段的状态间逻辑条件检验的问题,研究分析状态间逻辑条件检验的相互关系及影响,并提出了FSM状态间逻辑条件检验的优化算法,从而使时间复杂度降低,实现更加简便。最后,本文给出了优化算法的流程和一些实验结果,结果令人满意。     

HSM2：改进的有限状态机状态化简的启发式算法

在时序电路的自动综合中，状态化简作为一个重要的组成部分，对综合后电路的面积、时延、功耗和验证有着重要的影响。状态化简作为一个NP难题，人们在过去的几十年中对它作了大量的深入研究。     

格值有限状态自动机的半群

提出了格值有限状态自动机的定义,给出了格值有限状态自动机的两种同余关系,研究了格值有限状态自动机的半群的若干性质,最后给出了两种有限半群E(A)和E(A)的关系。     

N个有限状态机的死锁和死环回避算法

死锁和死环是分布式系统或计算机网络中进程间通信时经常发生的逻辑错误，它们往往造成分布式系统中的部分主机或整个系统瘫痪，本文提出两个回避死锁和死环的算法，这些算法可被用来设计分布式系统的通信协议，从而提高分布式系统的可靠性和减少协议开发成本。     

基于协议状态有限机的系统扫描检测算法

针对现有扫描检测算法对隐蔽扫描、慢扫描无法识别的不足,提出了基于协议状态有限机的检测算法,该算法能更准确地检测出普通扫描,对隐蔽扫描、慢扫描等现有技术难以检测的扫描也有较好的检测效果。实验测试表明该算法能提高系统扫描检测性能,降低误报率和报警次数。     

基于状态机子图同构匹配的私有工控协议溯源

在对工业互联网设备私有工控协议进行安全分析时,溯源其采用的工控网络协议标准十分困难。文章提出一种基于状态机子图同构匹配的私有工控协议溯源方法,可快速匹配私有工控协议所采用的工控网络协议标准。该方法首先对私有工控协议流量数据进行逆向解析,通过聚类算法提取消息格式和关键字段,根据关键字段构造增广前缀树(Augmented Prefix Tree Acceptor,APTA),推断出协议状态机图;然后采用子图同构匹配算法将该状态机图与工控协议标准状态机图进行子图匹配,解决流量数据有限导致生成状态机图不完整的问题。实验结果表明,该方法溯源准确率在95%以上,可快速定位私有协议采用的工控网络协议标准,从而为进一步的安全分析提供帮助。     

扰动模糊有限状态机的转移结构

利用代数方法和扰动模糊集的概念,引入了扰动模糊有限状态机概念。为研究扰动模糊有限状态机的转移结构,提出了扰动模糊有限状态机的扰动后继、扰动子系统、扰动子机、扰动生成元、扰动基等概念,并研究了其相关性质。     

Studying the separability relation between finite state machines

Several authors have studied the relationships between non‐deterministic finite state machines (FSMs). These relationships can be used, for example, for deriving conformance tests from specifications represented by FSMs. In this paper, the separability relation between FSMs is studied. In particular, an algorithm is presented that derives a shortest separating sequence of two non‐deterministic FSMs. Given FSMs S with n states and T with m states, it is shown that the upper bound on the length of a shortest separating sequence is 2^mn−1. Moreover, the upper bound is shown to be reachable. However, according to the conducted experiments, on average, the length of a shortest separating sequence of FSMs S and T states is less than mn and the existence of a separating sequence significantly depends on the number of non‐deterministic transitions in these FSMs. The proposed algorithm can also be used for deriving a separating sequence of two different states of a single FSM or for deriving a separating sequence of three or more FSMs. Copyright © 2007 John Wiley & Sons, Ltd.     

Parallel algorithms for reducing derivation time of distinguishing experiments for nondeterministic finite state machines

Many approaches have been proposed for deriving tests from finite state machine (FSM) specifications with respect to some established coverage criteria. A fundamental core problem in FSM-based testing relates to the derivation of input sequences that can distinguish states of an FSM specification, aka distinguishing sequences. A major effort in the construction of these sequences is based on the derivation of a successors search-tree labeled by sets of pairs of states of the given machine. We aim at reducing the time associated with such constructions through the use of state-of-the-art parallel technologies. Namely, we propose a parallel algorithm that we implement and evaluate on multicore CPUs and on many-core GPUs. We evaluate two alternative GPU implementations that use the CUDA and Thrust software platforms and a network of workstations based solution. The latter sports a workload partitioning based on Divisible Load Theory. A rigorous set of experiments highlights the differences of the proposed implementations in terms of execution time and speedup.     

A practical approach for testing timed deterministic finite state machines with single clock

Finite State Machines (FSMs) are widely used for verification and testing of many reactive systems and many methods are proposed for generating tests from FSMs with the guaranteed fault coverage. However, some systems can only be properly described when time constraints are considered, advocating the adoption of models with the notion of time. In this paper, a method for deriving conformance tests with the guaranteed fault coverage from a Timed FSM (TFSM) with a single clock is presented. Test derivation is based on a given fault domain that allows the derivation of test suites with reasonable length. More precisely, the fault domain includes every possible faulty TFSM implementation with the known largest time constraints boundaries and minimal duration of time guards. Given a deterministic possibly partial TFSM specification, a complete test suite that guarantees the detection of all faulty implementations with respect to the above fault domain is derived. Experiments with randomly generated timed FSMs are conducted to determine length of obtained test suites and assess the impact of varying the TFSM specification parameters on length of obtained test suites. Further, experiments with both untimed and timed machines are conducted and these experiments show that similar patterns for timed and untimed machines are obtained with respect to varying the number of states, inputs, and outputs of machines.     

Exhaustive property oriented model-based testing with symbolic finite state machines

We advocate a fusion of property-oriented testing (POT) and model-based testing (MBT). The existence of a symbolic finite state machine (SFSM) model fulfilling the properties of interest is exploited for property-directed test data generation and to create a test oracle. A new test generation strategy is presented for verifying that the system under test (SUT) satisfies the same LTL safety conditions over a given set of atomic propositions as the model. We prove that this strategy is exhaustive in the sense that any SUT violating at least one of these formulae will fail at least one test case of the generated suite. It is shown that the existence of a model allows for significantly smaller exhaustive test suites as would be necessary for POT without reference models. As a corollary, the main theorem also generalises a known result about SFSM-based conformance testing for language equivalence. Our approach fits well to industrial development processes for (potentially safety-critical) cyber-physical systems, where both models and properties representing system requirements are elaborated for development, verification, and validation.     

Factorisation of finite state machines under strong and observational equivalences

The factorisation problem is to construct the specification of a submoduleX when the specifications of the system and all submodules butX are given. It is usually described by the equation where P and X are submodules of system Q, ¦ is a composition operator, and is the equivalence criterion. In this paper we use a finite state machine (FSM) model consistent with CCS and study two factorisation problems:P |||P Q andP |||P Q, where ||| is a derived CCS composition operator, and represent strong and observational equivalences. Algorithms are presented and proved correct to find the most general specification of submoduleX forP |||P Q withQ -deterministic and forP |||P Q withQ deterministic. Conditions on the submachines of the most general solutions that remain solutions toP |||P Q(P |||P Q) are given. This paper extends and is based on the work of M. W. Shields.     

Incremental testing of finite state machines

The automatic generation of test suites for systems modelled as finite state machines (FSMs) is an important problem that impacts several critical applications. Known methods that automatically generate tests for FSMs, specially the W‐method and some derivations, strongly assume that the number of system states is small. If the overall number of states in the FSM specification is relatively large, such methods become difficult to use. However, often in practice, a system is defined as a combination of several subsystems, with the latter already independently designed, developed and tested. In this paper, we define the concept of combined FSMs and introduce a new method to test modular compositions of FSMs. This method allows for a new incremental testing strategy that turns the testing of new systems into a much more scalable process. As an example, we present an infinite family of naturally occurring FSM models for which our method produces exponentially more compact test suites than the W‐method. Copyright © 2012 John Wiley & Sons, Ltd.     

Heuristics for fault diagnosis when testing from finite state machines

When testing from finite state machines, a failure observed in the implementation under test (IUT) is called a symptom. A symptom could have been caused by an earlier state transfer failure. Transitions that may be used to explain the observed symptoms are called diagnosing candidates. Finding strategies to generate an optimal set of diagnosing candidates that could effectively identify faults in the IUT is of great value in reducing the cost of system development and testing. This paper investigates fault diagnosis when testing from finite state machines and proposes heuristics for fault isolation and identification. The proposed heuristics attempt to lead to a symptom being observed in some shorter test sequences, which helps to reduce the cost of fault isolation and identification. The complexity of the proposed method is analysed. A case study is presented, which shows how the proposed approach assists in fault diagnosis. Copyright © 2006 John Wiley & Sons, Ltd.     

Testing aspect‐oriented programs with finite state machines

Aspect‐oriented programming yields new types of programming faults due to the introduction of new constructs for dealing with crosscutting concerns. To reveal aspect faults, this paper presents a framework for testing whether or not aspect‐oriented programs conform to their state models. It supports two families of strategies (i.e. structure‐oriented and property‐oriented) for automated generation of aspect tests from aspect‐oriented state models. A structure‐oriented testing strategy derives tests and test code from an aspect‐oriented state model to meet a given structural coverage criterion, such as state coverage, transition coverage, or round trip. A property‐oriented testing strategy generates test code from the counterexamples of model checking. Two such strategies are checking an aspect‐oriented state model against trap properties and checking mutants of aspect models against system properties. Mutation analysis of aspect‐oriented programs is used to evaluate the effectiveness of these testing strategies. The experiments demonstrate that testing aspect‐oriented programs against their state models can detect many aspect faults. The comparative evaluations also reveal that the structure‐oriented and property‐oriented testing strategies complement each other—some aspect faults were detected by the structure‐oriented strategies, but not by the property‐oriented strategies and vice versa. Copyright © 2010 John Wiley & Sons, Ltd.     

Integration testing of object‐oriented components using finite state machines

In object‐oriented terms, one of the goals of integration testing is to ensure that messages from objects in one class or component are sent and received in the proper order and have the intended effect on the state of the objects that receive the messages. This research extends an existing single‐class testing technique to integration testing of multiple classes. The single‐class technique models the behaviour of a single class as a finite state machine, transforms the representation into a data flow graph that explicitly identifies the definitions and uses of each state variable of the class, and then applies conventional data flow testing to produce test case specifications that can be used to test the class. This paper extends those ideas to inter‐class testing by developing flow graphs, finding paths between pairs of definitions and uses, detecting some infeasible paths and automatically generating tests for an arbitrary number of classes and components. It introduces flexible representations for message sending and receiving among objects and allows concurrency among any or all classes and components. Data flow graphs are stored in a relational database and database queries are used to gather def‐use information. This approach is conceptually simple, mathematically precise, quite powerful and general enough to be used for traditional data flow analysis. This testing approach relies on finite state machines, database modelling and processing techniques and algorithms for analysis and traversal of directed graphs. The paper presents empirical results of the approach applied to an automotive system. This work was prepared by U.S. Government employees as part of their official duties and is, therefore, a work of the U.S. Government and not subject to copyright. Published in 2006 by John Wiley & Sons, Ltd.