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).

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.

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.

Software behavior depends on many factors. Combinatorial testing (CT) aims to generate small sets of test cases to uncover defects caused by those factors and their interactions. Covering array generation, a discrete optimization problem, is the most popular research area in the field of CT. Particle swarm optimization (PSO), an evolutionary search-based heuristic technique, has succeeded in generating covering arrays that are competitive in size. However, current PSO methods for covering array generation simply round the particle's position to an integer to handle the discrete search space. Moreover, no guidelines are available to effectively set PSOs parameters for this problem. In this paper, we extend the set-based PSO, an existing discrete PSO (DPSO) method, to covering array generation. Two auxiliary strategies (particle reinitialization and additional evaluation of gbest) are proposed to improve performance, and thus a novel DPSO for covering array generation is developed. Guidelines for parameter settings both for conventional PSO (CPSO) and for DPSO are developed systematically here. Discrete extensions of four existing PSO variants are developed, in order to further investigate the effectiveness of DPSO for covering array generation. Experiments show that CPSO can produce better results using the guidelines for parameter settings, and that DPSO can generate smaller covering arrays than CPSO and other existing evolutionary algorithms. DPSO is a promising improvement on PSO for covering array generation.

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.

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.

Search techniques can dramatically change our ability to solve a host of problems in applied science and engineering, many search techniques have been developed and applied successfully in many fields, including search based software engineering (SBSE). As a key problem of combinatorial testing, covering array generation has been widely studied and many search techniques have been applied which can be named as search based combinatorial testing (SBCT). SBCT is a branch of search based software testing (SBST) within SBSE. In this paper, to explore the applicability and effectiveness of SBCT, we design six variants from existing search algorithms: Genetic Algorithm, Particle Swarm Optimization and Ant Colony Algorithm by reversing and randomizing their mechanisms. We study their effectiveness in terms of generating a covering array and compare their performance. Experiments show that these search techniques can work well with distinct performance in covering array generation. We believe that these search techniques can be further improved by fine-tuning their configuration and used in broad ranges of area.

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.

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.

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.

Editorial for the special issue of Software: Practice and Experience which consists of six papers that are extended from the best papers of the 10th International Conference on Quality Software (QSIC 2010), Zhangjiajie, China, 14-15 July 2010.

An early step for most black-box testing methods is to identify a set of categories and choices (or their equivalents) from the specification. The identification is often performed in an ad hoc manner, thus the quality of categories and choices is in doubt. Poorly identified categories and choices will affect the comprehensiveness of test cases. In this paper, we describe several comparative studies using three commercial specifications and discuss the major results. The objectives of our studies are (a) to investigate the differences in the types and amounts of mistakes made between inexperienced and experienced software testers in an ad hoc identification approach and (b) to determine the extent of mistake reduction after discussing the mistakes with the software testers and providing them with an identification checklist.

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.

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.

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.

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.