In programming languages that use multiple dispatch, a single function can have multiple implementations, each of which may specialise the function's operation. Which one of these implementations to execute is determined by the data types of all the arguments to the function. Effective testing of functions that use multiple dispatch therefore requires diverse test inputs in terms of the data types of the input's arguments as well as their values. In this paper we describe an approach for generating test inputs where both the values and types are chosen probabilistically. The approach uses reflection to automatically determine how to create inputs with the desired types, and dynamically updates the probability distribution from which types are sampled in order to improve both the test efficiency and efficacy. We evaluate the technique on 247 methods across 9 built-in functions of Julia, a technical computing language that applies multiple dispatch at runtime. In the process, we identify three real faults in these widely-used functions.

A common and natural intuition among software testers is that test cases need to differ if a software system is to be tested properly and its quality ensured. Consequently, much research has gone into formulating distance measures for how test cases, their inputs and/or their outputs differ. However, common to these proposals is that they are data type specific and/or calculate the diversity only between pairs of test inputs, traces or outputs. We propose a new metric to measure the diversity of sets of tests: the test set diameter (TSDm). It extends our earlier, pairwise test diversity metrics based on recent advances in information theory regarding the calculation of the normalized compression distance (NCD) for multisets. A key advantage is that TSDm is a universal measure of diversity and so can be applied to any test set regardless of data type of the test inputs (and, moreover, to other test-related data such as execution traces). But this universality comes at the cost of greater computational effort compared to competing approaches. Our experiments on four different systems show that the test set diameter can help select test sets with higher structural and fault coverage than random selection even when only applied to test inputs. This can enable early test design and selection, prior to even having a software system to test, and complement other types of test automation and analysis. We argue that this quantification of test set diversity creates a number of opportunities to better understand software quality and provides practical ways to increase it.

Although citation counts are often considered a measure of academic impact, they are criticized for failing to evaluate impact as intended. In this paper we propose that software engineering citations may be classified according to how the citation is used by the author of the citing paper, and that through this classification of citation behaviour it is possible to achieve a more refined understanding of the cited paper's impact. Our objective in this work is to conduct an initial evaluation using the citation behaviour taxonomy proposed by Bornmann and Daniel. We independently classified citations to ten highly-cited papers published at the International Symposium on Empirical Software Engineering and Measurement (ESEM). The degree to which classifications were consistent between researchers was analyzed in order to assess the clarity of Bornmann and Daniel's taxonomy. We found poor to fair agreement between researchers even though the taxonomy was perceived as relatively easy to apply for the majority of citations. We were nevertheless able to identify clear differences in the profile of citation behaviors between the cited papers. We conclude that an improved taxonomy is required if classification is to be reliable, and that a degree of automation would improve reliability as well as reduce the time taken to make a classification.

Monte-Carlo Tree Search algorithms have proven extremely effective at playing games that were once thought to be difficult for AI techniques owing to the very large number of possible game states. The key feature of these algorithms is that rather than exhaustively searching game states, the algorithm navigates the tree using information returned from a relatively small number of random game simulations. A practical limitation of software model checking is the very large number of states that a model can take. Motivated by an analogy between exploring game states and checking model states, we propose that Monte-Carlo Tree Search algorithms might also be applied in this domain to efficiently navigate the model state space with the objective of finding counterexamples which correspond to potential software faults. We describe such an approach based on Nested Monte-Carlo Search---a tree search algorithm applicable to single player games---and compare its efficiency to traditional heuristic search algorithms when using Java PathFinder to locate deadlocks in 12 Java programs.

Software engineering lacks underpinning scientific theories both for the software it produces and the processes by which it does so. We propose that an approach based on information theory can provide such a theory, or rather many theories. We envision that such a benefit will be realised primarily through research based on the quantification of information involved and a mathematical study of the limiting laws that arise. However, we also argue that less formal but more qualitative uses for information theory will be useful. The main argument in support of our vision is based on the fact that both a program and an engineering process to develop such a program are fundamentally processes that transform information. To illustrate our argument we focus on software testing and develop an initial theory in which a test suite is input/output adequate if it achieves the channel capacity of the program as measured by the mutual information between its inputs and its outputs. We outline a number of problems, metrics and concrete strategies for improving software engineering, based on information theoretical analyses. We find it likely that similar analyses and subsequent future research to detail them would be generally fruitful for software engineering.

The efficiency of random testing can be improved by sampling test inputs using a generating program that incorporates knowledge about the types of input most likely to detect faults in the software-under-test (SUT). But when the input of the SUT is a complex data type--such as a domain-specific string, array, record, tree, or graph--creating such a generator may be time- consuming and may require the tester to have substantial prior experience of the domain. In this paper we propose the re-use of generators created for one SUT on other SUTs that take the same complex data type as input. The re-use of a generator in this way would have little overhead, and we hypothesise that the re-used generator will typically be as least as efficient as the most straightforward form of random testing: sampling test inputs from the uniform distribution. We investigate this proposal for two data types using five generators. We assess test efficiency against seven real-world SUTs, and in terms of both structural coverage and the detection of seeded faults. The results support the re-use of generators for complex data types, and suggest that if a library of generators is to be maintained for this purpose, it is possible to extend library generators to accommodate the specific testing requirements of newly-encountered SUTs.

Software acting on complex data structures can be challenging to test: it is difficult to generate diverse test data that satisfies structural constraints while simultaneously exhibiting properties, such as a particular size, that the test engineer believes will be effective in detecting faults. In our previous work we introduced GödelTest, a framework for generating such data structures using non-deterministic programs, and combined it with Differential Evolution to optimize the generation process. Monte-Carlo Tree Search (MCTS) is a search technique that has shown great success in playing games that can be represented as a sequence of decisions. In this paper we apply Nested Monte-Carlo Search, a single-player variant of MCTS, to the sequence of decisions made by the generating programs used by GödelTest, and show that this combination can efficiently generate random data structures which exhibit the specific properties that the test engineer requires. We compare the results to Boltzmann sampling, an analytical approach to generating random combinatorial data structures.

Statistical testing is a probabilistic approach to test data generation that has been demonstrated to be very effective at revealing faults. Its premise is to compensate for the imperfect connection between coverage criteria and the faults to be revealed by exercising each coverage element several times with different random data. The cornerstone of the approach is the often complex task of determining a suitable input profile, and recent work has shown that automated metaheuristic search can be a practical method of synthesising such profiles. The starting point of this paper is the hypothesis that, for some software, the existing grammar-based representation used by the search algorithm fails to capture important relationships between input arguments and this can limit the fault-revealing power of the synthesised profiles. We provide evidence in support of this hypothesis, and propose a solution in which the user provides some basic contextual knowledge to guide the search. Empirical results for two case studies are promising: knowledge gained by a very straightforward review of the software-under-test is sufficient to dramatically increase the efficacy of the profiles synthesised by search.

The effectiveness of probabilistic structural testing depends on the characteristics of the probability distribution from which test inputs are sampled at random. Metaheuristic search has been shown to be a practical method of optimising the characteristics of such distributions. However, the applicability of the existing search-based algorithm is limited by the requirement that the software's inputs must be a fixed number of numeric values.

Probabilistic testing techniques that sample input data at random from a probability distribution can be more effective at detecting faults than deterministic techniques. However, if overly large (and therefore expensive) test sets are to be avoided, the probability distribution from which the input data is sampled must be optimised to the particular software-under-test. Such an optimisation process is often resource-intensive. In this paper, we present a prototypical cloud platform-and architecture-that permits the optimisation of such probability distributions in a scalable, distributed and robust manner, and thereby enables cost-effective probabilistic testing.

For software testing to be effective the test data should cover a large and diverse range of the possible input domain. Boltzmann samplers were recently introduced as a systematic method to randomly generate data with a range of sizes from combinatorial classes, and there are a number of automated testing frameworks that serve a similar purpose. However, size is only one of many possible properties that data generated for software testing should exhibit. For the testing of realistic software systems we also need to trade off between multiple different properties or search for specific instances of data that combine several properties. In this paper we propose a general search-based framework for finding test data with specific properties. In particular, we use a metaheuristic, differential evolution, to search for stochastic models for the data generator. Evaluation of the framework demonstrates that it is more general and flexible than existing solutions based on random sampling.

It is with great pleasure that we accepted the privilege of editing this special issue of Software: Practice and Experience on the practical aspects of Search-based Software Engineering.Software systems are becoming ever larger and more complex as new architectures emerge, high-performance hardware becomes increasingly affordable, and systems must satisfy often highly constrained operating requirements.However, many traditional approaches to software design and implementation are unable to scale to meet the challenges presented by such systems.For this reason, a recent trend has been to automate tasks within the software engineering life cycle using machine-based search; this approach is known as Search-based Software Engineering (SBSE).The engineering task is reformulated as an optimization problem and solutions are found using efficient modern optimization algorithms, such as meta-heuristic search and operational research methods.SBSE promises much greater scalability than traditional labour-intensive methods since human effort is redirected to guide the search for solutions to the engineering problem, rather than perform the search itself.SBSE has been applied across the spectrum of software engineering activities, including: requirements engineering, project planning, software task allocation, code refactoring, protocol synthesis, test data generation, and the design of algorithms for highly resource-constrained hardware platforms.As the efficacy and scalability of this approach is established for an increasing number of software engineering problems, an emerging research interest is how to successfully use SBSE in practice.It was this focus on the practical experience of applying SBSE that defined this special issue.Following the initial call for papers, we received 18 manuscripts of which 5 were eventually accepted for this special issue, and a further paper being accepted for a regular issue of the journal.The accepted papers provide an interesting balance between solving practical problems within software engineering-which would be very costly to solve, if it is possible at all, using traditional methods-and demonstrating how existing solutions can be applied to real problems.The first paper, 'Evolutionary Deployment Optimization for Service Oriented Clouds', deals with a classic multi-objective problem that is a variant of the task allocation problem.In this paper the problem of allocating services to the available resources is considered such that the performance, and hence Service Level Agreements (SLA), for the cloud-based system are met.To achieve this requires carefully balanced trade-offs to be made based on statistical analysis of how the system will perform.For this purpose a genetic algorithm is deployed which manages to solve the problems resulting in a number of Pareto-optimal solutions.The work is demonstrated through a mix of empirical methods and a case study applied to a loan validator system.The second paper, 'The use of Search-based Optimization Techniques to Schedule and Staff Software Projects: An Approach and an Empirical Study', considers a related problem of how to allocate jobs to staff working on a software engineering project.Both single objective and multi-objective formulations of the problem are considered, the latter attempting to minimize, for example, both completion time and schedule fragmentation.A variety of search algorithms are applied to solve both formulations and their efficacy evaluated.The solution to the multi-objective formulation is a set of schedules illustrating different trade-offs between the competing objectives from which a project manager can choose.The work is demonstrated on two large-scale commercial software projects.The third paper, 'Automated Scheduling for Clone-based Refactoring using a Competent GA', addresses the highly important issue of the order in which to refactor software.Refactoring is another term for modifying software and it is widely recognized that the order has direct

Statistical testing has been shown to be more efficient at detecting faults in software than other methods of dynamic testing such as random and structural testing. Test data are generated by sampling from a probability distribution chosen so that each element of the software's structure is exercised with a high probability. However, deriving a suitable distribution is difficult for all but the simplest of programs. This paper demonstrates that automated search is a practical method of finding near-optimal probability distributions for real-world programs, and that test sets generated from these distributions continue to show superior efficiency in detecting faults in the software.

The critical functionality of many software applications relies on code that performs mathematically complex computations. However, such code is often difficult to test owing to the compound datatypes used and complicated mathematical operations performed. This paper proposes the use of automated search as an efficient means of generating test data for this type of software. Taking Matlab as an example of widely-used mathematical software, a technical framework is described that extends previous work on search-based test data generation in order to handle matrix datatypes and associated relational operators. An empirical evaluation demonstrates the feasibility of this approach.

Non-functional properties of software, such as power consumption and memory usage, are important factors in designing software for resource-constrained platforms. This is an area where Search-Based Software Engineering has yet to be applied, and this paper investigates the potential of using Genetic Programming and Multi-Objective Optimisation as key tools in satisfying non-functional requirements. We outline the benefits of such an approach and give an example application of evolving pseudorandom number generators and performing power-functionality trade-offs.