基于禁忌搜索算法的可扩展有限状态机模型测试数据自动生成

可扩展有限状态机(EFSM)模型的测试用例生成包括测试路径生成和测试数据生成两部分。然而,目前针对EFSM模型的测试研究大多集中于测试路径生成。为探索路径上测试数据的自动生成,提出一种面向EFSM路径的测试数据生成方法,利用禁忌搜索(TS)策略实现了EFSM测试数据的自动生成;分析了影响EFSM测试数据生成的关键因素,并与遗传算法(GA)的生成效率进行了比较。实验结果表明：基于TS算法的EFSM模型测试数据自动生成是确实可行的,其测试生成效率相对于GA有很大提高。     

An initial industrial evaluation of interactive search-based testing for embedded software

Search-based software testing promises the ability to generate and evaluate large numbers of test cases at minimal cost. From an industrial perspective, this could enable an increase in product quality without a matching increase in the time and effort required to do so.Search-based software testing, however, is a set of quite complex techniques and approaches that do not immediately translate into a process for use with most companies.For example, even if engineers receive the proper education and training in these new approaches, it can be hard to develop a general fitness function that covers all contingencies. Furthermore, in industrial practice, the knowledge and experience of domain specialists are often key for effective testing and thus for the overall quality of the final software system. But it is not clear how such domain expertise can be utilized in a search-based system.This paper presents an interactive search-based software testing (ISBST) system designed to operate in an industrial setting and with the explicit aim of requiring only limited expertise in software testing. It uses SBST to search for test cases for an industrial software module, while also allowing domain specialists to use their experience and intuition to interactively guide the search.In addition to presenting the system, this paper reports on an evaluation of the system in a company developing a framework for embedded software controllers. A sequence of workshops provided regular feedback and validation for the design and improvement of the ISBST system. Once developed, the ISBST system was evaluated by four electrical and system engineers from the company (the ‘domain specialists’ in this context) used the system to develop test cases for a commonly used controller module. As well as evaluating the utility of the ISBST system, the study generated interaction data that were used in subsequent laboratory experimentation to validate the underlying search-based algorithm in the presence of realistic, but repeatable, interactions.The results validate the importance that automated software testing tools in general, and search-based tools, in particular, can leverage input from domain specialists while generating tests. Furthermore, the evaluation highlighted benefits of using such an approach to explore areas that the current testing practices do not cover or cover insufficiently.     

A search-based framework for automatic testing of MATLAB/Simulink models

Search-based test-data generation has proved successful for code-level testing but almost no search-based work has been carried out at higher levels of abstraction. In this paper the application of such approaches at the higher levels of abstraction offered by MATLAB/Simulink models is investigated and a wide-ranging framework for test-data generation and management is presented. Model-level analogues of code-level structural coverage criteria are presented and search-based approaches to achieving them are described. The paper also describes the first search-based approach to the generation of mutant-killing test data, addressing a fundamental limitation of mutation testing. Some problems remain whatever the level of abstraction considered. In particular, complexity introduced by the presence of persistent state when generating test sequences is as much a challenge at the Simulink model level as it has been found to be at the code level. The framework addresses this problem. Finally, a flexible approach to test sub-set extraction is presented, allowing testing resources to be deployed effectively and efficiently.     

InRob: An approach for testing interoperability and robustness of real-time embedded software

Advances in digital technologies have contributed for significant reduction in accidents caused by hardware failures. However, the growing complexity of functions performed by embedded software has increased the number of accidents caused by software faults in critical systems. Moreover, due to the highly competitive market, software intensive subsystems are usually developed by different suppliers. Often these subsystems are required to interact with each other in order to provide a collaborative service. Testing approaches for subsystems integration support verification of the quality of service, focusing on the subsystems interfaces. The increasing complexity and tight coupling of real-time subsystems make integration testing unmanageable. The ad-hoc approach for testing is becoming less effective and more expensive. This article presents an integration testing approach denominated InRob, designed to verify the interoperability and robustness related to timing constraints of real-time embedded software. InRob guides the construction of services, based on formal models, aiming at the specifications of interoperability and robustness of test cases related to delays and time-outs of the messages exchanged in the interfaces of interconnected subsystems. The proposed formalism supports automatic test cases generation by verifying the relevant properties in the service behavioral model. As timing constraints are critical properties of aerospace systems, the feasibility of InRob is showed in the integration testing process of a telescope onboard in a satellite. The process is instantiated with existing testing tools and the case study is the software embedded in the telescope.     

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.     

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.     

An approach and tool for measurement of state variable based data-flow test coverage for aspect-oriented programs

ContextData-flow testing approaches have been used for procedural and object-oriented programs, and shown to be effective in detecting faults. However, few such approaches have been evaluated for aspect-oriented programs. In such programs, data-flow interactions can occur between base classes and aspects, which can affect the behavior of both. Faults resulting from such interactions are hard to detect unless the interactions are specifically targeted during testing.ObjectiveThis paper presents an approach and tool implementation for measuring data-flow coverage based on state variables defined in base classes or aspects in AspectJ programs. The paper also reports on an empirical study that compares the cost and effectiveness of data-flow test criteria that are based on state variables with two control-flow criteria.MethodEffectiveness of the criteria was evaluated for various fault types. Cost-effectiveness of test suites that cover all state variable definition-use associations (DUAs) was evaluated for three coverage levels: 100%, 90%, and 80%.ResultsThe effort needed to obtain a test case that achieves data-flow coverage is higher than the effort needed to obtain a test case that covers a block or a branch in an advised class. Covering certain data flow associations requires more effort than for other types of data flow associations. The data-flow test criteria based on state variables of a base-class are in general more effective than control-flow criteria.ConclusionsOverall, it is cost-effective to obtain test suites at the 90% coverage level of data-flow criteria.     

An algorithm for evaluating the state of input-and output-open systems modeled by finite automata in the course of testing complex objects

The problem of evaluating the state of systems that are open with respect to input and output for the purpose of creating a system for evaluating states when testing complex objects is considered. Solving the problem will make it possible to eliminate ambiguity in cases of insufficiency of the output parameters and where uncontrolled parameters exert an influence. It will also reduce the problem to that of successive evaluation of the states of output-open system and, subsequently, of the states of input-open systems. The search for a solution is conducted by means of an analysis of the set of states of a finite-automaton model in the set of output variables. An example illustrating practical implementation of the proposed approach is presented.     

An approach to recognize interacting features from B-Rep CAD models of prismatic machined parts using a hybrid (graph and rule based) technique

This paper presents a new hybrid (graph + rule based) approach for recognizing the interacting features from B-Rep CAD models of prismatic machined parts. The developed algorithm considers variable topology features and handles both adjacent and volumetric feature interactions to provide a single interpretation for the latter. The input CAD part model in B-Rep format is preprocessed to create the adjacency graphs for faces and features of associated topological entities and compute their attributes. The developed FR system initially recognizes all varieties of the simple and stepped holes with flat and conical bottoms from the feature graphs. A new concept of Base Explicit Feature Graphs and No-base Explicit Feature Graphs has been proposed which essentially delineates between features having planar base face like pockets, blind slots, etc. and those without planar base faces like passages, 3D features, conical bottom features, etc. Based on the structure of the explicit feature graphs, geometric reasoning rules are formulated to recognize the interacting feature types. Extracted data has been post-processed to compute the feature attributes and their parent-child relationships which are written into a STEP like native feature file format. The FR system was extensively tested with several standard benchmark components and was found to be robust and consistent. The extracted feature file can be used for integration with various downstream applications like CAPP.