Finding failures from passed test cases: improving the pattern classification approach to the testing of mesh simplification programs

Mesh simplification programs create three‐dimensional polygonal models similar to an original polygonal model, and yet use fewer polygons. They produce different graphics even though they are based on the same original polygonal model. This results in a test oracle problem. To address the problem, our previous work has developed a technique that uses a reference model of the program under test to train a classifier. Using such an approach may mistakenly mark a failure‐causing test case as passed. It lowers the testing effectiveness of revealing failures. This paper suggests piping the test cases marked as passed by a statistical pattern classification module to an analytical metamorphic testing (MT) module. We evaluate our approach empirically using three subject programs with over 2700 program mutants. The result shows that, using a resembling reference model to train a classifier, the integrated approach can significantly improve the failure detection effectiveness of the pattern classification approach. We also explain how MT in our design trades specificity for sensitivity. Copyright © 2009 John Wiley & Sons, Ltd.     

Distributed reachability testing of concurrent programs

Reachability testing is an approach to verifying concurrent programs. During reachability testing, every partially ordered synchronization sequence of a program with a given input is exercised exactly once. In this paper, we present the design and implementation of a distributed reachability testing algorithm for a cluster of workstations. This algorithm allows different test sequences to be exercised concurrently by different workstations without any synchronization, and without any duplication of sequences among workstations. Dynamic load balancing is performed using a work‐stealing scheme. A novel aspect of this scheme is that work‐stealing requests progress in rounds. This round‐based structure identifies overloaded workstations to target for work stealing. Empirical studies show good speedup for four benchmark Java programs and one Lotos specification. Copyright © 2010 John Wiley & Sons, Ltd.     

All‐uses testing of shared memory parallel programs

Parallelism has become a way of life for many scientific programmers. A significant challenge in bringing the power of parallel machines to these programmers is providing them with a suite of software tools similar to the tools that sequential programmers currently utilize. Unfortunately, writing correct parallel programs remains a challenging task.In particular, automatic or semi‐automatic testing tools for parallel programs are lacking. This paper takes a first step in developing an approach to providing all‐uses coverage for parallel programs. A testing framework and theoretical foundations for structural testing are presented, including test data adequacy criteria and hierarchy, formulation and illustration of all‐uses testing problems, classification of all‐uses test cases for parallel programs, and both theoretical and empirical results with regard to what can be achieved with all‐uses coverage for parallel programs. Copyright © 2003 John Wiley & Sons, Ltd.     

A combinatorial testing strategy for concurrent programs

One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, called t‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy called t‐way testing. We present an algorithm that implements t‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate that t‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.     

Applying simulation and design of experiments to the embedded software testing process

This paper presents some original solutions with regard to the deployment of the U.S. Department of Defense Simulation, Test and Evaluation Process (DoD STEP), using an automated target tracking radar system as a case study. Besides the integration of modelling and simulation, to form a model‐based approach to the software testing process, the number of experiments, i.e. test cases, have been dramatically reduced by applying an optimized design‐of‐experiment plan and an orthogonal array‐based robust testing methodology. Also, computer‐based simulation at various abstraction levels of the system/software under test can serve as a test oracle. Simulation‐based (stochastic) experiments, combined with optimized design‐of‐experiment plans, in the case study have shown a minimum productivity increase of 100 times in comparison to current practice without DoD STEP deployment. Copyright © 2004 John Wiley & Sons, Ltd.     

基于软件层次化模型的软件测试数据生成

针对基于Markov链模型的软件测试技术在测试数据生成时不考虑软件的结构信息,生成的测试数据集对代码路径的覆盖能力以及缺陷检测能力都较低的问题,将统计测试与基于Markov链模型的测试相结合,提出了一种新的软件测试模型——软件层次化模型。该模型涵盖了软件与外部环境之间的交互,同时描述了软件内部结构信息。还给出了该模型测试数据集的生成算法：首先生成符合使用情况的测试序列,然后为测试序列生成覆盖软件内部结构的输入数据。通过针对示例软件的实验结果表明,与基于Markov链模型的测试方法对比,基于软件层次化模型的测试在满足软件测试充分性要求的同时,提高了测试数据集的代码路径覆盖能力和缺陷检测能力。     

Using concepts of content‐based image retrieval to implement graphical testing oracles

Automation of testing is an essential requirement to render it viable for software development. Although there are several testing techniques and criteria in many different domains, developing methods to test programs with complex outputs remains an unsolved challenge. This setting includes programs with graphical output, which produce images or interface windows. One possible approach towards automating the testing activity is the use of automatic oracles in which a reference image, taken as correct, can be used to establish a correctness measure in the tested program execution. A method that uses concepts of content‐based image retrieval to facilitate oracle automation in the domain of programs with graphics output is presented. Two case studies, one using a computer‐aided diagnostic system and one using a Web application, are presented, including some reflections and discussions that demonstrate the feasibility of the proposed approach. Copyright © 2011 John Wiley & Sons, Ltd.     

A property-based testing framework for encryption programs

In recent years, a variety of encryption algorithms were proposed to enhance the security of software and systems. Validating whether encryption algorithms are correctly implemented is a challenging issue. Software testing delivers an effective and practical solution, but it also faces the oracle problem (that is, under many practical situations, it is impossible or too computationally expensive to know whether the output for any given input is correct). In this paper, we propose a property-based approach to testing encryption programs in the absence of oracles. Our approach makes use of the so-called metamorphic properties of encryption algorithms to generate test cases and verify test results. Two case studies were conducted to illustrate the proposed approach and validate its effectiveness. Experimental results show that even without oracles, the proposed approach can detect nearly 50% inserted faults with at most three metamorphic relations (MRs) and fifty test cases.     

Search‐based testing using constraint‐based mutation

Many modern automated test generators are based on either metaheuristic search techniques or use constraint solvers. Both approaches have their advantages, but they also have specific drawbacks: Search‐based methods may get stuck in local optima and degrade when the search landscape offers no guidance; constraint‐based approaches, on the other hand, can only handle certain domains efficiently. This paper describes a method that integrates both techniques and delivers the best of both worlds. On a high‐level view, the proposed method uses a genetic algorithm to generate tests, but the twist is that during evolution, a constraint solver is used to ensure that mutated offspring efficiently explores different control flow. Experiments on 20 case study programmes show that on average the combination improves branch coverage by 28% over search‐based techniques while reducing the number of tests by 55%, and improves coverage by 13% over constraint‐based techniques while reducing the number of tests by 73%. Copyright © 2013 John Wiley & Sons, Ltd.     

A transformation‐based approach to testing concurrent programs using UML activity diagrams

Unified Modeling Language (UML) activity diagrams are widely used to model concurrent interaction among multiple objects. In this paper, we propose a transformation‐based approach to generating scenario‐oriented test cases for applications modeled by UML activity diagrams. Using a set of transformation rules, the proposed approach first transforms a UML activity diagram specification into an intermediate representation, from which it then constructs test scenarios with respect to the given concurrency coverage criteria. The approach then finally derives a set of test cases for the constructed test scenarios. The approach resolves the difficulties associated with fork and join concurrency in the UML activity diagram and enables control over the number of the resulting test cases. We further implemented a tool to automate the proposed approach and studied its feasibility and effectiveness using a case study. Experimental results show that the approach can generate test cases on demand to satisfy a given concurrency coverage criterion and can detect up to 76.5% of seeded faults when a weak coverage criterion is used. With the approach, testers can not only schedule the software test process earlier, but can also better allocate the testing resources for testing concurrent applications. Copyright © 2015 John Wiley & Sons, Ltd.     

Structural testing for message‐passing concurrent programs: an extended test model

Developing high‐quality, error‐free message‐passing concurrent programs is not trivial. Although a number of different primitives with associated semantics are available to assist such development, they often increase the complexity of the testing process. In this paper, we extend our previous test model for message‐passing programs and present new structural testing criteria, taking into account additional features used in this paradigm, such as collective communication, non‐blocking sends, distinct semantics for non‐blocking receives, and persistent operations. Our new model also recognizes that sender primitives cannot always be matched with every receive primitive. This improvement allows us to remove statically a significant number of infeasible synchronization edges that would otherwise have to be analyzed later by the tester. In this paper, the test model is presented using the Message‐Passing Interface standard; however, our new model has been designed to be flexible, and it can be configured to support a range of different message‐passing environments or languages. We have carried out case studies showing the applicability of the new test model to represent message‐passing programs and also to reveal errors, mainly those errors related to inter‐process communication. In addition to increasing the number of features supported by the test model, we have also reduced the overall cost of testing significantly. Our case studies suggest that the number of synchronization edges can be reduced by up to 93%, mainly by eliminating infeasible edges between unmatchable communication primitives. The main contribution of the paper is to present a more flexible test model that provides improved coverage for message‐passing programs and at the same time reduces the cost of testing significantly. Copyright © 2012 John Wiley & Sons, Ltd.     

Dual programming approach to software testing

The testing phase of the software development process consumes about one-half of the development time and resources. This paper addresses the automation of the analysis stage of testing. Dual programming is introduced as one approach to implement this automation. It uses a higher level language to duplicate the functionality of the software under test. We contend that a higher level language (HLL) uses fewer lines of code than a lower level language (LLL) to achieve the same functionality, so testing the HLL program will require less effort than testing the LLL equivalent. The HLL program becomes the oracle for the LLL version. This paper describes experiments carried out using different categories of applications, and it identifies those most likely to profit from this approach. A metric is used to quantify savings realized. The results of the research are: (a) that dual programming can be used to automate the analysis stage of software testing; (b) that substantial savings of the cost of this testing phase can be realized when the appropriate pairing of primal and dual languages is made, and (c) that it is now possible to build a totally automated testing system. Recommendations are made regarding the applicability of the method to specific classes of applications.     

基于马尔可夫链模型的软件测试方法的研究与实现

在马尔可夫链模型的基础上,将软件测试结果的分析问题转化为一个经典概率问题。通过数学方法实现了软件测试模型的简化,加速了测试用例的生成,从而降低了测试的复杂度,解决了简化测试用例难度的问题。通过实例证明,这种测试技术具有一定的实用性和有效性。     

Systematic testing and formal verification to validate reactive programs

The use of systematic testing and formal verification in the validation of reactive systems implemented in synchronous languages is illustrated. Systematic testing and formal verification are two techniques for checking the consistency between a program and its specification. The approach to validation is through specification: two system views are developed in addition to the program, a behavioural specification for systematic testing and a logical specification for formal verification. Pursuing both activities, reactive programs can be validated both more efficiently (in terms of costs) and more effectively (in terms of confidence in correctness). This principle is demonstrated here using the well known lift example.     

基于升级路径的软件升级测试模型及其启示

软件升级测试是软件测试的重要方面。在分析软件升级路径数目爆炸式增长以及测试成本不断攀升的基础上,提出了一种升级路径优选方法,并在此基础上阐述了一种升级测试模型。理论和实践证明该模型是有效的;基于这种测试模型给出了软件升级架构设计的一些启示。     

Integration testing of Object-Oriented and Aspect-Oriented programs: A structural pairwise approach for Java

Several testing approaches focus on finding faults in software units of implementation. A problem not addressed by unit testing is the interaction among units, with respect to the correctness of their interfaces. In this paper a structural integration testing approach for Object-Oriented (OO) and Aspect-Oriented (AO) Java programs is presented. To make the activity more feasible, we address the testing of pairs of units (i.e., methods and pieces of advice). A model called (PairWise Def-Use) graph to represent the flow of control and data between pairs of units is proposed. Based on the , the following family of testing criteria is defined: all-pairwise-integrated-nodes (control-flow based), all-pairwise-integrated-edges (control-flow based), and all-pairwise-integrated-uses (data-flow based). To evaluate the proposed approach, an implementation of the criteria in a testing tool is presented along with an example of usage and an exploratory study. The study with 7 AO programs that are also OO was conducted to investigate the cost of application and usefulness of the approach. Results provided evidence that the criteria are practical and useful for integration testing of OO and AO programs.     

关于软件测试模型的探讨

近年来,计算机进入了千万百姓家,在教育、医学、军事等领域贡献了巨大力量,而作为信息技术的一种,软件规模越来越大,数量和种类越来越多,软件结构也愈加复杂,但是软件在社会各个领域都是不可或缺的,因此如何提高软件质量、安全性成为了企业、研究机构所关注的重要问题.大量实践表明,软件测试是决定软件质量的重要因素,软件开发有过程模型,而软件测试有测试模型.使用测试模型的主要目的是描述软件测试中包含的活动和其相互之间的关系,运用软件测试模型能够有效提高测试效率,减少人力和财力消耗.     

具有不确定需求的软件测试用例生成方法研究

软件测试是软件开发重要的一部分,是保证软件质量,提高软件可靠性的重要途径。测试在需求分析阶段就开始介入,而在现实中很多需求是不确定的,在软件测试的过程中会面临许多不确定性的挑战。主要研究具有不确定需求的软件测试用例生成方法,利用基于标记迁移系统的Partial Models（部分模型）对不确定的需求进行建模,进而基于建立的模型生成有效的测试用例。针对模型中具有的不确定性引入概率,对不确定的部分进行概率表示,进一步基于标记迁移系统和Partial Models的特点提出测试用例生成方法。由于模型中具有不确定信息,由此生成的测试用例具有一定的概率,基于此对测试用例进行优先级排序。     

基于MSC的网络游戏软件测试方法研究*

针对网络游戏软件测试方法研究方面的不足,结合基于模型测试方法和TTCN测试技术,对网络游戏软件可玩性的测试方法进行研究。采用MSC图作为网络游戏玩法建模工具,建立玩法测试模型;用TTCN-3核心语言对玩法测试模型加以实现;结合一个具体的网络游戏软件测试案例,给出上述测试方法和技术的解释。从理论角度验证了基于模型测试方法在网络游戏软件测试上的可行性;从技术角度表明了TTCN对网络游戏软件测试的有效性。     

基于TTCN-3底层协议测试方法研究*

TTCN-3测试语言不仅可以应用于普通的协议测试,也可以应用于硬件系统、应用服务系统以及与操作系统和硬件相关的服务型底层协议的测试。将协议一致性框架应用到TTCN-3中,在原有测试方法基础上,基于本实验室开发的测试平台,提出了一种新的测试方法,并以ARP为例按照新的测试方法对其进行测试,验证了ARP的一致性和TTCN-3语言应用于底层协议的可能。