Kaibo Liu, Zhenpeng Chen, Yiyang Liu, Jie M. Zhang, Mark Harman, Yudong Han, Yun Ma, Yihong Dong, Ge Li, Gang Huang. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

There has been a recent explosion of research on Large Language Models (LLMs) for software engineering tasks, in particular code generation. However, results from LLMs can be highly unstable; non-deterministically returning very different code for the same prompt. Such non-determinism affects the correctness and consistency of the generated code, undermines developers’ trust in LLMs, and yields low reproducibility in LLM-based papers. Nevertheless, there is no work investigating how serious this non-determinism threat is. To fill this gap, this article conducts an empirical study on the non-determinism of ChatGPT in code generation. We chose to study ChatGPT because it is already highly prevalent in the code generation research literature. We report results from a study of 829 code generation problems across three code generation benchmarks (i.e., CodeContests, APPS and HumanEval) with three aspects of code similarities: semantic similarity, syntactic similarity, and structural similarity. Our results reveal that ChatGPT exhibits a high degree of non-determinism under the default setting: the ratio of coding tasks with zero equal test output across different requests is 75.76%, 51.00% and 47.56% for three different code generation datasets (i.e., CodeContests, APPS and HumanEval), respectively. In addition, we find that setting the temperature to 0 does not guarantee determinism in code generation, although it indeed brings less non-determinism than the default configuration ( temperature \(=\) 1). In order to put LLM-based research on firmer scientific foundations, researchers need to take into account non-determinism in drawing their conclusions.

Assured Large Language Model Software Engineering (Assured LLMSE) addresses the twin challenges: 1. Ensuring LLM-generated code does not regress the properties of the original code 2. Quantifying the improvement over the original archived by the improve code in a verifiable and measurable way.

Existing research mostly improves the fairness of Machine Learning (ML) software regarding a single protected attribute at a time, but this is unrealistic given that many users have multiple protected attributes. This paper conducts an extensive study of fairness improvement regarding multiple protected attributes, covering 11 state-of-the-art fairness improvement methods. We analyze the effectiveness of these methods with different datasets, metrics, and ML models when considering multiple protected attributes. The results reveal that improving fairness for a single protected attribute can largely decrease fairness regarding unconsidered protected attributes. This decrease is observed in up to 88.3% of scenarios (57.5% on average). More surprisingly, we find little difference in accuracy loss when considering single and multiple protected attributes, indicating that accuracy can be maintained in the multiple-attribute paradigm. However, the effect on precision and recall when handling multiple protected attributes is about five times and eight times that of a single attribute. This has important implications for future fairness research: reporting only accuracy as the ML performance metric, which is currently common in the literature, is inadequate.

Flaky tests are tests that pass and fail on different executions of the same version of a program under test. They waste valuable developer time by making developers investigate false alerts (flaky test failures). To deal with this issue, many prediction methods have been proposed. However, the utility of these methods remains unclear since they are typically evaluated based on single-release data, ignoring that in many cases tests that fail flakily in one release also correctly fail (indicating the presence of bugs) in some other, meaning that it is possible for subsequent correctly-failing cases to pass unnoticed. In this paper, we show that this situation is prevalent and can raise significant concerns for both researchers and practitioners. In particular, we show that flaky tests, tests that exhibit flaky behaviour at some point in time, have a strong fault-revealing capability, i.e., they reveal more than 1/3 of all encountered regression faults. We also show that 76.2%, of all test executions that reveal faults in the codebase under test are made by tests that are classified as flaky by existing prediction methods. Overall, our findings motivate the need for future research to focus on predicting flaky test executions instead of flaky tests.

Abstract Source-to-source code translation automatically translates a program from one programming language to another. The existing research on code translation evaluates the effectiveness of their approaches by using either syntactic similarities (e.g., BLEU score), or test execution results. The former does not consider semantics, the latter considers semantics but falls short on the problem of insufficient data and tests. In this paper, we propose MBTA (Mutation-based Code Translation Analysis), a novel application of mutation analysis for code translation assessment. We also introduce MTS (Mutation-based Translation Score), a measure to compute the level of trustworthiness of a translator. If a mutant of an input program shows different test execution results from its translated version, the mutant is killed and a translation bug is revealed. Fewer killed mutants indicate better code translation. MBTA is novel in the sense that mutants are compared to their translated counterparts, and not to their original program’s translation. We conduct a proof-of-concept case study with 612 Java-Python program pairs and 75,082 mutants on the code translators TransCoder and j2py to evaluate the feasibility of MBTA. The results reveal that TransCoder and j2py fail to translate 70.44% and 70.64% of the mutants, respectively, i.e., more than two-thirds of all mutants are incorrectly translated by these translators. By analysing the MTS results more closely, we were able to reveal translation bugs not captured by the conventional comparison between the original and translated programs.

Decision-making software mainly based on Machine Learning (ML) may contain fairness issues (e.g., providing favourable treatment to certain people rather than others based on sensitive attributes such as gender or race). Various mitigation methods have been proposed to automatically repair fairness issues to achieve fairer ML software and help software engineers to create responsible software. However, existing bias mitigation methods trade accuracy for fairness (i.e., trade a reduction in accuracy for better fairness). In this paper, we present a novel search-based method for repairing ML-based decision making software to simultaneously increase both its fairness and accuracy. As far as we know, this is the first bias mitigation approach based on multi-objective search that aims to repair fairness issues without trading accuracy for binary classification methods. We apply our approach to two widely studied ML models in the software fairness literature (i.e., Logistic Regression and Decision Trees), and compare it with seven publicly available state-of-the-art bias mitigation methods by using three different fairness measurements. The results show that our approach successfully increases both accuracy and fairness for 61% of the cases studied, while the state-of-the-art always decrease accuracy when attempting to reduce bias. With our proposed approach, software engineers that previously were concerned with accuracy losses when considering fairness, are now enabled to improve the fairness of binary classification models without sacrificing accuracy.

Unfair behaviors of Machine Learning (ML) software have garnered increasing attention and concern among software engineers. To tackle this issue, extensive research has been dedicated to conducting fairness testing of ML software, and this article offers a comprehensive survey of existing studies in this field. We collect 100 papers and organize them based on the testing workflow (i.e., how to test) and testing components (i.e., what to test). Furthermore, we analyze the research focus, trends, and promising directions in the realm of fairness testing. We also identify widely adopted datasets and open-source tools for fairness testing.

Genetic Improvement (GI) uses search-based optimisation algorithms to automatically improve software with respect to both functional and non-functional properties. Our previous work showed that Regression Test Selection (RTS) can help speed up the use of GI and enhance the overall results while not affecting the software system’s validity. This article expands upon our investigation by answering further questions about safety and applying a GI algorithm based on Local Search (LS) in addition to the previously explored Genetic Programming (GP) approach. Further, we extend the number of subjects to 12 by analysing five larger real-world open-source programs. We empirically compare two state-of-the-art RTS techniques combined with GP and LS for these 12 programs. The results show that both RTS techniques are safe to use and can reduce the cost of GI by up to 80% and by 31% on average across programs. We also observe that both search-based algorithms impact the effectiveness gains of GI differently, and that various RTS strategies achieve differing gains in terms of efficiency. These results serve as further evidence that RTS must be used as a core component of the GI search process to maximise its effectiveness and efficiency.

There have been rapid recent developments in automated software test design, repair and program improvement. Advances in artificial intelligence also have great potential impact to tackle software testing research problems. In this paper we highlight open research problems and challenges from an industrial perspective. This perspective draws on our experience at Meta Platforms, which has been actively involved in software testing research and development for approximately a decade. As we set out here, there are many exciting opportunities for software testing research to achieve the widest and deepest impact on software practice. With this overview of the research landscape from an industrial perspective, we aim to stimulate further interest in the deployment of software testing research. We hope to be able to collaborate with the scientific community on some of these research challenges.

Online Judge platforms play a pivotal role in education, competitive programming, recruitment, career training, and large language model training. They rely on predefined test suites to judge the correctness of submitted solutions. It is therefore important that the solution judgement is reliable and free from potentially misleading false positives (i.e., incorrect solutions that are judged as correct). In this paper, we conduct an empirical study of 939 coding problems with 541,552 solutions, all of which are judged to be correct according to the test suites used by the platform, finding that 43.4% of the problems include false positive solutions (3,440 bugs are revealed in total). We also find that test suites are, nevertheless, of high quality according to widely-studied test effectiveness measurements: 88.2% of false positives have perfect (100%) line coverage, 78.9% have perfect branch coverage, and 32.5% have a perfect mutation score. Our findings indicate that more work is required to weed out false positive solutions and to further improve test suite effectiveness. We have released the detected false positive solutions and the generated test inputs to facilitate future research.

Mutation testing has been demonstrated to be one of the most powerful fault-revealing tools in the tester's tool kit. Much previous work implicitly assumed it to be sufficient to re-compute mutant suites per release. Sadly, this makes mutation results inconsistent; mutant scores from each release cannot be directly compared, making it harder to measure test improvement. Furthermore, regular code change means that a mutant suite's relevance will naturally degrade over time. We measure this degradation in relevance for 143,500 mutants in 4 non-trivial systems, finding that 52% degrade, on average. We introduce a mutant brittleness measure and use it to audit software systems and their mutation suites. We also demonstrate how consistent-by-construction long-standing mutant suites can be identified with a 10x improvement in mutant relevance over an arbitrary test suite. Our results indicate that the research community should avoid the re-computation of mutant suites and focus, instead, on long-standing mutants, thereby improving the consistency and relevance of mutation testing.

Bug reports are used by software testers to identify abnormal software behaviour. In this paper, we propose a multi-objective evolutionary approach to automatically generate finite state machines (FSMs) based on bug reports written in natural language, to automatically capture incorrect software behaviour. These FSMs can then be used by testers to both exercise the reported bugs and create tests that can potentially reveal new bugs. The FSM generation is guided by a Multi-Objective Evolutionary Algorithm (MOEA) that simultaneously minimises three objectives: size of the models, number of unrealistic states (over-generalisation), and number of states not covered by the models (under-generalisation). We assess the feasibility of our approach for 10 real-world software programs by exploiting three different MOEAs (NSGA-II, NSGA-III and MOEA/D) and benchmarking them with the baseline tool KLFA. Our results show that KLFA is not practical to be used with real-world software, because it generates models that over generalise software behaviour. Among the three MOEAs, NSGA-II obtained significantly better results than the other two for all 10 programs, detecting a greater number of bugs for 90% of the programs. We also studied the differences in quality and model performance when MOEAs are guided by only two objectives rather than three during the evolution. We found that the use of under-approximation (or over-approximation) and size as objectives generates infeasible solutions. On the other hand, using as objectives over-approximation and under-approximation generates feasible solutions yet still worse than those obtained using all three objectives for 100% of the cases. The size objective acts as a diversity factor. As a consequence, an algorithm guided by all three objectives avoids local optima, controls the size of the models, and makes the results more diverse and closer to the optimal Pareto set.

Software bias is an increasingly important operational concern for software engineers. We present a large-scale, comprehensive empirical study of 17 representative bias mitigation methods for Machine Learning (ML) classifiers, evaluated with 11 ML performance metrics (e.g., accuracy), 4 fairness metrics, and 20 types of fairness-performance tradeoff assessment, applied to 8 widely-adopted software decision tasks. The empirical coverage is much more comprehensive, covering the largest numbers of bias mitigation methods, evaluation metrics, and fairness-performance tradeoff measures compared to previous work on this important software property. We find that (1) the bias mitigation methods significantly decrease ML performance in 53% of the studied scenarios (ranging between 42%∼66% according to different ML performance metrics); (2) the bias mitigation methods significantly improve fairness measured by the 4 used metrics in 46% of all the scenarios (ranging between 24%∼59% according to different fairness metrics); (3) the bias mitigation methods even lead to decrease in both fairness and ML performance in 25% of the scenarios; (4) the effectiveness of the bias mitigation methods depends on tasks, models, the choice of protected attributes, and the set of metrics used to assess fairness and ML performance; (5) there is no bias mitigation method that can achieve the best tradeoff in all the scenarios. The best method that we find outperforms other methods in 30% of the scenarios. Researchers and practitioners need to choose the bias mitigation method best suited to their intended application scenario(s).

Machine translation plays an essential role in people's daily international communication. However, machine translation systems are far from perfect. To tackle this problem, researchers have proposed several approaches to testing machine translation. A promising trend among these approaches is to use word replacement, where only one word in the original sentence is replaced with another word to form a sentence pair. However, precise control of the impact of word replacement remains an outstanding issue in these approaches.

Much research on software testing makes an implicit assumption that test failures are deterministic such that they always witness the presence of the same defects. However, this assumption is not always true because some test failures are due to so-called flaky tests, i.e., tests with non-deterministic outcomes. To help testing researchers better investigate flakiness, we introduce a test flakiness assessment and experimentation platform, called FlakiMe. FlakiMe supports the seeding of a (controllable) degree of flakiness into the behaviour of a given test suite. Thereby, FlakiMe equips researchers with ways to investigate the impact of test flakiness on their techniques under laboratory-controlled conditions. To demonstrate the application of FlakiMe, we use it to assess the impact of flakiness on mutation testing and program repair (the PRAPR and ARJA methods). These results indicate that a 10% flakiness is sufficient to affect the mutation score, but the effect size is modest (2% - 5% ), while it reduces the number of patches produced for repair by 20% up to 100% of repair problems; a devastating impact on this application of testing. Our experiments with FlakiMe demonstrate that flakiness affects different testing applications in very different ways, thereby motivating the need for a laboratory-controllable flakiness impact assessment platform and approach such as FlakiMe.

We introduce Fausta, an algorithmic traffic gener-ation platform that enables analysis and testing at scale. Fausta has been deployed at Meta to analyze and test the WhatsApp plat-form infrastructure since September 2020, enabling WhatsApp developers to deploy reliable code changes to a code base of millions of lines of code, supporting over 2 billion users who rely on WhatsApp for their daily communications. Fausta covers expected and unexpected program behaviors in a privacy-safe controlled environment to support multiple use cases such as reliability testing, privacy analysis and performance regression detection. It currently supports three different algorithmic input generation strategies, each of which construct realistic backend server traffic that closely simulates production data, without replaying any real user data. Fausta has been deployed and closely integrated into the WhatsApp continuous integration process, catching bugs in development before they hit production. We report on the development and deployment of Fausta's reliability use case between September 2020 and August 2021. During this period it has found 1,876 unique reliability issues, with a fix rate of 74%, indicating a high degree of true positive fault revelation. We also report on the distribution of fault types revealed by Fausta, and the correlation between coverage and faults found. Overall, we do find evidence that higher coverage is correlated with fault revelation.

Machine Learning (ML) software can lead to unfair and unethical decisions, making software fairness bugs an increasingly significant concern for software engineers. However, addressing fairness bugs often comes at the cost of introducing more ML performance (e.g., accuracy) bugs. In this paper, we propose MAAT, a novel ensemble approach to improving fairness-performance trade-off for ML software. Conventional ensemble methods combine different models with identical learning objectives. MAAT, instead, combines models optimized for different objectives: fairness and ML performance. We conduct an extensive evaluation of MAAT with 5 state-of-the-art methods, 9 software decision tasks, and 15 fairness-performance measurements. The results show that MAAT significantly outperforms the state-of-the-art. In particular, MAAT beats the trade-off baseline constructed by a recent benchmarking tool in 92.2% of the overall cases evaluated, 12.2 percentage points more than the best technique currently available. Moreover, the superiority of MAAT over the state-of-the-art holds on all the tasks and measurements that we study. We have made publicly available the code and data of this work to allow for future replication and extension.

To ensure user satisfaction and success of mobile applications, it is important to provide highly performant applications. This is particularly important for resource-constrained systems such as mobile devices. Thereby, non-functional performance characteristics, such as energy and memory consumption, play an important role for user satisfaction. This paper provides a comprehensive survey of non-functional performance optimization for Android applications. We collected 156 unique publications, published between 2008 and 2020, that focus on the optimization of performance of mobile applications. We target our search at four performance characteristics: responsiveness, launch time, memory and energy consumption. For each performance characteristic, we categorize optimization approaches based on the method used in the corresponding publications. Furthermore, we identify research gaps in the literature for future work.

API misuses are well-known causes of software crashes and security vulnerabilities. However, their detection and repair is challenging given that the correct usages of (third-party)apis might be obscure to the developers of client programs. This paper presents the first empirical study to assess the ability of existing automated bug repair tools to repairapimisuses, which is a class of bugs previously unexplored. Our study examines and compares 14 Java test-suite-based repair tools (11 proposed before 2018, and three afterwards) on a manually curated benchmark (APIRepBench) consisting of 101apimisuses. We develop an extensible execution framework (APIARTy) to automatically execute multiple repair tools. Our results show that the repair tools are able to generate patches for 28 percent of theapimisuses considered. While the 11 less recent tools are generally fast (the median execution time of the repair attempts is 3.87 minutes and the mean execution time is 30.79 minutes), the three most recent are less efficient (i.e., 98 percent slower) than their predecessors. The tools generate patches forapimisuses that mostly belong to the categories of missingnullcheck, missing value, missing exception, and missing call. Most of the patches generated by all tools are plausible (65 percent), but only few of these patches are semantically correct to human patches (25 percent). Our findings suggest that the design of future repair tools should support the localisation of complex bugs, including different categories ofapimisuses, handling of timeout issues, and ability to configure large software projects. BothAPIRepBenchandAPIARTyhave been made publicly available for other researchers to evaluate the capabilities of repair tools on detecting and fixingapimisuses.

In this paper, we introduce a novel approach to predictive modeling for software engineering, named Learning From Mistakes (LFM). The core idea underlying our proposal is to automatically learn from past estimation errors made by human experts, in order to predict the characteristics of their future misestimates, therefore resulting in improved future estimates. We show the feasibility of LFM by investigating whether it is possible to predict the type, severity and magnitude of errors made by human experts when estimating the development effort of software projects, and whether it is possible to use these predictions to enhance future estimations. To this end we conduct a thorough empirical study investigating 402 maintenance and new development industrial software projects. The results of our study reveal that the type, severity and magnitude of errors are all, indeed, predictable. Moreover, we find that by exploiting these predictions, we can obtain significantly better estimates than those provided by random guessing, human experts and traditional machine learners in 31 out of the 36 cases considered (86 percent), with large and very large effect sizes in the majority of these cases (81 percent). This empirical evidence opens the door to the development of techniques that use the power of machine learning, coupled with the observation that human errors are predictable, to support engineers in estimation tasks rather than replacing them with machine-provided estimates.

Replication studies increase our confidence in previous results when the findings are similar each time, and help mature our knowledge by addressing both internal and external validity aspects. However, these studies are still rare in certain software engineering fields. In this paper, we replicate and extend a previous study, which denotes the current state-of-the-art for multi-objective software effort estimation, namely CoGEE. We investigate the original research questions with an independent implementation and the inclusion of a more robust baseline (LP4EE), carried out by the first author, who was not involved in the original study. Through this replication, we strengthen both the internal and external validity of the original study. We also answer two new research questions investigating the effectiveness of CoGEE by using four additional evolutionary algorithms (i.e., IBEA, MOCell, NSGA-III, SPEA2) and a well-known Java framework for evolutionary computation, namely JMetal (rather than the previously used R software), which allows us to strengthen the external validity of the original study. The results of our replication confirm that: (1) CoGEE outperforms both baseline and state-of-the-art benchmarks statistically significantly ($p <0.001$); (2) CoGEE’s multi-objective nature makes it able to reach such a good performance; (3) CoGEE’s estimation errors lie within claimed industrial human-expert-based thresholds. Moreover, our new results show that the effectiveness of CoGEE is generally not limited to nor dependent on the choice of the multi-objective algorithm. Using CoGEE with either NSGA-II, NSGA-III, or MOCell produces human competitive results in less than a minute. The Java version of CoGEE has decreased the running time by over 99.8 percent with respect to its R counterpart. We have made publicly available the Java code of CoGEE to ease its adoption, as well as, the data used in this study in order to allow for future replication and extension of our work.

This paper provides a comprehensive survey of techniques for testing machine learning systems; Machine Learning Testing (ML testing) research. It covers 144 papers on testing properties (e.g., correctness, robustness, and fairness), testing components (e.g., the data, learning program, and framework), testing workflow (e.g., test generation and test evaluation), and application scenarios (e.g., autonomous driving, machine translation). The paper also analyses trends concerning datasets, research trends, and research focus, concluding with research challenges and promising research directions in ML testing.

A cyber–cyber digital twin is a simulation of a software system. By contrast, a cyber–physical digital twin is a simulation of a non-software (physical) system. Although cyber–physical digital twins have received a lot of recent attention, their cyber–cyber counterparts have been comparatively overlooked. In this paper we show how the unique properties of cyber–cyber digital twins open up exciting opportunities for research and development. Like all digital twins, the cyber–cyber digital twin is both informed by and informs the behaviour of the twin it simulates. It is therefore a software system that simulates another software system, making it conceptually truly a twin, blurring the distinction between the simulated and the simulator. Cyber–cyber digital twins can be twins of other cyber–cyber digital twins, leading to a hierarchy of twins. As we shall see, these apparently philosophical observations have practical ramifications for the design, implementation and deployment of digital twins at Facebook.

A cyber cyber digital twin is a deployed software model that executes in tandem with the system it simulates, contributing to, and drawing from, the system's behaviour. This paper outlines Facebook's cyber cyber digital twin, dubbed WW, a twin of Facebook's WWW platform, built using web-enabled simulation. The paper focuses on the current research challenges and opportunities in the area of measurement. Measurement challenges lie at the heart of modern simulation. They directly impact how we use simulation outcomes for automated online and semi-automated offline decision making. Measurements also encompas how we verify and validate those outcomes. Modern simulation systems are increasingly becoming more like cyber cyber digital twins, effectively moving from manual to automated decision making, hence, these measurement challenges acquire ever greater significance.

Genetic improvement uses artificial intelligence to automatically improve software with respect to non-functional properties (AI for SE). In this paper, we propose the use of existing software engineering best practice to enhance Genetic Improvement (SE for AI). We conjecture that existing Regression Test Selection (RTS) techniques (which have been proven to be efficient and effective) can and should be used as a core component of the GI search process for maximising its effectiveness. To assess our idea, we have carried out a thorough empirical study assessing the use of both dynamic and static RTS techniques with GI to improve seven real-world software programs. The results of our empirical evaluation show that incorporation of RTS within GI significantly speeds up the whole GI process, making it up to 78% faster on our benchmark set, being still able to produce valid software improvements. Our findings are significant in that they can save hours to days of computational time, and can facilitate the uptake of GI in an industrial setting, by significantly reducing the time for the developer to receive feedback from such an automated technique. Therefore, we recommend the use of RTS in future test-based automated software improvement work. Finally, we hope this successful application of SE for AI will encourage other researchers to investigate further applications in this area.

To effectively test program changes using mutation testing, one needs to use mutants that are relevant to the altered program behaviours. In view of this, we introduce MuDelta, an approach that identifies commit-relevant mutants; mutants that affect and are affected by the changed program behaviours. Our approach uses machine learning applied on a combined scheme of graph and vector-based representations of static code features. Our results, from 50 commits in 21 Coreutils programs, demonstrate a strong prediction ability of our approach; yielding 0.80 (ROC) and 0.50 (PR Curve) AUC values with 0.63 and 0.32 precision and recall values. These predictions are significantly higher than random guesses, 0.20 (PR-Curve) AUC, 0.21 and 0.21 precision and recall, and subsequently lead to strong relevant tests that kill 45%more relevant mutants than randomly sampled mutants (either sampled from those residing on the changed component(s) or from the changed lines). Our results also show that MuDelta selects mutants with 27% higher fault revealing ability in fault introducing commits. Taken together, our results corroborate the conclusion that commit-based mutation testing is suitable and promising for evolving software.

Machine learning software can be unfair when making human-related decisions, having prejudices over certain groups of people. Existing work primarily focuses on proposing fairness metrics and presenting fairness improvement approaches. It remains unclear how key aspect of any machine learning system, such as feature set and training data, affect fairness. This paper presents results from a comprehensive study that addresses this problem. We find that enlarging the feature set plays a significant role in fairness (with an average effect rate of 38%). Importantly, and contrary to widely-held beliefs that greater fairness often corresponds to lower accuracy, our findings reveal that an enlarged feature set has both higher accuracy and fairness. Perhaps also surprisingly, we find that a larger training data does not help to improve fairness. Our results suggest a larger training data set has more unfairness than a smaller one when feature sets are insufficient; an important cautionary finding for practising software engineers.

The increasingly wide uptake of Machine Learning (ML) has raised the significance of the problem of tackling bias (i.e., unfairness), making it a primary software engineering concern. In this paper, we introduce Fairea, a model behaviour mutation approach to benchmarking ML bias mitigation methods. We also report on a large-scale empirical study to test the effectiveness of 12 widely-studied bias mitigation methods. Our results reveal that, surprisingly, bias mitigation methods have a poor effectiveness in 49% of the cases. In particular, 15% of the mitigation cases have worse fairness-accuracy trade-offs than the baseline established by Fairea; 34% of the cases have a decrease in accuracy and an increase in bias.

In this paper, we study the app store as a phenomenon from the developers' perspective to investigate the extent to which app stores affect software engineering tasks. Through developer interviews and questionnaires, we uncover findings that highlight and quantify the effects of three high-level app store themes: bridging the gap between developers and users, increasing market transparency and affecting mobile release management. Our findings have implications for testing, requirements engineering and mining software repositories research fields. These findings can help guide future research in supporting mobile app developers through a deeper understanding of the app store-developer interaction.

Priority inflation occurs when a Quality-Assurance (QA) engineer or a project manager requesting a feature inflates the priority of their task so that developers deliver the fix or the new functionality more quickly. We survey developers and show that priority inflation occurs and misallocates developer time. We are the first to apply empirical game-theoretic analysis (EGTA) to a software engineering problem, specifically priority inflation. First, we extract prioritisation strategies from 42,620 issues from Apache's JIRA, then useTaskAssessor, our EGTA-based modelling approach, to confirm conventional wisdom and show that the common process of a QA engineer assigning priority labels is susceptible to priority inflation. We then show that the common mitigation strategy of having a bug triage team assigning priorities does not resolve priority inflation and slows development. We then use mechanism design to deviseassessor-throttling, a new, lightweight prioritization process, immune to priority inflation. We show that assessor-throttling resolves 97 percent of high priority tasks, 69 percent better than simply relying on those filing tasks to assign priorities. Finally, we present The Fed, a browser extension for Chrome that supports assessor-throttling.

We propose a human-in-the-loop approach for oracle improvement and analyse whether the proposed oracle improvement process is helping developers to create better oracles. For this, we conducted two human studies with 68 participants overall: an oracle assessment study and an oracle improvement study. Our results show that developers exhibit poor performance (29 percent accuracy) when manually assessing whether an assertion oracle contains a false positive, a false negative or none of the two. This shows that automated detection of these oracle deficiencies is beneficial for the users. Our tool OASIs (Oracle ASsessment and Improvement) helps developers produce assertions with higher quality. Participants who used OASIs in the improvement study were able to achieve 33 percent of full and 67 percent of partial correctness as opposed to participants without the tool who achieved only 21 percent of full and 43 percent of partial correctness.

Although considered one of the most important decisions in the software development lifecycle, empirical evidence on how developers perform and perceive architectural changes remains scarce. Architectural decisions have far-reaching consequences yet, we know relatively little about the level of developers' awareness of their changes' impact on the software's architecture. We also know little about whether architecture-related discussions between developers lead to better architectural changes. To provide a better understanding of these questions, we use the code review data from 7 open source systems to investigate developers' intent and awareness when performing changes alongside the evolution of the changes during the reviewing process. We extracted the code base of 18,400 reviews and 51,889 revisions. 4,171 of the reviews have changes in their computed architectural metrics, and 731 present significant changes to the architecture. We manually inspected all reviews that caused significant changes and found that developers are discussing the impact of their changes on the architectural structure in only 31% of the cases, suggesting a lack of awareness. Moreover, we noticed that in 73% of the cases in which developers provided architectural feedback during code review, the comments were addressed, where the final merged revision tended to exhibit higher architectural improvement than reviews in which the system's structure is not discussed.

Constraints depict the dependency relationships between parameters in a software system under test. Because almost all systems are constrained in some way, techniques that adequately cater for constraints have become a crucial factor for adoption, deployment and exploitation of Combinatorial Testing (CT). Currently, despite a variety of different constraint handling techniques available, the relationship between these techniques and the generation algorithms that use them remains unknown, yielding an important gap and pressing concern in the literature of constrained combination testing. In this article, we present a comparative empirical study to investigate the impact of four common constraint handling techniques on the efficiency of six representative (greedy and search-based) test suite generation algorithms. The results reveal that theVerifytechnique implemented with the Minimal Forbidden Tuple (MFT) approach is the fastest, while theReplacetechnique is promising for producing the smallest constrained covering arrays, especially for algorithms that construct test cases one-at-a-time. The results also show that there is an interplay between efficiency of the constraint handler and the test suite generation algorithm into which it is developed.

This paper presents a large-scale study that investigates the bug resolution characteristics among popular Github projects written in different programming languages. We explore correlations but, of course, we cannot infer causation. Specifically, we analyse bug resolution data from approximately 70 million Source Line of Code, drawn from 3 million commits to 600 GitHub projects, primarily written in 10 programming languages. We find notable variations in apparent bug resolution time and patch (fix) size. While interpretation of results from such large-scale empirical studies is inherently difficult, we believe that the differences in medians are sufficiently large to warrant further investigation, replication, re-analysis and follow up research. For example, in our corpus, the median apparent bug resolution time (elapsed time from raise to resolve) for Ruby was 4X that for Go and 2.5X for Java. We also found that patches tend to touch more files for the corpus of strongly typed and for statically typed programs. However, we also found evidence for alowerelapsed resolution time for bug resolution committed to projects constructed from statically typed languages. These findings, if replicated in subsequent follow on studies, may shed further empirical light on the debate about the importance of static typing.

This paper presents TransRepair, a fully automatic approach for testing and repairing the consistency of machine translation systems. TransRepair combines mutation with metamorphic testing to detect inconsistency bugs (without access to human oracles). It then adopts probability-reference or cross-reference to post-process the translations, in a grey-box or black-box manner, to repair the inconsistencies. Our evaluation on two state-of-the-art translators, Google Translate and Transformer, indicates that TransRepair has a high precision (99%) on generating input pairs with consistent translations. With these tests, using automatic consistency metrics and manual assessment, we find that Google Translate and Transformer have approximately 36% and 40% inconsistency bugs. Black-box repair fixes 28% and 19% bugs on average for Google Translate and Transformer. Grey-box repair fixes 30% bugs on average for Transformer. Manual inspection indicates that the translations repaired by our approach improve consistency in 87% of cases (degrading it in 2%), and that our repairs have better translation acceptability in 27% of the cases (worse in 8%).

Software-intensive organizations rely on large numbers of software assets of different types, e.g., source-code files, tables in the data warehouse, and software configurations. Who is the most suitable owner of a given asset changes over time, e.g., due to reorganization and individual function changes. New forms of automation can help suggest more suitable owners for any given asset at a given point in time. By such efforts on ownership health, accountability of ownership is increased. The problem of finding the most suitable owners for an asset is essentially a program comprehension problem: how do we automatically determine who would be best placed to understand, maintain, evolve (and thereby assume ownership of) a given asset. This paper introduces the Facebook Ownesty system, which uses a combination of ultra large scale data mining and machine learning and has been deployed at Facebook as part of the company's ownership management approach. Ownesty processes many millions of software assets (e.g., source-code files) and it takes into account workflow and organizational aspects. The paper sets out open problems and challenges on ownership for the research community with advances expected from the fields of software engineering, programming languages, and machine learning.

Mutation testing research has often used the number of mutants as a surrogate measure for the true execution cost of generating and executing mutants. This poses a potential threat to the validity of the scientific findings reported in the literature. Out of 75 works surveyed in this paper, we found that 54 (72%) are vulnerable to this threat. To investigate the magnitude of the threat, we conducted an empirical evaluation using 10 real-world programs. The results reveal that: i) percentages of randomly sampled mutants differ from the true execution time, on average, by 44%, varying in difference from 19% to 91%; ii) errors arising from using the surrogate correlate with program size (ρ = 0.74) and number of mutants (ρ = 0.76), making the problem more pernicious for more realistic programs; iii) scientific findings concerning sampling strategies would have approximately 37% rank disagreement, indicating potentially dramatic impact on experiment validity. To investigate whether this threat matters in practice, we reproduced a seminal study on Selective Mutation (widely relied upon for more than two decades). The impact is stark: an inconclusive scientific finding using the surrogate is transformed to an unequivocal finding when using the true execution cost.

UI testing is tedious and time-consuming due to the manual effort required. Recent research has explored opportunities for reusing existing UI tests from an app to automatically generate new tests for other apps. However, the evaluation of such techniques currently remains manual, unscalable, and unreproducible, which can waste effort and impede progress in this emerging area. We introduce FrUITeR, a framework that automatically evaluates UI test reuse in a reproducible way. We apply FrUITeR to existing test-reuse techniques on a uniform benchmark we established, resulting in 11,917 test reuse cases from 20 apps. We report several key findings aimed at improving UI test reuse that are missed by existing work.

We present an empirical comparison of three test generation techniques, namely, Combinatorial Testing (CT), Random Testing (RT) and Adaptive Random Testing (ART), under different test scenarios. This is the first study in the literature to account for the (more realistic) testing setting in which the tester may not have complete information about the parameters and constraints that pertain to the system, and to account for the challenge posed by faults (in terms of failure rate). Our study was conducted on nine real-world programs under a total of 1683 test scenarios (combinations of available parameter and constraint information and failure rate). The results show significant differences in the techniques' fault detection ability when faults are hard to detect (failure rates are relatively low). CT performs best overall; no worse than any other in 98 percent of scenarios studied. ART enhances RT, and is comparable to CT in 96 percent of scenarios, but its computational cost can be up to 3.5 times higher than CT when the program is highly constrained. Additionally, when constraint information is unavailable for a highly-constrained program, a large random test suite is as effective as CT or ART, yet its computational cost of test generation is significantly lower than that of other techniques.

This paper outlines 4 open challenges for Software Testing in general and Search Based Software Testing in particular, arising from our experience with the Sapienz System Deployment at Facebook. The challenges may also apply more generally, thereby representing opportunities for the research community to further benefit from the growing interest in automated test design in industry.

Previous work on vulnerability prediction assume that predictive models are trained with respect to perfect labelling information (includes labels from future, as yet undiscovered vulnerabilities). In this paper we present results from a comprehensive empirical study of 1,898 real-world vulnerabilities reported in 74 releases of three security-critical open source systems (Linux Kernel, OpenSSL and Wiresark). Our study investigates the effectiveness of three previously proposed vulnerability prediction approaches, in two settings: with and without the unrealistic labelling assumption. The results reveal that the unrealistic labelling assumption can profoundly mis- lead the scientific conclusions drawn; suggesting highly effective and deployable prediction results vanish when we fully account for realistically available labelling in the experimental methodology. More precisely, MCC mean values of predictive effectiveness drop from 0.77, 0.65 and 0.43 to 0.08, 0.22, 0.10 for Linux Kernel, OpenSSL and Wiresark, respectively. Similar results are also obtained for precision, recall and other assessments of predictive efficacy. The community therefore needs to upgrade experimental and empirical methodology for vulnerability prediction evaluation and development to ensure robust and actionable scientific findings.

Test suites play a key role in ensuring software quality. A good test suite may detect more faults than a poor-quality one. Mutation testing is a powerful methodology for evaluating the fault-detection ability of test suites. In mutation testing, a large number of mutants may be generated and need to be executed against the test suite under evaluation to check how many mutants the test suite is able to detect, as well as the kind of mutants that the current test suite fails to detect. Consequently, although highly effective, mutation testing is widely recognized to be also computationally expensive, inhibiting wider uptake. To alleviate this efficiency concern, we propose Predictive Mutation Testing (PMT): the first approach to predicting mutation testing results without executing mutants. In particular, PMT constructs a classification model, based on a series of features related to mutants and tests, and uses the model to predict whether a mutant would be killed or remain alive without executing it. PMT has been evaluated on 163 real-world projects under two application scenarios (cross-version and cross-project). The experimental results demonstrate that PMT improves the efficiency of mutation testing by up to 151.4X while incurring only a small accuracy loss. It achieves above 0.80 AUC values for the majority of projects, indicating a good tradeoff between the efficiency and effectiveness of predictive mutation testing. Also, PMT is shown to perform well on different tools and tests, be robust in the presence of imbalanced data, and have high predictability (over 60 percent confidence) when predicting the execution results of the majority of mutants.

Reducing the energy consumption of software systems through optimisation techniques such as genetic improvement is gaining interest. However, efficient and effective improvement of software systems requires a better understanding of the code-change search space. One important choice practitioners have is whether to preserve the system's original output or permit approximation, with each scenario having its own search space characteristics. When output preservation is a hard constraint, we report that the maximum energy reduction achievable by the modification operators is 2.69 percent (0.76 percent on average). By contrast, this figure increases dramatically to 95.60 percent (33.90 percent on average) when approximation is permitted, indicating the critical importance of approximate output quality assessment for code optimisation. We investigate synergy, a phenomenon that occurs when simultaneously applied source code modifications produce an effect greater than their individual sum. Our results reveal that 12.0 percent of all joint code modifications produced such a synergistic effect, though 38.5 percent produce an antagonistic interaction in which simultaneously applied modifications are less effective than when applied individually. This highlights the need for more advanced search-based techniques.

Background: Code is repetitive and predictable in a way that is similar to the natural language. This means that code is "natural" and this "naturalness" can be captured by natural language modelling techniques. Such models promise to capture the program semantics and identify source code parts that `smell', i.e., they are strange, badly written and are generally error-prone (likely to be defective). Aims: We investigate the use of natural language modelling techniques in mutation testing (a testing technique that uses artificial faults). We thus, seek to identify how well artificial faults simulate real ones and ultimately understand how natural the artificial faults can be. Our intuition is that natural mutants, i.e., mutants that are predictable (follow the implicit coding norms of developers), are semantically useful and generally valuable (to testers). We also expect that mutants located on unnatural code locations (which are generally linked with error-proneness) to be of higher value than those located on natural code locations. Method: Based on this idea, we propose mutant selection strategies that rank mutants according to a) their naturalness (naturalness of the mutated code), b) the naturalness of their locations (naturalness of the original program statements) and c) their impact on the naturalness of the code that they apply to (naturalness differences between original and mutated statements). We empirically evaluate these issues on a benchmark set of 5 open-source projects, involving more than 100k mutants and 230 real faults. Based on the fault set we estimate the utility (i.e. capability to reveal faults) of mutants selected on the basis of their naturalness, and compare it against the utility of randomly selected mutants. Results: Our analysis shows that there is no link between naturalness and the fault revelation utility of mutants. We also demonstrate that the naturalness-based mutant selection performs similar (slightly worse) to the random mutant selection. Conclusions: Our findings are negative but we consider them interesting as they confute a strong intuition, i.e., fault revelation is independent of the mutants' naturalness.

The oracle problem remains one of the key challenges in software testing, for which little automated support has been developed so far. We introduce OASIs, a search-based tool for Java that assists testers in oracle assessment and improvement. It does so by combining test case generation to reveal false positives and mutation testing to reveal false negatives. In this work, we describe how OASIs works, provide details of its implementation, and explain how it can be used in an iterative oracle improvement process with a human in the loop. Finally, we present a summary of previous empirical evaluation showing that the fault detection rate of the oracles after improvement using OASIs increases, on average, by 48.6%.

Code review has been widely adopted by both industrial and open source software development communities. Research in code review is highly dependant on real-world data, and although existing researchers have attempted to provide code review datasets, there is still no dataset that links code reviews with complete versions of the system's code base mainly because reviewed versions are not kept in the system's version control repository. Thus, we present CROP, the Code Review Open Platform, the first curated code review repository that links review data with isolated complete versions (snapshots) of the source code at the time of review. CROP currently provides data for 8 software systems, 48,975 reviews and 112,617 patches, including versions of the systems that are inaccessible in the systems' original repositories. Moreover, CROP is extensible, and it will be continuously curated and extended.

In this paper we provide empirical evidence that the rating that an app attracts can be accurately predicted from the features it offers. Our results, based on an analysis of 11,537 apps from the Samsung Android and BlackBerry World app stores, indicate that the rating of 89% of these apps can be predicted with 100% accuracy. Our prediction model is built by using feature and rating information from the existing apps offered in the App Store and it yields highly accurate rating predictions, using only a few (11-12) existing apps for case-based prediction. These findings may have important implications for requirements engineering in app stores: They indicate that app developers may be able to obtain (very accurate) assessments of the customer reaction to their proposed feature sets (requirements), thereby providing new opportunities to support the requirements elicitation process for app developers.

This paper describes some of the challenges and opportunities when deploying static and dynamic analysis at scale, drawing on the authors' experience with the Infer and Sapienz Technologies at Facebook, each of which started life as a research-led start-up that was subsequently deployed at scale, impacting billions of people worldwide. The paper identifies open problems that have yet to receive significant attention from the scientific community, yet which have potential for profound real world impact, formulating these as research questions that, we believe, are ripe for exploration and that would make excellent topics for research projects. Note: This paper accompanies the authors' joint keynote at the 18th IEEE International Working Conference on Source Code Analysis and Manipulation, September 23rd-24th, 2018 - Madrid, Spain.

We describe the deployment of the Sapienz Search Based Software Engineering (SBSE) testing system. Sapienz has been deployed in production at Facebook since September 2017 to design test cases, localise and triage crashes to developers and to monitor their fixes. Since then, running in fully continuous integration within Facebook’s production development process, Sapienz has been testing Facebook’s Android app, which consists of millions of lines of code and is used daily by hundreds of millions of people around the globe. We continue to build on the Sapienz infrastructure, extending it to provide other software engineering services, applying it to other apps and platforms, and hope this will yield further industrial interest in and uptake of SBSE (and hybridisations of SBSE) as a result. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Search-based software engineering has been extensively applied to the problem of finding improved modular structures that maximize cohesion and minimize coupling. However, there has, hitherto, been no longitudinal study of developers' implementations, over a series of sequential releases. Moreover, results validating whether developers respect the fitness functions are scarce, and the potentially disruptive effect of search-based remodularization is usually overlooked. We present an empirical study of 233 sequential releases of ten different systems; the largest empirical study reported in the literature so far, and the first longitudinal study. Our results provide evidence that developers do, indeed, respect the fitness functions used to optimize cohesion/coupling (they are statistically significantly better than arbitrary choices with p ≪ 0.01), yet they also leave considerable room for further improvement (cohesion/coupling can be improved by 25% on average). However, we also report that optimizing the structure is highly disruptive (on average more than 57% of the structure must change), while our results reveal that developers tend to avoid such disruption. Therefore, we introduce and evaluate a multiobjective (MO) evolutionary approach that minimizes disruption while maximizing cohesion/coupling improvement. This allows developers to balance reticence to disrupt existing modular structure, against their competing need to improve cohesion and coupling. The MO approach is able to find modular structures that improve the cohesion of developers' implementations by 22.52%, while causing an acceptably low level of disruption (within that already tolerated by developers).

Genetic improvement (GI) uses automated search to find improved versions of existing software. We present a comprehensive survey of this nascent field of research with a focus on the core papers in the area published between 1995 and 2015. We identified core publications including empirical studies, 96% of which use evolutionary algorithms (genetic programming in particular). Although we can trace the foundations of GI back to the origins of computer science itself, our analysis reveals a significant upsurge in activity since 2012. GI has resulted in dramatic performance improvements for a diverse set of properties such as execution time, energy and memory consumption, as well as results for fixing and extending existing system functionality. Moreover, we present examples of research work that lies on the boundary between GI and other areas, such as program transformation, approximate computing, and software repair, with the intention of encouraging further exchange of ideas between researchers in these fields.

A variety of meta-heuristic search algorithms have been introduced for optimising software release planning. However, there has been no comprehensive empirical study of different search algorithms across multiple different real-world datasets. In this article, we present an empirical study of global, local, and hybrid meta- and hyper-heuristic search-based algorithms on 10 real-world datasets. We find that the hyper-heuristics are particularly effective. For example, the hyper-heuristic genetic algorithm significantly outperformed the other six approaches (and with high effect size) for solution quality 85% of the time, and was also faster than all others 70% of the time. Furthermore, correlation analysis reveals that it scales well as the number of requirements increases.

Mutation testing realises the idea of fault-based testing, i.e., using artificial defects to guide the testing process. It is used to evaluate the adequacy of test suites and to guide test case generation. It is a potentially powerful form of testing, but it is well-known that its effectiveness is inhibited by the presence of equivalent mutants. We recently studied Trivial Compiler Equivalence (TCE) as a simple, fast and readily applicable technique for identifying equivalent mutants for C programs. In the present work, we augment our findings with further results for the Java programming language. TCE can remove a large portion of all mutants because they are determined to be either equivalent or duplicates of other mutants. In particular, TCE equivalent mutants account for 7.4 and 5.7 percent of all C and Java mutants, while duplicated mutants account for a further 21 percent of all C mutants and 5.4 percent Java mutants, on average. With respect to a benchmark ground truth suite (of known equivalent mutants), approximately 30 percent (for C) and 54 percent (for Java) are TCE equivalent. It is unsurprising that results differ between languages, since mutation characteristics are language-dependent. In the case of Java, our new results suggest that TCE may be particularly effective, finding almost half of all equivalent mutants.

Genetic improvement uses automated search to find improved versions of existing software. Genetic improvement has previously been concerned with improving a system with respect to all possible usage scenarios. In this paper, we show how genetic improvement can also be used to achieve specialisation to a specific set of usage scenarios. We use genetic improvement to evolve faster versions of a C++ program, a Boolean satisfiability solver called MiniSAT, specialising it for three different applications, each with their own characteristics. Our specialised solvers achieve between 4 and 36 percent execution time improvement, which is commensurate with efficiency gains achievable using human expert optimisation for the general solver. We also use genetic improvement to evolve faster versions of an image processing tool called ImageMagick, utilising code from GraphicsMagick, another image processing tool which was forked from it. We specialise the format conversion functionality to greyscale images and colour images only. Our specialised versions achieve up to 3 percent execution time improvement.

Many studies suggest using coverage concepts, such as branch coverage, as the starting point of testing, while others as the most prominent test quality indicator. Yet the relationship between coverage and fault-revelation remains unknown, yielding uncertainty and controversy. Most previous studies rely on the Clean Program Assumption, that a test suite will obtain similar coverage for both faulty and fixed ('clean') program versions. This assumption may appear intuitive, especially for bugs that denote small semantic deviations. However, we present evidence that the Clean Program Assumption does not always hold, thereby raising a critical threat to the validity of previous results. We then conducted a study using a robust experimental methodology that avoids this threat to validity, from which our primary finding is that strong mutation testing has the highest fault revelation of four widely-used criteria. Our findings also revealed that fault revelation starts to increase significantly only once relatively high levels of coverage are attained.

We show that information extracted from crowd-based testing can enhance automated mobile testing. We introduce Polariz, which generates replicable test scripts from crowd-based testing, extracting cross-app `motif' events: automatically-inferred reusable higher-level event sequences composed of lower-level observed event actions. Our empirical study used 434 crowd workers from Mechanical Turk to perform 1,350 testing tasks on 9 popular Google Play apps, each with at least 1 million user installs. The findings reveal that the crowd was able to achieve 60.5% unique activity coverage and proved to be complementary to automated search-based testing in 5 out of the 9 subjects studied. Our leave-one-out evaluation demonstrates that coverage attainment can be improved (6 out of 9 cases, with no disimprovement on the remaining 3) by combining crowd-based and search-based testing.

Although considered one of the most important decisions in a software development lifecycle, empirical evidence on how developers perform and perceive architectural changes is still scarce. Given the large implications of architectural decisions, we do not know whether developers are aware of their changes' impact on the software's architecture, whether awareness leads to better changes, and whether automatically making developers aware would prevent degradation. Therefore, we use code review data of 4 open source systems to investigate the intent and awareness of developers when performing changes. We extracted 8,900 reviews for which the commits are available. 2,152 of the commits have changes in their computed architectural metrics, and 338 present significant changes to the architecture. We manually inspected all reviews for commits with significant changes and found that only in 38% of the time developers are discussing the impact of their changes on the architectural structure, suggesting a lack of awareness. Finally, we observed that developers tend to be more aware of the architectural impact of their changes when the architectural structure is improved, suggesting that developers should be automatically made aware when their changes degrade the architectural structure.

Model-driven software engineering raises the abstraction level making complex systems easier to understand than if written in textual code. Nevertheless, large complicated software systems can have large models, motivating the need for slicing techniques that reduce the size of a model. We present a generalization of observation-based slicing that allows the criterion to be defined using a variety of kinds of observable behavior and does not require any complex dependence analysis. We apply our implementation of generalized observational slicing for tree-structured representations to Simulink models. The resulting slice might be the subset of the original model responsible for an observed failure or simply the sub-model semantically related to a classic slicing criterion. Unlike its predecessors, the algorithm is also capable of slicing embedded Stateflow state machines. A study of nine real-world models drawn from four different application domains demonstrates the effectiveness of our approach at dramatically reducing Simulink model sizes for realistic observation scenarios: for 9 out of 20 cases, the resulting model has fewer than 25% of the original model's elements.

In spite of several decades of software metrics research and practice, there is little understanding of how software metrics relate to one another, nor is there any established methodology for comparing them. We propose a novel experimental technique, based on search-based refactoring, to ‘animate’ metrics and observe their behaviour in a practical setting. Our aim is to promote metrics to the level of active, opinionated objects that can be compared experimentally to uncover where they conflict, and to understand better the underlying cause of the conflict. Our experimental approaches include semi-random refactoring, refactoring for increased metric agreement/disagreement, refactoring to increase/decrease the gap between a pair of metrics, and targeted hypothesis testing. We apply our approach to five popular cohesion metrics using ten real-world Java systems, involving 330,000 lines of code and the application of over 78,000 refactorings. Our results demonstrate that cohesion metrics disagree with each other in a remarkable 55 % of cases, that Low-level Similarity-based Class Cohesion (LSCC) is the best representative of the set of metrics we investigate while Sensitive Class Cohesion (SCOM) is the least representative, and we discover several hitherto unknown differences between the examined metrics. We also use our approach to investigate the impact of including inheritance in a cohesion metric definition and find that doing so dramatically changes the metric.

Context: App stores provide a software development space and a market place that are both different from those to which we have become accustomed for traditional software development: The granularity is finer and there is a far greater source of information available for research and analysis. Information is available on price, customer rating and, through the data mining approach presented in this paper, the features claimed by app developers. These attributes make app stores ideal for empirical software engineering analysis. Objective: This paper1 exploits App Store Analysis to understand the rich interplay between app customers and their developers. Method: We use data mining to extract app descriptions, price, rating, and popularity information from the Blackberry World App Store, and natural language processing to elicit each apps’ claimed features from its description. Results: The findings reveal that there are strong correlations between customer rating and popularity (rank of app downloads). We found evidence for a mild correlation between app price and the number of features claimed for the app and also found that higher priced features tended to be lower rated by their users. We also found that free apps have significantly (p-value < 0.001) higher ratings than non-free apps, with a moderately high effect size (A^12=0.68). All data from our experiments and analysis are made available on-line to support further investigations.

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.

Uncertainty is characterised by incomplete understanding. It is inevitable in the early phase of requirements engineering, and can lead to unsound requirement decisions. Inappropriate requirement choices may result in products that fail to satisfy stakeholders' needs, and might cause loss of revenue. To overcome uncertainty, requirements engineering decision support needs uncertainty management. In this research, we develop a decision support framework METRO for the Next Release Problem (NRP) to manage algorithmic uncertainty and requirements uncertainty. An exact NRP solver (NSGDP) lies at the heart of METRO. NSGDP's exactness eliminates interference caused by approximate existing NRP solvers. We apply NSGDP to three NRP instances, derived from a real world NRP instance, RALIC, and compare with NSGA-II, a widely-used approximate (inexact) technique. We find the randomness of NSGA-II results in decision makers missing up to 99.95 percent of the optimal solutions and obtaining up to 36.48 percent inexact requirement selection decisions. The chance of getting an inexact decision using existing approximate approaches is negatively correlated with the implementation cost of a requirement (Spearman r up to -0.72). Compared to the inexact existing approach, NSGDP saves 15.21 percent lost revenue, on average, for the RALIC dataset.

App Store Analysis studies information about applications obtained from app stores. App stores provide a wealth of information derived from users that would not exist had the applications been distributed via previous software deployment methods. App Store Analysis combines this non-technical information with technical information to learn trends and behaviours within these forms of software repositories. Findings from App Store Analysis have a direct and actionable impact on the software teams that develop software for app stores, and have led to techniques for requirements engineering, release planning, software design, security and testing. This survey describes and compares the areas of research that have been explored thus far, drawing out common aspects, trends and directions future research should take to address open problems and challenges.

Software engineering and development is well-known to suffer from unplanned overtime, which causes stress and illness in engineers and can lead to poor quality software with higher defects. Recently, we introduced a multi-objective decision support approach to help balance project risks and duration against overtime, so that software engineers can better plan overtime. This approach was empirically evaluated on six real world software projects and compared against state-of-the-art evolutionary approaches and currently used overtime strategies. The results showed that our proposal comfortably outperformed all the benchmarks considered. This paper extends our previous work by investigating adaptive multi-objective approaches to meta-heuristic operator selection, thereby extending and (as the results show) improving algorithmic performance. We also extended our empirical study to include two new real world software projects, thereby enhancing the scientific evidence for the technical performance claims made in the paper. Our new results, over all eight projects studied, showed that our adaptive algorithm outperforms the considered state of the art multi-objective approaches in 93 percent of the experiments (with large effect size). The results also confirm that our approach significantly outperforms current overtime planning practices in 100 percent of the experiments (with large effect size).

Context: Categorising software systems according to their functionality yields many benefits to both users and developers. Goal: In order to uncover the latent clustering of mobile apps in app stores, we propose a novel technique that measures app similarity based on claimed behaviour. Method: Features are extracted using information retrieval augmented with ontological analysis and used as attributes to characterise apps. These attributes are then used to cluster the apps using agglomerative hierarchical clustering. We empirically evaluate our approach on 17,877 apps mined from the BlackBerry and Google app stores in 2014. Results: The results show that our approach dramatically improves the existing categorisation quality for both Blackberry (from 0.02 to 0.41 on average) and Google (from 0.03 to 0.21 on average) stores. We also find a strong Spearman rank correlation (ρ= 0.96 for Google and ρ= 0.99 for BlackBerry) between the number of apps and the ideal granularity within each category, indicating that ideal granularity increases with category size, as expected. Conclusions: Current categorisation in the app stores studied do not exhibit a good classification quality in terms of the claimed feature space. However, a better quality can be achieved using a good feature extraction technique and a traditional clustering method.

Although white-box regression test prioritization has been well-studied, the more recently introduced black-box prioritization approaches have neither been compared against each other nor against more well-established white-box techniques. We present a comprehensive experimental comparison of several test prioritization techniques, including well-established white-box strategies and more recently introduced black-box approaches. We found that Combinatorial Interaction Testing and diversity-based techniques (Input Model Diversity and Input Test Set Diameter) perform best among the black-box approaches. Perhaps surprisingly, we found little difference between black-box and white-box performance (at most 4% fault detection rate difference). We also found the overlap between black- and white-box faults to be high: the first 10% of the prioritized test suites already agree on at least 60% of the faults found. These are positive findings for practicing regression testers who may not have source code available, thereby making white-box techniques inapplicable. We also found evidence that both black-box and white-box prioritization remain robust over multiple system releases.

We introduce a bi-objective effort estimation algorithm that combines Confidence Interval Analysis and assessment of Mean Absolute Error. We evaluate our proposed algorithm on three different alternative formulations, baseline comparators and current state-of-the-art effort estimators applied to five real-world datasets from the PROMISE repository, involving 724 different software projects in total. The results reveal that our algorithm outperforms the baseline, state-of-the-art and all three alternative formulations, statistically significantly (p < 0.001) and with large effect size (Â12 ≥ 0.9) over all five datasets. We also provide evidence that our algorithm creates a new state-of-the-art, which lies within currently claimed industrial human-expert-based thresholds, thereby demonstrating that our findings have actionable conclusions for practicing software engineers.

We introduce mutation-aware fault prediction, which leverages additional guidance from metrics constructed in terms of mutants and the test cases that cover and detect them. We report the results of 12 sets of experiments, applying 4 different predictive modelling techniques to 3 large real-world systems (both open and closed source). The results show that our proposal can significantly (p ≤ 0.05) improve fault prediction performance. Moreover, mutation-based metrics lie in the top 5% most frequently relied upon fault predictors in 10 of the 12 sets of experiments, and provide the majority of the top ten fault predictors in 9 of the 12 sets of experiments.

We introduce a technique for assessing and improving test oracles by reducing the incidence of both false positives and false negatives. We prove that our approach can always result in an increase in the mutual information between the actual and perfect oracles. Our technique combines test case generation to reveal false positives and mutation testing to reveal false negatives. We applied the decision support tool that implements our oracle improvement technique to five real-world subjects. The experimental results show that the fault detection rate of the oracles after improvement increases, on average, by 48.6% (86% over the implicit oracle). Three actual, exposed faults in the studied systems were subsequently confirmed and fixed by the developers.

We introduce Sapienz, an approach to Android testing that uses multi-objective search-based testing to automatically explore and optimise test sequences, minimising length, while simultaneously maximising coverage and fault revelation. Sapienz combines random fuzzing, systematic and search-based exploration, exploiting seeding and multi-level instrumentation. Sapienz significantly outperforms (with large effect size) both the state-of-the-art technique Dynodroid and the widely-used tool, Android Monkey, in 7/10 experiments for coverage, 7/10 for fault detection and 10/10 for fault-revealing sequence length. When applied to the top 1,000 Google Play apps, Sapienz found 558 unique, previously unknown crashes. So far we have managed to make contact with the developers of 27 crashing apps. Of these, 14 have confirmed that the crashes are caused by real faults. Of those 14, six already have developer-confirmed fixes.

Much research on software testing and test techniques relies on experimental studies based on mutation testing. In this paper we reveal that such studies are vulnerable to a potential threat to validity, leading to possible Type I errors; incorrectly rejecting the Null Hypothesis. Our findings indicate that Type I errors occur, for arbitrary experiments that fail to take countermeasures, approximately 62% of the time. Clearly, a Type I error would potentially compromise any scientific conclusion. We show that the problem derives from such studies’ combined use of both subsuming and subsumed mutants. We collected articles published in the last two years at three leading software engineering conferences. Of those that use mutation-based test assessment, we found that 68% are vulnerable to this threat to validity.

A dependence cluster is a set of mutually inter-dependent program elements. Prior studies have found that large dependence clusters are prevalent in software systems. It has been suggested that dependence clusters have potentially harmful effects on software quality. However, little empirical evidence has been provided to support this claim. The study presented in this paper investigates the relationship between dependence clusters and software quality at the function-level with a focus on effort-aware fault-proneness prediction. The investigation first analyzes whether or not larger dependence clusters tend to be more fault-prone. Second, it investigates whether the proportion of faulty functions inside dependence clusters is significantly different from the proportion of faulty functions outside dependence clusters. Third, it examines whether or not functions inside dependence clusters playing a more important role than others are more fault-prone. Finally, based on two groups of functions (i.e., functions inside and outside dependence clusters), the investigation considers a segmented fault-proneness prediction model. Our experimental results, based on five well-known open-source systems, show that (1) larger dependence clusters tend to be more fault-prone; (2) the proportion of faulty functions inside dependence clusters is significantly larger than the proportion of faulty functions outside dependence clusters; (3) functions inside dependence clusters that play more important roles are more fault-prone; (4) our segmented prediction model can significantly improve the effectiveness of effort-aware fault-proneness prediction in both ranking and classification scenarios. These findings help us better understand how dependence clusters influence software quality.

App developers would like to understand the impact of their own and their competitors’ software releases. To address this we introduce Causal Impact Release Analysis for app stores, and our tool, CIRA, that implements this analysis. We mined 38,858 popular Google Play apps, over a period of 12 months. For these apps, we identified 26,339 releases for which there was adequate prior and posterior time series data to facilitate causal impact analysis. We found that 33% of these releases caused a statistically significant change in user ratings. We use our approach to reveal important characteristics that distinguish causal significance in Google Play. To explore the actionability of causal impact analysis, we elicited the opinions of app developers: 56 companies responded, 78% concurred with the causal assessment, of which 33% claimed that their company would consider changing its app release strategy as a result of our findings.

Genetic Improvement (GI) is an area of Search Based Software Engineering which seeks to improve software's non-functional properties by treating program code as if it were genetic material which is then evolved to produce more optimal solutions. Hitherto, the majority of focus has been on optimising program's execution time which, though important, is only one of many non-functional targets. The growth in mobile computing, cloud computing infrastructure, and ecological concerns are forcing developers to focus on the energy their software consumes. We report on investigations into using GI to automatically find more energy efficient versions of the MiniSAT Boolean satisfiability solver when specialising for three downstream applications. Our results find that GI can successfully be used to reduce energy consumption by up to 25%

We genetically improve BarraCUDA using a BNF grammar incorporating C scoping rules with GP. Barracuda maps next generation DNA sequences to the human genome using the Burrows-Wheeler algorithm (BWA) on nVidia Tesla parallel graphics hardware (GPUs). GI using phenotypic tabu search with manually grown code can graft new features giving more than 100 fold speed up on a performance critical kernel without loss of accuracy.

We introduce a mutation-based approach to automatically discover and expose `deep' (previously unavailable) parameters that affect a program's runtime costs. These discovered parameters, together with existing (`shallow') parameters, form a search space that we tune using search-based optimisation in a bi-objective formulation that optimises both time and memory consumption. We implemented our approach and evaluated it on four real-world programs. The results show that we can improve execution time by 12\% or achieve a 21\% memory consumption reduction in the best cases. In three subjects, our deep parameter tuning results in a significant improvement over the baseline of shallow parameter tuning, demonstrating the potential value of our deep parameter extraction approach.

Software Product Line (SPL) feature selection involves the optimization of multiple objectives in a large and highly constrained search space. We introduce SATIBEA, that augments multi-objective search-based optimization with constraint solving to address this problem, evaluating it on five large real-world SPLs, ranging from 1,244 to 6,888 features with respect to three different solution quality indicators and two diversity metrics. The results indicate that SATIBEA statistically significantly outperforms the current state-of-the-art (p

The surge of search based software engineering research has been hampered by the need to develop customized search algorithms for different classes of the same problem. For instance, two decades of bespoke Combinatorial Interaction Testing (CIT) algorithm development, our exemplar problem, has left software engineers with a bewildering choice of CIT techniques, each specialized for a particular task. This paper proposes the use of a single hyperheuristic algorithm that learns search strategies across a broad range of problem instances, providing a single generalist approach. We have developed a Hyperheuristic algorithm for CIT, and report experiments that show that our algorithm competes with known best solutions across constrained and unconstrained problems: For all 26 real-world subjects, it equals or outperforms the best result previously reported in the literature. We also present evidence that our algorithm's strong generic performance results from its unsupervised learning. Hyperheuristic search is thus a promising way to relocate CIT design intelligence from human to machine.

Identifying equivalent mutants remains the largest impediment to the widespread uptake of mutation testing. Despite being researched for more than three decades, the problem remains. We propose Trivial Compiler Equivalence (TCE) a technique that exploits the use of readily available compiler technology to address this long-standing challenge. TCE is directly applicable to real-world programs and can imbue existing tools with the ability to detect equivalent mutants and a special form of useless mutants called duplicated mutants. We present a thorough empirical study using 6 large open source programs, several orders of magnitude larger than those used in previous work, and 18 benchmark programs with hand-analysis equivalent mutants. Our results reveal that, on large real-world programs, TCE can discard more than 7% and 21% of all the mutants as being equivalent and duplicated mutants respectively. A human- based equivalence verification reveals that TCE has the ability to detect approximately 30% of all the existing equivalent mutants.

Search Based Software Testing (SBST) formulates testing as an optimisation problem, which can be attacked using computational search techniques from the field of Search Based Software Engineering (SBSE). We present an analysis of the SBST research agenda, focusing on the open problems and challenges of testing non-functional properties, in particular a topic we call 'Search Based Energy Testing' (SBET), Multi-objective SBST and SBST for Test Strategy Identification. We conclude with a vision of FIFIVERIFY tools, which would automatically find faults, fix them and verify the fixes. We explain why we think such FIFIVERIFY tools constitute an exciting challenge for the SBSE community that already could be within its reach.

Automated transplantation would open many exciting avenues for software development: suppose we could autotransplant code from one system into another, entirely unrelated, system. This paper introduces a theory, an algorithm, and a tool that achieve this. Leveraging lightweight annotation, program analysis identifies an organ (interesting behavior to transplant); testing validates that the organ exhibits the desired behavior during its extraction and after its implantation into a host. While we do not claim automated transplantation is now a solved problem, our results are encouraging: we report that in 12 of 15 experiments, involving 5 donors and 3 hosts (all popular real-world systems), we successfully autotransplanted new functionality and passed all regression tests. Autotransplantation is also already useful: in 26 hours computation time we successfully autotransplanted the H.264 video encoding functionality from the x264 system to the VLC media player; compare this to upgrading x264 within VLC, a task that we estimate, from VLC's version history, took human programmers an average of 20 days of elapsed, as opposed to dedicated, time.

The aim of test case prioritisation is to determine an ordering of test cases that maximises the likelihood of early fault revelation. Previous prioritisation techniques have tended to be single objective, for which the additional greedy algorithm is the current state-of-the-art. Unlike test suite minimisation, multi objective test case prioritisation has not been thoroughly evaluated. This paper presents an extensive empirical study of the effectiveness of multi objective test case prioritisation, evaluating it on multiple versions of five widely-used benchmark programs and a much larger real world system of over 1 million lines of code. The paper also presents a lossless coverage compaction algorithm that dramatically scales the performance of all algorithms studied by between 2 and 4 orders of magnitude, making prioritisation practical for even very demanding problems.

Many papers on App Store Mining are susceptible to the App Sampling Problem, which exists when only a subset of apps are studied, resulting in potential sampling bias. We introduce the App Sampling Problem, and study its effects on sets of user review data. We investigate the effects of sampling bias, and techniques for its amelioration in App Store Mining and Analysis, where sampling bias is often unavoidable. We mine 106,891 requests from 2,729,103 user reviews and investigate the properties of apps and reviews from 3 different partitions: the sets with fully complete review data, partially complete review data, and no review data at all. We find that app metrics such as price, rating, and download rank are significantly different between the three completeness levels. We show that correlation analysis can find trends in the data that prevail across the partitions, offering one possible approach to App Store Analysis in the presence of sampling bias.

We introduce a theoretical characterisation of feature lifecycles in app stores, to help app developers to identify trends and to find undiscovered requirements. To illustrate and motivate app feature lifecycle analysis, we use our theory to empirically analyse the migratory and non-migratory behaviours of 4,053 non-free features from two App Stores (Samsung and BlackBerry). The results reveal that, in both stores, intransitive features (those that neither migrate nor die out) exhibit significantly different behaviours with regard to important properties, such as their price. Further correlation analysis also highlights differences between trends relating price, rating, and popularity. Our results indicate that feature lifecycle analysis can yield insights that may also help developers to understand feature behaviours and attribute relationships.

Observation-based slicing is a recently-introduced, language-independent slicing technique based on the dependencies observable from program behaviour. Due to the well-known limits of dynamic analysis, we may only compute an under-approximation of the true observation-based slice. However, because the observation-based slice captures all possible dependence that can be observed, even such approximations can yield insight into the limitations of static slicing. For example, a static slice, S, that is strictly smaller than the corresponding observation based slice is potentially unsafe. We present the results of three sets of experiments on 12 different programs, including benchmarks and larger programs, which investigate the relationship between static and observation-based slicing. We show that, in extreme cases, observation-based slices can find the true minimal static slice, where static techniques cannot. For more typical cases, our results illustrate the potential for observation-based slicing to highlight limitations in static slicers. Finally, we report on the sensitivity of observation-based slicing to test quality.

The Next Release Problem involves determining the set of requirements to implement in the next release of a software project. When the problem was first formulated in 2001, Integer Linear Programming, an exact method, was found to be impractical because of large execution times. Since then, the problem has mainly been addressed by employing metaheuristic techniques. In this paper, we investigate if the single-objective and bi-objective Next Release Problem can be solved exactly and how to better approximate the results when exact resolution is costly. We revisit Integer Linear Programming for the single-objective version of the problem. In addition, we integrate it within the Epsilon-constraint method to address the bi-objective problem. We also investigate how the Pareto front of the bi-objective problem can be approximated through an anytime deterministic Integer Linear Programming-based algorithm when results are required within strict runtime constraints. Comparisons are carried out against NSGA-II. Experiments are performed on a combination of synthetic and real-world datasets. We show that a modern Integer Linear Programming solver is now a viable method for this problem. Large single objective instances and small bi-objective instances can be solved exactly very quickly. On large bi-objective instances, execution times can be significant when calculating the complete Pareto front. However, good approximations can be found effectively. This study suggests that (1) approximation algorithms can be discarded in favor of the exact method for the single-objective instances and small bi-objective instances, (2) the Integer Linear Programming-based approximate algorithm outperforms the NSGA-II genetic approach on large bi-objective instances, and (3) the run times for both methods are low enough to be used in real-world situations.

It is our pleasure to introduce this special issue on Mutation Testing. The special issue contains nine papers, including four extended versions of papers presented at the 7th International Workshop on Mutation Analysis and five new submissions. We have divided the special issue into three broad areas based on the topics covered. The first area focuses on the techniques for making mutation testing more efficient and practical; the second area revisits some fundamental questions about mutants, whilst the third area presents some advanced applications of mutation testing for model-based testing. Mutation Testing has been proven to be an effective way to measure the quality of a test suite in terms of its ability to detect faults 1. The history of mutation testing can be traced back to 1971 in a publication by Richard Lipton 2 as well as in publications from the late 1970s by DeMillo et al. 3 and Hamlet 4. In Mutation Testing, faults are deliberately seeded into the original program (by simple syntactic changes) to create a set of faulty programs called mutants, each containing a different syntactic change. The general principle underpinning Mutation Testing is that artificial faults can be used to represent common programming mistakes. By carefully choosing the location within the program and the types of faults, it is possible to simulate any test adequacy criteria whilst providing improved fault detection. A recent survey on mutation testing provides evidence to suggest that the approach is increasing in maturity and practical application 5. One reason why mutation testing has become a popular testing approach is that it is a straightforward process to apply. To assess the quality of a given test set, the generated mutants are executed against the input test set. If the result of running a mutant is different from the result of running the original program for any test cases in the input test set, the seeded fault denoted by the mutant is detected. One outcome of the Mutation Testing process is the mutation score, which indicates the quality of the input test set. The mutation score is the ratio of the number of detected faults over the total number of seeded faults. Mutation Testing has been widely adopted in the academic community as a means to evaluate software testing techniques 6, as well as to generate tests and test oracles 7, 8. However, it still suffers from a number of problems that prevent the wider industrial uptake of this effective testing approach. One problem that prevents Mutation Testing from becoming a practical testing technique is the high computational cost of executing a large number of mutants against a test set. Other problems are related to the amount of effort involved in identifying equivalent mutants. Each submission received three reviews from a board of 36 mutation testing experts. For all submissions extended from the mutation workshop, we have recruited at least one new reviewer to ensure wider accessibility to a non-mutation expert testing audience. The first area covers the topic of making mutation testing more efficient and practical. The three papers in this area introduce novel techniques to optimize mutant execution, to reduce redundant mutants and to detect equivalent mutants. In the first paper 'Reducing Mutation Costs Through Uncovered Mutants', Pedro Reales Mateo and Macario Polo Usaola propose an improved mutant schema, namely, 'MUSIC' to reduce the execution cost for mutation testing. The MUSIC approach records runtime information about structural and mutation coverage; it reduces the execution cost by removing mutant execution tasks, which are not covered by the test cases. The second paper 'Higher Accuracy and Lower Run Time: Efficient Mutation Analysis using Non-redundant Mutation Operators' by René Just and Franz Schweiggert attempts to reduce the number of mutants by applying only non-redundant mutation operators. The authors identified a set of operators that tend to not generate any redundant mutants, and their results show that 20% of the runtime cost could be saved using the selected operators. The third paper 'Employing Second-order Mutation for Isolating First-order Equivalent Mutants' by Marinos Kintis, Mike Papadakis and Nicos Malevris seeks to automatically identify equivalent mutants through higher order mutation. Their approach combines impact analysis for both first-order and second-order mutants, and it achieved an equivalent mutant classification precision of 73% and a classification recall of 65%. The three papers in the second area revisit some fundamental questions about mutants and explore a new application of mutation testing. The first paper 'Quality Metrics for Mutation Testing with Applications to WS-BPEL Compositions' by Antonia Estero-Botaro, Francisco Palomo-Lozano, Inmaculada Medina-Bulo, Juan José Domínguez-Jiménez and Antonio García-Domínguez attempts to discover what it means for mutants to be effective. They formally define a set of metrics to measure the quality of mutation operators and evaluate them using WS-BPEL applications. The second paper 'MuRanker: a Mutant Ranking Tool' by Akbar Siami Namin, Xiaozhen Xue, Omar Rosas and Pankaj Sharma proposes metrics to measure the mutant complexity based on how easy or hard they are to kill. They implemented a prototype tool, MuRanker, which can help testers to prioritize the analysis of mutants based on their killing ability. The third paper 'Metallaxis-FL: Mutation-based Fault Localisation' by Mike Papadakis and Yves Le Traon explores the application of mutation testing for fault localization. This approach combines code coverage and mutation information to rank suspicious statements. The results show that it outperforms other traditional coverage-based fault detection approaches. The third area covers some advanced applications of mutation analysis for model-based testing techniques. This is an under-studied area compared with traditional program mutation. The first paper 'Using Mutation to Assess Fault Detection Capability of Model Review' by Paolo Arcaini, Angelo Gargantini and Elvinia Riccobene introduces a set of mutation operators for NuSMV Models. The mutant models simulate common behavioural faults and can be used to evaluate the fault detection ability of automated model review techniques. The second paper 'Towards an Automation of the Mutation Analysis Dedicated to Model Transformation' by Vincent Aranega, Jean-Marie Mottu, Anne Etien, Thomas Degueule, Benoit Baudry and Jean-Luc Dekeyser proposes to use mutation testing to test model transformations. They designed a set of mutation operators targeting three actions in model transformation: navigation, filtering and creation/modification. These are evaluated on the class2rdbms technique, which generates relational database management systems model from class diagrams. The third paper 'Model-based Mutation Testing from Security Protocols in HLPSL' by Frédéric Dadeau, Pierre-Cyrille Héam, Rafik Kheddam, Ghazi Maatoug and Michael Rusinowitch proposes a set of mutation operators to generate mutants for HLPSL security protocols. It also demonstrates that concretization test data generation techniques can be used to construct test scripts to kill the mutants. We wish to thank the authors and reviewers for their contributions to this special issue and Rob Hierons and Jeff Offutt for helping to manage the review process.

We show that the genetic improvement of programs (GIP) can scale by evolving increased performance in a widely-used and highly complex 50000 line system. Genetic improvement of software for multiple objective exploration (GISMOE) found code that is 70 times faster (on average) and yet is at least as good functionally. Indeed, it even gives a small semantic gain.

editorial Free AccessIntroduction to the Special Issue on ISSTA 2013 Editors: Mark Harman University College London, UK University College London, UKView Profile , Mauro Pezzé University of Milano Bicocca and University of Lugano University of Milano Bicocca and University of LuganoView Profile Authors Info & Claims ACM Transactions on Software Engineering and MethodologyVolume 24Issue 4August 2015 Article No.: 21pp 1–3https://doi.org/10.1145/2809789Published:02 September 2015Publication History 0citation219DownloadsMetricsTotal Citations0Total Downloads219Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Testing involves examining the behaviour of a system in order to discover potential faults. Given an input for a system, the challenge of distinguishing the corresponding desired, correct behaviour from potentially incorrect behavior is called the “test oracle problem”. Test oracle automation is important to remove a current bottleneck that inhibits greater overall test automation. Without test oracle automation, the human has to determine whether observed behaviour is correct. The literature on test oracles has introduced techniques for oracle automation, including modelling, specifications, contract-driven development and metamorphic testing. When none of these is completely adequate, the final source of test oracle information remains the human, who may be aware of informal specifications, expectations, norms and domain specific information that provide informal oracle guidance. All forms of test oracles, even the humble human, involve challenges of reducing cost and increasing benefit. This paper provides a comprehensive survey of current approaches to the test oracle problem and an analysis of trends in this important area of software testing research and practice.

Combinatorial interaction testing (CIT) is important because it tests the interactions between the many features and parameters that make up the configuration space of software systems. Simulated Annealing (SA) and Greedy Algorithms have been widely used to find CIT test suites. From the literature, there is a widely-held belief that SA is slower, but produces more effective tests suites than Greedy and that SA cannot scale to higher strength coverage. We evaluated both algorithms on seven real-world subjects for the well-studied two-way up to the rarely-studied six-way interaction strengths. Our findings present evidence to challenge this current orthodoxy: real-world constraints allow SA to achieve higher strengths. Furthermore, there was no evidence that Greedy was less effective (in terms of time to fault revelation) compared to SA; the results for the greedy algorithm are actually slightly superior. However, the results are critically dependent on the approach adopted to constraint handling. Moreover, we have also evaluated a genetic algorithm for constrained CIT test suite generation. This is the first time strengths higher than 3 and constraint handling have been used to evaluate GA. Our results show that GA is competitive only for pairwise testing for subjects with a small number of constraints.

Genetic Improvement (GI) is shown to optimise, in some cases by more than 35percent, a critical component of healthcare industry software across a diverse range of six nVidia graphics processing units (GPUs). GP and other search based software engineering techniques can automatically optimise the current rate limiting CUDA parallel function in the NiftyReg open source C++ project used to align or register high resolution nuclear magnetic resonance NMRI and other diagnostic NIfTI images. Future Neurosurgery techniques will require hardware acceleration, such as GPGPU, to enable real time comparison of three dimensional in theatre images with earlier patient images and reference data. With millimetre resolution brain scan measurements comprising more than ten million voxels the modified kernel can process in excess of 3 billion active voxels per second.

Uncertainty is inevitable in real world requirement engineering. It has a significant impact on the feasibility of proposed solutions and thus brings risks to the software release plan. This paper proposes a multi-objective optimization technique, augmented with Monte-Carlo Simulation, that optimizes requirement choices for the three objectives of cost, revenue, and uncertainty. The paper reports the results of an empirical study over four data sets derived from a single real world data set. The results show that the robust optimal solutions obtained by our approach are conservative compared to their corresponding optimal solutions produced by traditional Multi-Objective Next Release Problem. We obtain a robustness improvement of at least 18% at a small cost (a maximum 0.0285 shift in the 2D Pareto-front in the unit space). Surprisingly we found that, though a requirement's cost is correlated with inclusion on the Pareto-front, a requirement's expected revenue is not.

Failed error propagation (FEP) is known to hamper software testing, yet it remains poorly understood. We introduce an information theoretic formulation of FEP that is based on measures of conditional entropy. This formulation considers the situation in which we are interested in the potential for an incorrect program state at statement s to fail to propagate to incorrect output. We define five metrics that differ in two ways: whether we only consider parts of the program that can be reached after executing s and whether we restrict attention to a single program path of interest .We give the results of experiments in which it was found that on average one in 10 tests suffered from FEP, earlier studies having shown that this figure can vary significantly between programs. The experiments also showed that our metrics are well-correlated with FEP. Our empirical study involved 30 programs, for which we executed a total of 7,140,000 test cases. The results reveal that the metrics differ in their performance but the Spearman rank correlation with failed error propagation is close to 0.95 for two of the metrics. These strong correlations in an experimental setting, in which all information about both FEP and conditional entropy is known, open up the possibility in the longer term of devising inexpensive information theory based metrics that allow us to minimise the effect of FEP.

Though mutation testing has been widely studied for more than thirty years, the prevalence and properties of equivalent mutants remain largely unknown. We report on the causes and prevalence of equivalent mutants and their relationship to stubborn mutants (those that remain undetected by a high quality test suite, yet are non-equivalent). Our results, based on manual analysis of 1,230 mutants from 18 programs, reveal a highly uneven distribution of equivalence and stubbornness. For example, the ABS class and half UOI class generate many equivalent and almost no stubborn mutants, while the LCR class generates many stubborn and few equivalent mutants. We conclude that previous test effectiveness studies based on fault seeding could be skewed, while developers of mutation testing tools should prioritise those operators that we found generate disproportionately many stubborn (and few equivalent) mutants.

This paper studies the whitebox coverage and fault detection achieved by Output Uniqueness, a newly proposed blackbox test criterion, using 6 web applications. We find that output uniqueness exhibits average correlation coefficients of 0.85, 0.83 and 0.97 with statement, branch and path coverage respectively. More interestingly, output uniqueness finds 92% of the real faults found by branch coverage (and a further 47% that remained undetected by such whitebox techniques). These results suggest that output uniqueness may provide a useful surrogate when whitebox techniques are inapplicable and an effective complement where they are.

We study the simultaneous test effectiveness and efficiency improvement achievable by Strongly Subsuming Higher Order Mutants (SSHOMs), constructed from 15,792 first order mutants in four Java programs. Using SSHOMs in place of the first order mutants they subsume yielded a 35%-45% reduction in the number of mutants required, while simultaneously improving test efficiency by 15% and effectiveness by between 5.6% and 12%. Trivial first order faults often combine to form exceptionally non-trivial higher order faults; apparently innocuous angels can combine to breed monsters. Nevertheless, these same monsters can be recruited to improve automated test effectiveness and efficiency.

Recent work on genetic-programming-based approaches to automatic program patching have relied on the insight that the content of new code can often be assembled out of fragments of code that already exist in the code base. This insight has been dubbed the plastic surgery hypothesis; successful, well-known automatic repair tools such as GenProg rest on this hypothesis, but it has never been validated. We formalize and validate the plastic surgery hypothesis and empirically measure the extent to which raw material for changes actually already exists in projects. In this paper, we mount a large-scale study of several large Java projects, and examine a history of 15,723 commits to determine the extent to which these commits are graftable, i.e., can be reconstituted from existing code, and find an encouraging degree of graftability, surprisingly independent of commit size and type of commit. For example, we find that changes are 43% graftable from the exact version of the software being changed. With a view to investigating the difficulty of finding these grafts, we study the abundance of such grafts in three possible sources: the immediately previous version, prior history, and other projects. We also examine the contiguity or chunking of these grafts, and the degree to which grafts can be found in the same file. Our results are quite promising and suggest an optimistic future for automatic program patching methods that search for raw material in already extant code in the project being patched.

Current slicing techniques cannot handle systems written in multiple programming languages. Observation-Based Slicing (ORBS) is a language-independent slicing technique capable of slicing multi-language systems, including systems which contain (third party) binary components. A potential slice obtained through repeated statement deletion is validated by observing the behaviour of the program: if the slice and original program behave the same under the slicing criterion, the deletion is accepted. The resulting slice is similar to a dynamic slice. We evaluate five variants of ORBS on ten programs of different sizes and languages showing that it is less expensive than similar existing techniques. We also evaluate it on bash and four other systems to demonstrate feasible large-scale operation in which a parallelised ORBS needs up to 82% less time when using four threads. The results show that an ORBS slicer is simple to construct, effective at slicing, and able to handle systems written in multiple languages without specialist analysis tools.

This paper presents a survey of work on Search Based Software Engineering (SBSE) for Software Product Lines (SPLs). We have attempted to be comprehensive, in the sense that we have sought to include all papers that apply computational search techniques to problems in software product line engineering. Having surveyed the recent explosion in SBSE for SPL research activity, we highlight some directions for future work. We focus on suggestions for the development of recent advances in genetic improvement, showing how these might be exploited by SPL researchers and practitioners: Genetic improvement may grow new products with new functional and non-functional features and graft these into SPLs. It may also merge and parameterise multiple branches to cope with SPL branchmania.

This paper presents the results of a large scale empirical study of coherent dependence clusters. All statements in a coherent dependence cluster depend upon the same set of statements and affect the same set of statements; a coherent cluster's statements have ‘coherent’ shared backward and forward dependence. We introduce an approximation to efficiently locate coherent clusters and show that it has a minimum precision of 97.76%. Our empirical study also finds that, despite their tight coherence constraints, coherent dependence clusters are in abundance: 23 of the 30 programs studied have coherent clusters that contain at least 10% of the whole program. Studying patterns of clustering in these programs reveals that most programs contain multiple substantial coherent clusters. A series of subsequent case studies uncover that all clusters of significant size map to a logical functionality and correspond to a program structure. For example, we show that for the program acct, the top five coherent clusters all map to specific, yet otherwise non-obvious, functionality. Cluster visualization also brings out subtle deficiencies in program structure and identifies potential refactoring candidates. A study of inter-cluster dependence is used to highlight how coherent clusters are connected to each other, revealing higher-level structures, which can be used in reverse engineering. Finally, studies are presented to illustrate how clusters are not correlated with program faults as they remain stable during most system evolution.

The nature of the requirements analysis problem, based as it is on uncertain and often inaccurate estimates of costs and effort, makes sensitivity analysis important. Sensitivity analysis allows the decision maker to identify those requirements and budgets that are particularly sensitive to misestimation. However, finding scalable sensitivity analysis techniques is not easy because the underlying optimization problem is NP-hard. This article introduces an approach to sensitivity analysis based on exact optimization. We implemented this approach as a tool, O ATSAC , which allowed us to experimentally evaluate the scalability and applicability of Requirements Sensitivity Analysis (RSA). Our results show that O ATSAC scales sufficiently well for practical applications in Requirements Sensitivity Analysis. We also show how the sensitivity analysis can yield insights into difficult and otherwise obscure interactions between budgets, requirements costs, and estimate inaccuracies using a real-world case study.

Software Engineering and development is well-known to suffer from unplanned overtime, which causes stress and illness in engineers and can lead to poor quality software with higher defects. In this paper, we introduce a multi-objective decision support approach to help balance project risks and duration against overtime, so that software engineers can better plan overtime. We evaluate our approach on 6 real world software projects, drawn from 3 organisations using 3 standard evaluation measures and 3 different approaches to risk assessment. Our results show that our approach was significantly better (p <; 0.05) than standard multi-objective search in 76% of experiments (with high Cohen effect size in 85% of these) and was significantly better than currently used overtime planning strategies in 100% of experiments (with high effect size in all). We also show how our approach provides actionable overtime planning results and investigate the impact of the three different forms of risk assessment.

Modelling plays a vital and pervasive role in software engineering: it provides means to manage complexity via abstraction, and enables the creation of larger, more complex systems. Search-based software engineering (SBSE) offers a productive and proven approach to software engineering through automated discovery of near-optimal solutions to problems, and has proven itself to be effective on a wide variety of software-and systems engineering problems. CMSBSE 2013 was a forum allowing researchers from both communities to meet, discuss synergies and differences, and present topics related to the intersection of search and modelling. Particular goals of CMSBSE were to highlight that SBSE and modelling have substantial conceptual and technical synergy, and to identify and present opportunities in which they can be combined, whilst also aiming to grow the community working in this area.

Many organisations have turned to crowdsource their software development projects. This raises important pricing questions, a problem that has not previously been addressed for the emerging crowdsourcing development paradigm. We address this problem by introducing 16 cost drivers for crowdsourced development activities and evaluate 12 predictive pricing models using 4 popular performance measures. We evaluate our predictive models on TopCoder, the largest current crowdsourcing platform for software development. We analyse all 5,910 software development tasks (for which partial data is available), using these to extract our proposed cost drivers. We evaluate our predictive models using the 490 completed projects (for which full details are available). Our results provide evidence to support our primary finding that useful prediction quality is achievable (Pred(30)>0.8). We also show that simple actionable advice can be extracted from our models to assist the 430,000 developers who are members of the TopCoder software development market.

Can the methods of empirical software engineering give us answers to the truly important open questions in the field?

Combinatorial Interaction Testing (CIT) is important because it tests the interactions between the many features and parameters that make up the configuration space of software systems. However, in order to be practically applicable, it must be able to cater for soft and hard real-world constraints and should, ideally, report a test priority order that maximises earliest fault detection. We show that we can achieve the highest strength CIT in 5.65 minutes on average. This was previously thought to be too computationally expensive to be feasible. Furthermore, we show that higher strength suites find more faults, while prioritisations using lower strengths are no worse at achieving early fault revelation.

Clone detection finds application in many software engineering activities such as comprehension and refactoring. However, the confounding configuration choice problem poses a widely-acknowledged threat to the validity of previous empirical analyses. We introduce desktop and parallelised cloud-deployed versions of a search based solution that finds suitable configurations for empirical studies. We evaluate our approach on 6 widely used clone detection tools applied to the Bellon suite of 8 subject systems. Our evaluation reports the results of 9.3 million total executions of a clone tool; the largest study yet reported. Our approach finds significantly better configurations (p < 0.05) than those currently used, providing evidence that our approach can ameliorate the confounding configuration choice problem.

Many of the problems posed by the migration of computation to cloud platforms can be formulated and solved using techniques associated with Search Based Software Engineering (SBSE). Much of cloud software engineering involves problems of optimisation: performance, allocation, assignment and the dynamic balancing of resources to achieve pragmatic trade-offs between many competing technical and business objectives. SBSE is concerned with the application of computational search and optimisation to solve precisely these kinds of software engineering challenges. Interest in both cloud computing and SBSE has grown rapidly in the past five years, yet there has been little work on SBSE as a means of addressing cloud computing challenges. Like many computationally demanding activities, SBSE has the potential to benefit from the cloud; ‘SBSE in the cloud’. However, this paper focuses, instead, of the ways in which SBSE can benefit cloud computing. It thus develops the theme of ‘SBSE for the cloud’, formulating cloud computing challenges in ways that can be addressed using SBSE.

SUMMARY Service‐oriented architecture (SOA) is gaining momentum as an emerging distributed system architecture for business‐to‐business collaborations. This momentum can be observed in both industry and academic research. SOA presents new challenges and opportunities for testing and verification, leading to an upsurge in research. This paper surveys the previous work undertaken on testing and verification of service‐centric systems, which in total are 177 papers, showing the strengths and weaknesses of current strategies and testing tools and identifying issues for future work. Copyright © 2012 John Wiley & Sons, Ltd.

The 4th International Conference on Software Testing, Verification, and Validation (ICST 2011) was held on 21-25 March 2011, in Berlin, Germany. The aim of the ICST conference is to bring together researchers and practitioners who study the theory, techniques, technologies, and applications that concern all aspects of software testing, verification, and validation of software systems. The ICST 2011 program chairs, Mark Harman and Bogdan Korel, selected 35 research papers for inclusion in the proceedings from among 166 submissions. All papers were refereed by at least three program committee members. Of the 35 papers accepted, we selected six papers for consideration for this special issue of STVR. These papers were extended from their conference version by the authors and were reviewed according to the STVR reviewing process. Five papers successfully completed the review process and are contained in this special issue. These papers are spread across two special issues of STVR. This issue includes the first three papers. The rest of this editorial provides a brief overview of these three papers. The first paper, ‘Configuring Effective Navigation Models and Abstract Test Cases for Web Applications by Analyzing User Behavior’ by Sara Sprenkle, Lori Pollock and Lucy Simko, reports on an exploratory study of automatically generated abstract test cases and the underlying usage-based navigation models for Web applications. The results suggest that web testers can easily configure statistical model-based automated test generators to generate tests closely related to user behaviour. The second paper, ‘Testing of Data-Centric and Event-Based Dynamic Service Compositions’ by Waldemar Hummer, Orna Raz, Onn Shehory, Philipp Leitner, and Schahram Dustdar, investigates integration testing of data-centric and event-based dynamic service compositions with an emphasis on data-flow centric coverage goals. The evaluation of the presented approach for different performance characteristics demonstrates the end-to-end practicability of the approach. The third paper, ‘Demand-driven Propagation-based Strategies for Testing Changes’ by Raul Santelices and Mary Jean Harrold, presents a novel, demand-driven approach for performing the propagation-based testing of changes. The experimental study shows that the approach can be practical and can scale to large programs.

This is the second of two volumes of the Special Issue on Software Testing, Verification, and Validation (STVR). Five papers successfully completed the review process. These papers are spread across two special issues of STVR. The previous issue of STVR includes the first three papers. This issue includes the remaining two papers. The rest of this editorial provides a brief overview of these two papers. The first paper, ’Checked Coverage: An Indicator for Oracle Quality’ by David Schuler and Andreas Zeller, proposes an approach to assess oracle quality. The concept of checked coverage is introduced – the dynamic slice of covered statements. The results of the experimental study suggest that the checked coverage is a good indicator for oracle quality, The second paper, ’Handling Test Length Bloat’ by Gordon Fraser and Andrea Arcuri, investigates the effect of test length and bloat in the context of testing object-oriented software, where test cases are sequences of method calls. The bloat occurs when the test length abnormally grows over time during search-based test generation. Techniques to overcome the length bloat are presented. The results of an experimental study demonstrate that these techniques can improve the performance of the search process. In conclusion, we would like to thank the authors of this and the previous special issue for preparing the extended versions of the ICST-2011 conference papers. We are particularly thankful to all reviewers for timely and constructive reviews. Finally, we hope that this special issue will be stimulating for many practitioners and researchers and will help in advancing the knowledge and research in software testing, verification, and validation.

Several authors have found evidence of large dependence clusters in the source code of a diverse range of systems, domains, and programming languages. This raises the question of how we might efficiently locate the fragments of code that give rise to large dependence clusters. We introduce an algorithm for the identification of linchpin vertices, which hold together large dependence clusters, and prove correctness properties for the algorithm’s primary innovations. We also report the results of an empirical study concerning the reduction in analysis time that our algorithm yields over its predecessor using a collection of 38 programs containing almost half a million lines of code. Our empirical findings indicate improvements of almost two orders of magnitude, making it possible to process larger programs for which it would have previously been impractical.

Test case prioritization techniques seek to maximize early fault detection. Fault localization seeks to use test cases already executed to help find the fault location. There is a natural interplay between the two techniques; once a fault is detected, we often switch focus to fault fixing, for which localization may be a first step. In this article we introduce the Fault Localization Prioritization (FLP) problem, which combines prioritization and localization. We evaluate three techniques: a novel FLP technique based on information theory, FLINT (Fault Localization using INformation Theory), that we introduce in this article, a standard Test Case Prioritization (TCP) technique, and a “test similarity technique” used in previous work. Our evaluation uses five different releases of four software systems. The results indicate that FLP and TCP can statistically significantly reduce fault localization costs for 73% and 76% of cases, respectively, and that FLINT significantly outperforms similarity-based localization techniques in 52% of the cases considered in the study.

Slicing is useful for many software engineering applications and has been widely studied for three decades, but there has been comparatively little work on slicing extended finite state machines (EFSMs). This paper introduces a set of dependence-based EFSM slicing algorithms and an accompanying tool. We demonstrate that our algorithms are suitable for dependence-based slicing. We use our tool to conduct experiments on 10 EFSMs, including benchmarks and industrial EFSMs. Ours is the first empirical study of dependence-based program slicing for EFSMs. Compared to the only previously published dependence-based algorithm, our average slice is smaller 40 percent of the time and larger only 10 percent of the time, with an average slice size of 35 percent for termination insensitive slicing.

A large number of software metrics have been proposed in the literature, but there is little understanding of how these metrics relate to one another. We propose a novel experimental technique, based on search-based refactoring, to assess software metrics and to explore relationships between them. Our goal is not to improve the program being refactored, but to assess the software metrics that guide the auto- mated refactoring through repeated refactoring experiments.

Search Based Software Engineering (SBSE) has proved to be a very effective way of optimising software engineering problems. Nevertheless, its full potential as a means of dynamic adaptivity remains under explored. This paper sets out the agenda for Dynamic Adaptive SBSE, in which the optimisation is embedded into deployed software to create self-optimising adaptive systems. Dynamic Adaptive SBSE will move the research agenda forward to encompass both software development processes and the software products they produce, addressing the long-standing, and as yet largely unsolved, grand challenge of self-adaptive systems.

The uniqueness (or otherwise) of test outputs ought to have a bearing on test effectiveness, yet it has not previously been studied. In this paper we introduce a novel test suite adequacy criterion based on output uniqueness. We propose 4 definitions of output uniqueness with varying degrees of strictness. We present a preliminary evaluation for web application testing that confirms that output uniqueness enhances fault-finding effectiveness. The approach outperforms random augmentation in fault finding ability by an overall average of 280% in 5 medium sized, real world web applications.

Automated web crawlers can be used to explore and exercise portions of a web application under test. However, the possibility to achieve full exploration of a web application through automated crawling is severely limited by the choice of the input values submitted with forms. Depending on the crawler's capabilities, a larger or smaller portion of web application will be automatically explored. In this paper, we introduce web crawl ability metrics to quantify properties of application pages and forms that affect crawl ability. Moreover, we show that our metrics can be used to identify the boundaries between those parts of the application that can be successfully crawled automatically and those parts that will require manual intervention or other crawl ability support. We have validated our crawl ability metrics on real web applications, for which low crawl ability was indeed associated with the existence of pages never exercised during automated crawling.

Models inferred from execution traces (logs) may admit more behaviours than those possible in the real system (over-approximation) or may exclude behaviours that can indeed occur in the real system (under-approximation). Both problems negatively affect model based testing. In fact, over-approximation results in infeasible test cases, i.e., test cases that cannot be activated by any input data. Under-approximation results in missing test cases, i.e., system behaviours that are not represented in the model are also never tested. In this paper we balance over- and under-approximation of inferred models by resorting to multi-objective optimization achieved by means of two search-based algorithms: A multi-objective Genetic Algorithm (GA) and the NSGA-II. We report the results on two open-source web applications and compare the multi-objective optimization to the state-of-the-art KLFA tool. We show that it is possible to identify regions in the Pareto front that contain models which violate fewer application constraints and have a higher bug detection ratio. The Pareto fronts generated by the multi-objective GA contain a region where models violate on average 2% of an application's constraints, compared to 2.8% for NSGA-II and 28.3% for the KLFA models. Similarly, it is possible to identify a region on the Pareto front where the multi-objective GA inferred models have an average bug detection ratio of 110 : 3 and the NSGA-II inferred models have an average bug detection ratio of 101 : 6. This compares to a bug detection ratio of 310928 : 13 for the KLFA tool.

This paper introduces two test cases regeneration approaches for web applications, one uses standard Def-Use testing but for state variables, the other uses a novel value-aware dataflow approach. Our overall approach is to combine requests from a test suite to form client-side request sequences, based on dataflow analysis of server-side session variables and database tables. We implemented our approach as a tool SART (State Aware Regeneration Tool) and used it to evaluate our proposed approaches on 4 real world web applications. Our results show that for all 4 applications, both server-side coverage and fault detection were statistically significantly improved. Even on relatively high quality test suites our algorithms improve average coverage by 14.74% and fault detection by 9.19%.

Optimising programs for non-functional properties such as speed, size, throughput, power consumption and bandwidth can be demanding; pity the poor programmer who is asked to cater for them all at once! We set out an alternate vision for a new kind of software development environment inspired by recent results from Search Based Software Engineering (SBSE). Given an input program that satisfies the functional requirements, the proposed programming environment will automatically generate a set of candidate program implementations, all of which share functionality, but each of which differ in their non-functional trade offs. The software designer navigates this diverse Pareto surface of candidate implementations, gaining insight into the trade offs and selecting solutions for different platforms and environments, thereby stretching beyond the reach of current compiler technologies. Rather than having to focus on the details required to manage complex, inter-related and conflicting, non-functional trade offs, the designer is thus freed to explore, to understand, to control and to decide rather than to construct.

This paper introduces app store mining and analysis as a form of software repository mining. Unlike other software repositories traditionally used in MSR work, app stores usually do not provide source code. However, they do provide a wealth of other information in the form of pricing and customer reviews. Therefore, we use data mining to extract feature information, which we then combine with more readily available information to analyse apps' technical, customer and business aspects. We applied our approach to the 32,108 non-zero priced apps available in the Blackberry app store in September 2011. Our results show that there is a strong correlation between customer rating and the rank of app downloads, though perhaps surprisingly, there is no correlation between price and downloads, nor between price and rating. More importantly, we show that these correlation findings carry over to (and are even occasionally enhanced within) the space of data mined app features, providing evidence that our `App store MSR' approach can be valuable to app developers.

This is an overview of the keynote presentation on SBSE at the Sixth IEEE International Symposium on Theoretical Aspects of Software Engineering (TASE 2012), held on the 4th-6th July 2012 in Beijing, China.

SUMMARY During regression testing, a modified system is often retested using an existing test suite. Since the size of the test suite may be very large, testers are interested in detecting faults in the modified system as early as possible during this retesting process. Test prioritization attempts to order tests for execution so that the chances of early detection of faults during retesting are increased. The existing prioritization methods are based on the source code of the system under test. In this paper, we present and evaluate two model‐based selective methods and a dependence‐based method of test prioritization utilizing the state‐based model of the system under test. These methods assume that the modifications are made both on the system under test and its model. The existing test suite is executed on the system model and information about this execution is used to prioritize tests. Execution of the model is inexpensive as compared with execution of the system under test; therefore, the overhead associated with test prioritization is relatively small. In addition, we present an analytical framework for evaluation of test prioritization methods. This framework may reduce the cost of evaluation as compared with the framework that is based on observation. We have performed an empirical study in which we compared different test prioritization methods. The results of the empirical study suggest that system models may improve the effectiveness of test prioritization with respect to early fault detection. Copyright © 2011 John Wiley & Sons, Ltd.

Regression testing is a testing activity that is performed to provide confidence that changes do not harm the existing behaviour of the software. Test suites tend to grow in size as software evolves, often making it too costly to execute entire test suites. A number of different approaches have been studied to maximize the value of the accrued test suite: minimization, selection and prioritization. Test suite minimization seeks to eliminate redundant test cases in order to reduce the number of tests to run. Test case selection seeks to identify the test cases that are relevant to some set of recent changes. Test case prioritization seeks to order test cases in such a way that early fault detection is maximized. This paper surveys each area of minimization, selection and prioritization technique and discusses open problems and potential directions for future research. Copyright (C) 2010 John Wiley & Sons, Ltd.

SUMMARY Existing automated test data generation techniques tend to start from scratch, implicitly assuming that no pre‐existing test data are available. However, this assumption may not always hold, and where it does not, there may be a missed opportunity; perhaps the pre‐existing test cases could be used to assist the automated generation of additional test cases. This paper introduces search‐based test data regeneration, a technique that can generate additional test data from existing test data using a meta‐heuristic search algorithm. The proposed technique is compared to a widely studied test data generation approach in terms of both efficiency and effectiveness. The empirical evaluation shows that test data regeneration can be up to 2 orders of magnitude more efficient than existing test data generation techniques, while achieving comparable effectiveness in terms of structural coverage and mutation score. Copyright © 2010 John Wiley & Sons, Ltd.

Search-Based Test Data Generation reformulates testing goals as fitness functions so that test input generation can be automated by some chosen search-based optimization algorithm. The optimization algorithm searches the space of potential inputs, seeking those that are “fit for purpose,” guided by the fitness function. The search space of potential inputs can be very large, even for very small systems under test. Its size is, of course, a key determining factor affecting the performance of any search-based approach. However, despite the large volume of work on Search-Based Software Testing, the literature contains little that concerns the performance impact of search space reduction. This paper proposes a static dependence analysis derived from program slicing that can be used to support search space reduction. The paper presents both a theoretical and empirical analysis of the application of this approach to open source and industrial production code. The results provide evidence to support the claim that input domain reduction has a significant effect on the performance of local, global, and hybrid search, while a purely random search is unaffected.

This paper introduces a messy-GA for transition coverage of Simulink/StateFlow models. We introduce a tool that implements our approach and evaluate it on three benchmark embedded system Simulink models. Our messy-GA is able to achieve statistically significantly better coverage when compared to both random search and to a commercial tool for Simulink/StateFlow model Testing.

This paper introduces Model Projection. Finite state models such as Extended Finite State Machines are being used in an ever increasing number of software engineering activities. Model projection facilitates model development by specializing models for a specific operating environment. A projection is useful in many design-level applications including specification reuse and property verification.

This paper introduces three related algorithms and a tool, SWAT, for automated web application testing using Search Based Software Testing (SBST). The algorithms significantly enhance the efficiency and effectiveness of traditional search based techniques exploiting both static and dynamic analysis. The combined approach yields a 54% increase in branch coverage and a 30% reduction in test effort. Each improvement is separately evaluated in an empirical study on 6 real world web applications.

We present an algorithm for constructing fitness functions that improve the efficiency of search-based testing when trying to generate branch adequate test data. The algorithm combines symbolic information with dynamic analysis and has two key advantages: It does not require any change in the underlying test data generation technique and it avoids many problems traditionally associated with symbolic execution, in particular the presence of loops. We have evaluated the algorithm on industrial closed source and open source systems using both local and global search-based testing techniques, demonstrating that both are statistically significantly more efficient using our approach. The test for significance was done using a one-sided, paired Wilcoxon signed rank test. On average, the local search requires 23.41% and the global search 7.78% fewer fitness evaluations when using a symbolic execution based fitness function generated by the algorithm.

This paper introduces SHOM, a mutation-based test data generation approach that combines Dynamic Symbolic Execution and Search Based Software Testing. SHOM targets strong mutation adequacy and is capable of killing both first and higher order mutants. We report the results of an empirical study using 17 programs, including production industrial code from ABB and Daimler and open source code as well as previously studied subjects. SHOM achieved higher strong mutation adequacy than two recent mutation-based test data generation approaches, killing between 8% and 38% of those mutants left unkilled by the best performing previous approach.

Abstract Allocating resources to a software project and assigning tasks to teams constitute crucial activities that affect project cost and completion time. Finding a solution for such a problem is NP‐hard; this requires managers to be supported by proper tools for performing such an allocation. This paper shows how search‐based optimization techniques can be combined with a queuing simulation model to address these problems. The obtained staff and task allocations aim to minimize the completion time and reduce schedule fragmentation. The proposed approach allows project managers to run multiple simulations, compare results and consider trade‐offs between increasing the staffing level and anticipating the project completion date and between reducing the fragmentation and accepting project delays. The paper presents results from the application of the proposed search‐based project planning approach to data obtained from two large‐scale commercial software maintenance projects. Copyright © 2011 John Wiley & Sons, Ltd.

Search-Based Testing is a widely studied technique for automatically generating test inputs, with the aim of reducing the cost of software engineering activities that rely upon testing. However, search-based approaches degenerate to random testing in the presence of flag variables, because flags create spikes and plateaux in the fitness landscape. Both these features are known to denote hard optimization problems for all search-based optimization techniques. Several authors have studied flag removal transformations and fitness function refinements to address the issue of flags, but the problem of loop-assigned flags remains unsolved. This article introduces a testability transformation along with a tool that transforms programs with loop-assigned flags into flag-free equivalents, so that existing search-based test data generation approaches can successfully be applied. The article presents the results of an empirical study that demonstrates the effectiveness and efficiency of the testability transformation on programs including those made up of open source and industrial production code, as well as test data generation problems specifically created to denote hard optimization problems.

Mutation Testing is a fault-based software testing technique that has been widely studied for over three decades. The literature on Mutation Testing has contributed a set of approaches, tools, developments, and empirical results. This paper provides a comprehensive analysis and survey of Mutation Testing. The paper also presents the results of several development trend analyses. These analyses provide evidence that Mutation Testing techniques and tools are reaching a state of maturity and applicability, while the topic of Mutation Testing itself is the subject of increasing interest.

Software module clustering is the problem of automatically organizing software units into modules to improve program structure. There has been a great deal of recent interest in search-based formulations of this problem in which module boundaries are identified by automated search, guided by a fitness function that captures the twin objectives of high cohesion and low coupling in a single-objective fitness function. This paper introduces two novel multi-objective formulations of the software module clustering problem, in which several different objectives (including cohesion and coupling) are represented separately. In order to evaluate the effectiveness of the multi-objective approach, a set of experiments was performed on 17 real-world module clustering problems. The results of this empirical study provide strong evidence to support the claim that the multi-objective approach produces significantly better solutions than the existing single-objective approach.

Rather than attempting to evolve a complete program from scratch we demonstrate genetic interface programming (GIP) by automatically generating a parallel CUDA kernel with identical functionality to existing highly optimised ancient sequential C code (gzip). Generic GPGPU nVidia kernel C++ code is converted into a BNF grammar. Strongly typed genetic programming uses the BNF to generate compilable and executable graphics card kernels. Their fitness is given by running the population on a GPU with randomised subsets of training data itself derived from gzip's SIR test suite. Back-to-back validation uses the original code as a test oracle.

SBSE techniques have been widely applied to requirements selection and prioritization problems in order to ascertain a suitable set of requirements for the next release of a system. Unfortunately, it has been widely observed that requirements tend to be changed as the development process proceeds and what is suitable for today, may not serve well into the future. Though SBSE has been widely applied to requirements analysis, there has been no previous work that seeks to balance the requirements needs of today with those of the future. This paper addresses this problem. It introduces a multi-objective formulation of the problem which is implemented using multi-objective Pareto optimal evolutionary algorithms. The paper presents the results of experiments on both synthetic and real world data. Copyright 2010 ACM.

Large clusters of mutual dependence can cause problems for comprehension, testing and maintenance. This paper introduces the concept of coherent dependence clusters, techniques for their efficient identification, visualizations to better understand them, empirical results concerning their practical significance. As the paper will show, coherent dependence clusters facilitate a fine grained analysis of the subtle relationships between clusters of dependence.

This paper makes a case for Source Code Analysis and Manipulation. The paper argues that it will not only remain important, but that its importance will continue to grow. This argument is partly based on the 'law' of tendency to executability, which the paper introduces. The paper also makes a case for Source Code Analysis purely for the sake of analysis. Analysis for its own sake may not be merely indulgent introspection. The paper argues that it may ultimately prove to be hugely important as source code gradually gathers together all aspects of human socioeconomic and governmental processes and systems.

Search-based optimization techniques have been applied to structural software test data generation since 1992, with a recent upsurge in interest and activity within this area. However, despite the large number of recent studies on the applicability of different search-based optimization approaches, there has been very little theoretical analysis of the types of testing problem for which these techniques are well suited. There are also few empirical studies that present results for larger programs. This paper presents a theoretical exploration of the most widely studied approach, the global search technique embodied by Genetic Algorithms. It also presents results from a large empirical study that compares the behavior of both global and local search-based optimization on real-world programs. The results of this study reveal that cases exist of test data generation problem that suit each algorithm, thereby suggesting that a hybrid global-local search (a Memetic Algorithm) may be appropriate. The paper presents a Memetic Algorithm along with further empirical results studying its performance.

All large-scale projects contain a degree of risk and uncertainty. Software projects are particularly vulnerable to overruns, due to the this uncertainty and the inherent difficulty of software project cost estimation. In this paper we introduce a search based approach to software project robustness. The approach is to formulate this problem as a multi objective Search Based Software Engineering problem, in which robustness and completion time are treated as two competing objectives. The paper presents the results of the application of this new approach to four large real-world software projects, using two different models of uncertainty.

Software engineering is plagued by problems associated with unreliable cost estimates. This paper introduces an approach to sensitivity analysis for requirements engineering. It uses Search-Based Software Engineering to aid the decision maker to explore sensitivity of the cost estimates of requirements for the Next Release Problem (NRP). The paper presents both single- and multi-objective formulation of NRP with empirical sensitivity analysis on synthetic and real-world data. The results show strong correlation between the level of inaccuracy and the impact on the selection of requirements, as well as between the cost of requirements and the impact, which is as intuitively expected. However, there also exist a few sensitive exceptions to these trends; the paper uses a heat-map style visualisation to reveal these exceptions which require careful consideration. The paper also shows that such unusually sensitivity patterns occur in real-world data and how the proposed approach clearly identifies them.

Mutation testing is a powerful software engineering technique for fault finding. It works by injecting known faults (mutations) into software and seeing if the test suite finds them. It remains very expensive and the few valuable traditional mutants that resemble real faults are mixed in with many others that denote unrealistic faults. The expense and lack of realism inhibit industrial uptake of mutation testing. Genetic programming searches the space of complex faults to find realistic higher order mutants. Despite the much larger search space, we have found mutants composed of multiple changes to the C source code that challenge the tester and which cannot be represented in the first order space.

Dependence analysis underpins many activities in software maintenance such as comprehension and impact analysis. As a result, dependence has been studied widely for programming languages, notably through work on program slicing. However, there is comparatively little work on dependence analysis at the model level and hitherto, no empirical studies. We introduce a slicing tool for Extended Finite State Machines (EFSMs) and use the tool to gather empirical results on several forms of dependence found in ten EFSMs, including well-known benchmarks in addition to real-world EFSM models. We investigate the statistical properties of dependence using statistical tests for correlation and formalize and prove four of the empirical findings arising from our empirical study. The paper thus provides the maintainer with both empirical data and foundational theoretical results concerning dependence in EFSM models.

Pair-wise comparison has been successfully utilised in order to prioritise test cases by exploiting the rich, valuable and unique knowledge of the tester. However, the prohibitively large cost of the pair-wise comparison method prevents it from being applied to large test suites. In this paper, we introduce a cluster-based test case prioritisation technique. By clustering test cases, based on their dynamic runtime behaviour, we can reduce the required number of pair-wise comparisons significantly. The approach is evaluated on seven test suites ranging in size from 154 to 1,061 test cases. We present an empirical study that shows that the resulting prioritisation is more effective than existing coverage-based prioritisation techniques in terms of rate of fault detection. Perhaps surprisingly, the paper also demonstrates that clustering (even without human input) can outperform unclustered coverage-based technologies, and discusses an automated process that can be used to determine whether the application of the proposed approach would yield improvement.

A dependence cluster is a maximal set of program components that all depend upon one another. Previous work has highlighted the prevalence of large dependence clusters in source code, presenting potential problems for comprehension, testing, and maintenance. This paper is concerned with source code analysis techniques for identifying the causes of large dependence clusters. The paper presents results of a study of low-level causes of dependence clusters, which reveals that a large cluster can be caused by the smallest atomic unit source code: a single vertex or edge of the program's dependence graph. These are termed the linchpin vertices and edges in this paper.

A dependence cluster is a set of program statements, all of which are mutually inter-dependent. This article reports a large scale empirical study of dependence clusters in C program source code. The study reveals that large dependence clusters are surprisingly commonplace. Most of the 45 programs studied have clusters of dependence that consume more than 10% of the whole program. Some even have clusters consuming 80% or more. The widespread existence of clusters has implications for source code analyses such as program comprehension, software maintenance, software testing, reverse engineering, reuse, and parallelization.

Evolutionary testing is an approach to automating test data generation that uses an evolutionary algorithm to search a test object's input domain for test data. Nested predicates can cause problems for evolutionary testing, because information needed for guiding the search only becomes available as each nested conditional is satisfied. This means that the search process can overfit to early information, making it harder, and sometimes near impossible, to satisfy constraints that only become apparent later in the search. The article presents a testability transformation that allows the evaluation of all nested conditionals at once. Two empirical studies are presented. The first study shows that the form of nesting handled is prevalent in practice. The second study shows how the approach improves evolutionary test data generation.

There has been little attention to search based test data generation in the presence of pointer inputs and dynamic data structures, an area in which recent concolic methods have excelled. This paper introduces a search based testing approach which is able to handle pointers and dynamic data structures. It combines an alternating variable hill climb with a set of constraint solving rules for pointer inputs. The result is a lightweight and efficient method, as shown in the results from a case study, which compares the method to CUTE, a concolic unit testing tool.

This paper introduces an approach to web application regression testing, based upon repair of user session data. The approach is entirely automated. It consists of a white box examination of the structure of the changed web application to detect changes and a set of techniques to map these detected changes onto repair actions. The paper reports the results of experiments that explore both the performance and effectiveness of the approach. The effectiveness experiment uses an implementation of the repair algorithm applied to the online bookstore application over a series of 10 releases.

Requirements engineering for multiple customers, each of whom have competing and often conflicting priorities, raises issues of negotiation, mediation and conflict resolution. This paper uses a multi-objective optimisation approach to support investigation of the trade-offs in various notions of fairness between multiple customers. Results are presented to validate the approach using two real-world data sets and also using data sets created specifically to stress test the approach. Simple graphical techniques are used to visualize the solution space.

Key Statement Analysis extracts from a program, statements that form the core of the program’s computation. A good set of key statements is small but has a large impact. Key statements form a useful starting point for understanding and manipulating a program. An empirical investigation of three kinds of key statements is presented. The three are based on Bieman and Ott’s principal variables. To be effective, the key statements must have high impact and form a small, highly cohesive unit. Using a minor improvement of metrics for measuring impact and cohesion, key statements are shown to capture about 75% of the semantic effect of the function from which they are drawn. At the same time, they have cohesion about 20 percentage points higher than the corresponding function. A statistical analysis of the differences shows that key statements have higher average impact and higher average cohesion (p≪0.001).

Traditional mutation testing considers only first order mutants, created by the injection of a single fault. Often these first order mutants denote trivial faults that are easily killed. This paper investigates higher order mutants (HOMs). It introduces the concept of a subsuming HOM; one that is harder to kill than the first order mutants from which it is constructed. By definition, subsuming HOMs denote subtle fault combinations. The paper reports the results of an empirical study into subsuming HOMs, using six benchmark programs. This is the largest study of mutation testing to date. To overcome the exponential explosion in the number of mutants considered, the paper introduces a search based approach to the identification of subsuming HOMs. Results are presented for a greedy algorithm, a genetic algorithm and a hill climbing algorithm.

Special Issue on

The first ‘Testing: Academic & Industrial Conference—Practice and Research Techniques’ (TAIC PART 2006) was held at Cumberland Lodge Windsor during 29–31 August 2006. The general chair was Mark Harman (King's College London), the programme chair was Phil McMinn (University of Sheffield), and the local arrangements chair was Zheng Li (King's College London). TAIC PART is firmly grounded in fostering collaboration between industry and academia. It aims to bring together industrial software developers and users together with academic researchers working on the theory and practice of software testing. TAIC PART 2006 was a unique, not-for-profit conference that combined what we believe to be the best aspects of three kinds of event: a formal academic conference, a research workshop, and a retreat. The aim was to act not only as a forum for the exchange of ideas, but also as a vehicle to stimulate, deepen, and widen partnership between the academia and industry in software testing internationally. In all, 54 delegates from 11 different countries, comprising 32 academics and 22 industrialists, attended the conference. The event featured two keynotes, regular paper sessions, a PhD symposium, and a ‘speed dating’ session devoted to stimulating collaboration between attendees. The first keynote was given by Bill Woodworth, Corporate Director of IBM Quality Software Engineering. Bill spoke on test management at IBM, of which he has over 25 years of experience. John Hatcliff, who delivered the second keynote, is Professor in the Computing and Information Sciences Department at Kansas State University. John spoke on his internationally leading work on testing and software model checking. TAIC PART 2006 received a total of 50 full-paper submissions. After a rigorous reviewing process, 24 papers were accepted, with 8 of those papers from industry, 10 papers containing academic research, and a further 6 short papers accepted for the special PhD programme. Accepted papers covered a wide spectrum of state-of-the-art testing practice and research, including fault prediction, model-based testing, test specifications, the testing life cycle, search-based testing, database testing, web service testing, test requirements analysis, integration testing, empirical and case studies, and industrial challenges. The conference proceedings were published by IEEE and are available online. Two papers in this special issue are extended versions of some of the best papers originally presented at the conference. They have also been through a further reviewing process. The first paper is the result of an academic–industrial collaboration. In their paper ‘Quality Assurance for TTCN-3 Test Specifications’, Helmut Neukirchen, Benjamin Zeiss, and Jens Grabowski, of the University of Göttingen, and Paul Baker and Dominic Evans, of Motorola Labs, propose a technique to (1) assess the quality of existing test suites through metrics; (2) improve it through refactoring; and (3) detect refactoring opportunities by means of rules that are based on quality metrics. They focus on test suites expressed in the Testing and Test Control Notation TTCN-3, a language designed to support the specification of test suites in the telecommunication domain. The quality attribute considered in this work is maintainability, decomposed into analysability and changeability. Size, complexity, and coupling metrics are defined to characterize such quality attributes. The refactoring catalogue includes 23 TTCN-3-specific refactorings and 28 Java refactorings that are applicable to TTCN-3 as well. Eight rules are defined to check the applicability of refactorings automatically. These are implemented in a tool called ‘TRex’. The second paper, entitled ‘Automated Discovery of State Transitions and their Functions in Source Code’, by Neil Walkinshaw, Shaukat Ali, Kirill Bogdanov, and Mike Holcombe, presents a technique to reverse engineer source code into a state machine. It allows a developer to identify the states at a given point and statements that are responsible for state transitions. The technique also combines several ingredients, including symbolic execution and state abstraction, and is demonstrated with examples. Finally, we are grateful to our sponsors, whose financial contributions made it possible for TAIC PART 2006 to happen. Funding was received from the EPSRC and also from industry, including support from DaimlerChrysler, Ericsson, IPL Ltd., LDRA Ltd., Motorola, and Vizuri. The TAIC PART website (http://www2006.taicpart.org) serves as lasting resource to the event, containing the programme, photographs, and downloadable presentations of all the talks.

Refactoring aims to improve the quality of a software systems' structure, which tends to degrade as the system evolves. While manually determining useful refactorings can be challenging, search based techniques can automatically discover useful refactorings. Current search based refactoring approaches require metrics to be combined in a complex fashion, and producea single sequence of refactorings. In this paper we show how Pareto optimality can improve search based refactoring, making the combination of metrics easier, and aiding the presentation of multiple sequences of optimal refactorings to users.

There has been a considerable body of work on search-based test data generation for branch coverage. However, hitherto, there has been no work on multi-objective branch coverage. In many scenarios a single-objective formulation is unrealistic; testers will want to find test sets that meet several objectives simultaneously in order to maximize the value obtained from the inherently expensive process of running the test cases and examining the output they produce. This paper introduces multi-objective branch coverage.The paper presents results from a case study of the twin objectives of branch coverage and dynamic memory consumption for both real and synthetic programs. Several multi-objective evolutionary algorithms are applied. The results show that multi-objective evolutionary algorithms are suitable for this problem, and illustrates the way in which a Pareto optimal search can yield insights into the trade-offs between the two simultaneous objectives.

This paper is concerned with the Multi-Objective Next Release Problem (MONRP), a problem in search-based requirements engineering. Previous work has considered only single objective formulations. In the multi-objective formulation, there are at least two (possibly conflicting) objectives that the software engineer wishes to optimize. It is argued that the multi-objective formulation is more realistic, since requirements engineering is characterised by the presence of many complex and conflicting demands, for which the software engineer must find a suitable balance. The paper presents the results of an empirical study into the suitability of weighted and Pareto optimal genetic algorithms, together with the NSGA-II algorithm, presenting evidence to support the claim that NSGA-II is well suited to the MONRP. The paper also provides benchmark data to indicate the size above which the MONRP becomes non--trivial.

Brooks' milestone 'Mythical Man Month' established the observation that there is no simple conversion between people and time in large scale software projects. Communication and training overheads yield a subtle and variable relationship between the person-months required for a project and the number of people needed to complete the task within a given timeframe. This paper formalises several instantiations of Brooks' law and uses these to construct project schedule and staffing instances — using a search-based project staffing and scheduling approach — on data from two large real world maintenance projects. The results reveal the impact of different formulations of Brooks' law on project completion time and on staff distribution across teams, and the influence of other factors such as the presence of dependencies between work packages on the effect of communication overhead.

Evolutionary testing has been widely studied as a technique for automating the process of test case generation. However, to date, there has been no theoretical examination of when and why it works. Furthermore, the empirical evidence for the effectiveness of evolutionary testing consists largely of small scale laboratory studies. This paper presents a first theoretical analysis of the scenarios in which evolutionary algorithms are suitable for structural test case generation. The theory is backed up by an empirical study that considers real world programs, the search spaces of which are several orders of magnitude larger than those previously considered.

Previous work has treated test case selection as a single objective optimisation problem. This paper introduces the concept of Pareto efficiency to test case selection. The Pareto efficient approach takes multiple objectives such as code coverage, past fault-detection history and execution cost, and constructs a group of non-dominating, equivalently optimal test case subsets. The paper describes the potential bene?ts of Pareto efficient multi-objective test case selection, illustrating with empirical studies of two and three objective formulations.

Search based software engineering (SBSE) is an approach to software engineering in which search based optimization algorithms are used to identify optimal or near optimal solutions and to yield insight. SBSE techniques can cater for multiple, possibly competing objectives and/or constraints and applications where the potential solution space is large and complex. Such situations are common in software engineering, leading to an increasing interest in SBSE. This paper provides a brief overview of SBSE, explaining some of the ways in which it has already been applied to program-comprehension related activities. The paper also outlines some possible future applications of and challenges for the further application of SBSE to program comprehension.

There has recently been a great deal of interest in search-based test data generation, with many local and global search algorithms being proposed. However, to date, there has been no investigation ofthe relationship between the size of the input domain (the search space) and performance of search-based algorithms. Static analysis can be used to remove irrelevant variables for a given test data generation problem, thereby reducing the search space size. This paper studies the effect of this domain reduction, presenting results from the application of local and global search algorithms to real world examples. This provides evidence to support the claimthat domain reduction has implications for practical search-based test data generation.

Abstract When testing from finite state machines, a failure observed in the implementation under test (IUT) is called a symptom. A symptom could have been caused by an earlier state transfer failure. Transitions that may be used to explain the observed symptoms are called diagnosing candidates. Finding strategies to generate an optimal set of diagnosing candidates that could effectively identify faults in the IUT is of great value in reducing the cost of system development and testing. This paper investigates fault diagnosis when testing from finite state machines and proposes heuristics for fault isolation and identification. The proposed heuristics attempt to lead to a symptom being observed in some shorter test sequences, which helps to reduce the cost of fault isolation and identification. The complexity of the proposed method is analysed. A case study is presented, which shows how the proposed approach assists in fault diagnosis. Copyright © 2006 John Wiley & Sons, Ltd.

This article presents results from a study of techniques that improve the performance of graph-based interprocedural slicing of the System Dependence Graph (SDG). This is useful in “massive slicing” where slices are required for many or all of the possible set of slicing criteria. Several different techniques are considered, including forming strongly connected components, topological sorting, and removing transitive edges. Data collected from a test bed of just over 1,000,000 lines of code are presented. This data illustrates the impact on computation time of the techniques. Together, the best combination produces a 71% reduction in run-time (and a 64% reduction in memory usage). The complete set of techniques also illustrates the point at which faster computation is not viable due to prohibitive preprocessing costs.

This article presents results from a study of all slices from 43 programs, ranging up to 136,000 lines of code in size. The study investigates the effect of five aspects that affect slice size. Three slicing algorithms are used to study two algorithmic aspects: calling-context treatment and slice granularity. The remaining three aspects affect the upstream dependencies considered by the slicer. These include collapsing structure fields, removal of dead code, and the influence of points-to analysis. The results show that for the most precise slicer, the average slice contains just under one-third of the program. Furthermore, ignoring calling context causes a 50% increase in slice size, and while (coarse-grained) function-level slices are 33% larger than corresponding statement-level slices, they may be useful predictors of the (finer-grained) statement-level slice size. Finally, upstream analyses have an order of magnitude less influence on slice size.

Regression testing is an expensive, but important, process. Unfortunately, there may be insufficient resources to allow for the reexecution of all test cases during regression testing. In this situation, test case prioritization techniques aim to improve the effectiveness of regression testing by ordering the test cases so that the most beneficial are executed first. Previous work on regression test case prioritization has focused on Greedy Algorithms. However, it is known that these algorithms may produce suboptimal results because they may construct results that denote only local minima within the search space. By contrast, metaheuristic and evolutionary search algorithms aim to avoid such problems. This paper presents results from an empirical study of the application of several greedy, metaheuristic, and evolutionary search algorithms to six programs, ranging from 374 to 11,148 lines of code for three choices of fitness metric. The paper addresses the problems of choice of fitness metric, characterization of landscape modality, and determination of the most suitable search technique to apply. The empirical results replicate previous results concerning Greedy Algorithms. They shed light on the nature of the regression testing search space, indicating that it is multimodal. The results also show that Genetic Algorithms perform well, although Greedy approaches are surprisingly effective, given the multimodal nature of the landscape.

This poster paper addresses the problem of choosing sets of software components to combine in component-based software engineering. It formulates both ranking and selection problems as feature subset selection problems to which search based software engineering can be applied. We will consider selection and ranking of elements from a set of software components from the component base of a large telecommunications organisation.

This paper addresses the problem of determining the next set of releases in the course of software evolution. It formulates both ranking and selection of candidate software components as a series of feature subset selection problems to which search based software engineering can be applied. The approach is automated using greedy and simulated annealing algorithms and evaluated using a set of software components from the component base of a large telecommunications organization. The results are compared to those obtained by a panel of (human) experts. The results show that the two automated approaches convincingly outperform the expert judgment approach

One approach to supporting program comprehension involves binding concepts to source code. Previously proposed approaches to concept binding have enforced nonoverlapping boundaries. However, real-world programs may contain overlapping concepts. This paper presents techniques to allow boundary overlap in the binding of concepts to source code. In order to allow boundaries to overlap, the concept binding problem is reformulated as a search problem. It is shown that the search space of overlapping concept bindings is exponentially large, indicating the suitability of sampling-based search algorithms. Hill climbing and genetic algorithms are introduced for sampling the space. The paper reports on experiments that apply these algorithms to 21 COBOL II programs taken from the commercial financial services sector. The results show that the genetic algorithm produces significantly better solutions than both the hill climber and random search.

This paper introduces the Species per Path approach to search-based software test data generation. The approach transforms the program under test into a version in which multiple paths to the search target are factored out. Test data are then sought for each individual path by dedicated 'species' operating in parallel. The factoring out of paths results in several individual search landscapes, with feasible paths giving rise to landscapes that are potentially more conducive to test data discovery than the original overall landscape.The paper presents the results of two empirical studies that validate and verify the approach. The validation study supports the claim that the approach is widely applicable and practical. The verification study shows that it is possible to generate test data for targets with the approach that are troublesome for the standard evolutionary method.

This paper describes a method for automatically generating unique input output (UIO) sequences for FSM conformance testing. UIOs are used in conformance testing to verify the end state of a transition sequence. UIO sequence generation is represented as a search problem and genetic algorithms are used to search this space. Empirical evidence indicates that the proposed method yields considerably better (up to 62% better) results compared with random UIO sequence generation.

Abstract A formal relationship between program slicing and partial evaluation is established. It is proved that for terminating programs, a residual program produced by partial evaluation is semantically equivalent to a conditioned slice.

No abstract available.

Aspect-oriented programming (AOP) provides mechanisms for the separation of crosscutting concerns - functionalities scattered through the system and tangled with the base code. Existing systems are a natural testbed for the AOP approach since they often contain several crosscutting concerns which could not be modularized using traditional programming constructs. This paper presents an automated approach to the problem of migrating systems developed according to the object-oriented programming (OOP) paradigm into aspect-oriented programming (AOP). A simple set of six refactorings has been defined to transform OOP to AOP and has been implemented in the AOP-migrator tool, an Eclipse plug-in. A set of enabling transformations from OOP to OOP complement the initial set of refactorings. The paper presents the results of four case studies, which use the approach to migrate selected crosscutting concerns from medium-sized Java programs (in the range of 10K to 40K lines of code) into equivalent programs in AspectJ. The case study results show the feasibility of the migration and indicate the importance of the enabling transformations as a preprocessing step

No abstract available.

Two of the attractions of search-based software engineering (SBSE) derive from the nature of the fitness functions used to guide the search. These have proved to be highly robust (for a variety of different search algorithms) and have yielded insight into the nature of the search space itself, shedding light upon the software engineering problem in hand.This paper aims to exploit these two benefits of SBSE in the context of search based module clustering. The paper presents empirical results which compare the robustness of two fitness functions used for software module clustering: one (MQ) used exclusively for module clustering. The other is EVM, a clustering fitness function previously applied to time series and gene expression data.The results show that both metrics are relatively robust in the presence of noise, with EVM being the more robust of the two. The results may also yield some interesting insights into the nature of software graphs.

This paper evaluates the use of three different search-based techniques, namely genetic algorithms, hill climbing and simulated annealing, and two problem representations, for planning resource allocation in large massive maintenance projects. In particular, the search-based approach aims to find an optimal or near optimal order in which to allocate work packages to programming teams, in order to minimize the project duration. The approach is validated by an empirical study of a large, commercial Y2K massive maintenance project, which compares these techniques with each other and with a random search (to provide base line comparison data). Results show that an ordering-based genome encoding (with tailored cross over operator) and the genetic algorithm appear to provide the most robust solution, though the hill climbing approach also performs well. The best search technique results reduce the project duration by as much as 50%.

This paper presents a human-guided automated approach to refactoring object oriented programs to the aspect oriented paradigm. The approach is based upon the iterative application of four steps: discovery, enabling, selection, and refactoring. After discovering potentially applicable refactorings, the enabling step transforms the code to improve refactorability. During the selection phase the particular refactorings to apply are chosen. Finally, the refactoring phase transforms the code by moving the selected code to a new aspect. This paper presents the results of an evaluation in which one of the crosscutting concerns of a 40,000 LoC program (JHotDraw) is refactored.

A dependence cluster is a set of program statements all of which are mutually inter-dependent. Such clusters can cause problems for maintenance, because a change to any statement in the cluster will have a potential impact on all statements in the cluster. This paper introduces the concept of dependence clusters and dependence pollution and shows how a simple visualisation can be used to quickly and effectively locate them. The paper presents the results of two empirical studies and several case studies which evaluate the approach. The results indicate the importance of dependence cluster analysis: for a set of 20 programs, ranging in size from 1,170 LoC to 179,623 LoC, 99.6% of clusters identified were within 1% tolerance of being identical, while dependence clusters were found to be surprisingly common: 80% of the programs studied contained clusters of 10% or more of the program.

During regression testing, a modified system is retested using the existing test suite. Because the size of the test suite may be very large, testers are interested in detecting faults in the system as early as possible during the retesting process. Test prioritization tries to order test cases for execution so the chances of early detection of faults during retesting are increased. The existing prioritization methods are based on the code of the system. System modeling is a widely used technique to model state-based systems. In this paper, we present methods of test prioritization based on state-based models after changes to the model and the system. The model is executed for the test suite and information about model execution is used to prioritize tests. Execution of the model is inexpensive as compared to execution of the system; therefore the overhead associated with test prioritization is relatively small. In addition, we present an analytical framework for evaluation of test prioritization methods. This framework may reduce the cost of evaluation as compared to the existing evaluation framework that is based on experimentation (observation). We have performed an experimental study in which we compared different test prioritization methods. The results of the experimental study suggest that system models may improve the effectiveness of test prioritization with respect to early fault detection.

Source-code based test data generation is a process of finding program input on which a selected element, e.g., a target statement, is executed. There exist many test generation methods that automatically find a solution to the test generation problem. The existing methods work well for many programs. However, they may fail or are inefficient for programs with complex logic and intricate relationships between program elements. In this paper we present a testability transformation that transforms programs so that the chances of finding a solution are increased when the existing methods fail using only the original program. In our approach data dependence analysis is used to identify statements in the program that affect computation of the fitness function associated with the target statement. The transformed program contains only these statements, and it is used to explore different ways the fitness may be computed. These explorations are inexpensive when using the transformed program as compared to explorations using the original program. As a result, executions in the transformed program that lead to the evaluation of the fitness function to the target value are identified. The identified executions are then used to guide the search in the original program to find an input on which the target statement is executed. In this paper, the approach is evaluated using a case study which demonstrates the potential for this testability transformation to improve the efficacy of the test generation

Program slicing is an automated source code extraction technique that has been applied to a number of problems including testing, debugging, maintenance, reverse engineering, program comprehension, reuse and program integration. In all these applications the size of the slice is crucial; the smaller the better. It is known that statement minimal slices are not computable, but the question of dataflow minimal slicing has remained open since Weiser posed it in 1979. This paper proves that static slicing algorithms produce dataflow minimal end slices for programs which can be represented as schemas which are free and liberal.

Test data generation by hand is a tedious, expensive and error-prone activity, yet testing is a vital part of the development process. Several techniques have been proposed to automate the generation of test data, but all of these are hindered by the presence of unstructured control flow. This paper addresses the problem using testability transformation. Testability transformation does not preserve the traditional meaning of the program, rather it deals with preserving test-adequate sets of input data. This requires new equivalence relations which, in turn, entail novel proof obligations. The paper illustrates this using the branch coverage adequacy criterion and develops a branch adequacy equivalence relation and a testability transformation for restructuring. It then presents a proof that the transformation preserves branch adequacy.

Abstract Program slicing and concept assignment have both been proposed as source code extraction techniques. Unfortunately, each has a weakness that prevents wider application. For slicing, the extraction criterion is expressed at a very low level; constructing a slicing criterion requires detailed code knowledge which is often unavailable. The concept assignment extraction criterion is expressed at the domain level. However, unlike a slice, the extracted code is not executable as a separate subprogram in its own right. This paper introduces a unification of slicing and concept assignment which exploits their combined advantages, while overcoming these two individual weaknesses. Our ‘concept slices’ are executable programs extracted using high‐level criteria. The paper introduces four techniques that combine slicing and concept assignment and algorithms for each. These algorithms were implemented in two separate tools used to illustrate the application of the concept slicing algorithms in two very different case studies. The first is a commercially‐written COBOL module from a large financial organization, the second is an open source utility program written in C. Copyright © 2005 John Wiley & Sons, Ltd.

In systems developed without aspect-oriented programming, code implementing a crosscutting concern may be spread over many different parts of a system. Identifying such code automatically could be of great help during maintenance of the system. First of all, it allows a developer to more easily find the places in the code that must be changed when the concern changes and, thus, makes such changes less time consuming and less prone to errors. Second, it allows the code to be refactored to an aspect-oriented solution, thereby improving its modularity. In this paper, we evaluate the suitability of clone detection as a technique for the identification of crosscutting concerns. To that end, we manually identify five specific crosscutting concerns in an industrial C system and analyze to what extent clone detection is capable of finding them. We consider our results as a stepping stone toward an automated "aspect miner” based on clone detection.

Like other engineering disciplines, software engineering is typically concerned with near optimal solutions or those which fall within a specified applicable tolerance. More recently, search-based techniques have started to find application in software engineering problem domains. This area of search-based software engineering has its origins in work on search-based testing, which began in the mid 1990s. Already, search-based solutions have been applied to software engineering problems right through the development life cycle.

Evolutionary testing is an effective technique for automatically generating good quality test data. However, for structural testing, the technique degenerates to random testing in the presence of flag variables, which also present problems for other automated test data generation techniques. Previous work on the flag problem does not address flags assigned in loops.This paper introduces a testability transformation that transforms programs with loop--assigned flags so that existing genetic approaches can be successfully applied. It then presents empirical data demonstrating the effectiveness of the transformation. Untransformed, the genetic algorithm flounders and is unable to find a solution. Two transformations are considered. The first allows the search to find a solution. The second reduces the time taken by an order of magnitude and, more importantly, reduces the slope of the cost increase; thus, greatly increasing the complexity of the problem to which the genetic algorithm can be applied. The paper also presents a second empirical study showing that loop--assigned flags are prevalent in real world code. They account for just under 11% of all flags.

Abstract Conditioned slicing is a source code extraction technique. The extraction is performed with respect to a slicing criterion which contains a set of variables and conditions of interest. Conditioned slicing removes the parts of the original program which cannot affect the variables at the point of interest, when the conditions are satisfied. This produces a conditioned slice, which preserves the behaviour of the original with respect to the slicing criterion. Conditioned slicing has applications in source code comprehension, reuse, restructuring and testing. Unfortunately, implementation is not straightforward because the full exploitation of conditions requires the combination of symbolic execution, theorem proving and traditional static slicing. Hitherto, this difficultly has hindered development of fully automated conditioning slicing tools. This paper describes the first fully automated conditioned slicing system, CONSIT, detailing the theory that underlies it, its architecture and the way it combines symbolic execution, theorem proving and slicing technologies. The use of CONSIT is illustrated with respect to the applications of testing and comprehension. Copyright © 2003 John Wiley & Sons, Ltd.

Methods and Testing

Empirical data concerning the qualitative and quantitative nature of program dependence is presented for a set of 20 programs ranging from 600 lines of code to 167,000 lines of code. The sources of dependence considered are global variables and formal parameters and the targets considered are a program's predicate nodes. The results show that as the number of formal parameters available to a predicate increases, there is a decrease in the proportion of these formal parameters which are depended upon by the predicate. No such correlation was found for global variables. Results from theoretical and actual computation time analysis indicate that the computation of dependence information is practical, suggesting that the analysis may be beneficial to several application areas. The paper also presents results concerning correlations that provide strong evidence that the global and formal dependence sources are independent of one another and that the numbers of globals and formals are independent of the size of the procedure that contains them. Finally, two visualization techniques for displaying dependence information are introduced. Illustrations show how these visualizations and predicate dependence analysis can assist in activities such as testing, comprehension, and evolution.

A testability transformation is a source-to-source transformation that aims to improve the ability of a given test generation method to generate test data for the original program. We introduce testability transformation, demonstrating that it differs from traditional transformation, both theoretically and practically, while still allowing many traditional transformation rules to be applied. We illustrate the theory of testability transformation with an example application to evolutionary testing. An algorithm for flag removal is defined and results are presented from an empirical study which show how the algorithm improves both the performance of evolutionary test data generation and the adequacy level of the test data so-generated.

Many source code analyses are closely related to and strongly influenced by interdependence among program components. This paper reports results from an empirical study of the interdependences involving program predicates and the formal parameters and global variables which potentially affect them. The findings show that it is possible to eliminate from consideration approximately 30% of the formal parameters, 50% of the 'touched' global variables, and 97% of the 'visible' global variables. Another important and encouraging finding is a strong inverse correlation between the number of formal parameters and dependence level. The fact that no such correlation was found for global variables provides evidence to support the conjecture that global variables are harmful.

A large-scale study of 43 C programs totaling just over 1 million lines of code is presented. The study includes the forward and backward static slice on every executable statement. In total 2353598 slices were constructed, with an average slice size being just under 30% of the original program. The results also show that ignoring calling-context led to a 50% increase in average slice size and, in contrast to previous results, a 66-77% increase in computation time (due to the increased size). Though not the principal focus of the study, the results also show an average pace for the slicing engine, on a standard PC, of 3 million lines of code per second thereby providing additional evidence for static slicing's practicability.

Automated software module clustering is important for maintenance of legacy systems written in a 'monolithic format' with inadequate module boundaries. Even where systems were originally designed with suitable module boundaries, structure tends to degrade as the system evolves, making re-modularization worthwhile. This paper focuses upon search-based approaches to the automated module clustering problem, where hitherto, the local search approach of hill climbing has been found to be most successful. In the paper we show that results from a set of multiple hill climbs can be combined to locate good 'building blocks' for subsequent searches. Building blocks are formed by identifying the common features in a selection of best hill climbs. This process reduces the search space, while simultaneously 'hard wiring' parts of the solution. The paper reports the results of an empirical study that show that the multiple hill climbing approach does indeed guide the search to higher peaks in subsequent executions. The paper also investigates the relationship between the improved results and the system size.

Abstract The attempt to design and integrate consistent changes to an existing system is the essence of software maintenance. Software developers also confront similar problems: there are changes during testing and the release of new system builds. Whether in development or maintenance, changes to evolving systems must be made consistently; that is, without damaging correct computations. It is difficult for the programmer to ascertain the complete effect of a code change; the programmer may make a change to a program that is syntactically and semantically legal, but which has ripples into the parts of the program that were intended to remain unchanged. Using the standard denotational semantics for procedural programming languages, this paper formalizes decomposition slicing, which identifies interferences between software components and isolates the components to be changed. We enumerate the conditions for changing one component in ways that will guarantee that changes to it will not interact inconsistently and prove that changes made under these conditions are sound. Thus, the programmer can then execute changes secure in the knowledge that the semantics of the new system are guaranteed to be consistent with the projection of the semantics of the original for which it behaved correctly. Validating that the changes do not interfere not only guarantees consistency with respect to previous unchanging behaviors, but can also be achieved with a complexity proportional to the size of the change to be made. Copyright © 2003 John Wiley & Sons, Ltd.

This paper reports the results of a study on the impact of a type of side effect (SE) upon program comprehension. We applied a crossover design on different tests involving fragments of C code that include increment and decrement operators. Each test had an SE version and a side-effect-free counterpart. The variables measured in the treatments were the number of correct answers and the time spent in answering. The results show that the side-effect operators considered significantly reduce performance in comprehension-related tasks, providing empirical justification for the belief that side effects are harmful.

Formal methods have traditionally been used for specification and development of software. However there are potential benefits for the testing stage as well. The panel session associated with this paper explores the usefulness or otherwise of formal methods in various contexts for improving software testing. A number of different possibilities for the use of formal methods are explored and questions raised. The contributors are all members of the UK FORTEST Network on formal methods and testing. Although the authors generally believe that formal methods are useful in aiding the testing process, this paper is intended to provoke discussion. Dissenters are encouraged to put their views to the panel or individually to the authors.

Program slicing is a source-code extraction technique that identifies parts of a program which have no effect upon a chosen set of variables at a point of interest. Slices can be constructed statically (with respect to no input information) or conditionally (with respect to partial input information). They can also be constructed in either a purely syntax-preserving or amorphous way. Amorphous slices tend to be smaller than their syntax-preserving counterparts but they may not be syntactically related to the original. This paper presents the results of a case study which assesses the value of static and conditioned slicing (in both syntax-preserving and amorphous formulations) upon the problem of dynamic memory analysis. The results confirmed our belief that slicing is helpful for dynamic memory analysis: syntax-preserving static slicing produced an order-of-magnitude reduction in the size of the program to be analysed. Amorphous static slicing produced a further reduction in slice size. Finally, conditioned slicing (both syntax-preserving and amorphous) produced the smallest slices (12 to 35 lines of code).

Evolutionary testing is a search based approach to the automated generation of systematic test data, in which the search is guided by the test data adequacy criterion. Two problems for evolutionary testing are the large size of the search space and structural impediments in the implementation of the program which inhibit the formulation of a suitable fitness function to guide the search. In this paper we claim that slicing can be used to narrow the search space and transformation can be applied to the problem of structural impediments. The paper presents examples of how these two techniques have been successfully employed to make evolutionary testing both more efficient and more effective.

Side-effects are widely believed to impede program comprehension and have a detrimental effect upon software maintenance. This paper introduces an algorithm for side-effect removal which splits the side-effects into their pure expression meaning and their state-changing meaning. Symbolic execution is used to determine the expression meaning, while transformation is used to place the state-changing part in a suitable location in a transformed version of the program. This creates a program which is semantically equivalent to the original but guaranteed to be free from side-effects. The paper also reports the results of an empirical study which demonstrates that the application of the algorithm causes a significant improvement in program comprehension.

Abstract This paper describes the use of conditioned slicing to assist partition testing, illustrating this with a case study. The paper shows how a conditioned slicing tool can be used to provide confidence in the uniformity hypothesis for correct programs, to aid fault detection in incorrect programs and to highlight special cases. Copyright © 2001 John Wiley & Sons, Ltd

Th paper shows how analysis of programs in terms of pre- and postconditions can be improved using a generalisation of conditioned program slicing called pre/post conditioned slicing. Such conditions play an important role in program comprehension, reuse, verification and reengineering. Fully automated analysis is impossible because of the inherent undecidability of pre- and post- conditions. The method presented reformulates the problem to circumvent this. The reformulation is constructed so that programs which respect the pre- and post-conditions applied to them have empty slices. For those which do not respect the conditions, the slice contains statements which could potentially break the conditions. This separates the automatable part of the analysis from the human analysis.

Conditioned slicing is a powerful generalisation of static and dynamic slicing which has applications to many problems in software maintenance and evolution, including reuse, reengineering and program comprehension. However there has been relatively little work on the implementation of conditioned slicing. Algorithms for implementing conditioned slicing necessarily involve reasoning about the values of program predicates in certain sets of states derived from the conditioned slicing criterion, making implementation particularly demanding. The paper introduces ConSIT, a conditioned slicing system which is based upon conventional static slicing, symbolic execution and theorem proving. ConSIT is the first fully automated implementation of conditioned slicing. An implementation of ConSIT is available for experimentation at http://www.mcs.gold.ac.uk//spl tilde/mas01sd/consit.html.

Abstract. Stream X-machines have been used in order to specify a range of systems. One of the strengths of this approach is that, under certain well-defined conditions, it is possible to produce a finite test that is guaranteed to determine the correctness of the implementation under test (IUT). Initially only deterministic stream X-machines were considered in the literature. This is largely because the standard test algorithm relies on the stream X-machine being deterministic. More recently the problem of testing to determine whether the IUT is equivalent to a non-deterministic stream X-machine specification has been tackled. Since non-determinism can be important for specifications, this is an extremely useful extension. In many cases, however, we wish to test for a weaker notion of correctness called conformance . This paper considers a particular form of non-determinism, within stream X-machines, that will be called quasi-non-determinism. It then investigates the generation of tests that are guaranteed to determine whether the IUT conforms to a quasi-non-deterministic stream X-machine specification. The test generation algorithm given is a generalisation of that used for testing from a deterministic stream X-machine.

While mutation testing has proved to be an effective way of finding software faults, currently it is only applied to relatively small programs. One of the main reasons for this is the human analysis required in detecting equivalent mutants. Here program slicing is used to simplify this problem. Progam slicing is also used to reduce the number of equivalent mutants produced. Copyright © 1999 John Wiley & Sons, Ltd.

Problems associated with understanding, verifying and re-engineering the way in which a system allocates and releases dynamic memory present significant challenges to the software maintainer. Because the questions underlying these problems are undecidable, no system can provide a completely fail safe certification. For example, in checking for memory leaks, a system can only warn of potential problems, but cannot guarantee that no leaks remain. We present an approach to modelling the dynamic memory access properties of a program using amorphous program slicing to create a Dynamic Memory Model (DMM). The slices are constructed from a transformed version of the original program in which heap access has been made explicit using a pseudo variable to denote the top of the heap. The DMM is a simplified version of the original program which is concerned solely with the dynamic memory access behaviour of the original. We illustrate the use of DMMs in problems of comprehension, verification and re-engineering. We introduce a proof-of-concept DMM construction algorithm, showing how slicing simplification power can be dramatically improved using domain-specific transformation rules.

Program slicing is an automatic program abstraction technique whose many applications include software maintenance, re-engineering and comprehension, all of which rely crucially upon the precision of the slicing algorithm used. When slicing is applied to maintenance problems, the programs to be sliced are typically legacy systems, often written in older, ‘unstructured’ programming styles. For slicing to be a useful tool to the software maintainer it is therefore important to have precise algorithms for slicing unstructured programs. Unfortunately the standard algorithms for slicing structured programs do not extend correctly to the unstructured paradigm, and currently proposed modifications to these standard algorithms produce either unnecessarily large slices or slices which are not true subsets of the original program from which they are constructed. This paper introduces a modification of Agrawal's algorithm for slicing unstructured programs, which overcomes these difficulties. The new algorithm produces thinner slices than any previously published algorithm while respecting both the semantic and syntactic constraints of slicing. © 1998 John Wiley & Sons, Ltd.

Abstract Program slicing is a technique by which statements are deleted from a program in such a way as to preserve a projection of the original program's semantics. It is shown that slicing algorithms based upon traditional defined and referenced variable sets do not preserve a projection of strict semantics with respect to computations which cause errors. Rather, these approaches preserve a projection of the program's semantics which is lazy with respect to errors. A modified version of defined and referenced variable sets is introduced, which provides the freedom to choose the form of semantics to be preserved.

Abstract Program slicing is a technique for automatically identifying the statements of a program which affect a selected subset of its variables. A large program can be divided into a number of smaller program (its slices), each constructed for different variable subsets. The slices are typically simpler than the original program, thereby simplifying the process of testing a property of the program which only concerns the corresponding subset of its variables. However, some aspects of a program's computation are not captured by a set of variables, rendering slicing inapplicable. To overcome this difficulty a program can be rewritten in a self‐checking form by the addition of assignment statements to denote these ‘implicit’ computations. Initially this makes the program longer. However, slicing can now be applied to the introspective program, forming a slice concerned solely with the implicit computation. The simplification power of slicing is then improved using program transformation. To illustrate this approach, the implicit computation which dictates whether or not a program is robust is taken as an example. Whether or not a program is robust is not generally decidable making the approach described here particularly appealing because the slices constructed are approximate answers to the undecidable question ‘Is the program p robust?’.