On the order of test goals in specification-based testing

Model-based testing techniques often select test cases according to test goals such as coverage criteria or mutation adequacy. Complex criteria and large models lead to large test suites, and a test case created for one coverage item usually covers several other items as well. This can be problematic if testing is expensive and resources are limited. Therefore, test case generation can be optimized in order to avoid unnecessary test cases and minimize the test generation and execution costs. Because of this optimization the order in which test goals are selected is expected to have an impact on both the performance of the test case generation and the size of resulting test suites, although finding the optimal order is not feasible in general. In this paper we report on experiments to determine the effects of the order in which test goals are selected on performance and the size of resulting test suites, and evaluate different heuristics to select test goals such that the time required to generate test suites as well as their size are minimized. The test case generation approach used for experimentation uses model checkers, and experimentation shows that good results can be achieved with any random ordering, but some improvement is still possible with simple heuristics.     

Two case studies in grammar-based test generation

Grammar-based test generation (GBTG) has seen extensive study and practical use since the 1970s. GBTG was introduced to generate source code for testing compilers from context-free grammars specifying language syntax. More recently, GBTG has been applied to many other testing problems, including the generation of eXtensible Markup Language (XML) documents and the generation of packets for testing communications protocols. Recent research has shown how to integrate covering-array techniques such as pairwise testing into GBTG tools. While the integration offers considerable power to the tester, there are few practical demonstrations in the literature. We present two case studies showing how to use grammars and covering arrays for automated software testing. The first case study exposes HTML injection vulnerabilities in an RSS feed parser. The second case study determines the effectiveness of network firewalls when faced with TCP flag attacks. The case studies illustrate the use of covering arrays in a GBTG context, the use of visualization to understand large test logs, and the issues and tradeoffs in the design of fully automated GBTG test suites.     

Automated test generation technique for aspectual features in AspectJ

ContextAspect-oriented programming (AOP) has been promoted as a means for handling the modularization of software systems by raising the abstraction level and reducing the scattering and tangling of crosscutting concerns. Studies from literature have shown the usefulness and application of AOP across various fields of research and domains. Despite this, research shows that AOP is currently used in a cautious way due to its natural impact on testability and maintainability.ObjectiveTo realize the benefits of AOP and to increase its adoption, aspects developed using AOP should be subjected to automated testing. Automated testing, as one of the most pressing needs of the software industry to reduce both effort and costs in assuring correctness, is a delicate issue in testing aspect-oriented programs that still requires advancement and has a way to go before maturity.MethodPrevious attempts and studies in automated test generation process for aspect-oriented programs have been very limited. This paper proposes a rigorous automated test generation technique, called RAMBUTANS, with its tool support based on guided random testing for the AspectJ programs.ResultsThe paper reports the results of a thorough empirical study of 9 AspectJ benchmark programs, including non-trivial and larger software, by means of mutation analysis to compare RAMBUTANS and the four existing automated AOP testing approaches for testing aspects in terms of fault detection effectiveness and test effort efficiency. The results of the experiment and statistical tests supplemented by effect size measures presented evidence of the effectiveness and efficiency of the proposed technique at 99% confidence level (i.e. p < 0.01).ConclusionThe study showed that the resulting randomized tests were reasonably good for AOP testing, thus the proposed technique could be worth using as an effective and efficient AOP-specific automated test generation technique.     

面向对象分布式Web自动化实现

随着Web开发项目的日益庞大,自动化测试技术的重要性日益突出。自动化测试技术的出现,大大提高了软件测试的效率和测试人员的积极性。本文对自动化测试含义、种类及主流自动化测试框架进行了阐述;并介绍了一种基于Selenium2．0的面向对象分布武Web自动化测试的实现。     

Rapid goal-oriented automated software testing using MEA-graph planning

With the rapid growth in the development of sophisticated modern software applications, the complexity of the software development process has increased enormously, posing an urgent need for the automation of some of the more time-consuming aspects of the development process. One of the key stages in the software development process is system testing. In this paper, we evaluate the potential application of AI planning techniques in automated software testing. The key contributions of this paper include the following: (1) A formal model of software systems from the perspective of software testing that is applicable to important classes of systems and is amenable to automation using AI planning methods. (2) The design of a framework for an automated planning system (APS) for applying AI planning techniques for testing software systems. (3) Assessment of the test automation framework and a specific AI Planning algorithm, namely, MEA-Graphplan (Means-Ends Analysis Graphplan), algorithm to automatically generate test data. (4) A case study is presented to evaluate the proposed automated testing method and compare the performance of MEA-Graphplan with that of Graphplan. The empirical results show that for software testing, the MEA-Graphplan algorithm can perform computationally more efficiently and effectively than the basic Graph Planning algorithm.

VyrdMC: Driving Runtime Refinement Checking with Model Checkers

This paper presents VyrdMC, a runtime verification tool we are building for concurrent software components. The correctness criterion checked by VyrdMC is refinement: Each execution of the implementation must be consistent with an atomic execution of the specification. VyrdMC combines testing, model checking, and Vyrd, the runtime refinement checker we developed earlier. A test harness first drives the component to a non-trivial state which serves as the starting state for a number of simple, very small multi-threaded test cases. An execution-based model checker explores for each test case all distinct thread interleavings while Vyrd monitors executions for refinement violations. This combined approach has the advantage of improving the coverage of runtime refinement checking at modest additional computational cost, since model checkers are only used to explore thread interleavings of a small, fixed test program. The visibility and detailed checking offered by using refinement as the correctness criterion differentiate our approach from simply being a restricted application of model checking. An important side benefit is the reduction in program instrumentation made possible if VyrdMC is built using a model checker with its own virtual machine, such as Java PathFinder [Guillaume Brat, Klaus Havelund, Seung-Joon Park, and Willem Visser. Model Checking Programs. In IEEE International Conference on Automated Software Engineering (ASE), September 2000]. We are investigating the use of two different model checkers for building VyrdMC: Java PathFinder, an explicit-state model checker and Verisoft, a “stateless” model checker [P. Godefroid. Model Checking for Programming Languages using VeriSoft. In Proceedings of the 24th ACM Symposium on Principles of Programming Languages, pages 174–186, Paris, January 1997].     

Automatically performing weak mutation with the aid of symbolic execution,concolic testing and search-based testing

Automating software testing activities can increase the quality and drastically decrease the cost of software development. Toward this direction, various automated test data generation tools have been developed. The majority of existing tools aim at structural testing, while a quite limited number aim at a higher level of testing thoroughness such as mutation. In this paper, an attempt toward automating the generation of mutation-based test cases by utilizing existing automated tools is proposed. This is achieved by reducing the killing mutants’ problem into a covering branches one. To this extent, this paper is motivated by the use of state of the art techniques and tools suitable for covering program branches when performing mutation. Tools and techniques such as symbolic execution, concolic execution, and evolutionary testing can be easily adopted toward automating the test input generation activity for the weak mutation testing criterion by simply utilizing a special form of the mutant schemata technique. The propositions made in this paper integrate three automated tools in order to illustrate and examine the method’s feasibility and effectiveness. The obtained results, based on a set of Java program units, indicate the applicability and effectiveness of the suggested technique. The results advocate that the proposed approach is able to guide existing automating tools in producing test cases according to the weak mutation testing criterion. Additionally, experimental results with the proposed mutation testing regime show that weak mutation is able to speedup the mutant execution time by at least 4.79 times when compared with strong mutation.     

Verifying Time Partitioning in the DEOS Scheduling Kernel

This paper describes an experiment to use the Spin model checking system to support automated verification of time partitioning in the Honeywell DEOS real-time scheduling kernel. The goal of the experiment was to investigate whether model checking with minimal abstraction could be used to find a subtle implementation error that was originally discovered and fixed during the standard formal review process. The experiment involved translating a core slice of the DEOS scheduling kernel from C++ into Promela, constructing an abstract “test-driver” environment and carefully introducing several abstractions into the system to support verification. Attempted verification of several properties related to time-partitioning led to the rediscovery of the known error in the implementation. The case study indicated several limitations in existing tools to support model checking of software. The most difficult task in the original DEOS experiment was constructing an adequate environment to close the system for verification. The fidelity of the environment was of crucial importance for achieving meaningful results during model checking. In this paper, we describe the initial environment modeling effort and a follow-on experiment with using semi-automated environment generation methods. Program abstraction techniques were also critical for enabling verification of DEOS. We describe an implementation scheme for predicate abstraction, an approach based on abstract interpretation, which was developed to support DEOS verification.     

基于SPEA2+SDE算法的测试用例自动生成技术研究

软件测试是确保软件质量的重要手段。然而随着软件结构和功能的日益多样化,软件测试的复杂度和成本大为提高。测试用例自动生成技术可以降低手工测试的高额成本,同时提高测试结果的可信度。主要研究了基于进化算法的测试用例自动生成技术,通过比较不同算法对于若干经典程序的测试用例生成效率,提出了SPEA2+SDE算法,其可以很好地用于测试用例的自动生成。最后通过Kruskal-Wallis非参数检验,说明了上述结论的广泛性和可靠性。     

On-line reconfiguration to enhance the routing flexibility of complex automated material handling operations

Traditionally, automated material handling systems are not designed to be reconfigurable and changes to layouts and material flow directions often require significant downtime for physical modifications and reprogramming to be made. As a consequence of global trends towards mass customisation, higher mix and lower volume production, shorter product life cycle, shorter lead-time, increasing velocity of goods across supply chains, and the increasing use of industrial information technology (IT), modern automated material handling systems (AMHS) should be designed with reconfiguration features to maximise utilisation and to enhance its flexibility. This paper focuses on how on-line reconfiguration of complex AMHS can be technically achieved (from both hardware and software considerations), which enables operational routing flexibility as well as recovery routing flexibility when faults occur. Three common “design for on-line reconfiguration” areas are first proposed, namely, resource availability of the entire AMHS or its components, reversible direction of an individual or a group of conveyors, and expandable operating range (or domain) of common-aisle transporters. Design considerations and implementation techniques for a class of reconfigurable AMHS are then discussed. Finally, we illustrate how on-line reconfiguration was implemented for a large-scale complex automated warehouse with several AMHS.     

Establishing flight software reliability: testing,model checking,constraint-solving,monitoring and learning

In this paper we discuss the application of a range of techniques to the verification of mission-critical flight software at NASA’s Jet Propulsion Laboratory. For this type of application we want to achieve a higher level of confidence than can be achieved through standard software testing. Unfortunately, given the current state of the art, especially when efforts are constrained by the tight deadlines and resource limitations of a flight project, it is not feasible to produce a rigorous formal proof of correctness of even a well-specified stand-alone module such as a file system (much less more tightly coupled or difficult-to-specify modules). This means that we must look for a practical alternative in the area between traditional testing and proof, as we attempt to optimize rigor and coverage. The approaches we describe here are based on testing, model checking, constraint-solving, monitoring, and finite-state machine learning, in addition to static code analysis. The results we have obtained in the domain of file systems are encouraging, and suggest that for more complex properties of programs with complex data structures, it is possibly more beneficial to use constraint solvers to guide and analyze execution (i.e., as in testing, even if performed by a model checking tool) than to translate the program and property into a set of constraints, as in abstraction-based and bounded model checkers. Our experience with non-file-system flight software modules shows that methods even further removed from traditional static formal methods can be assisted by formal approaches, yet readily adopted by test engineers and software developers, even as the key problem shifts from test generation and selection to test evaluation.     

A Light-Weight Fault Injection Approach to Test Automated Production System PLC Software in Industrial Practice

A light-weight software-implemented fault injection (SWIFI) testing approach is introduced, focusing on technical process faults and system faults. The reaction of automated production systems (aPSs) and their programmable logic controller (PLC) software to these faults is tested. In order to tailor the testing approach to the aPS domain in industrial practice, our test generation is based on a classification of possible deviations, i.e. a classification of possible technical process and system faults as the PLC perceives them. As a result, both specification and test execution become more efficient for practitioners. Furthermore, the test specification is tailored for execution on IEC 61131-3 programming environments. In this, the execution of test cases both against simulation or the real aPS, is enabled.     

Testing with model checkers: a survey

About a decade after the initial proposal to use model checkers for the generation of test cases we take a look at the results in this field of research. Model checkers are formal verification tools, capable of providing counterexamples to violated properties. Normally, these counterexamples are meant to guide an analyst when searching for the root cause of a property violation. They are, however, also very useful as test cases. Many different approaches have been presented, many problems have been solved, yet many issues remain. This survey paper reviews the state of the art in testing with model checkers. Copyright © 2008 John Wiley & Sons, Ltd.     

基于锚点类的GDA标准接口测试方法

介绍一种GDA标准接口的自动化测试方法。选择业务系统相关的锚点类．根据锚点类去除CIM模型中对业务系统无效的搓型,制定对业务系统有效的测试模型,分析测试数据,根据测试模型自动化生成测试的输入和期望输出．从而实现对GDA标准接口的自动化测试。与传统的测试方法相比,可适用于任意的CIM模型,任意的测试数据,随机生成测试的输入数据．保证测试的有效性、准备性及覆盖性。     

Exploring models for semantic category verification

Many artificial intelligence tasks, such as automated question answering, reasoning, or heterogeneous database integration, involve verification of a semantic category (e.g. “coffee” is a drink, “red” is a color, while “steak” is not a drink and “big” is not a color). In this research, we explore completely automated on-the-fly verification of a membership in any arbitrary category which has not been expected a priori. Our approach does not rely on any manually codified knowledge (such as WordNet or Wikipedia) but instead capitalizes on the diversity of topics and word usage on the World Wide Web, thus can be considered “knowledge-light” and complementary to the “knowledge-intensive” approaches. We have created a quantitative verification model and established (1) what specific variables are important and (2) what ranges and upper limits of accuracy are attainable. While our semantic verification algorithm is entirely self-contained (not involving any previously reported components that are beyond the scope of this paper), we have tested it empirically within our fact seeking engine on the well known TREC conference test questions. Due to our implementation of semantic verification, the answer accuracy has improved by up to 16% depending on the specific models and metrics used.     

Empirical evaluations on the cost-effectiveness of state-based testing: An industrial case study

ContextTest models describe the expected behavior of the software under test and provide the basis for test case and oracle generation. When test models are expressed as UML state machines, this is typically referred to as state-based testing (SBT). Despite the importance of being systematic while testing, all testing activities are limited by resource constraints. Thus, reducing the cost of testing while ensuring sufficient fault detection is a common goal in software development. No rigorous industrial case studies of SBT have yet been published.ObjectiveIn this paper, we evaluate the cost-effectiveness of SBT on actual control software by studying the combined influence of four testing aspects: coverage criterion, test oracle, test model and unspecified behavior (sneak paths).MethodAn industrial case study was used to investigate the cost-effectiveness of SBT. To enable the evaluation of SBT techniques, a model-based testing tool was configured and used to automatically generate test suites. The test suites were evaluated using 26 real faults collected in a field study.ResultsResults show that the more detailed and rigorous the test model and oracle, the higher the fault-detection ability of SBT. A less precise oracle achieved 67% fault detection, but the overall cost reduction of 13% was not enough to make the loss an acceptable trade-off. Removing details from the test model significantly reduced the cost by 85%. Interestingly, only a 24–37% reduction in fault detection was observed. Testing for sneak paths killed the remaining eleven mutants that could not be killed by the conformance test strategies.ConclusionsEach of the studied testing aspects influences cost-effectiveness and must be carefully considered in context when selecting strategies. Regardless of these choices, sneak-path testing is a necessary step in SBT since sneak paths are common while also undetectable by conformance testing.     

基于规则引擎的测试用例自动生成方法研究与实现

测试用例自动生成是软件自动化测试的基础与关键。本文实现了基于规则引擎的自动测试用例生成技术,探讨了相应的测试覆盖准则,分析了测试数据的生成。     

Verifying compiled file system code

This article presents a case study on retrospective verification of the Linux Virtual File System (VFS), which is aimed at checking violations of API usage rules and memory properties. Since VFS maintains dynamic data structures and is written in a mixture of C and inlined assembly, modern software model checkers cannot be applied. Our case study centres around our novel automated software verification tool, the SOCA Verifier, which symbolically executes and analyses compiled code. We describe how this verifier deals with complex features such as memory access, pointer aliasing and computed jumps in the VFS implementation, while reducing manual modelling to a minimum. Our results show that the SOCA Verifier is capable of analysing the complex Linux VFS implementation reliably and efficiently, thereby going beyond traditional testing tools and into niches that current software model checkers do not reach. This testifies to the SOCA Verifier’s suitability as an effective and efficient bug-finding tool during the development of operating system components.     

Generating test data from state‐based specifications

Although the majority of software testing in industry is conducted at the system level, most formal research has focused on the unit level. As a result, most system‐level testing techniques are only described informally. This paper presents formal testing criteria for system level testing that are based on formal specifications of the software. Software testing can only be formalized and quantified when a solid basis for test generation can be defined. Formal specifications represent a significant opportunity for testing because they precisely describe what functions the software is supposed to provide in a form that can be automatically manipulated. This paper presents general criteria for generating test inputs from state‐based specifications. The criteria include techniques for generating tests at several levels of abstraction for specifications (transition predicates, transitions, pairs of transitions and sequences of transitions). These techniques provide coverage criteria that are based on the specifications and are made up of several parts, including test prefixes that contain inputs necessary to put the software into the appropriate state for the test values. The test generation process includes several steps for transforming specifications to tests. These criteria have been applied to a case study to compare their ability to detect seeded faults. Copyright © 2003 John Wiley & Sons, Ltd.     

An event‐flow model of GUI‐based applications for testing

Graphical user interfaces (GUIs) are by far the most popular means used to interact with today's software. The functional correctness of a GUI is required to ensure the safety, robustness and usability of an entire software system. GUI testing techniques used in practice are resource intensive; model‐based automated techniques are rarely employed. A key reason for the reluctance in the adoption of model‐based solutions proposed by researchers is their limited applicability; moreover, the models are expensive to create. Over the past few years, the present author has been developing different models for various aspects of GUI testing. This paper consolidates all of the models into one scalable event‐flow model and outlines algorithms to semi‐automatically reverse‐engineer the model from an implementation. Earlier work on model‐based test‐case generation, test‐oracle creation, coverage evaluation, and regression testing is recast in terms of this model by defining event‐space exploration strategies (ESESs) and creating an end‐to‐end GUI testing process. Three such ESESs are described: for checking the event‐flow model, test‐case generation, and test‐oracle creation. Two demonstrational scenarios show the application of the model and the three ESESs for experimentation and application in GUI testing. Copyright © 2007 John Wiley & Sons, Ltd.