基于EFSM用户自定义故障模型的测试集生成

提出了一种用户自定义故障的EFSM测试集生成方法。该方法应用EFSM切片对EFSM模型进行合理的缩减,有效地避免了从EFSM到FSM转换得到测试集而产生状态空间爆炸的问题,也得到最短的测试用例集合。实验结果表明了新算法对生成最短EFSM测试集是有效的。     

Estimating the feasibility of transition paths in extended finite state machines

There has been significant interest in automating testing on the basis of an extended finite state machine (EFSM) model of the required behaviour of the implementation under test (IUT). Many test criteria require that certain parts of the EFSM are executed. For example, we may want to execute every transition of the EFSM. In order to find a test suite (set of input sequences) that achieves this we might first derive a set of paths through the EFSM that satisfy the criterion using, for example, algorithms from graph theory. We then attempt to produce input sequences that trigger these paths. Unfortunately, however, the EFSM might have infeasible paths and the problem of determining whether a path is feasible is generally undecidable. This paper describes an approach in which a fitness function is used to estimate how easy it is to find an input sequence to trigger a given path through an EFSM. Such a fitness function could be used in a search-based approach in which we search for a path with good fitness that achieves a test objective, such as executing a particular transition, and then search for an input sequence that triggers the path. If this second search fails then we search for another path with good fitness and repeat the process. We give a computationally inexpensive approach (fitness function) that estimates the feasibility of a path. In order to evaluate this fitness function we compared the fitness of a path with the ease with which an input sequence can be produced using search to trigger the path and we used random sampling in order to estimate this. The empirical evidence suggests that a reasonably good correlation (0.72 and 0.62) exists between the fitness of a path, produced using the proposed fitness function, and an estimate of the ease with which we can randomly generate an input sequence to trigger the path.     

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.     

基于扩展有限状态机测试序列生成方法研究

扩展有限状态机是对有限状态机的扩展,由于引入了变量、状态迁移的前置条件以及状态迁移所引起的操作,它的测试序列存在可执行性问题。讨论了基于扩展有限状态机的测试序列生成方法的主要特点及局限性,指出了有待进一步研究的若干问题。     

多单元协议一致性测试中的同步序列的生成

有限状态机模型一般被用来描述通信协议和其它各类的分布式系统,对于一个多端口的有限状态机,需要多个测试单元进行测试,使用一个包括K个（K≥2）测试单元的测试系统可以检查一个多单元通信协议软件的收发行为是否与协议规格一致,在测试过程中,K个测试单元之间可能会出珊步问题,目前,主要是通过增加外部同步操作来解决同步问题,提出了一种新的同步测试序列生成模型－－同步有向图,它可以判断一个给定的协议规格是否可以在不需要外部同步操作的情况下,产生同步测试序列;如果可以产生,则此生成中以将非同步测试相应的同步测试序列;另外此生成模型还可以用来选择为测试系统增加外部同步通道的方法。     

基于同步有向图的同步测试序列生成方法

使用多测试单元的测试系统可以对多端口协议实现进行一致性测试，但是在进行这种一致性测试时，测试系统各个端口之间可能会出现同步问题，现在，解决同步问题常用的办法是在测试单元相应端口之间增加同步连接，然后通过此同步连接相互发送同步消息来进行同步，多端口协议和其它类型的分布式系统可以用有限状态机模型来描述，目前，同步问题被分为双端口同步问题，多端口同步问题，紧同步问题等多种类型，该文考虑两种有限状态机测试问题，第一种是面向端口的测试，不考虑有限状态机测试单元之间的通信问题，第二种面向组的测试，有限状态机中的各个端口被分成互不相关的多个组，属于不同组中的测试单元之间互不通信，该文提出了一种基于同步有向图的同步测试序列生成方法，这种生成方法适用于Pair同步，Port同步和组同步问题，并且，这种方法也可以用来判断如何在非同步测试序列中增加同步通信，将非同步测试序列转化为同步测试序列。     

Synthesis of finite state machines for improved state verification

Finite State Machines (FSMs) are used in diverse areas to model hardware and software systems. Verification of FSMs is essential to ensure reliability of systems. To verify that a machine is in an expected state in testing, Unique Input/Output (UIO) sequences are used. The aforementioned testing methodology requires that each state in the FSM has an UIO. However, it is possible for a given machine that few or even none of its states have an UIO sequence. This paper presents a guided heuristic algorithm for synthesizing FSMs such that each state has an UIO sequence. The states of an FSM with identical I/O labels on transitions are grouped in order to identify the states which do not possess UIO sequence. The transitions are then augmented by adding extra output terminals incrementally so that new UIO sequences are created for the states. A greedy approach is used to optimize the number of added outputs. Initially, the transitions which lead to state convergence (i.e., transitions with identical input/output labels taking a set of states to the same next state) and constrained self-loop (i.e., transitions taking a set of states either to itself or leads to state convergence) are identified since a state with only these transitions will never have a UIO sequence. Extra output terminals are added to the FSM which are used only while testing and the augmented output labels make sure that the states are neither convergent nor has constrained self-loop, thereby ensuring UIO sequence. The proposed algorithm, referred to as AUGP, was tested with a large number of FSMs including the Microelectronics Center of North Carolina (MCNC) FSM benchmarks. The augmented state transition table was used as input to a UIO computation algorithm (developed by the same authors [Ahmad I, et al. IEE Proc Comput Digital Tech 2004;151(2):131]) to check the performance of the augmentation algorithm and the tested FSMs were found to possess UIO sequence for all states.     

Sleep modes effectiveness in backbone networks with limited configurations

In this work we propose a strategy to minimize the impact of energy saving techniques on the performance of an Internet Service Provider network. We study the problem of putting in sleep mode links of a backbone network, while limiting the number of times each device changes its power state (full power mode or sleep mode). Our aim is to limit the number of network configurations, i.e., the change of the current set of network links at full power. We tackle the problem both analytically and by simulations. We first present a model, based on random graph theory, to compute the links energy saving given a traffic variation, QoS requirements, and the number of allowed network configurations. The same analysis is then repeated over two realistic case studies, and with realistic algorithms to choose the set of links in sleep mode. Results show (both analytically and by simulation) that the energy savings with few configurations (two or three per day) are close to the maximum one, in which a new configuration is applied for each traffic matrix. Moreover, we show that few configurations per day limit the number of overhead messages required for exchanging information about the device state. Thus, we can conclude that a practical implementation of sleep mode strategies for network operators is to define, on the basis of typical traffic trend, few configurations to be activated in specific time instants.     

An integrated search-based approach for automatic testing from extended finite state machine (EFSM) models

Context

The extended finite state machine (EFSM) is a modelling approach that has been used to represent a wide range of systems. When testing from an EFSM, it is normal to use a test criterion such as transition coverage. Such test criteria are often expressed in terms of transition paths (TPs) through an EFSM. Despite the popularity of EFSMs, testing from an EFSM is difficult for two main reasons: path feasibility and path input sequence generation. The path feasibility problem concerns generating paths that are feasible whereas the path input sequence generation problem is to find an input sequence that can traverse a feasible path.

Objective

While search-based approaches have been used in test automation, there has been relatively little work that uses them when testing from an EFSM. In this paper, we propose an integrated search-based approach to automate testing from an EFSM.

Method

The approach has two phases, the aim of the first phase being to produce a feasible TP (FTP) while the second phase searches for an input sequence to trigger this TP. The first phase uses a Genetic Algorithm whose fitness function is a TP feasibility metric based on dataflow dependence. The second phase uses a Genetic Algorithm whose fitness function is based on a combination of a branch distance function and approach level.

Results

Experimental results using five EFSMs found the first phase to be effective in generating FTPs with a success rate of approximately 96.6%. Furthermore, the proposed input sequence generator could trigger all the generated feasible TPs (success rate = 100%).

Conclusion

The results derived from the experiment demonstrate that the proposed approach is effective in automating testing from an EFSM.     

有限状态机模型测试序列生成算法研究

在测试工程学中,应用测试生成树构建测试序列是相关测试方法的基础步骤,在传统测试生成树的基础上加入约束集的概念,使产生的测试生成树符合生产实际。同时在面向状态识别的测试方法中,考虑约束集对所生成状态区分序列的影响,基于带约束的测试生成树产生相应的特征集、状态识别集和UIO序列,提出或者改进了相应的算法。同时将测试方法扩展到了NFSM的情形下,提出了NFSM模型中前缀序列的生成算法和状态识别集的构建算法;结合状态识别矩阵与有限状态机同步乘积,提出在NFSM模型中的适应性测试方法,扩展了FSM应用于测试理论的完备性。建立了相应的测试方法工具集,实现了上述算法,验证了其可行性。最后给出了下一步的工作。     

Canonical finite state machines for distributed systems

There has been much interest in testing from finite state machines (FSMs) as a result of their suitability for modelling or specifying state-based systems. Where there are multiple ports/interfaces a multi-port FSM is used and in testing, a tester is placed at each port. If the testers cannot communicate with one another directly and there is no global clock then we are testing in the distributed test architecture. It is known that the use of the distributed test architecture can affect the power of testing and recent work has characterised this in terms of local s-equivalence: in the distributed test architecture we can distinguish two FSMs, such as an implementation and a specification, if and only if they are not locally s-equivalent. However, there may be many FSMs that are locally s-equivalent to a given FSM and the nature of these FSMs has not been explored. This paper examines the set of FSMs that are locally s-equivalent to a given FSM M. It shows that there is a unique smallest FSM χ_min(M) and a unique largest FSM χ_max(M) that are locally s-equivalent to M. Here smallest and largest refer to the set of traces defined by an FSM and thus to its semantics. We also show that for a given FSM M the set of FSMs that are locally s-equivalent to M defines a bounded lattice. Finally, we define an FSM that, amongst all FSMs locally s-equivalent to M, has fewest states. We thus give three alternative canonical FSMs that are locally s-equivalent to an FSM M: one that defines the smallest set of traces, one that defines the largest set of traces, and one with fewest states. All three provide valuable information and the first two can be produced in time that is polynomial in terms of the number of states of M. We prove that the problem of finding an s-equivalent FSM with fewest states is NP-hard in general but can be solved in polynomial time for the special case where there are two ports.     

Research on the dynamic reconfiguration of Web application using two-phase compatibility verification

Implemented by dynamic service composition and integration, Web application has significantly affected our daily life, such as e-commerce and e-government. However, the open and ever-changing environment makes Web users more vulnerable to the usability problem, i.e. unreachable pages and reduced responsiveness. Accordingly, there is a need to deliver reliable Web application with attributes that cover the correctness and reliability. For the efficient handling of failures, the compatibility verification of dynamic reconfiguration strategies is attached great importance since it can guarantee the robustness and high quality of Web-based software. This paper extends the classical finite state machine (FSM) to formalize the behaviour of Web application, namely the extended FSM for Web applications (EFSM4WA) model. This model is also suitable to formally describe the interaction behaviours of dynamic reconfiguration when Web application encountered failure. Then, the compatibility verification of dynamic reconfiguration is carried out in two phases. During the first phase, it adopts the trace projection approach to check the compatibility against the synchronized product model in a qualitative way, which will select a set of candidate Web applications. During the second phase, it takes performance into consideration to choose a high-reliability Web application in a quantitative way. Finally, a case study is demonstrated to show the applicability of our approach.     

Hardness and inapproximability of minimizing adaptive distinguishing sequences

An adaptive distinguishing sequence (ADS) can be used for identifying an unknown initial state of a finite state machine (FSM). It has been long known that checking the existence of an ADS for an FSM, and finding an ADS for an FSM when one exists, can be performed in polynomial time. However, the problem of finding a minimum ADS has not been studied so far. Generating a minimum ADS is especially motivated when such an ADS is used repeatedly, e.g. for the construction of a test sequence. We introduce a number of metrics to define a minimum ADS and show that the problem of generating a minimum ADS with respect to these metrics is NP-complete. In addition, we provide inapproximability results for these hard problems and show that not only deciding but also approximating such a minimum ADS is a hard problem. We modify the only polynomial time ADS generation algorithm existing, and experimentally show that these modifications construct reduced ADSs. We also validate the motivation of ADS minimization by presenting experimental results on the effect of using reduced ADSs to generate test sequences.     

Testing in context: framework and test derivation

The paper addresses the problem of testing a component embedded within a given modular system. A context of the component represents the rest of the system and serves as its operational or testing environment. A framework for testing in context is presented based on the model of a system of communicating finite state machines. In particular, the problems of test executability and fault propagation in the presence of the context are identified and discussed. The proposed solution to these problems consists in computing so-called approximation of the specification in context, i.e. the FSM model of the component's properties that can be controlled and observed through the context. The approximation assures executability of tests and fault propagation through the context and serves as a base for test derivation. A conformance relation used for test derivation is shown to be the reduction relation between an implementation and the approximation of the given specification. This relation requires that the implementation produces a (sub)set of output sequences that can be produced by its specification in response to every input sequence. An approach to test generation for the reduction relation and deterministic implementations is also presented.     

Parameter optimization for spray coating

The aim of planning path-oriented spray-coating processes is to find a time-dependent continuous sequence of spray gun configurations so that a coating of desired thickness is achieved when executing the sequence. A novel approach to solving the planning task, called “geometry-last”, is outlined which leads to a more general gun configuration cover problem. The gun configuration cover problem is to find a finite set of spray gun configurations, which minimizes the error between a target coating and the coating induced by simultaneously activating those configurations. A suitable objective function for gun configuration covers is defined, and algorithmic solutions for the optimization problem are presented, including speed-up by hierarchization and use of graphics hardware. An experimental evaluation shows that good approximations of the desired coatings can be achieved within reasonable computing times. In contrast to other approaches, geometry-last gains additional flexibility required to find complex paths for free-form workpieces.     

Enumeration of all wedged equilibrium configurations in contact problem with Coulomb friction

For a linear structure subjected to the unilateral contact condition with a fixed obstacle, we refer to a nontrivial equilibrium state as a wedged configuration. Finding a wedged configuration is called a wedging problem. This paper discusses theoretical properties of solution set of the finite-dimensional wedging problem with the Coulomb friction, and presents numerical methods for computing all the wedged configurations. We propose algorithms for enumerating all the finitely many representative solutions, with which we can completely describe the solution set of the wedging problem. There exists a positive critical friction coefficient defined as the minimum value of friction coefficient with which at least one wedged configuration exists. We also propose an algorithm for computing the critical friction coefficient, which is based on the bisection method and the second-order cone program.     

On the complexity of existence of homing sequences for nondeterministic finite state machines

The paper discusses complexity of the problem of checking existence of a homing sequence for an observable complete finite state machines (FSMs). The minimum length of such a sequence for FSMs of certain class is known to be exponential in the number of the FSM states. It is shown that the problem of checking the existence of such a sequence belongs to class PSPACE.     

Control of hysteresis in smart actuators with application to micro-positioning

Hysteresis in smart material actuators makes the effective use of these actuators quite challenging. The Preisach operator has been widely used to model smart material hysteresis. Motivated by positioning applications of smart actuators, this paper addresses the value inversion problem for a class of discretized Preisach operators, i.e., to find an optimal input trajectory given a desired output value. This problem is solved through optimal state transition of a finite state machine (FSM) that corresponds to the discretized Preisach operator. A state-space reduction scheme for the FSM is developed, which significantly saves the memory and the computation time. Experimental results on micro-positioning control of a magnetostrictive actuator are presented to demonstrate the effectiveness of the proposed approach.     

Modelling the Environment of a Mobile Robot with the Embedded Flow State Machine

A type of topological approach to mobile robot navigation is discussed and experimentally evaluated. The environment as experienced by a moving robot is treated as a dynamical system. Simple types of reactive behavior are supplemented with eventual decisions to switch between them. When switching criteria are defined, the system may be described in the form similar to a finite state machine. Since it is embedded in the environment and dependent on the sensory flow of the robot, we introduce the term “Embedded flow state machine” (EFSM). We implemented it with a recurrent neural network, trained on a sequence of sensory contents and actions. One of the main virtues of this approach is that no explicit localization is required, since the recurrent neural network holds the state implicitly. The EFSM is applicable to multi-step prediction of sensory information and the travelled distances between decision points, given a sequence of decisions at decision points. Thus, the optimal path to a specified goal can be sought. One of the main issues is, for how many steps ahead the prediction is reliable enough. In other words, is it feasible to perform environment modelling and path planning in this manner? The approach is tested on a miniature mobile robot, equipped with proximity sensors and a color video camera. Decision ‘points,’ where deviations from the wall-following behavior are allowed, are based on color object recognition. In the case of an experimental environment of medium complexity, this approach was successful.