Context: In metamorphic testing (MT), a set of metamorphic relations (MRs) are identified to verify whether or not a trained deep neural network (DNN) can produce consistent performance when specific transformations are applied to its input. Most DNNs trained with existing methods often perform poorly with respect to MRs, thereby indicating that these DNNs are not robust. Objective: To improve DNN’s performance in the context of MT, a set of defined MRs is used to generate training inputs to retrain a DNN model. Our main objective is to develop a method to balance a DNN’s accuracy and robustness with less time consumption and having the capability to cater to multiple MRs. Methods: In this paper, we introduce our regularization-based method (known as MT-Boost), which uses reinforcement learning to search for the best way of using MRs to generate inputs and express them as loss function regularizers. When developing MT-Boost, we transform the robustness-improving problem into a reinforcement-learning agent’s training problem. Results: MT-Boost is evaluated on eight DNN models with four popular datasets. MT-Boost achieves the largest robustness improvement for each model and maintains relatively high accuracy performance when compared with seven other baseline methods. Our sensitivity analysis also shows the high stability performance of MT-Boost across four reinforcement-learning algorithms and other hyperparameters. Conclusion: Experimental results show that MT-Boost is effective and efficient for improving DNN’s robustness.

Large language models (LLMs) have rapidly become a powerful tool in automated code generation, yet most research has focused on their correctness and efficiency rather than the stylistic patterns of their outputs. In this preliminary study, we analyze the code patterns generated by five popular LLMs—ChatGPT, Gemini, Claude, Grok, and DeepSeek—in their free versions, across three LeetCode problems, one top-ranking each from the easy, medium, and hard categories. Our evaluation employs key metrics including inline comment density, naming conventions, and edge case handling, highlighting both similarities and differences in verbosity, comprehensibility, and robustness among the codes generated by models. The findings of this study have important implications for software engineering and education, suggesting that LLM-generated code can serve as both a tool for rapid prototyping and an effective learning resource for beginners. Our future work will extend this analysis to a broader set of coding challenges and compare LLM outputs with human-written code to develop robust criteria for evaluating automated code generation.

Metamorphic testing has become one mainstream technique to address the notorious oracle problem in software testing, thanks to its great successes in revealing real-life bugs in a wide variety of software systems. Metamorphic relations, the core component of metamorphic testing, have continuously attracted research interests from both academia and industry. In the last decade, a rapidly increasing number of studies have been conducted to systematically generate metamorphic relations from various sources and for different application domains. In this article, based on the systematic review on the state of the art for metamorphic relations’ generation, we summarize and highlight visions for further advancing the theory and techniques for identifying and constructing metamorphic relations and discuss promising research directions in related areas.

Metamorphic testing, thanks to its high failure-detection effectiveness especially in the absence of test oracle, has been widely applied in both the traditional context of software testing and other relevant fields such as fault localization and program repair. Its core element is a set of metamorphic relations, which are the necessary properties of the target algorithm in the form of the relationships among multiple inputs and corresponding expected outputs. When a relation is violated by the outputs of a group of test cases, namely metamorphic group of test cases, that are constructed based on the relation, a failure is said to be revealed. Traditionally, the primary task of software testing is to reveal failures. Therefore, from the perspective of software testing, it may not need to know which test case(s) in the metamorphic group cause the violation and thus the failure. However, such information is definitely helpful for other software engineering activities, such as software debugging. The current literature of metamorphic testing lacks a systematic mechanism of identifying the actual failure-revealing test cases, which hinders its applicability and effectiveness in other relevant fields. In this article, we propose a new technique for the FAILure-revealing Test case Identification in Metamorphic testing, namely FAILTIM. The approach is based on a novel application of statistical methods. More specifically, we leverage and adapt the basic ideas of spectrum-based techniques, which are originally used in fault localization, and propose the utilization of a set of risk formulas to estimate the suspiciousness of each individual test case in metamorphic groups. Failure-revealing test cases are then suggested according to their suspiciousness. A series of experiments have been conducted to evaluate the effectiveness and efficiency of FAILTIM using 9 subject programs and 30 risk formulas. The experimental results showed that the new approach can achieve a high accuracy in identifying the actual failure-revealing test cases in metamorphic testing. Consequently, our study will help boost the applicability and performance of metamorphic testing beyond testing to other software engineering areas. The present work also unfolds a number of research directions for further advancing the theory of metamorphic testing and more broadly, software testing.

Software developers can only obtain a very small amount of information from the individual failure-causing inputs, which makes debugging difficult. Therefore, it is necessary to explore additional failure-causing inputs (failure regions) using the known failure-causing inputs. In order to accurately and efficiently identify the failure region, we propose a novel two-stage search algorithm, TS-FRI. In the initial exploration stage, a round-robin search identifies several boundary failure-causing points, and the failure region's centroid is estimated. During the main search stage, the boundary failure-causing points are identified through iterative division of the input domain with an equally sized partitioning strategy. This results in the boundary points being as dispersed as possible around the failure-region boundary, with the polytope formed by the points approximating the failure region (e.g., a polygon in two dimensions). The proposed algorithm is validated through simulation and empirical analysis: The experimental results show that the TS-FRI accuracy is at least comparable to the best accuracy of the compared three algorithms, and can be ten times better. In addition, TS-FRI only takes a quarter of the computation time and half the failure-validation cost of the other algorithms.

Metamorphic Testing (MT) has been repeatedly proven effective in detecting software faults. MT detects faults by checking the Metamorphic Relations (MRs) among Source Test Cases (STCs) and Follow-up Test Cases (FTCs) and the corresponding outputs. Metamorphic Groups (MGs) denote the associated STCs and FTCs. The performance of MT relates strongly to the MRs and MGs. However, previous studies that on MG generation mainly focused on improving the effectiveness (i.e. fault-detection capability) of MT, but to some extent overlooked the efficiency. This paper proposes a new kind of MG generation algorithms called Metamorphic-Testing-based Adaptive Random Testing through Partitioning (MT-PART). These algorithms at-tempt to improve both the effectiveness and the efficiency of MT by dynamically partitioning the input domain and generating new STCs and FTCs that are uniformly distributed over their corresponding input domains. Through empirical experiments, we found that our algorithms are able to significantly outper-form other existing MG generation algorithms in terms of test efficiency, while maintaining good test effectiveness.

This study introduces a website serving as an Open Educational Resource (OER), dedicated to Metamorphic Testing (MT) and Metamorphic Relation (MR) generation, with a specific focus on Autonomous Driving Systems (ADSs). It offers a comprehensive introduction to MT and ADSs, and presents a specially designed scenario template that simplifies the MR generation process for ADS functions. This template enhances accessibility, making it more user-friendly for a wider audience, and facilitates systematic application, ensuring that users can apply test case and MR generation in a structured and organized manner. The MR generation guidelines that work with the template lower the learning barrier for beginners in MT, thus facilitating easier adoption and application of MT to ADSs.

The performance of metamorphic testing relates strongly to the quality of test cases. However, most related research has only focused on source test cases, ignoring follow-up test cases to some extent. In this paper, we identify a potential problem that may be encountered with existing metamorphic group generation algorithms. We then propose a possible solution to address this problem. Based on this solution, we design a new algorithm for generating effective source and follow-up test cases. To improve the performance (test effectiveness and efficiency) of metamorphic testing. We introduce the concept of the input-domain difference problem, which is likely to affect the performance of metamorphic group generation algorithms. We propose a new test-case distribution criterion for metamorphic testing to address this problem. Based on our proposed criterion, we further present a new metamorphic group generation algorithm, from a black-box perspective, with new distance metrics to facilitate this algorithm. Our algorithm performs significantly better than existing algorithms, in terms of test effectiveness, efficiency and test-case diversity. Through experiments, we find that the input-domain difference problem is likely to affect the performance of metamorphic group generation algorithms. The experimental results demonstrate that our algorithm can achieve good test efficiency, effectiveness, and test-case diversity.

Concurrent programs are normally composed of multiple concurrent threads sharing memory space. These threads are often interleaved, which may lead to some non-determinism in execution results, even for the same program input. This poses huge challenges to the testing of concurrent programs, especially on the test result verification—that is, the prevalent existence of the oracle problem. In this article, we investigate the application of metamorphic testing (MT), a mainstream technique to address the oracle problem, into the testing of concurrent programs. Based on the unique features of interleaved executions in concurrent programming, we propose an extended notion of metamorphic relations, the core part of MT, which are particularly designed for the testing of concurrent programs. A comprehensive testing approach, namely ConMT , is thus developed and a tool is built to automate its implementation on concurrent programs written in Java. Empirical studies have been conducted to evaluate the performance of ConMT, and the experimental results show that in addition to addressing the oracle problem, ConMT outperforms the baseline traditional testing techniques with respect to a higher degree of automation, better bug detection capability, and shorter testing time. It is clear that ConMT can significantly improve the cost-effectiveness for the testing of concurrent programs and thus advances the state of the art in the field. The study also brings novelty into MT, hence promoting the fundamental research of software testing.

Concerns have been growing over fake news and its impact. Software that can automatically detect fake news is becoming more popular. However, the accuracy and reliability of such fake-news detection software remains questionable, partly due to a lack of testing and verification. Testing this kind of software may face the oracle problem, which refers to difficulty (or inability) of identifying the correctness of the software’s output in a reasonable amount of time. Metamorphic testing (MT) has a record of effectively alleviating the oracle problem, and has been successfully applied to testing fake-news detection software. This paper reports on a study, extending previous work, exploring the use of MT for fake-news detection software. The study includes new metamorphic relations and additional experimental results and analysis. Some alternative MR-generation approaches are also explored. The study targets software where the output is a real/fake news decision, enhancing the applicability of MT to current fake-news detection software. The paper also explores the impact of the prediction accuracy of the fake-news detection software on the MT process. The study demonstrates the validity and applicability of MT to fake-news detection software. The prediction accuracy of the software has a greater impact on MT experiments with greater changes between the source and follow-up inputs, and less dependence on prediction stability. Some possible factors affecting the experimental results are discussed, and directions for future work are provided.

Over the past decade, metamorphic testing has gained rapidly increasing attention from both academia and industry, particularly thanks to its high efficacy on revealing real-life software faults in a wide variety of application domains. On the basis of a set of metamorphic relations among multiple software inputs and their expected outputs, metamorphic testing not only provides a test case generation strategy by constructing new (or follow-up) test cases from some original (or source) test cases, but also a test result verification mechanism through checking the relationship between the outputs of source and follow-up test cases. Many efforts have been made to further improve the cost-effectiveness of metamorphic testing from different perspectives. Some studies attempted to identify “good” metamorphic relations, while other studies were focused on applying effective test case generation strategies especially for source test cases. In this article, we propose improving the cost-effectiveness of metamorphic testing by leveraging the feedback information obtained in the test execution process. Consequently, we develop a new approach, namely feedback-directed metamorphic testing, which makes use of test execution information to dynamically adjust the selection of metamorphic relations and selection of source test cases. We conduct an empirical study to evaluate the proposed approach based on four laboratory programs, one GNU program, and one industry program. The empirical results show that feedback-directed metamorphic testing can use fewer test cases and take less time than the traditional metamorphic testing for detecting the same number of faults. It is clearly demonstrated that the use of feedback information about test execution does help enhance the cost-effectiveness of metamorphic testing. Our work provides a new perspective to improve the efficacy and applicability of metamorphic testing as well as many other software testing techniques.

Autonomous driving has gained much attention from both industry and academia. Currently, Deep Neural Networks (DNNs) are widely used for perception and control in autonomous driving. However, several fatal accidents caused by autonomous vehicles have raised serious safety concerns about autonomous driving models. Some recent studies have successfully used the metamorphic testing technique to detect thousands of potential issues in some popularly used autonomous driving models. However, prior study is limited to a small set of metamorphic relations, which do not reflect rich, real-world traffic scenarios and are also not customizable. This paper presents a novel declarative rule-based metamorphic testing framework calledRMT.RMTprovides a rule template with natural language syntax, allowing users to flexibly specify an enriched set of testing scenarios based on real-world traffic rules and domain knowledge.RMTautomatically parses human-written rules to metamorphic relations using an NLP-based rule parser referring to an ontology list and generates test cases with a variety of image transformation engines. We evaluatedRMTon three autonomous driving models. With an enriched set of metamorphic relations,RMTdetected a significant number of abnormal model predictions that were not detected by prior work. Through a large-scale human study on Amazon Mechanical Turk, we further confirmed the authenticity of test cases generated byRMTand the validity of detected abnormal model predictions.

Metamorphic testing (MT) has been growing in pop-ularity, but it can still be quite challenging and time-consuming to assess its performance. Typical approaches to performance assessment can require a series of steps, and depend on a variety of factors, often requiring serendipity. This can be a bottleneck for some aspects of MT research. Central to MT, metamorphic relations (MRs) represent necessary properties of the system under test (SUT). In traditional software testing, simulations are often employed to examine and compare the performance of dif-ferent testing strategies. However, these simulations are typically designed based on the assumed availability (and applicability) of a test oracle - a mechanism to decide the correctness of the SUT output or behaviour. A key reason for the popularity of MT is its proven record of effective software testing, without the need for a test oracle. This strength, however, also means that traditional ways of using simulations to analyse software testing approaches are not applicable for MT. This lack of cheap and fast ways to conduct simulation analyses of MT is a hurdle for many aspects of MT research, and may be an obstacle to its more widespread adoption. To address this, in this paper we introduce the concept of MR-violation regions (MRVRs), and show how they can be used for a certain category of MRs, Deterministic MRs (DMRs), to build simulation tools for MT. We analyse the differences between MRVRs and traditional, oracle-defined failure regions; and report on a preliminary case study exploring MRVRs in numerical-input-domain systems from previous MT studies. We anticipate that the proposed MT simulation framework may facilitate more research into MT, and may help lead to its more widespread adoption.

Deep neural networks (DNNs) have achieved a major success in solving challenging tasks such as social networks analysis and image classification. Despite the prosperous development of DNNs, recent research has demonstrated the feasibility of exploiting DNNs using adversarial examples, in which a small distortion is added into the input data to largely mislead prediction of DNNs.Determining the similarity of two binary codes is the foundation for many reverse engineering, re-engineering, and security applications. Currently, the majority of binary code matching tools are based on DNNs, the dependability of which has not been completely studied. In this research, we present an attack that perturbs software in executable format to deceive DNN-based binary code matching. Unlike prior attacks which mostly change non-functional code components to generate adversarial programs, our approach proposes the design of several semantics-preserving transformations directly toward the control flow graph of binary code, making it particularly effective to deceive DNNs. To speedup the process, we design a framework that leverages gradient- or hill climbing-based optimizations to generate adversarial examples in both white-box and black-box settings. We evaluated our attack against two popular DNN-based binary code matching tools, asm2vec and ncc, and achieve reasonably high success rates. Our attack toward an industrial-strength DNN-based binary code matching service, BinaryAI, shows that the proposed attack can fool remote APIs in challenging black-box settings with a success rate of over 16.2% (on average). Furthermore, we show that the generated adversarial programs can be used to augment robustness of two white-box models, asm2vec and ncc, reducing the attack success rates by 17.3% and 6.8% while preserving stable, if not better, standard accuracy.

[J1C2 Presentation Abstract at IEEE SERVICES 2022 for IEEE Transactions on Services Computing, 2022, 15(2):736-751. DOI: 10.1109/TSC.2019.2960496].

Mutation testing is basically a fault-based software testing technique, which has been proposed to measure the fault detection effectiveness of a test suite using programs with simulated faults (namely mutants). However, mutation testing is time consuming and computationally expensive because of the normal use of a large amount of mutants. Thus, reducing the mutants is of great significance. To address this problem, various mutant reduction techniques have been proposed. Among them, the identification of redundant mutants aims at removing mutants whose test results can be inferred by other mutants. This article proposes a redundant mutant identification technique based on selective symbolic execution called ReMuSSE for weak mutation testing. Redundant mutants could be revealed by identifying those with similar program execution state changes within a program block involving mutated statements. An empirical study was conducted using 13 C programs from different application domains with varying sizes. The empirical results showed that ReMuSSE could identify up to 31.4% redundant mutants and consequentially save up to 35.2% time cost of weak mutation testing. The results demonstrated that ReMuSSE could effectively identify redundant mutants and thus could significantly improve the efficiency of weak mutation testing.

In recent years, service oriented architecture (SOA) has been increasingly adopted to develop distributed applications in the context of the Internet. To develop reliable SOA-based applications, an important issue is how to ensure the quality of web services. In this article, we propose a dynamic random testing (DRT) technique for web services, which is an improvement over the widely-practiced random testing (RT) and partition testing (PT) approaches. We examine key issues when adapting DRT to the context of SOA, including a framework, guidelines for parameter settings, and a prototype for such an adaptation. Empirical studies are reported where DRT is used to test three real-life web services, and mutation analysis is employed to measure the effectiveness. Our experimental results show that, compared with the three baseline techniques, RT, Adaptive Testing (AT) and Random Partition Testing (RPT), DRT demonstrates higher fault-detection effectiveness with a lower test case selection overhead. Furthermore, the theoretical guidelines of parameter setting for DRT are confirmed to be effective. The proposed DRT and the prototype provide an effective and efficient approach for testing web services.

Metamorphic Relations (MRs) play a key role in determining the fault detection capability of Metamorphic Testing (MT). As human judgement is required for MR identification, systematic MR generation has long been an important research area in MT. Additionally, due to the extra program executions required for follow-up test cases, some concerns have been raised about MT cost-effectiveness. Consequently, the reduction in testing costs associated with MT has become another important issue to be addressed. MR composition can address both of these problems. This technique can automatically generate new MRs by composing existing ones, thereby reducing the number of follow-up test cases. Despite this advantage, previous studies on MR composition have empirically shown that some composite MRs have lower fault detection capability than their corresponding component MRs. To investigate this issue, we performed theoretical and empirical analyses to identify what characteristics component MRs should possess so that their corresponding composite MR has at least the same fault detection capability as the component MRs do. We have also derived a convenient, but effective guideline so that the fault detection capability of MT will most likely not be reduced after composition.

Since the popularization of social media, news has entered our lives digitally. While news is spreading broader and faster, fake news is becoming an increasingly popular topic. Fake news detection is therefore important in both social media and research areas. With artificial intelligence technology, software engineers have developed a lot of fake news detection systems. One of the biggest challenges for such systems is that they may face the oracle problem, which means that there may not be a way, or it may take too long time, to confirm the correctness of a specific output. Metamorphic Testing has been applied successfully to alleviate the oracle problem in many different areas, including in artificial intelligence. In this paper, we propose several metamorphic relations for fake news detection and report on experiments using metamorphic testing on fake news detection applications.

Information is indispensable in modern society. People’s daily communication and work depend on information transmission. Unsafe storage or transmission of data may result in privacy and security problems. One way to attempt to prevent such issues is to use encryption algorithms to transform information into encrypted forms. Because the encryption steps of most encryption algorithms are complex, deciding the correctness of the encrypted output may take a long time in practice. This kind of problem is called the Test Oracle problem. In contrast to traditional software testing, Metamorphic Testing (MT) does not focus on the correctness of each individual output, but examines whether the inputs and outputs of multiple executions of a Program Under Test (PUT) satisfy necessary relations of the PUT, called metamorphic relations. This paper reports on an experience of applying MT to test three encryption algorithms — Data Encryption Standard (DES), Triple Data Encryption Standard (3DES), and Advanced Encryption Standard (AES).

Visual question answering (VQA) takes an image and a natural-language question as input and returns a natural-language answer. To date, VQA models are primarily assessed by their accuracy on high-level reasoning questions. Nevertheless, Given that perception tasks (e.g., recognizing objects) are the building blocks in the compositional process required by high-level reasoning, there is a demanding need to gain insights into how much of a problem low-level perception is. Inspired by the principles of software metamorphic testing, we introduce MetaVQA, a model-agnostic framework for benchmarking perception capability of VQA models. Given an image i, MetaVQA is able to synthesize a low-level perception question q. It then jointly transforms (i, q) to one or a set of sub-questions and sub-images. MetaVQA checks whether the answer to (i, q) satisfies metamorphic relationships (MRs), denoting perception consistency, with the composed answers of transformed questions and images. Violating MRs denotes a failure of answering perception questions. MetaVQA successfully detects over 4.9 million perception failures made by popular VQA models with metamorphic testing. The state-of-the-art VQA models (e.g., the champion of VQA 2020 Challenge) suffer from perception consistency problems. In contrast, the Oscar VQA models, by using anchor points to align questions and images, show generally better consistency in perception tasks. We hope MetaVQA will revitalize interest in enhancing the low-level perceptual abilities of VQA models, a cornerstone of high-level reasoning.

Recent years have seen a rapid development of machine learning based multi-module unmanned aerial vehicle (UAV) systems. To address the oracle problem in autonomous systems, numerous studies have been conducted to use metamorphic testing to automatically generate test scenes for various modules, e.g., those in self-driving cars. However, as most of the studies are based on unit testing including end-to-end model-based testing, a similar testing approach may not be equally effective for UAV systems where multiple modules are working closely together. Therefore, in this paper, instead of unit testing, we propose a novel metamorphic system testing framework for UAV, named MSTU, to detect the defects in multi-module UAV systems. A preliminary evaluation plan to apply MSTU on an emerging autonomous multi-module UAV system is also presented to demonstrate the feasibility of the proposed testing framework.

Adaptive random testing (ART) improves the failure-detection effectiveness of Random testing (RT) by making test cases more evenly distributed in the input domain. The Fixed-size-Candidate-set ART (FSCS-ART) is one of the most classical algorithms, which selects the candidate test case furthest from the previously executed test case as the next test case. However, when the number of executed test cases is large, the computational overhead will be very high. In this paper, we propose an enhanced version of FSCS-ART based on a modified Metric-Memory tree (MM-tree), namely Fixed-size-Candidate-set ART based on the modified MM-tree (MMFC-ART). Simulations and empirical studies are conducted to verify the effectiveness and efficiency of MMFC-ART. The experimental results indicate that MMFC-ART significantly reduces the computational overhead while ensuring comparable or better failure-detection effectiveness than FSCS-ART. Meanwhile, compared with KD-tree-enhanced Fixed-size-Candidate-set ART (KDFC-ART), MMFC-ART has better performance in high dimensions in terms of efficiency. In terms of effectiveness, MMFC-ART has better failure-detection effectiveness in some scenarios. Overall, MMFC-ART is cost-effective compared to FSCS-ART and KDFC-ART.

Metamorphic testing (MT) was introduced about a quarter of a century ago. It is increasingly being accepted by researchers and the industry as a useful testing technique. The studies, research results, applications, and extensions of MT have given us many insights and visions for its future. Our visions include: MRs will be a practical means to top up test case generation techniques, beyond the alleviation of the test oracle problem; MT will not only be a standalone technique, but conveniently integrated with other methods; MT and MRs will evolve beyond software testing, or even beyond verification; MRs may be anything that you can imagine, beyond the necessary properties of algorithms; MT research will be beyond empirical studies and move toward a theoretical foundation; MT will not only bring new concepts to software testing but also new concepts to other disciplines; MRs will alleviate the reliable test set problem beyond traditional approaches. These visions may help researchers explore the challenges and opportunities for MT in the next decade.

Abstract Combinatorial interaction testing (CIT) aims at constructing a covering array (CA) of all value combinations at a specific interaction strength, to detect faults that are caused by the interaction of parameters. CIT has been widely used in different applications, with many algorithms and tools having been proposed to support CA construction. To date, however, there appears to have been no studies comparing different CA constructors when only some of the CA test cases are executed. In this paper, we present an investigation of five popular CA constructors: ACTS, Jenny, PICT, CASA and TCA. We conducted empirical studies examining the five programs, focusing on interaction coverage and fault detection. The experimental results show that when there is no preference or special justification for using other CA constructors, then Jenny is recommended—because it achieves better interaction coverage and fault detection than the other four constructors in many cases. Our results also show that when using ACTS or CASA, their CAs must be prioritized before testing. The main reason for this is that these CAs can result in considerable interaction coverage or fault detection capabilities when executing a large number of test cases; however, they may also produce the lowest rates of fault detection and interaction coverage.

This paper presents an automated, domain-independent, metamorphic testing platform called MTKeras. In this paper, we report on an investigation demonstrating the effectiveness and usability of MTKeras through five case studies in the four domains of image classification, sentiment analysis, search engines and database management systems. We also report on the effectiveness of combining metamorphic relation (input) patterns in individual metamorphic relations, enhancing the failure-finding abilities of the individual relations. The results of our experiments support combining patterns, and the use of MTKeras. The research reported in this paper shows the applicability of metamorphic relation patterns, and introduces a practical tool for the research community.

Test-suite-based automated program repair (APR) techniques acquire information from an input test suite to guide the repair process, aiming to produce a repair that can pass all test cases of the input test suite. Obviously, the input test suite has a critical impact on the repair effectiveness of APR techniques. This article reports on a study of the APR input test suites from a new perspective. We first propose a novel method of constructing the APR input test suites, using information derived from violated metamorphic relations. We then empirically evaluate our construction method using three APR techniques (Angelix, CETI, and GenProg), comparing it with random and code-coverage-based construction methods that are used as the experimental control. The results show that our approach is complementary to these two input test suite construction methods. This article illustrates a new use of metamorphic relations for program repair.

Existing test case prioritization (TCP) techniques have limitations when applied to real-world projects, because these techniques require certain information to be made available before they can be applied. For example, the family of input-based TCP techniques are based on test case values or test script strings; other techniques use test coverage, test history, program structure, or requirements information. Existing techniques also cannot guarantee to always be more effective than random prioritization (RP) that does not have any precondition. As a result, RP remains the most applicable and most fundamental TCP technique. This article proposes an extremely simple, effective, and efficient way to prioritize test cases through the introduction of a dispersity metric. Our technique is as applicable as RP. We conduct empirical studies using 43 different versions of 15 real-world projects. Empirical results show that our technique is more effective than RP. Our algorithm has a linear computational complexity and, therefore, provides a practical solution to the problem of prioritizing very large test suites (such as those containing hundreds of thousands, or millions, of test cases), where the execution time of conventional nonlinear prioritization algorithms can be prohibitive. Our technique also provides a practical solution to TCP when neither input-based nor execution-based techniques are applicable due to lack of information.

Metamorphic testing is well known for its ability to alleviate the oracle problem in software testing. The main idea ofmetamorphic testing is to test a software system by checking whether each identified metamorphic relation (MR) holds among severalexecutions. In this regard, identifying MRs is an essential task in metamorphic testing. In view of the importance of this identificationtask, METRIC (METamorphic Relation Identification based on Category-choice framework) was developed to help software testersidentify MRs from a given set of complete test frames. However, during MR identification, METRIC primarily focuses on the inputdomain without sufficient attention given to the output domain, thereby hindering the effectiveness of METRIC. Inspired by this problem,we have extended METRIC into METRIC+by incorporating the information derived from the output domain for MR identification. A toolimplementing METRIC+has also been developed. Two rounds of experiments, involving four real-life specifications, have beenconducted to evaluate the effectiveness and efficiency of METRIC+. The results have confirmed that METRIC+is highly effective andefficient in MR identification. Additional experiments have been performed to compare the fault detection capability of the MRsgenerated by METRIC+and those bymMT (another MR identification technique). The comparison results have confirmed that the MRsgenerated by METRIC+are highly effective in fault detection.

This paper describes an on-going project to develop a Virtual Reality platform to deliver phobia-inspired experiences. These experiences could induce a reaction in the user that may help the user overcome, or alleviate, the phobia. The platform includes monitoring sensors that could be used to measure how much impact the experience is having. The project development has been taking place at a Sino-foreign Higher Education Institution in Mainland China, University of Nottingham Ningbo China (UNNC). UNNC has already been host to a number of OER (Open Educational Resource) development projects, and the current project is also anticipated to eventually be released to the OER community. This paper presents the background, development, and current state of the project. Challenges to project completion, and future work are also outlined.

Diversity is the key factor for test cases to detect program failures. Adaptive random testing (ART) is one of the effective methods to improve the diversity of test cases. Being an ART algorithm, the evolutionary adaptive random testing (eAR) only increases the distance between test cases to enhance its failure detection ability. This paper presents a new ART algorithm, MoesART, based on multi-objective evolutionary search. In this algorithm, in addition to the dispersion diversity, two other new diversities (or optimization objectives) are designed from the perspectives of the balance and proportionality of test cases. Then, the Pareto optimal solution returned by the NSGA-II framework is used as the next test case. In the experiments, the typical block failure pattern in the cases of two-dimensional and three-dimensional input domains is used to validate the effectiveness of the proposed MoesART algorithm. The experimental results show that MoesART exhibits better failure detection ability than both eAR and the fixed-sized-candidate-set ART (FSCS-ART), especially for the programs with three-dimensional input domain.

Abstract test cases (ATCs) have been widely used in practice, including in combinatorial testing and in software product line testing. When constructing a set of ATCs, due to limited testing resources in practice (e.g., in regression testing), test case prioritization (TCP) has been proposed to improve the testing quality, aiming at ordering test cases to increase the speed with which faults are detected. One intuitive and extensively studied TCP technique for ATCs is λ-wise Level-combination Coverage based Prioritization (λLCP), a static, black-box prioritization technique that only uses the ATC information to guide the prioritization process. A challenge facing λLCP, however, is the necessity for the selection of the fixed prioritization strength λ before testing-testers need to choose an appropriate λ value before testing begins. Choosing higher λ values may improve the testing effectiveness of λLCP (e.g., by finding faults faster), but may reduce the testing efficiency (by incurring additional prioritization costs). Conversely, choosing lower λ values may improve the efficiency, but may also reduce the effectiveness. In this paper, we propose a new family of λLCP techniques, Repeated Small-strength Level-combination Coverage-based Prioritization (RSLCP), that repeatedly achieves the full combination coverage at lower strengths. RSLCP maintains λLCP's advantages of being static and black box, but avoids the challenge of prioritization strength selection. We have performed an empirical study involving five different versions of each of five C programs. Compared with λLCP, and Incremental-strength LCP (ILCP), our results show that RSLCP could provide a good tradeoff between testing effectiveness and efficiency. Our results also show that RSLCP is more effective and efficient than two popular techniques of Similarity-based Prioritization (SP). In addition, the results of empirical studies also show that RSLCP can remain robust over multiple system releases.

A geographic information system (GIS) provides basic location-enabled services for many different applications related to navigation, education, and telecommunications. It is a foundation for analysis and visualization. Testing GIS is critical, but challenging due to the difficulty to assess the correctness of GIS outputs, which is called the test oracle problem of software testing. Metamorphic testing alleviates the problem by constructing metamorphic relations (MRs) among multiple inputs and outputs of the program under test. In this article, a semiautomated metamorphic testing (SAMT) method, based on the formal MR model and an improved adaptive random testing algorithm, was proposed to the GIS. To evaluate the performance of our approach, we conducted a case study on a superficial area calculation program, a typical component of GIS. Six kinds of MR construction methods were suggested for the GIS domain program testing. The experimental results show that SAMT can detect the mutations effectively that could solve the test oracle problem efficiently. More importantly, there is no need to manual participation in the testing process, except for the MR construction.

Unsupervised machine learning is the training of an artificial intelligence system using information that is neither classified nor labeled, with a view to modeling the underlying structure or distribution in a dataset. Since unsupervised machine learning systems are widely used in many real-world applications, assessing the appropriateness of these systems and validating their implementations with respect to individual users' requirements and specific application scenarios/contexts are indisputably two important tasks. Such assessments and validation tasks, however, are fairly challenging due to the absence of a priori knowledge of the data. In view of this challenge, in this article, we develop a METamorphic Testing approach to assessing and validating unsupervised machine LEarning systems, abbreviated as mettle. Our approach provides a new way to unveil the (possibly latent) characteristics of various machine learning systems, by explicitly considering the specific expectations and requirements of these systems from individual users' perspectives. To support mettle, we have further formulated 11 generic metamorphic relations (MRs), covering users' generally expected characteristics that should be possessed by machine learning systems. We have performed an experiment and a user evaluation study to evaluate the viability and effectiveness of mettle. Our experiment and user evaluation study have shown that, guided by user-defined MR-based adequacy criteria, end users are able to assess, validate, and select appropriate clustering systems in accordance with their own specific needs. Our investigation has also yielded insightful understanding and interpretation of the behavior of the machine learning systems from an end-user software engineering's perspective, rather than a designer's or implementor's perspective, who normally adopts a theoretical approach.

Modern information technology paradigms, such as online services and off-the-shelf products, often involve a wide variety of users with different or even conflicting objectives. Every software output may satisfy some users, but may also fail to satisfy others. Furthermore, users often do not know the internal working mechanisms of the systems. This situation is quite different from bespoke software, where developers and users typically know each other. This paper proposes an approach to help users to better understand the software that they use, and thereby more easily achieve their objectives-even when they do not fully understand how the system is implemented. Our approach borrows the concept of metamorphic relations from the field of metamorphic testing (MT), using it in an innovative way that extends beyond MT. We also propose a “symmetry” metamorphic relation pattern and a “change direction” metamorphic relation input pattern that can be used to derive multiple concrete metamorphic relations. Empirical studies reveal previously unknown failures in some of the most popular applications in the world, and show how our approach can help users to better understand and better use the systems. The empirical results provide strong evidence of the simplicity, applicability, and effectiveness of our methodology.

This document is an extended abstract of an IEEE Software paper, "Metamorphic Testing: Testing the Untestable," presented as a J1C2 (Journal publication first, Conference presentation following) at the IEEE Computer Society signature conference on Computers, Software and Applications (COMPSAC 2019), hosted by Marquette University, Milwaukee, Wisconsin, USA.

Test‐case prioritisation (TCP) attempts to schedule the order of test‐case execution such that faults can be detected as quickly as possible. TCP has been widely applied in many testing scenarios such as regression testing and fault localisation. Abstract test cases (ATCs) are derived from models of the system under test and have been applied to many testing environments such as model‐based testing and combinatorial interaction testing. Although various empirical and analytical comparisons for some ATC prioritisation (ATCP) techniques have been conducted, to the best of the authors’ knowledge, no comparative study focusing on the most current techniques has yet been reported. In this study, they investigated 18 ATCP techniques, categorised into four classes. They conducted a comprehensive empirical study to compare 16 of the 18 ATCP techniques in terms of their testing effectiveness and efficiency. They found that different ATCP techniques could be cost‐effective in different testing scenarios, allowing us to present recommendations and guidelines for which techniques to use under what conditions.

Random testing and partition testing are two major families of software testing techniques. They have been compared both theoretically and empirically in numerous studies for decades, and it has been widely acknowledged that they have their own advantages and disadvantages and that their innate characteristics are fairly complementary to each other. Some work has been conducted to develop advanced testing techniques through the integration of random testing and partition testing, attempting to preserve the advantages of both while minimizing their disadvantages. In this paper, we propose a new testing approach, adaptive partition testing, where test cases are randomly selected from some partition whose probability of being selected is adaptively adjusted along the testing process. We particularly develop two algorithms, Markov-chain based adaptive partition testing and reward-punishment based adaptive partition testing, to implement the proposed approach. The former algorithm makes use of Markov matrix to dynamically adjust the probability of a partition to be selected for conducting tests; while the latter is based on a reward and punishment mechanism. We conduct empirical studies to evaluate the performance of the proposed algorithms using ten faulty versions of three large-scale open source programs. Our experimental results show that, compared with two baseline techniques, namely random partition testing (RPT) and dynamic random testing (DRT), our algorithms deliver higher fault-detection effectiveness with lower test case selection overhead. It is demonstrated that the proposed adaptive partition testing is an effective testing approach, taking advantages of both random testing and partition testing.

Adaptive random testing (ART) was developed as an enhanced version of random testing to increase the effectiveness of detecting failures in programs by spreading the test cases evenly over the input space. However, heavy computation may be incurred. In this paper, three enhanced algorithms for fixed-size-candidate-set ART (FSCS-ART) are proposed based on the k-dimensional tree (KD-tree) structure. The first algorithm Naive-KDFC constructs a KD-tree by splitting the input space with respect to every dimension successively in a round-robin fashion. The second algorithm SemiBal-KDFC improves the balance of the KD-tree by prioritizing the splitting according to the spread in each dimension. In order to control the number of traversed nodes in backtracking, the third algorithm LimBal-KDFC introduces an upper bound for the nodes involved. Simulation and empirical studies have been conducted to investigate the efficiency and effectiveness of the three algorithms. The experimental results show that these algorithms significantly reduce the computation time of the original FSCS-ART for low dimensions and for the case of high dimensions with low failure rates. The efficiency of SemiBal-KDFC is better than that of Naive-KDFC when the dimension is no more than 8, but LimBal-KDFC is the most efficient of all three. Although the limited backtracking leads only to an approximate nearest neighbor in LimBal-KDFC, its failure-detection effectiveness is, in fact, better than FSCS-ART in high-dimensional input spaces and has no significant deterioration in low-dimensional spaces.

Abstract test cases are derived by modeling the system under test, and have been widely applied in practice, such as for software product line testing and combinatorial testing. Abstract test case prioritization (ATCP) is used to prioritize abstract test cases and aims at achieving higher rates of fault detection. Many ATCP algorithms have been proposed, using different prioritization criteria and information. One ATCP approach makes use of fixed-strength level-combinations information covered by abstract test cases, and is called fixed-strength interaction coverage based prioritization (FICBP). Before using FICBP, the prioritization strength λ needs to be decided. Previous studies have generally focused on λ values ranging between 1 and 6. However, no study has investigated the appropriateness of such a range, nor how to assign the prioritization strength for FICBP. To answer these questions, this paper reports on an empirical study involving four real-life programs (each of which with six versions). The experimental results indicate that λ should be set approximately equal to a value corresponding to half of the number of parameters, when testing resources are sufficient. Our results also show that when testing resources are limited or insufficient, either small or large λ values are suggested for FICBP.

As part of a software testing process, output verification poses a challenge when the output is not numeric or textual, such as graphical. The industry practice of using human oracles (testers) to observe and verify the correctness of the actual results is both expensive and error-prone. In particular, this practice is usually unsustainable when developing web applications — the most popular software of our era. This is because web applications change frequently due to the fast-evolving requirements amid popular demand. To improve the cost effectiveness of browser output verification, in this study we design failure-based testing techniques and evaluate the effectiveness and efficiency thereof in the context of web testing. With a novel application of the concept of adaptive random sequence (ARS), our approach leverages peculiar characteristics of failure patterns found in browser layout rendering. An empirical study shows that the use of failure patterns and inclination to guide the testing flow leads to more cost-effective results than other classic methods. This study extends the application of ARSs from the input space of programs to their output space, and also shows that adaptive random testing (ART) can outperform random testing (RT) in both failure detection effectiveness (in terms of F-measure) and failure detection efficiency (in terms of execution time).

Nowadays, service oriented architecture (SOA) has become one mainstream paradigm for developing distributed applications. As the basic unit in SOA, web services can be composed to construct complex applications. The quality of web services and their compositions is critical to the success of SOA applications. Testing, as a major quality assurance technique, is confronted with new challenges in the context of service compositions. In this paper, we propose a scenario-oriented testing approach that can automatically generate test cases for service compositions. Our approach is particularly focused on the service compositions specified by Business Process Execution Language for web services (WS-BPEL), a widely recognized executable service composition language. In the approach, a WS-BPEL service composition is first abstracted into a graph model; test scenarios are then derived from the model; finally, test cases are generated according to different scenarios. We also developed a prototype tool implementing the proposed approach, and an empirical study was conducted to demonstrate the applicability and effectiveness of our approach. The experimental results show that the automatic scenario-oriented testing approach is effective in detecting many types of faults seeded in the service compositions.

We report on the application of Genetic Programming to Software Fault Localisation, a problem in the area of Search-Based Software Engineering (SBSE). We give both empirical and theoretical evidence for the human competitiveness of the evolved fault localisation formulæ under the single fault scenario, compared to those generated by human ingenuity and reported in many papers, published over more than a decade. Though there have been previous human competitive results claimed for SBSE problems, this is the first time that evolved solutions have been formally proved to be human competitive. We further prove that no future human investigation could outperform the evolved solutions. We complement these proofs with an empirical analysis of both human and evolved solutions, which indicates that the evolved solutions are not only theoretically human competitive, but also convey similar practical benefits to human-evolved counterparts.

Random testing (RT) has been identified as one of the most popular testing techniques, due to its simplicity and ease of automation. Adaptive random testing (ART) has been proposed as an enhancement to RT, improving its fault-detection effectiveness by evenly spreading random test inputs across the input domain. To achieve the even spreading, ART makes use of distance measurements between consecutive inputs. However, due to the nature of object-oriented software (OOS), its distance measurement can be particularly challenging: Each input may involve multiple classes, and interaction of objects through method invocations. Two previous studies have reported on how to test OOS at a single-class level using ART. In this study, we propose a new similarity metric to enable multiclass level testing using ART. When generating test inputs (for multiple classes, a series of objects, and a sequence of method invocations), we use the similarity metric to calculate the distance between two series of objects, and between two sequences of method invocations. We integrate this metric with ART and apply it to a set of open-source OO programs, with the empirical results showing that our approach outperforms other RT and ART approaches in OOS testing.

Test case prioritization schedules test cases in a certain order aiming to improve the effectiveness of regression testing. Random sequence is a basic and simple prioritization technique, while Adaptive Random Sequence (ARS) makes use of extra information to improve the diversity of random sequence. Some researchers have proposed prioritization techniques using ARS with white-box information, such as code coverage information, or with black-box information, such as string distances of the input data. In this paper, we propose new black-box test case prioritization techniques using ARS, and the diversity of test cases is assessed by category-partition-based distance. Our experimental studies show that these new techniques deliver higher fault-detection effectiveness than random prioritization, especially in the case of smaller ratio of failed test cases. In addition, in the comparison of different distance metrics, techniques with category-partition-based distance generally deliver better fault-detection effectiveness and efficiency, meanwhile in the comparison of different ordering algorithms, our ARS-based ordering algorithms usually have comparable fault-detection effectiveness but much lower computation overhead, and thus are much more cost-effective.

Random testing (RT) has been widely used in the testing of various software and hardware systems. Adaptive random testing (ART) is a family of random testing techniques that aim to enhance the failure-detection effectiveness of RT by spreading random test cases evenly throughout the input domain. ART has been empirically shown to be effective on software with numeric inputs. However, there are two aspects of ART that need to be addressed to render its adoption more widespread-applicability to programs with nonnumeric inputs, and the high computation overhead of many ART algorithms. We present a linear-order ART algorithm for software with non-numeric inputs. The key requirement for using ART with non-numeric inputs is an appropriate “distance” measure. We use the concepts of categories and choices from category-partition testing to formulate such a measure. We investigate the failure-detection effectiveness of our technique by performing an empirical study on 14 object programs, using two standard metrics-F-measure and P-measure. Our ART algorithm statistically significantly outperforms RT on 10 of the 14 programs studied, and exhibits performance similar to RT on three of the four remaining programs. The selection overhead of our ART algorithm is close to that of RT.

Random testing is a fundamental testing technique that can be used to generate test cases for both hardware and software systems. Quasi-random testing was proposed as an enhancement to the cost-effectiveness of random testing: In addition to having similar computation overheads to random testing, it makes use of quasi-random sequences to generate low-discrepancy and low-dispersion test cases that help deliver high failure-detection effectiveness. Currently, few algorithms exist to generate quasi-random sequences, and these are mostly deterministic, rather than random. A previous study of quasi-random testing has examined two methods for randomizing quasi-random sequences to improve their applicability in testing. However, these randomization methods still have shortcomings-one method does not introduce much randomness to the test cases, while the other does not support incremental test case generation. In this paper, we present an innovative approach to incrementally randomizing quasi-random sequences. The test cases generated by this new approach show a high degree of randomness and evenness in distribution. We also conduct simulations and empirical studies to demonstrate the applicability and effectiveness of our approach in software testing.

Metamorphic testing is a testing technique that can be used to verify the functional correctness of software in the absence of an ideal oracle. This paper extends metamorphic testing into a user-oriented approach to software verification, validation, and quality assessment, and conducts large scale empirical studies with four major web search engines: Google, Bing, Chinese Bing, and Baidu. These search engines are very difficult to test and assess using conventional approaches owing to the lack of an objective and generally recognized oracle. The results are useful for both search engine developers and users, and demonstrate that our approach can effectively alleviate the oracle problem and challenges surrounding a lack of specifications when verifying, validating, and evaluating large and complex software systems.

It is still a challenge to select "good" test inputs for concurrent programs within limited testing resources. We present in this paper a test case diversity metric for multi-threaded programs, which evaluates a test input with its effect in exposing concurrent thread interactions. We then propose an input-driven active testing approach with two test input selection strategies based on our test case diversity metric. We implement our testing approach based on Maple, an interleaving coverage-driven active testing tool. The effectiveness and efficiency of our testing approach are compared closely with Maple, which on its own is supplied with random test inputs. Experimental results show that our testing approach can outperform the original active testing approach in the number of test inputs executed and the time usage for fulfilling the interleaving coverage criterion of Maple. The selected test inputs based on our test case diversity metric are very cost-effective in exposing concurrent thread interactions and hence can help detect concurrency bugs with less cost and effort.

Fault Localization Prioritization (FLP) aims at reordering existing test cases so that the location of detected faulty components can be identified earlier, using certain fault localization techniques. Although some researchers have proposed adaptive prioritization strategies with white-box code coverage information, such information may not always be available. In this paper, we address the FLP problem using black-box information derived from partitioning the input domain. Based on the well-known technique of Spectra-Based Fault Localization (SBFL), three test case prioritization strategies are designed following some basic SBFL heuristics. The implementation of these proposed strategies relies only on the partition information, and does not require any test case execution history. Experiments show that our strategies, when compared with pure random selection, result in a faster localization of faulty statements, reducing the number of test case executions required. Here, we analyze the characteristics and merits of the three proposed strategies.

A major test case generation approach is to divide the input domain into disjoint partitions, from which test cases can be selected. However, we observe that in some traditional approaches to partition testing, the same partition may be associated with different output scenarios. Such an observation implies that the partitioning of the input domain may not be precise enough for effective software fault detection. To solve this problem, partition testing should be fine-tuned to additionally use the information of output scenarios in test case generation, such that these test cases are more fine-grained not only with respect to the input partitions but also from the perspective of output scenarios.

Despite a significant increase in security of modern information systems, cyber attacks have become more sophisticated as attackers combine multiple vulnerabilities to penetrate networks resulting in devastating consequences. In the past, attack graphs had been important tools for analyzing and understanding how various vulnerabilities could be combined through many potential interactions and connections between network components to compromise security. Full attack graphs for a realistic network, however, can be very large and complex, making it difficult to analyze and to decide what changes should be made in the network to make it sufficiently secure. We propose in this paper a novel approach to analyze network vulnerability and to identify all the combinations of exploits that are critical to the overall security of a network. Unlike previous graph-based algorithms that generate attack trees (or graphs) to cover all possible sequences of vulnerabilities, our method directly analyzes and eliminates less critical vulnerabilities without building the actual attack graph. The proposed approach relies on a unique evaluation of a vulnerability metric defined in this paper and its effectiveness is demonstrated through an example of a network that provides voice over IP services.

In software testing, something which can verify the correctness of test case execution results is called an oracle. The oracle problem occurs when either an oracle does not exist, or exists but is too expensive to be used. Metamorphic testing is a testing approach which uses metamorphic relations, properties of the software under test represented in the form of relations among inputs and outputs of multiple executions, to help verify the correctness of a program. This paper presents new empirical evidence to support this approach, which has been used to alleviate the oracle problem in various applications and to enhance several software analysis and testing techniques. It has been observed that identification of a sufficient number of appropriate metamorphic relations for testing, even by inexperienced testers, was possible with a very small amount of training. Furthermore, the cost-effectiveness of the approach could be enhanced through the use of more diverse metamorphic relations. The empirical studies presented in this paper clearly show that a small number of diverse metamorphic relations, even those identified in an ad hoc manner, had a similar fault-detection capability to a test oracle, and could thus effectively help alleviate the oracle problem.

Random testing (RT) and subdomain testing are two major software testing strategies. Their simplicity makes them likely the most efficient testing strategies with respect to the time required for test case selection. However, the disadvantage of RT is its defect detection effectiveness. Adaptive testing (AT) is a feedback-based software testing strategy that has been shown to be more effective than RT and partition testing (PT). However, a major concern in the application of AT is its complexity and computational cost for test case selection. In this paper, we propose a hybrid approach that uses AT and random partition testing (RPT) in an alternating manner. The motivation for this approach is that both strategies are employed such that the underlying computational complexity of AT is reduced by introducing RPT into the testing process without affecting the defect detection effectiveness. A case study with seven real-life subject programs is presented. The experimental results demonstrate that this novel strategy considerably reduces the computational overhead of the original AT strategy but still outperforms the pure RT strategy and PT strategy in terms of the number of test cases used to detect and remove a given number of defects. In addition, a sensitivity analysis is conducted to validate the robustness of our strategy.

Combinatorial interaction testing is a well-recognized testing method, and has been widely applied in practice, often with the assumption that all test cases in a combinatorial test suite have the same fault detection capability. However, when testing resources are limited, an alternative assumption may be that some test cases are more likely to reveal failure, thus making the order of executing the test cases critical. To improve testing cost-effectiveness, prioritization of combinatorial test cases is employed. The most popular approach is based on interaction coverage, which prioritizes combinatorial test cases by repeatedly choosing an unexecuted test case that covers the largest number of uncovered parameter value combinations of a given strength (level of interaction among parameters). However, this approach suffers from some drawbacks. Based on previous observations that the majority of faults in practical systems can usually be triggered with parameter interactions of small strengths, we propose a new strategy of prioritizing combinatorial test cases by incrementally adjusting the strength values. Experimental results show that our method performs better than the random prioritization technique and the technique of prioritizing combinatorial test suites according to test case generation order, and has better performance than the interaction-coverage-based test prioritization technique in most cases.

An important research area of Spectrum-Based Fault Localization (SBFL) is the effectiveness of risk evaluation formulas. Most previous studies have adopted an empirical approach, which can hardly be considered as sufficiently comprehensive because of the huge number of combinations of various factors in SBFL. Though some studies aimed at overcoming the limitations of the empirical approach, none of them has provided a completely satisfactory solution. Therefore, we provide a theoretical investigation on the effectiveness of risk evaluation formulas. We define two types of relations between formulas, namely, equivalent and better. To identify the relations between formulas, we develop an innovative framework for the theoretical investigation. Our framework is based on the concept that the determinant for the effectiveness of a formula is the number of statements with risk values higher than the risk value of the faulty statement. We group all program statements into three disjoint sets with risk values higher than, equal to, and lower than the risk value of the faulty statement, respectively. For different formulas, the sizes of their sets are compared using the notion of subset. We use this framework to identify the maximal formulas which should be the only formulas to be used in SBFL.

Random testing is a basic software testing technique that can be used to assess the software reliability as well as to detect software failures. Adaptive random testing has been proposed to enhance the failure-detection capability of random testing. Previous studies have shown that adaptive random testing can use fewer test cases than random testing to detect the first software failure. In this paper, we evaluate and compare the performance of adaptive random testing and random testing from another perspective, that of code coverage. As shown in various investigations, a higher code coverage not only brings a higher failure-detection capability, but also improves the effectiveness of software reliability estimation. We conduct a series of experiments based on two categories of code coverage criteria: structure-based coverage, and fault-based coverage. Adaptive random testing can achieve higher code coverage than random testing with the same number of test cases. Our experimental results imply that, in addition to having a better failure-detection capability than random testing, adaptive random testing also delivers a higher effectiveness in assessing software reliability, and a higher confidence in the reliability of the software under test even when no failure is detected.

Random testing (RT), a fundamental software testing technique, has been widely used in practice. Adaptive random testing (ART), an enhancement of RT, performs better than original RT in terms of fault detection capability. However, not much work has been done on effectiveness analysis of ART in the combinatorial test spaces. In this paper, we propose a novel family of ART-based algorithms for generating combinatorial test suites, mainly based on fixed-size-candidate-set ART and restricted random testing (that is, ART by exclusion). We use an empirical approach to compare the effectiveness of test sets obtained by our proposed methods and random selection strategy. Experimental data demonstrate that the ART-based tests cover all possible combinations at a given strength more quickly than randomly chosen tests, and often detect more failures earlier and with fewer test cases in simulations.

In recent years, Service Oriented Architecture (SOA) has been increasingly adopted to develop applications in the context of Internet. To develop reliable SOA-based applications, an important issue is how to ensure the quality of Web services. In this paper, we propose a dynamic random testing (DRT) technique for Web services which is an improvement of the widely practiced random testing. We examine key issues when adapting DRT to the context of SOA and develop a prototype for such an adaptation. Empirical studies are reported where DRT is used to test two real-life Web services and mutation analysis is employed to measure the effectiveness. The experimental results show that DRT can save up to 24% test cases in terms of detecting the first seeded fault, and up to 21% test cases in terms of detecting all seeded faults, both with the cases of uniformed mutation analysis and distribution-aware mutation analysis, which refer to faults being seeded in an even or clustered way, respectively. The proposed DRT and the prototype provide an effective approach to testing Web Services.

SUMMARY Adaptive random testing is an enhancement of random testing. Previous studies on adaptive random testing assumed that once a failure is detected, testing is terminated and debugging is conducted immediately. It has been shown that adaptive random testing normally uses fewer test cases than random testing for detecting the first software failure. However, under many practical situations, testing should not be withheld after the detection of a failure. Thus, it is important to investigate the effectiveness with respect to the detection of multiple failures. In this paper, we compare adaptive random testing and random testing under various scenarios and examine whether adaptive random testing is still able to use fewer test cases than random testing to detect multiple software failures. Our study delivers some interesting results and highlights a number of promising research projects. Copyright © 2011 John Wiley & Sons, Ltd.

SUMMARY Search services are the main interface through which people discover information on the Internet. A fundamental challenge in testing search services is the lack of oracles. The sheer volume of data on the Internet prohibits testers from verifying the results. Furthermore, it is difficult to objectively assess the ranking quality because different assessors can have very different opinions on the relevance of a Web page to a query. This paper presents a novel method for automatically testing search services without the need of a human oracle. The experimental findings reveal that some commonly used search engines, including Google, Yahoo!, and Live Search, are not as reliable as what most users would expect. For example, they may fail to find pages that exist in their own repositories, or rank pages in a way that is logically inconsistent. Suggestions are made for search service providers to improve their service quality. Copyright © 2010 John Wiley & Sons, Ltd.

This paper extends the choce relation framework, abbreviated as choc'late, which assists software testers in the application of category/choice methods to testing. choc'late assumes that the tester is able to construct a single choice relation table from the entire specification; this table then forms the basis for test case generation using the associated algorithms. This assumption, however, may not hold true when the specification is complex and contains many specification components. For such a specification, the tester may construct a preliminary choice relation table from each specification component, and then consolidate all the preliminary tables into a final table to be processed by choc'late for test case generation. However, it is often difficult to merge these preliminary tables because such merging may give rise to inconsistencies among choice relations or overlaps among choices. To alleviate this problem, we introduce a DividE-and-conquer methodology for identifying categorieS, choiceS, and choicE Relations for Test case generation, abbreviated as dessert. The theoretical framework and the associated algorithms are discussed. To demonstrate the viability and effectiveness of our methodology, we describe case studies using the specifications of three real-life commercial software systems.

In random testing, the distribution of the generated test cases is known as the test profile. We consider the effects of different test profiles, taking advantage of probabilistic information about likely failure-revealing inputs, on the effectiveness of random testing for debugging. We examine a failure-proportional testing strategy, in which tests are randomly sampled with replacement, with probability proportional to a previously identified failure probability distribution, compared to a uniform testing strategy, in which tests are randomly sampled uniformly from the entire input domain. We show that neither strategy optimises failure-detection capabilities, and show an alternative strategy that does. We also consider selection without replacement, and examine the robustness of some strategies given a divergence between the estimated and actual failure probability distributions.

Service Oriented Architecture (SOA) has become a major application development paradigm. As a basic unit of SOA applications, Web services significantly affect the quality of the applications constructed from them. Since the development and consumption of Web services are completely separated under SOA environment, the consumers are normally provided with limited knowledge of the services and thus have little information about test oracles. The lack of source code and the restricted control of Web services limit the testability of Web services. To address the prominent oracle problem when testing Web services, we propose a metamorphic testing framework for Web services taking into account the unique features of SOA. We conduct a case study where the new metamorphic testing framework is employed to test a Web service that implements the electronic payment. The results of case study show the feasibility of the framework for web services, and also the efficiency of metamorphic testing. The work presented in the paper alleviates the test oracle problem when testing Web services under SOA.

In this paper, we present our experience of testing wireless embedded software. We used a wireless metering system in operation, and its software as a case study to demonstrate how a property-based testing technique, called metamorphic testing, can be used in detecting software failures of this wireless embedded system. Our study shows that a careful design of test environments and selection of system properties will enable us to trace back the cause of failures and help in fault diagnosis and debugging.

Metamorphic testing is a technique for the verification of software output without a complete testing oracle. Mathematical optimization, implemented in software, is a problem for which verification can often be challenging. In this paper, we apply metamorphic testing to one such optimization problem, the quadratic assignment problem (QAP). From simple observations of the properties of the QAP, we describe how to derive a number of metamorphic relations useful for verifying the correctness of a QAP solver. We then compare the effectiveness of these metamorphic relations, in "killing" mutant versions of an exact QAP solver, to a simulated oracle. We show that metamorphic testing can be as effective as the simulated oracle for killing mutants. We examine the relative effectiveness of different metamorphic relations, both singly and in combination, and conclude that combining metamorphic relations can be significantly more effective than using a single relation.

SUMMARY Random testing (RT), which simply selects test cases at random from the whole input domain, has been widely applied to test software and assess the software reliability. However, it is controversial whether RT is an effective method to detect software failures. Adaptive random testing (ART) is an enhancement of RT in terms of failure‐detection effectiveness. Its basic intuition is to evenly spread random test cases all over the input domain. There are various notions to achieve the goal of even spread, and each notion can be implemented by different algorithms. For example, ‘by exclusion’ and ‘by partitioning’ are two different notions to evenly spread test cases. Restricted random testing (RRT) is a typical algorithm for the notion of ‘by exclusion’, whereas the notion of ‘by partitioning’ can be implemented by either the technique of bisection (ART‐B) or the technique of random partitioning (ART‐RP). In this paper, we propose a generic approach that can be used to implement different notions. In the new approach, test cases are simply selected based on test profiles that are in turn designed according to certain notions. In this study, we design several test profiles for the notions of ‘by exclusion’ and ‘by partitioning’, and then use these profiles to illustrate our new approach. Our experimental results show that compared with the original RRT, ART‐B, and ART‐RP algorithms, our new approach normally brings at least a higher failure‐detection capability or a lower computational overhead. Copyright © 2011 John Wiley & Sons, Ltd.

Recently, Kapoor and Bowen [2007] have extended the works by Kuhn [1999], Tsuchiya and Kikuno [2002], and Lau and Yu [2005]. However, their proofs overlook the possibility that a mutant of the Boolean specifications under test may be equivalent. Hence, each of their fault relationships is either incorrect or has an incorrect proof. In this article, we give counterexamples to the incorrect fault relationships and provide new proofs for the valid fault relationships. Furthermore, a co-stronger fault relation is introduced to establish a new fault class hierarchy for general Boolean specifications.

We present an integrated method for program proving, testing, and debugging. Using the concept of metamorphic relations, we select necessary properties for target programs. For programs where global symbolic evaluation can be conducted and the constraint expressions involved can be solved, we can either prove that these necessary conditions for program correctness are satisfied or identify all inputs that violate the conditions. For other programs, our method can be converted into a symbolic-testing approach. Our method extrapolates from the correctness of a program for tested inputs to the correctness of the program for related untested inputs. The method supports automatic debugging through the identification of constraint expressions that reveal failures.

One important focus of software engineering is how to develop quality software. Software testing is the main approach to the software quality assurance. Nowadays, more and more end-users write the program on their own but lack formal trainings on how to test their programs, and hence cannot guarantee the quality of their own software. Metamorphic testing is a simple, automatable, and cost-effective testing methodology. It is particularly suitable for end-users to test their own programs, because it does not demand the user to have great knowledge of software testing but knowledge of the program under development. In this paper, we report our experience in teaching metamorphic testing to various groups of students at Swinburne University of Technology, Melbourne, Australia. Our work not only enhances the teaching of software testing, but also fosters the training of end-user programmers.

Queuing network modelling is a modelling technique for capacity planning studies of computer and communication systems. Due to complexity of the technique, it is very difficult to know from the computed outputs whether the computation of the modelling software is correct. It is necessary to have an effective testing technique to address this problem. Recently, it has been noticed that metamorphic testing is an effective technique for this kind of problem. In this paper, we study the technique of metamorphic testing in testing queuing network modelling through a set of testing experiments in the Java Modelling Tool – a popular open source queuing network modelling suite.

BACKGROUND: Recent advances in experimental and computational technologies have fueled the development of many sophisticated bioinformatics programs. The correctness of such programs is crucial as incorrectly computed results may lead to wrong biological conclusion or misguided downstream experimentation. Common software testing procedures involve executing the target program with a set of test inputs and then verifying the correctness of the test outputs. However, due to the complexity of many bioinformatics programs, it is often difficult to verify the correctness of the test outputs. Therefore our ability to perform systematic software testing is greatly hindered. RESULTS: We propose to use a novel software testing technique, metamorphic testing (MT), to test a range of bioinformatics programs. Instead of requiring a mechanism to verify whether an individual test output is correct, the MT technique verifies whether a pair of test outputs conform to a set of domain specific properties, called metamorphic relations (MRs), thus greatly increases the number and variety of test cases that can be applied. To demonstrate how MT is used in practice, we applied MT to test two open-source bioinformatics programs, namely GNLab and SeqMap. In particular we show that MT is simple to implement, and is effective in detecting faults in a real-life program and some artificially fault-seeded programs. Further, we discuss how MT can be applied to test programs from various domains of bioinformatics. CONCLUSION: This paper describes the application of a simple, effective and automated technique to systematically test a range of bioinformatics programs. We show how MT can be implemented in practice through two real-life case studies. Since many bioinformatics programs, particularly those for large scale simulation and data analysis, are hard to test systematically, their developers may benefit from using MT as part of the testing strategy. Therefore our work represents a significant step towards software reliability in bioinformatics.

Random testing techniques have been extensively used in reliability assessment, as well as in debug testing. When used to assess software reliability, random testing selects test cases based on an operational profile; while in the context of debug testing, random testing often uses a uniform distribution. However, generally neither an operational profile nor a uniform distribution is chosen from the perspective of maximizing the effectiveness of failure detection. Adaptive random testing has been proposed to enhance the failure detection capability of random testing by evenly spreading test cases over the whole input domain. In this paper, we propose a new test profile, which is different from both the uniform distribution, and operational profiles. The aim of the new test profile is to maximize the effectiveness of failure detection. We integrate this new test profile with some existing adaptive random testing algorithms, and develop a family of new random testing algorithms. These new algorithms not only distribute test cases more evenly, but also have better failure detection capabilities than the corresponding original adaptive random testing algorithms. As a consequence, they perform better than the pure random testing.

We propose in this paper a novel approach to analyze network vulnerability and to obtain a quantitative value representing the level of security achieved in an arbitrary network. Unlike previous graph-based algorithms that generate attack trees (or graphs) to cover all possible sequences of vulnerabilities and therefore are not scalable, our method utilizes the attack graph’s principles, but directly analyzes and produces the desired security measure for a network without building the actual attack graph. The proposed approach relies on a unique evaluation of vulnerability metric defined in this paper and is demonstrated through an example of a network that provides voice over IP services.

Software cybernetics is an emerging area that explores the interplay between software and control. The controlled Markov chain (CMC) approach to software testing supports the idea of software cybernetics by treating software testing as a control problem, where the software under test serves as a controlled object modeled by a controlled Markov chain and the software testing strategy serves as the corresponding controller. The software under test and the corresponding software testing strategy form a closed-loop feedback control system. The theory of controlled Markov chains is used to design and optimize the testing strategy in accordance with the testing/reliability goal given explicitly and a priori. Adaptive software testing adjusts and improves software testing strategy online by using the testing data collected in the course of software testing. In doing so, the online parameter estimations play a key role. In this paper, we study the effects of genetic algorithm and the gradient method for doing online parameter estimation in adaptive software testing. We find that genetic algorithm is effective and does not require prior knowledge of the software parameters of concern. Although genetic algorithm is computationally intensive, it leads the adaptive software testing strategy to an optimal software testing strategy that is determined by optimizing a given testing goal, such as minimizing the total cost incurred for removing a given number of defects. On the other hand, the gradient method is computationally favorable, but requires appropriate initial values of the software parameters of concern. It may lead, or fail to lead, the adaptive software testing strategy to an optimal software testing strategy, depending on whether the given initial parameter values are appropriate or not. In general, the genetic algorithm should be used instead of the gradient method in adaptive software testing. Simulation results show that adaptive software testing does work and outperforms random testing.

Failure patterns describe typical ways in which inputs revealing program failure are distributed across the input domain—in many cases, clustered together in contiguous regions. Based on these observations several debug testing methods have been developed. We examine the upper bound of debug testing effectiveness improvements possible through making assumptions about the shape, size and orientation of failure patterns. We consider the bounds for testing strategies with respect to minimizing the F-measure, maximizing the P-measure, and maximizing the E-measure. Surprisingly, we find that the empirically measured effectiveness of some existing methods that are not based on these assumptions is close to the theoretical upper bound of these strategies. The assumptions made to obtain the upper bound, and its further implications, are also examined.

Recently, adaptive random testing (ART) has been developed to enhance the fault-detection effectiveness of random testing (RT). It has been known in general that the fault-detection effectiveness of ART depends on the distribution of failure-causing inputs, yet this understanding is in coarse terms without precise details. In this paper, we conduct an in-depth investigation into the factors related to the distribution of failure-causing inputs that have an impact on the fault-detection effectiveness of ART. This paper gives a comprehensive analysis of the favourable conditions for ART. Our study contributes to the knowledge of ART and provides useful information for testers to decide when it is more cost-effective to use ART.

Our paper proposes an implementable procedure for using the method of quasi-random sequences in software debug testing. In random testing, the sequence of tests (if considered as points in an -dimensional unit hypercube) will give rise to regions where there are clusters of points, as well as underpopulated regions. Quasi-random sequences, also known as low-discrepancy or low-dispersion sequences, are sequences of points in such a hypercube that are spread more evenly throughout. Based on the observation that program faults tend to lead to contiguous failure regions within a program's input domain, and that an even spread of random tests enhances the failure detection effectiveness for certain failure patterns, we examine the use of quasi-random sequences as a replacement for random sequences in automated testing. Because there are only a small number of quasi-random sequence generation algorithms, and each of them can only generate a small number of distinct sequences, the applicability of quasi-random sequences in testing real programs is severely restricted. To alleviate this problem, we examine the use of two types of randomized quasi-random sequences, which are quasi-random sequences permuted in a nondeterministic fashion in such a way as to retain their low discrepancy properties. We show that testing using randomized quasi-random sequences is often significantly more effective than random testing.

Adaptive random testing (ART) methods are software testing methods which are based on random testing, but which use additional mechanisms to ensure more even and widespread distributions of test cases over an input domain. Restricted random testing (RRT) is a version of ART which uses exclusion regions and restriction of test case generation to outside these regions. RRT has been found to perform very well, but incurs some additional computational cost in its restriction of the input domain. This paper presents a method of reducing overheads called forgetting, where the number of test cases used in the restriction algorithm can be limited, and thus the computational overheads reduced. The motivation for forgetting comes from its importance as a human strategy for learning. Several implementations are presented and examined using simulations. The results are very encouraging

During the testing of context-sensitive middleware-based software, the middleware checks the current situation to invoke the appropriate functions of the applications. Since the middleware remains active and the situation may continue to evolve, however, the conclusion of some test cases may not easily be identified. Moreover, failures appearing in one situation may be superseded by subsequent correct outcomes and, therefore, be hidden. We alleviate the above problems by making use of a special kind of situation, which we call checkpoints, such that the middleware will not activate the functions under test. We recommend testers to generate test cases that start at a checkpoint and end at another. Testers may identify relations that associate different execution sequences of a test case. They then check the results of each test case to detect any contravention of such relations. We illustrate our technique with an example that shows how hidden failures can be detected. We also report the experimentation carried out on an RFID-based location-sensing application on top of a context-sensitive middleware.

Restricted Random Testing (RRT) is a new method of testing software that improves upon traditional Random Testing (RT) techniques. Research has indicated that failure patterns (portions of an input domain which, when executed, cause the program to fail or reveal an error) can influence the effectiveness of testing strategies. For certain types of failure patterns, it has been found that a widespread and even distribution of test cases in the input domain can be significantly more effective at detecting failure compared with ordinary RT. Testing methods based on RT, but which aim to achieve even and widespread distributions, have been called Adaptive Random Testing (ART) strategies. One implementation of ART is RRT. RRT uses exclusion zones around executed, but non-failure-causing, test cases to restrict the regions of the input domain from which subsequent test cases may be drawn. In this paper, we introduce the motivation behind RRT, explain the algorithm and detail some empirical analyses carried out to examine the effectiveness of the method. Two versions of RRT are presented: Ordinary RRT (ORRT) and Normalized RRT (NRRT). The two versions share the same fundamental algorithm, but differ in their treatment of non-homogeneous input domains. Investigations into the use of alternative exclusion shapes are outlined, and a simple technique for reducing the computational overheads of RRT, prompted by the alternative exclusion shape investigations, is also explained. The performance of RRT is compared with RT and another ART method based on maximized minimum test case separation (DART), showing excellent improvement over RT and a very favorable comparison with DART.

Quasi-random sequences, also known as low-discrepancy or low-dispersion sequences, are sequences of points in an n-dimensional unit hypercube. These sequences have the property that points are spread more evenly throughout the cube than random point sequences, which result in regions where there are clusters of points and others that are sparsely populated. Based on the observation that program faults tend to lead to contiguous failure regions within a program's input domain, and that an even spread of random tests enhances the failure detection effectiveness for certain failure patterns, we examine the use of these sequences as a replacement for random sequences in automated testing.The limited number of quasi-random sequences available from the standard algorithms poses significant practical problems for use when testing real programs, and especially for evaluating its effectiveness. We examine the use of randomised quasi-random sequences, which are permuted in a nondeterministic fashion but still retain their low discrepancy properties, to overcome this problem, and show that testing using randomised quasi-random sequences is often significantly more effective than random testing.

Based on the intuition that widely spread test cases should have greater chance of hitting the nonpoint failure-causing regions, several adaptive random testing (ART) methods have recently been proposed to improve traditional random testing (RT). However, most of the ART methods require additional distance computations to ensure an even spread of test cases. In this paper, we introduce the concept of localization that can be integrated with some ART methods to reduce the distance computation overheads. By localization, test cases would be selected from part of the input domain instead of the whole input domain, and distance computation would be done for some instead of all previous test cases. Our empirical results show that the fault detecting capability of our method is comparable to those of other ART methods.

Temporal verification is an important method to check the temporal correctness of workflow management systems (WfMSs). However, the current temporal verification is relatively independent of the workflow system environments. It does not pay sufficient attention to the interrelationship between the temporal verification at different stages, the mutual dependency between some temporal constraints, and the run-time checkpoint selection strategy, which hence hinders the incorporation and consistency between the temporal verification and the workflow system environments. In this paper, we effectively integrate the temporal verification at different stages and explore the dependency between some temporal constraints. In addition, we present a new effective runtime checkpoint selection strategy which dynamically selects appropriate checkpoints based on the activity completion duration. Furthermore, based on these analyses, we develop some new methods for more efficient temporal verification. These analyses and new methods help to eliminate the gap between the temporal verification and the workflow system environments.

Adaptive random testing is a black box testing method based on the intuition that random testing failure-finding efficiency can be improved upon, in certain situations, by ensuring a more widespread and evenly distributed spread of test cases in the input domain. One way of achieving this distribution is through the use of exclusion zones and restriction, resulting in a method called restricted random testing (RRT). Recent investigations into the RRT method have revealed several interesting and significant insights. A method of reducing the computational overheads of testing methods by partitioning an input domain, and applying the method to only one of the subdomains, mapping the test cases to other subdomains, has recently been introduced. This method, called mirroring, in addition to alleviating computational costs, has some properties which fit nicely with the insights into RRT, offering solutions to some possible shortcomings of RRT. In this paper we discuss the RRT method and additional insights; we explain mirroring; and we detail applications of mirroring to RRT. The mirror RRT method proves to be a very attractive variation of RRT.

Context-sensitive middleware-based software is an emerging kind of ubiquitous computing application. The components of such software communicate proactively among themselves according to the situational attributes of their environments, known as the "contexts". The actual process of accessing and updating the contexts lies with the middleware. The latter invokes the relevant local and remote operations whenever any context inscribed in the situation-aware interface is satisfied. Since the applications operate in a highly dynamic environment, the testing of context-sensitive software is challenging. Metamorphic testing is a property-based testing strategy. It recommends that, even if a test case does not reveal any failure, follow-up test cases should be further constructed from the original to check whether the software satisfies some necessary conditions of the problem to be implemented. This work proposes to use isotropic properties of contexts as metamorphic relations for testing context-sensitive software. For instance, distinct points on the same isotropic curve of contexts would entail comparable responses by the components. This notion of testing context relations is novel, robust, and intuitive to users.

Software defect curves describe the behavior of the estimate of the number of remaining software defects as software testing proceeds. They are of two possible patterns: single-trapezoidal-like curves or multiple-trapezoidal-like curves. In this paper we present some necessary and/or sufficient conditions for software defect curves of the Goel-Okumoto NHPP model. These conditions can be used to predict the effect of the detection and removal of a software defect on the variations of the estimates of the number of remaining defects. A field software reliability dataset is used to justify the trapezoidal shape of software defect curves and our theoretical analyses. The results presented in this paper may provide useful feedback information for assessing software testing progress and have potentials in the emerging area of software cybernetics that explores the interplay between software and control.

We describe in this paper a choice relation framework for supporting category-partition test case generation. We capture the constraints among various values (or ranges of values) of the parameters and environment conditions identified from the specification, known formally as choices. We express these constraints in terms of relations among choices and combinations of choices, known formally as test frames. We propose a theoretical backbone and techniques for consistency checks and automatic deductions of relations. Based on the theory, algorithms have been developed for generating test frames from the relations. These test frames can then be used as the basis for generating test cases. Our algorithms take into consideration the resource constraints specified by software testers, thus maintaining the effectiveness of the test frames (and hence test cases) generated.

We study the effect of applying metamorphic testing to alleviate the oracle problem for numerical programs. We discuss a case study on the testing of a program that solves an elliptic partial differential equation with Dirichlet boundary conditions. We identify a metamorphic relation for the equation and demonstrate the effectiveness of metamorphic testing in identifying the error. The relation identified should also be applicable to other numerical methods that yield better approximations on the refinement of grid points or step sizes.

We present a semi-proving method for verifying necessary conditions for program correctness. Our approach is based on the integration of global symbolic evaluation and metamorphic testing. It is relatively easier than conventional program proving, and helps to alleviate the problem that software testing cannot show the absence of faults.

A partition testing strategy consists of two components: a partitioning scheme which determines the way in which the program's input domain is partitioned into subdomains; and an allocation of test cases which determines the exact number of test cases selected from each subdomain. This paper investigates the problem of determining the test allocation when a particular partitioning scheme has been chosen. We show that this problem can be formulated as a classic problem of decision-making under uncertainty, and analyze several well known criteria to resolve this kind of problem. We present algorithms that solve the test allocation problem based on these criteria, and evaluate these criteria by means of a simulation experiment. We also discuss the applicability and implications of applying these criteria in the context of partition testing.

Although testing is the most popular method for assuring software quality, there are two recognized limitations, known as the reliable test set problem and the oracle problem. Fault-based testing is an attempt by Morell to alleviate the reliable test set problem. In this paper, we propose to enhance fault-based testing to address the oracle problem as well. We present an integrated method that combines metamorphic testing with fault-based testing using real and symbolic inputs.

Various black-box methods for the generation of test cases have been proposed in the literature. Many of these methods, including the category-partition method and the classification-tree method, follow the approach of partition testing, in which the input domain is partitioned into subdomains according to important aspects of the specification, and test cases are then derived from the subdomains. Though comprehensive in terms of these important aspects, execution of all the test cases so generated may not be feasible under the constraint of tight testing resources. In such circumstances, there is a need to select a smaller subset of test cases from the original test suite for execution. In this paper, we propose the use of white-box information to guide the selection of test cases from the original test suite generated by a black-box testing method. Furthermore, we have developed some techniques and algorithms to facilitate the implementation of our approach, and demonstrated its viability and benefits by means of a case study.

Abstract This paper considers test case selection for programs whose specifications are expressed by Boolean algebra. The approach is to select test cases based on Boolean specifications. Three test case selection strategies are proposed that aim at the detection of theliteral insertion faultand theliteral reference fault. Although theMAX‐Bstrategy proposed by Weyukeret al.guarantees detection of these types of faults, the proposed strategies are more effective in the sense that the derived test cases form a subset of those selected by theMAX‐Bstrategy. Copyright © 2001 John Wiley & Sons, Ltd.

Object-oriented programming consists of several different levels of abstraction, namely, the algorithmic level, class level, cluster level, and system level. The testing of object-oriented software at the algorithmic and system levels is similar to conventional program testing. Testing at the class and cluster levels poses new challenges. Since methods and objects may interact with one another with unforeseen combinations and invocations, they are much more complex to simulate and test than the hierarchy of functional calls in conventional programs. In this paper, we propose a methodology for object-oriented software testing at the class and cluster levels. In class-level testing, it is essential to determine whether objects produced from the execution of implemented systems would preserve the properties defined by the specification, such as behavioral equivalence and nonequivalence. Our class-level testing methodology addresses both of these aspects. For the testing of behavioral equivalence, we propose to select fundamental pairs of equivalent ground terms as test cases using a black-box technique based on algebraic specifications, and then determine by means of a white-box technique whether the objects resulting from executing such test cases are observationally equivalent. To address the testing of behavioral nonequivalence, we have identified and analyzed several nontrivial problems in the current literature. We propose to classify term equivalence into four types, thereby setting up new concepts and deriving important properties. Based on these results, we propose an approach to deal with the problems in the generation of nonequivalent ground terms as test cases. Relatively little research has contributed to cluster-level testing. In this paper, we also discuss black-box testing at the cluster level. We illustrate the feasibility of using contract, a formal specification language for the behavioral dependencies and interactions among cooperating objects of different classes in a given cluster. We propose an approach to test the interactions among different classes using every individual message-passing rule in the given Contract specification. We also present an approach to examine the interactions among composite message-passing sequences. We have developed four testing tools to support our methodology.

This paper describes an integrated methodology for the construction of test cases from functional specifications using the classification-tree method. It is an integration of our extensions to the classification-hierarchy table, the classification tree construction algorithm, and the classification tree restructuring technique. Based on the methodology, a prototype system ADDICT, which stands for AutomateD test Data generation system using the Integrated Classification-Tree method, has been built.

The problem of test suite reduction is to find a subset of test cases from the test suite that can still satisfy the same testing objective. Such a subset is referred to as a representative set of the test suite. We use a problem reduction technique, namely the 1-to-1 redundancy dividing strategy, to find the optimal representative sets, which are the representative sets of the smallest size. The 1-to-1 redundancy dividing strategy guarantees that an optimal representative set of the reduced test suite is still an optimal representative set of the original one. However, the converse is not necessarily true. This paper investigates how to find all optimal representative sets of the original test suite from the reduced one. Furthermore, for the minimal representative sets whose proper subsets are not representative sets, the same problem is addressed.

To compare the performance of different testing strategies, P-measure and E-measure are two effectiveness measures used in previous analytical studies. P-measure, which is defined as the probability of detecting at least one failure, is a measure of how likely it is that failure-causing inputs are selected at least once as test cases. E-measure, which is defined as the expected number of failures detected, is a measure of how frequently failure-causing inputs are selected as test cases. However, we have no a priori knowledge of how many failure-causing inputs there are, or where they may lie. In this paper, we study P-measure and E-measure in terms of how much attention an arbitrary input receives. In the context of P-measure, the attention received by an arbitrary input is the probability that the input is selected at least once as a test case, while in the context of E-measure, the attention is the expected number of times that an input is selected as a test case. The attentions received by an input using the proportional sampling strategy and random testing are then compared. The attention received by an input is found to be the same under the two testing strategies for E-measure, whereas for P-measure the attention is always higher for the proportional sampling strategy than for random testing. This new perspective allows us to provide simpler proofs of some known results. Furthermore, we are able to show that the difference in the expected number of distinct test cases considered by the proportional sampling strategy is larger than that of random testing by at most 2k, where k is the number of partitions and is independent of the number of test cases selected.

Interaction diagrams are used in multi-agent systems to graphically describe agent computation threads and communications while fragmentations are the algebraic representations of interaction diagrams. The IDAF (Interaction Diagrams And Fragmentations) tool suite has been developed based on the formalism of interaction diagrams and fragmentations. The tool suite consists of ValidatoR, FormatteR, TranslatoR, GrapheR and TesteR. This paper describes the usage of the tool suite and demonstrates it in two different multi-agent systems.

Because of the growing importance of object-oriented programming, a number of testing strategies have been proposed. They are based either on pure black-box or white-box techniques. We propose in this article a methodology to integrate the black- and white-box techniques. The black-box technique is used to select test cases. The white-box technique is mainly applied to determine whether two objects resulting from the program execution of a test care are observationally equivalent. It is also used to select test cases in some situations. We define the concept of a fundamental pair as a pair of equivalent terms that are formed by replacing all the variables on both sides of an axiom by normal forms. We prove that an implementation is consistent with respect to all equivalent terms if and only if it is consistent with respect to all fundamental pairs. In other words, the testing coverage of fundamental pairs is as good as that of all possible term rewritings, and hence we need only concentrate on the testing of fundamental pairs. Our strategy is based on mathematical theorems. According to the strategy, we propose an algorithm for selecting a finite set of fundamental pairs as test cases. Given a pair of equivalent terms as a test case, we should then determine whether the objects that result from executing the implemented program are observationally equivalent. We prove, however, that the observational equivalence of objects cannot be determined using a finite set of observable contexts (which are operation sequences ending with an observer function) derived from any black-box technique. Hence we supplement our approach with a “relevant observable context” technique, which is a heuristic white-box technique to select a relevant finite subset of the set of observable contexts for determining the observational equivalence. The relevant observable contezxts are constructed from a data member relevance graph (DRG), which is an abstraction of the given implementation for a given specificatin. A semiautomatic tool hass been developed to support this technique.

A partition testing strategy consists of two components: a partitioning scheme which determines the way in which the program's input domain is partitioned into subdomains, and an allocation of test cases which determines the exact number of test cases selected from each subdomain. Whereas previous research studies have suggested many partitioning schemes, there have been few guidelines as to how the test allocations should be chosen, and in practice allocations are often done in an ad hoc manner. This paper investigates the problem of determining the test allocation when a particular partitioning scheme has been chosen. We show that this problem can be formulated as a classic problem of decision-making under uncertainty, and analyze the several most common criteria used to resolve this kind of problem. We also discuss the applicability and implications of applying these criteria in the context of partition testing.

Test data selection for software represented as Boolean formulae has not received much attention until the last decade. Most of the approaches are expression driven because generation of test cases is based on the Boolean formulae being tested. The paper discusses test data generation using a fault based approach in the sense that generation of test cases is based on particular types of faults occurring in the Boolean expression. Two special types of faults are considered. Moreover, two strategies of test case selection that guarantee the detection of these two types of faults are proposed.

The optimally refined proportional sampling strategy has been recommended as a better alternative to random testing, when dividing the input domain into equal-sized partitions is easy. This paper investigates some properties of the optimally refined proportional sampling strategy. This investigation provides some useful information on how well the optimally refined proportional sampling strategy outperforms random testing.

The classification-hierarchy table developed by Chen and Poon (1996) provides a systematic approach to construct classification trees from given sets of classifications and their associated classes. The paper enhances their study by defining a metric to measure the "quality" of a classification tree, and providing an algorithm to improve this quality.

Although previous studies have shown that partition testing strategies are not always very effective, with appropriate restrictions on the test allocation they can be guaranteed to be safe, in the sense that they will never be less reliable in detecting at least one failure than random testing. Several sufficient conditions for this have already been established in the literature. In particular, the proportional sampling strategy, which allocates test cases in proportion to the size of the subdomains from which they are selected, has been proved to be safe for all programs. In practice, since the number of test cases must be positive integers, often the proportional sampling strategy can only be approximated. This paper examines the necessary conditions for safe partition testing strategies. We also prove that, when the input domain is large enough with respect to the numbers of failure-causing inputs and test cases, a safe partition testing strategy cannot deviate from the proportional sampling strategy other than rounding due to integral constraints.

We investigate the efficacy of subdomain testing and random testing using the expected number of failures detected (the E-measure) as a measure of effectiveness. Simple as it is, the E-measure does provide a great deal of useful information about the fault detecting capability of testing strategies. With the E-measure, we obtain new characterizations of subdomain testing, including several new conditions that determine whether subdomain testing is more or less effective than random testing. Previously, the efficacy of subdomain testing strategies has been analyzed using the probability of detecting at least one failure (the P-measure) for the special case of disjoint subdomains only. On the contrary, our analysis makes use of the E-measure and considers also the general case in which subdomains may or may not overlap. Furthermore, we discover important relations between the two different measures. From these relations, we also derive corresponding characterizations of subdomain testing in terms of the P-measure.

Although data flow analysis has been successfully applied in testing programs written in procedural programming languages, its current form as not powerful enough to test object-oriented programs. The methodology of conventional data flow analysis should be extended to incorporate new techniques to test C++ programs. We propose how data flow analysis should be extended and demonstrate how it can be used to detect data flow anomalies.

Weyuker and Jeng (1991) have investigated the conditions that affect the performance of partition testing and have compared analytically the fault-detecting ability of partition testing and random testing. Chen and Yu (1994) have generalized some of Weyuker and Jeng's results. We extend the analysis to subdomain testing in which subdomains may overlap. We derive several results for a special case and demonstrate a technique to extend some of our results to more general cases. We believe that this technique should be very useful in further investigating the behaviour of subdomain testing.

Abstract In this paper, we investigate the feasibility of applying logic programming to structured design. We propose to use Prolog as a common machinery for the representation of various structured tools. We illustrate through examples how to produce structure charts from data flow diagrams, and evaluate them according to commonly recommended design guidelines. If the structure charts produced are not satisfactory, the inherent backtracking mechanism in Prolog will help to produce other versions for further evaluation.

Weyuker and Jeng (ibid., vol. SE-17, pp. 703-711, July 1991) have investigated the conditions that affect the performance of partition testing and have compared analytically the fault-detecting ability of partition testing and random testing. This paper extends and generalizes some of their results. We give more general ways of characterizing the worst case for partition testing, along with a precise characterization of when this worst case is as good as random testing. We also find that partition testing is guaranteed to perform at least as well as random testing so long as the number of test cases selected is in proportion to the size of the subdomains.>

Gallier1 generalised the notion of consistency in studying the sufficient conditions for the existence of optimal fixpoints. Chen2 introduced the notion of ⩽-relatedness in investigating some fixpoints for the class of non-deterministic recursive programs. In this paper, it is proved that the notions of ⩽-relatedness and consistency are equivalent for the class of multi-valued functions.

Abstract This paper presents a description of, and experience in using, AIDA, an automated instrumentation system to perform data flow analysis for Pascal programs. AIDA is capable of detecting not only data flow anomalies, but also certain kinds of errors. It is a useful software testing and development tool for Pascal programs. The associated implementation problems and their solutions are presented.