Identifying the effects of modifications as data dependencies

Dependence analysis on an extended finite state machine (EFSM) representation of the requirements of a system under test has been used in model-based regression testing for regression test suite (RTS) reduction (reducing the size of a given test suite by eliminating redundancies), for RTS prioritization (ordering test cases in a given test suite for early fault detection), or for RTS selection (selecting a subset of a test suite covering the identified dependencies). These particular uses of dependence analysis are based on the definitions of various types of control and data dependencies (between transitions in an EFSM) caused by a given set of modifications on the requirements. This paper considers the existing definitions of data dependencies for capturing the effects of the modifications, gives examples of their inaccuracy and incompleteness, proposes new definitions, and proves the soundness and completeness of these new definitions. Any previous work on regression testing using definitions of data dependencies capturing the effects of modifications can benefit from the proposed definitions.     

Validation of SDL specifications using EFSM-based test generation

Existing methods for testing an SDL specification mainly allow for either black box simulation or conformance testing to verify that the behavior of an implementation matches its corresponding model. However, this relies on the potentially hazardous assumption that the model is completely correct. We propose a test generation method that can accomplish conformance verification as well as coverage criteria-driven white box testing of the specification itself. We first reformat a set of EFSMs equivalent to the processes in an SDL specification and identify “hot spots” – nodes or edges in the EFSM which should be prioritized during testing to effectively increase coverage. Then, we generate test sequences intended to cover selected hot spots; we address the possible infeasibility of such a test sequence by allowing for its rejection decided by a constraint solver and re-generation of an alternate test sequence to the hot spot. In this paper, we present our test generation method and tool, and provide case studies on five SDL processes demonstrating the effectiveness of our coverage-based test sequence selection.     

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.     

基于UML状态图的C/S模式软件系统的一致性测试例生成

C/S模式的软件系统具有多层次结构、采用面向对象编程技术等特点,为其生成一致性测试变得十分困难.使用UML状态图,为一个C/S模式的软件系统建模,将建立好的模型转换为扩展的有限状态机,并在该有限状态机上使用UIO序列与中国邮递员算法相结合的方法进行测试例的生成,最后应用数据流分析技术对生成的测试例进行分析,排除了其中不可执行的测试例.该方法利用了UML状态图易于建模的优点,降低了测试生成的难度,缩短了测试例的长度并节省了软件开发的成本.     

基于UML状态图的类测试用例自动生成方法

UML作为面向对象软件开发的事实上的标准建模语言，近年来得到了广泛的应用，基于UML的测试也成为面向对象软件测试的研究热点。该文把基于扩展的有限状态机EFSM的唯一输入输出UIO测试用例自动生成方法和UML的类的状态图相结合，提出了一种基于UML状态图的类的测试用例自动生成方法。     

Axis estimation and grouping of rotationally symmetric object segments

This paper proposes a new method for estimating the symmetric axis of a pottery from its small fragment using surface geometry. Also, it provides a scheme for grouping such fragments into shape categories using distribution of surface curvature. For automatic assembly of pot from broken sherds, axis estimation is an important task and when a fragment is small, it is difficult to estimate axis orientation since it looks like a patch of a sphere and conventional methods mostly fail. But the proposed method provides fast and robust axis estimation by using multiple constraints. The computational cost is also too lowered. To estimate the symmetric axis, the proposed algorithm uses three constraints: (1) The curvature is constant on a circumference C_H. (2) The curvature is invariant in any scale. (3) Also the principal curvatures does not vary on C_H. C_H is a planar circle which is one of all the possible circumferences of a pottery or sherd. A hypothesis test for axis is performed using maximum likelihood. The variance of curvature, multi-scale curvature and principal curvatures is computed in the likelihood function. We also show that the principal curvatures can be used for grouping of sherds. The grouping of sherds will reduce the computation significantly by omitting impossible configurations in broken pottery assembly process.     

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.     

基于UML规格说明的增量式测试用例生成

测试用例的生成是软件测试的关键环节。本文把基于UML的规格说明和扩展的有限自动机结合起来，利用矩阵存储扩展自动机的状态和状态转换信息，用伪等价类生成树递增地生成测试用例，对类测试的测试用例自动生成作了有益的探讨     

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

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

Studies on a micro turbine device with both journal- and thrust-air bearings

This paper presents design, fabrication, analysis and test of a silicon-based micro turbine device that is driven by compressed air. To improve the motion stability at high rotational speed, the turbine device employs an enhanced micro air bearing system that includes both journal air bearing and thrust air bearings. The double-sides dynamic thrust air bearings are designed to support the rotor from both its top and bottom sides. The top thrust air bearing employs pump-in spiral groove configuration, and the bottom bearing uses pump-out spiral groove configuration. The dynamic journal air bearing is formed by a plain circular trench with a short journal length (L) and a narrow radial clearance (C). The critical aspect ratio (L/C) over 20:1 is realized through an optimized fabrication process. The micro turbine device has been fabricated, integrated and tested. During the test, the turbine device demonstrated stable operations at a rotational speed of 14,700 rpm.     

Consolidating and applying the SDL-pattern approach: a detailed case study

This paper is on design methodology for communication systems. The SDL-pattern approach proposed recently is consolidated and applied rigorously and in detail to the design of a typical communication system on two levels of abstraction. The design is decomposed into a number of steps, each of which is carried out systematically, building on well-proven, generic pieces of solutions that have proven useful in previous projects. These generic solutions—termed SDL patterns—support reuse-driven design of communication systems, raise the vocabulary of protocol engineer to a problem-oriented level, assist the discovery and exploitation of commonalities, and lead to well-justified designs. The selection and use of SDL patterns is supported by a fine-grained incremental design process, the pattern definition takes advantage of formal design languages, and a set of heuristics addresses the decomposition of communication requirements. All these elements are presented and applied in detail to the design of a simple, but functionally complete communication system.     

化工过程EFSM 模型的应用

扩展有限状态机(EFSM)是一种构造模型的形式化描述语言.首先根据化工过程特征,改进EFSM模型和数据依赖关系,构建变量、状态及相互之间转换条件和动作的化工过程EFSM描述模型;然后提出化工过程变量之间的静、动态依赖关系和故障传播路径的分析方法;最后通过典型化工过程CSTR仿真应用验证了EFSM模型描述及分析方法的可行性和有效性,为工业过程的故障传播分析提供一种新的思路和方法.     

A framework for compositional nonblocking verification of extended finite-state machines

This paper presents a framework for compositional nonblocking verification of discrete event systems modelled as extended finite-state machines (EFSM). Previous results are improved to consider general conflict-equivalence based abstractions of EFSMs communicating both via shared variables and events. Performance issues resulting from the conversion of EFSM systems to finite-state machine systems are avoided by operating directly on EFSMs, deferring the unfolding of variables into state machines as long as possible. Several additional methods to abstract EFSMs and remove events are also presented. The proposed algorithm has been implemented in the discrete event systems tool Supremica, and the paper presents experimental results for several large EFSM models that can be verified faster than by previously used methods.     

Some experiments in relaxation image matching using corner features

A relaxation method based on patterns of local features is used to find matches between pairs of images or subimages that differ in position or orientation. A local operator is applied to the two images to detect two sets of “corners” C₁ …, C_m and D₁, …, D_n, each of them characterized by position, orientation, contrast and “sharpness” (of the angle). For each pair (C_i, D_j), a figure of merit is computed and a relaxation process is used to iteratively adjust these figures of merit, based on the merits of other pairs in approximately corresponding positions. After a few iterations of this process, “good” matches (pairs having much better merit than their next best choices) are clustered, yielding sets of transformation parameters (shift vectors or rotation angles) under which many corners correspond. This method has yielded good results for TV images of objects such as tools and industrial parts, as well as for aerial images of terrain.     

A unified integration and component testing approach from deterministic stream X-machine specifications

One of the great benefits of using a stream X-machine to specify a system is its associated testing method. Under certain design for test conditions, this method produces a test suite that can determine the correctness of the implementation under test (IUT), provided that the basic components of the stream X-machine model have been correctly implemented. However, such an approach implies that each component can be tested in isolation from the rest of the system. This is a limitation that, in practice, can be resolved by developing stubs and drivers. However, this adds complexity to the testing process and, furthermore, these new pieces of software can introduce faults that can invalidate the theoretical results of the aforementioned testing method. This paper extends the approach by allowing component testing to be performed in parallel with integration testing, while still guaranteeing the IUT correctness under the given design for test conditions. It also shows how the integration test suite, produced in previous publications, can be reduced.     

A distributed framework for demand-driven software vulnerability detection

Security testing aims at detecting program security flaws through a set of test cases and has become an active area of research. The challenge is how to efficiently produce test cases that are highly effective in detecting security flaws. This paper presents a novel distributed demand-driven security testing system to address this challenge. It leverages how end users use the software to increase the coverage of essential paths for security testing. The proposed system consists of many client sites and one testing site. The software under test is installed at each client site. Whenever a new path is about to be exercised by a user input, it will be sent to the testing site for security testing. At the testing site, symbolic execution is used to check any potential vulnerability on this new path. If a vulnerability is detected, a signature is automatically generated and updated to all client sites for protection. The benefits are as follows. First, it allows us to focus testing on essential paths, i.e., the paths that are actually being explored by users or attackers. Second, it stops an attacker from exploiting an unreported vulnerability at the client site. A prototype system has been implemented to evaluate the performance of the proposed system. The results show that it is both effective and efficient in practice.     

含过程调用EFSM模型测试数据生成

针对含过程调用EFSM模型测试数据生成中过程调用的不可执行问题,提出了一种能对过程调用进行处理以实现模型的测试数据自动生成方法。该方法将被调子过程描述为一个EFSM模型,将表示主过程及子过程的EFSM模型合并为一个新的模型,合并后的模型符合EFSM模型规范,采用遗传算法对该模型进行测试数据自动生成。实验结果表明,该方法能够较好地解决含过程调用EFSM模型的测试数据自动生成问题。