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.     

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

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

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

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

An automated software reliability prediction system for safety critical software

Software reliability is one of the most important software quality indicators. It is concerned with the probability that the software can execute without any unintended behavior in a given environment. In previous research we developed the Reliability Prediction System (RePS) methodology to predict the reliability of safety critical software such as those used in the nuclear industry. A RePS methodology relates the software engineering measures to software reliability using various models, and it was found that RePS’s using Extended Finite State Machine (EFSM) models and fault data collected through various software engineering measures possess the most satisfying prediction capability. In this research the EFSM-based RePS methodology is improved and implemented into a tool called Automated Reliability Prediction System (ARPS). The features of the ARPS tool are introduced with a simple case study. An experiment using human subjects was also conducted to evaluate the usability of the tool, and the results demonstrate that the ARPS tool can indeed help the analyst apply the EFSM-based RePS methodology with less number of errors and lower error criticality.     

Formal testing from timed finite state machines

In this paper we present a formal methodology to test both the functional and temporal behaviors in systems where temporal aspects are critical. We extend the classical finite state machines model with features to represent timed systems. Our formalism allows three different ways to express the timing requirements of systems. Specifically, we consider that time requirements can be expressed either by means of fix time values, by using random variables, or by considering time intervals. Different implementation relations, depending on both the interpretation of time and on the non-determinism appearing in systems, are presented and related. We also study how test cases are defined and applied to implementations. Test derivation algorithms, producing sound and complete test suites, are also presented. That is, by deriving these test suites we relate the different notions of passing tests and the different implementation relations. In other words, for a given correctness criterion, a system represents an appropriate implementation of a given model if and only if the system successfully passes all the test belonging to the derived test suite.     

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.     

On adaptive experiments for nondeterministic finite state machines

Adaptive experiments are well defined in the context of finite state machine (FSM) based analysis, in particular, in FSM based testing where homing and distinguishing experiments with FSMs are used for test derivation. In this paper, we define and propose algorithms for deriving adaptive homing and distinguishing experiments for non-initialized nondeterministic finite state machines (NFSMs). For NFSMs, the construction of adaptive experiments is rather complex as the partition over produced outputs does not define a partition over the set of states but a collection of intersecting subsets, and thus, the refinement of such set system is more difficult than the refinement of a partition. Given a complete non-initialized possibly non-observable NFSM, we establish necessary and sufficient conditions for having adaptive homing and distinguishing experiments and evaluate the height of these experiments.     

EFSM模型的字符串类型测试数据自动生成

基于软件描述模型的测试数据自动生成研究中,字符串类型测试数据生成是一个研究热点和难点。EFSM模型是一种重要的软件描述模型。分析了EFSM模型的特点,针对面向EFSM模型目标路径的字符串测试数据生成,建立了字符串输入变量模型和操作模型,结合静态测试的特点,给出了通过字符串变量模型在目标路径上的符号执行结果生成字符串类型测试数据的方法。实验结果表明,该方法能够达到预期效果,提高测试生成效率。     

FSM-based testing from user defined faults adapted to incremental and mutation testing

We study the problem of deriving a test suite with guaranteed fault coverage from a given finite state machine specification with respect to some given user defined faults. We consider the case when an implementation under test can have more states than its specification while user defined faults are implemented in an arbitrary way. We show that our approach can be used for FSM-based incremental and mutation testing and correspondingly we investigate cases that can be used for reducing length of obtained test suites. In some cases, worst-case length of obtained test suite becomes polynomial. Experiments show significant gains is using our approach in comparison to testing the whole specification.     

面向语句的MBFL变异体约减策略

在软件调试过程中如何高效、精确地定位程序中的错误代码是软件开发人员普遍关注的问题。MBFL是一种基于变异分析的错误定位技术,它在获得较高错误定位精度的同时会生成大量变异体,并在变异体上执行测试用例集,开销庞大。为了减少MBFL的变异执行开销,提出面向语句的变异体约减策略,通过分析测试用例的执行信息, 按一定比例 对每条由失败测试用例覆盖的语句生成的变异体集合进行约减。实验结果表明,在7个程序包的112个错误版本上,应用面向语句的变异体约减策略的MBFL,在保持较高错误定位精度的同时,能够有效减少73.51%~79.98%的变异执行开销。     

Evaluating test suite characteristics,cost, and effectiveness of FSM-based testing methods

ContextTesting from finite state machines has been investigated due to its well-founded and sound theory as well as its practical application. There has been a recurrent interest in developing methods capable of generating test suites that detect all faults in a given fault domain. However, the proposal of new methods motivates the comparison with traditional methods.ObjectiveWe compare the methods that generate complete test suites from finite states machines. The test suites produced by the W, HSI, H, SPY, and P methods are analyzed in different configurations.MethodComplete and partial machines were randomly generated varying numbers of states, inputs, outputs, and transitions. These different configurations were used to compare test suite characteristics (number of resets, test case length) and the test suite length (i.e., the sum of the length of its test cases). The fault detection ratio was evaluated using mutation testing to produce faulty implementations with an extra state.ResultsOn average, the recent methods (H, SPY, and P) produced longer test cases but smaller test suites than the traditional methods (W, HSI). The recent methods generated test suites of similar length, though P produced slightly smaller test suites. The SPY and P methods had the highest fault detection ratios and HSI had the lowest. For all methods, there was a positive correlation between the number of resets and the test suite length and between the test case length and the fault detection ratio.ConclusionThe recent methods rely on fewer and longer test cases to reduce the overall test suite length, while the traditional methods produce more and shorter test cases. Longer test cases are correlated to fault detection ratio which favored SPY, though all methods have a ratio of over 92%.     

Java语言中数组越界故障的静态测试研究

面向具体故障的软件测试技术是当今一个研究热点。数组越界是Java程序设计中的常见故障,该类故障极易导致计算结果错误或系统崩溃。针对Java语言中常见数组越界故障进行了分析,并从面向具体故障的测试思想出发,建立了Java语言中数组越界的故障模型,结合静态测试的特点,给出了一种静态查找此类故障的方法。此方法已实现,并已应用于面向故障的软件测试系统中。     

IPSETFUL: an iterative process of selecting test cases for effective fault localization by exploring concept lattice of program spectra

Fault localization is an important and challenging task during software testing. Among techniques studied in this field, program spectrum based fault localization is a promising approach. To perform spectrum based fault localization, a set of test oracles should be provided, and the effectiveness of fault localization depends highly on the quality of test oracles. Moreover, their effectiveness is usually affected when multiple simultaneous faults are present. Faced with multiple faults it is difficult for developers to determine when to stop the fault localization process. To address these issues, we propose an iterative fault localization process, i.e., an iterative process of selecting test cases for effective fault localization (IPSETFUL), to identify as many faults as possible in the program until the stopping criterion is satisfied. It is performed based on a concept lattice of program spectrum (CLPS) proposed in our previous work. Based on the labeling approach of CLPS, program statements are categorized as dangerous statements, safe statements, and sensitive statements. To identify the faults, developers need to check the dangerous statements. Meantime, developers need to select a set of test cases covering the dangerous or sensitive statements from the original test suite, and a new CLPS is generated for the next iteration. The same process is proceeded in the same way. This iterative process ends until there are no failing tests in the test suite and all statements on the CLPS become safe statements. We conduct an empirical study on several subject programs, and the results show that IPSETFUL can help identifymost of the faults in the program with the given test suite. Moreover, it can save much effort in inspecting unfaulty program statements compared with the existing spectrum based fault localization techniques and the relevant state of the art technique.     

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.     

Confirming configurations in EFSM testing

We investigate the problem of configuration verification for the extended FSM (EFSM) model. This is an extension of the FSM state identification problem. Specifically, given a configuration ("state vector") and an arbitrary set of configurations, determine an input sequence such that the EFSM in the given configuration produces an output sequence different from that of the configurations in the given set or at least in a maximal proper subset. Such a sequence can be used in a test case to confirm the destination configuration of a particular EFSM transition. We demonstrate that this problem could be reduced to the EFSM traversal problem, so that the existing methods and tools developed in the context of model checking become applicable. We introduce notions of EFSM projections and products and, based on these notions, we develop a theoretical framework for determining configuration-confirming sequences. The proposed approach is illustrated on a realistic example.     

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.     

On the Use of Functional Test Generation in Diagnostic Test Generation for Synchronous Sequential Circuits

We study the relationship between diagnostic test generation for a gate-level fault model, which is used for generating diagnostic test sets for manufacturing defects, and functional test generation for a high-level fault model. In general, a functional fault may partially represent some of the effects of one gate-level fault but not another. Generating a test sequence for the functional fault is then likely to detect one gate-level fault but not the other, thus distinguishing the two faults. This relationship points to the ability to use a functional test generation procedure (that targets functional fault detection) as a way of generating diagnostic test sequences for gate-level faults. We use this observation in two ways. The more direct way is to define functional faults that correspond to the differences between pairs of gate-level faults. The second way is to use functional test sequences as diagnostic test sequences without explicitly considering gate-level faults. We support the use of the resulting procedures with experimental results.     

基于改进FSM的RBAC测试集约简方法

使用完备的有限状态机生成一致性测试集虽然有效,但数量庞大。针对该问题,考虑一般系统访问控制的基本需求,提出6种探索式方法对有限状态机(FSM)进行约简,有效避免状态爆炸的现象发生,简化了生成的一致性测试集大小。对基于FSM生成树进行实验,结果表明,改进FSM对缩小基于角色的访问控制系统一致性测试集是有效的。     

Empirical studies of test‐suite reduction

Test‐suite reduction techniques attempt to reduce the costs of saving and reusing test cases during software maintenance by eliminating redundant test cases from test suites. A potential drawback of these techniques is that reducing the size of a test suite might reduce its ability to reveal faults in the software. Previous studies have suggested that test‐suite reduction techniques can reduce test‐suite size without significantly reducing the fault‐detection capabilities of test suites. These studies, however, involved particular programs and types of test suites, and to begin to generalize their results, further work is needed. This paper reports on the design and execution of additional studies, examining the costs and benefits of test‐suite reduction, and the factors that influence these costs and benefits. In contrast to previous studies, results of these studies reveal that the fault‐detection capabilities of test suites can be severely compromised by test‐suite reduction. Copyright © 2002 John Wiley & Sons, Ltd.