Evaluation and Improvement of Automated Software Test Suites Von der Fakultät für Informatik, Elektrotechnik und Informationstechnik der Universität Stuttgart zur Erlangung der Würde eines Doktors der Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlung Vorgelegt von Rainer Niedermayr aus Bozen, Italien Hauptberichter: Prof. Dr. Stefan Wagner Mitberichter: Prof. Dr. Benoit Baudry Tag der mündlichen Prüfung: 7. Oktober 2019 Institut für Softwaretechnologie 2019 Acknowledgments This dissertation was written under the supervision of Prof. Dr. StefanWagner between 2015 and 2019. I am very grateful for his mentorship, academic guidance, and advice. In addition, I am thankful for my inclusion in the research group at the Institute of Software Technology at University of Stuttgart and want to thank all of the members for their support and the discussions at the seminars. My sincere thanks also go to Prof. Dr. Benoit Baudry for co-supervising this dissertation, inspiring discussions in Gothenburg and Stockholm, and his valuable feedback on my work. I am grateful for the support of Dr. Elmar Juergens, who had already been advisor of my Master’s thesis, for encouraging me to undertake a PhD and giving me the opportunity to do so at CQSE GmbH. I also want to thank him for our productive discussions. I wish to thank Oscar Luis Vera-Pérez for his interest in my work, his implementation of the Descartes plug-in, and our discussions. I am grateful to the numerous people who collaborated on papers, re- viewed papers, or gave feedback on this dissertation. They are, in alphabetical order: Florian Deißenböck, Nils Göde, Roman Haas, Elmar Juergens, Martin 3 Monperrus, Dennis Pagano, Jakob Rott, Tobias Röhm, Daniela Steidl, Alexan- der von Rhein, and Andreas Wilhelm. In addition, I am thankful to Florian Dreier and Jakob Rott for their work on the Test Impact Analysis and our discussions. I want to thank my family for their invaluable support, not only during my dissertation, but throughout my education. The funding from the German Federal Ministry of Education and Research (BMBF) is gratefully acknowledged. Stuttgart, 7th October 2019 Rainer Niedermayr 4 Zusammenfassung Automatisierte Softwaretests sind eine wichtige Qualitätssicherungsmaß- nahme in Softwareprojekten und helfen Fehler in einer Anwendung früh- zeitig aufzudecken. Zur Bewertung von Testsuiten wurden in der Vergan- genheit verschiedene Metriken und Verfahren vorgeschlagen. Dabei sind Code-Coverage-Metriken am weitesten verbreitet und werden vor allem in der kommerziellen Softwareentwicklung eingesetzt. Jedoch sind diese nur bedingt geeignet, die Effektivität von Testsuiten hinsichtlich ihrer Fehlerauf- deckungsrate zu bewerten. Ein anderes wirkungsvolles und aussagekräftiges Verfahren ist Mutation Testing, bei dem Fehler in den Anwendungscode einer Software eingefügt werden und geprüft wird, ob die vorhandenen Testfälle diese aufdecken können. In Bezug auf die Bestimmung der Testeffektivität ist Mutation Testing anderen Verfahren deutlich überlegen, jedoch ist es sehr rechenintensiv und sogenannte äquivalente Mutanten können die Ergebnisse verfälschen. Wegen dieser Probleme wird Mutation Testing in der Praxis derzeit kaum eingesetzt. Das Ziel dieser Dissertation ist es, aussagekräftigere Metriken und Verfah- ren zur Bewertung von Testsuiten zu entwickeln, welche mit vertretbarem Berechnungsaufwand anwendbar sind. Diese sollen Code-Coverage-Metriken in Bezug auf die Aussagekraft übertreffen und gleichzeitig weniger rechen- intensiv als derzeit verwendete Mutation-Testing-Verfahren sein. Dazu wurde ein leichtgewichtiges Verfahren zur Erkennung von schein- 5 getesteten Methoden konzipiert, umgesetzt und evaluiert. Scheingetestete Methoden sind von mindestens einem Testfall überdeckt, jedoch erkennt keiner der überdeckenden Testfälle, wenn die gesamte Logik aus der Me- thode entfernt wird. Außerdem wurde ein Machine-Learning-Modell zur Vorhersage von scheingetesteten Methoden entwickelt, welches ein neu eingeführtes Maß für die Aufrufdistanz zwischen Methoden und Testfällen sowie weitere kostengünstig berechenbare Metriken verwendet. Im Rahmen der Arbeit wurde ein weiteres Machine-Learning-Modell zur Identifizierung von Methoden mit einem niedrigem Fehlerrisiko vorgeschlagen. Solche Me- thoden können bei Qualitätssicherungsmaßnahmen nachrangig behandelt oder ausgeschlossen werden, sodass beispielsweise der Aufwand für die Erkennung scheingetesteter Methoden weiter reduziert wird. Die Ergebnisse zeigen, dass scheingetestete Methoden in allen untersuch- ten Studienobjekten auftreten und relevante Testunzulänglichkeiten darstel- len. Machine-Learning-Modelle können scheingetestete Methoden effizient vorhersagen, sodass diese Modelle als eine kostengünstige Annäherung vor einer Mutationsanalyse eingesetzt oder in Situationen verwendet wer- den können, in denen Mutationsanalysen nicht anwendbar sind. Mit einem weiteren Machine-Learning-Modell können basierend auf Code-Metriken Methoden identifiziert werden, die ein niedriges Fehlerrisiko aufweisen. Dies trifft auf etwa ein Drittel der Methoden zu, die folglich im Test mit einer niedrigeren Priorität behandelt werden können. Die entworfenen Verfahren ermöglichen sowohl eine verhältnismäßig leichtgewichtige, anwendbare Berechnung von scheingetesteten Methoden als auch eine Vorhersage derselben basierend auf Methoden- und Testfall- metriken. Durch scheingetestete Methoden aufgedeckte Probleme in Test- suiten sind für Entwickler einfach verständlich und adressierbar, sodass Entwickler die Effektivität ihrer Testsuite verbessern können. Außerdem hilft die Identifikation von Methoden mit einem niedrigen Fehlerrisiko, Testauf- wände auf relevante Methoden zu fokussieren. Effektivere Testsuiten können mehr Fehler bereits während des Softwareentwicklungsprozesses aufdecken und helfen damit, die Qualität eines Softwareprodukts zu verbessern sowie Fehlerfolgekosten zu reduzieren. 6 Abstract Automated software tests are an important means of quality assurance in software projects and for helping to detect faults in software products early. While various measures and techniques have been proposed to evaluate test suites, code coverage metrics are the most common and are widely used in industry. However, it is questionable whether code coverage metrics are suitable to determine the fault detection capabilities of a test suite. Another powerful and valid technique for assessing test suites is mutation testing, which introduces faults into an application’s code and checks whether the existing test cases can detect them. When determining fault detection capabilities, mutation testing is clearly superior to other measures, but it is computationally very complex and suffers from the problem of equivalent mutants, which distort the results. Due to these problems, mutation testing has rarely been adopted as a test adequacy criterion in practice. The aim of this dissertation was to develop measures and techniques to better determine the effectiveness of a test suite with reasonable computa- tional efforts. We wanted to come up with an approach that outperforms code coverage metrics in terms of validity and is, at the same time, less resource-intensive than currently used mutation testing approaches. To do this, we proposed, implemented and evaluated a light-weight mu- tation approach to identify pseudo-tested methods; that is, methods that 7 are covered by at least one test case, but none of the test cases can detect the removal of the whole logic from the method. We further developed a machine-learning model to predict pseudo-tested methods based on a newly introduced measure for characterizing the proximity between meth- ods and test cases and further easily computable measures. We also built machine-learning models to identify low-fault-risk methods, which can be excluded from quality-assurance activities to focus on the relevant methods and further speed up pseudo-testedness analyses. The results show that pseudo-tested methods exist in all analyzed study objects and constitute relevant test inadequacies. Prediction models can efficiently identify pseudo-tested methods, which means that such models can be applied as a preceding, less costly step to mutation testing or be used in scenarios where mutation testing is not applicable. Depending on what level of risk is acceptable, approximately one-third of the methods can be classified as having a low fault risk, and these methods can be predicted with a machine-learning model based on code metrics. The devised approachesmake it possible to identify pseudo-testedmethods by using an applicable, light-weight computation or a prediction based on method and test case metrics. Flaws in test suites uncovered by pseudo-tested methods are easy for developers to interpret and take action on, enabling the developers to improve the effectiveness of their test suite. The identification of methods with a low fault risk helps allocate test suite improvement efforts to the relevant methods. More effective test suites can reveal more faults during the software development phase, which can help improve the overall quality of a software product and reduce failure follow-up costs. 8 Contents 1 Introduction 13 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3 Research Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Contributions to Knowledge . . . . . . . . . . . . . . . . . . . . . . 17 1.5 Previously Published Material . . . . . . . . . . . . . . . . . . . . . 19 1.6 Structure of Dissertation . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Background 21 2.1 Testing Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.1 Test Cases and Test Suites . . . . . . . . . . . . . . . . . . . 22 2.1.2 Test Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.3 Test Verdict . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.4 Test Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.5 Test Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.6 Test and Application Code . . . . . . . . . . . . . . . . . . . 27 2.1.7 Regression Testing . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 Error, Fault, Defect & Failure . . . . . . . . . . . . . . . . . . . . . 28 2.3 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 9 2.4 Mutation Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4.2 Benefits and Downsides . . . . . . . . . . . . . . . . . . . . . 32 2.4.3 Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.1 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . 36 2.5.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3 State of the Art 41 3.1 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.1 Studies Confirming Coverage as Effectiveness Indicator . 42 3.1.2 Studies Disproving Coverage as Effectiveness Indicator . 43 3.2 Checked Coverage & Assertion Coverage . . . . . . . . . . . . . . 44 3.2.1 Checked Coverage . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.2 Assertion Coverage . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3 Mutation Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.1 Addressing the Computational Complexity . . . . . . . . . 48 3.3.2 Addressing Equivalent Mutants . . . . . . . . . . . . . . . . 51 3.3.3 Use In Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3.4 Pseudo-Testedness . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4 Defect Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.5 Test Case Selection and Prioritization . . . . . . . . . . . . . . . . 56 3.6 Research Gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4 Concept of Pseudo-Tested Methods 61 4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3 Definition of the Mutation Operator . . . . . . . . . . . . . . . . . 67 4.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.4.1 Configuration Options . . . . . . . . . . . . . . . . . . . . . . 73 4.4.2 Alternative Implementation in Descartes . . . . . . . . . . 74 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 10 Contents 5 Presence of Pseudo-Tested Methods and Their Characteristics 77 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.2 Study Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.3 Execution of the Mutation Analysis . . . . . . . . . . . . . . . . . 80 5.4 Existence of Pseudo-Tested Methods . . . . . . . . . . . . . . . . . 80 5.5 Examples of Pseudo-Tested Methods . . . . . . . . . . . . . . . . . 83 5.6 Characteristics of Pseudo-Tested Methods . . . . . . . . . . . . . 88 5.7 Threats to Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6 Predicting Pseudo-Tested Methods 101 6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.3 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.4 Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.4.1 Research Questions . . . . . . . . . . . . . . . . . . . . . . . . 107 6.4.2 Study Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.4.3 Study Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.4.4 Data Collection and Processing . . . . . . . . . . . . . . . . 111 6.4.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.4.6 Threats to Validity . . . . . . . . . . . . . . . . . . . . . . . . 121 6.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7 Identifying Low-Fault-Risk Methods 127 7.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.2 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7.2.1 Metric Computation . . . . . . . . . . . . . . . . . . . . . . . 130 7.2.2 Data Pre-Processing . . . . . . . . . . . . . . . . . . . . . . . 134 7.2.3 IDP Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.3 Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.3.1 Research Questions . . . . . . . . . . . . . . . . . . . . . . . . 137 7.3.2 Study Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.3.3 Fault Data Extraction . . . . . . . . . . . . . . . . . . . . . . . 139 Contents 11 7.3.4 Study Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7.3.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.3.6 Threats to Validity . . . . . . . . . . . . . . . . . . . . . . . . 154 7.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 7.4.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 7.4.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 7.4.3 Relation to Defect Prediction . . . . . . . . . . . . . . . . . . 158 7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 8 Enhanced Test Case Selection and Prioritization 161 8.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 8.2 Existing Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 8.2.1 Required Input Data . . . . . . . . . . . . . . . . . . . . . . . 164 8.2.2 Test Case Selection . . . . . . . . . . . . . . . . . . . . . . . . 164 8.2.3 Test Case Prioritization . . . . . . . . . . . . . . . . . . . . . 166 8.2.4 Provision of Results . . . . . . . . . . . . . . . . . . . . . . . . 167 8.3 Enhanced Approach with Test Effectiveness Information . . . . 167 8.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 8.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 9 Conclusion and Future Work 173 9.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 9.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 9.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 Bibliography 179 List of Figures 209 List of Tables 211 List of Listings 213 List of Abbreviations 215 12 Contents Ch ap te r 1 Introduction This chapter describes the motivation, problem statement, research goal, and contributions of this dissertation. It also presents the list of publications and outlines the structure of this dissertation. 13 1.1 Motivation Automated software tests are an important means of quality assurance in software projects. These tests execute parts of an application, compare the computed result or observed behavior with the expected one, and determine whether an application is acting as expected. Thus, they help reveal faults at an early stage and prevent regressions in software applications. A significant proportion of software development efforts are spent on testing (Brooks Jr., 1995; Dustin et al., 2009). Therefore, efforts should be made to use testing resources efficiently to maximize their benefit. In order to be able to decide which parts of an application benefit most from further testing and which ones can be considered as having been tested thoroughly enough, it is important to have a good understanding of an application’s testing state. Therefore, a valid and expressive evaluation of a test suite’s effectiveness is needed. Various measures and techniques to evaluate test suites have been pro- posed. Code coverage metrics are the most common measures (Huang, 1975; Zhu et al., 1997) and are widely used in industry (Yang et al., 2009). Code coverage expresses which proportion of the application code is executed by test cases and can be computed at different levels. For example, line coverage expresses which proportion of an application’s executable lines out of all lines are executed by tests. Common coverage metrics at other levels are branch coverage and decision coverage (Chilenski and Miller, 1994); they are relatively easy to compute and their performance overhead is negli- gible in the test suites of most applications. However, code coverage metrics measure test completeness and do not assess oracle quality. Therefore, they are not necessarily suitable for evaluating a test suite’s effectiveness in terms of detecting faults (Antinyan et al., 2018; Inozemtseva and Holmes, 2014). More advanced approaches to evaluate test suites take data-flow criteria into account and check the relations between variable definitions and their uses (Rapps and Weyuker, 1982). For example, the all-defs criterion requires that every variable definition is executed and used at least once by a test case. Similarly, the concept of checked coverage proposed by Schuler and 14 1 | Introduction Zeller (2011) measures the proportion of executable lines that is checked by test assertions. Those authors used dynamic slicing for computing the metric and found that it comes with a substantial run-time overhead and input/output (I/O) overhead for writing trace files. Besenreuther (2014) introduced assertion coverage, which is similar to checked coverage, but based on executed lines instead of executable ones. His approach traces the variables at run-time during the test execution. It comes with no I/O overhead for writing trace files, but has higher requirements regarding main memory than dynamic slicing. These approaches provide a more meaningful test evaluation regarding fault detection capabilities than code coverage, but are substantially more expensive to compute. Another powerful technique with which to evaluate test suites is mutation testing (Jia and Harman, 2011), which involves generating mutants by seeding faults into the application code and checking whether the tests can kill (detect) these faults. This technique takes oracle quality into account and measures fault detection capabilities. While it provides more meaningful results than code coverage metrics, the increase in validity brings downsides in terms of execution time and applicability. Commonly used mutation operators create many mutants for a single method; in the worst case, all test cases need to be executed for each mutant to determine whether it can be killed or not. Hence, despite several optimization techniques, mutation testing is computationally complex due to the effort needed to generate and test a large number of mutants. Furthermore, equivalent mutants distort the results and are considered a major problem. Consequently, there are no indications that mutation testing has been widely adopted as a test efficacy criterion in practice (Ivanković et al., 2018; Jia and Harman, 2011; Madeyski et al., 2014). 1.2 Problem Statement It is important to know how thoroughly a software application has been tested in order to decide whether a new version of an application is ready 1.2 | Problem Statement 15 for release or whether further testing is necessary to ensure that it behaves as expected. In the latter case, it is relevant to know which parts of the application have been insufficiently tested and would benefit most from further testing. To answer these questions, code coverage metrics are the de facto standard in industry. However, a test case that triggers the execution of a large portion of an application contributes a lot of coverage, even if it does not contain any assertions. That is, these metrics do not take into account whether covered methods are tested with appropriate assertions, or whether they are executed without any assertions or only incomplete ones. According to Fowler (2004), test cases that do not contain any assertions are useless, unless their purpose is to check the absence of thrown exceptions. Consequently, the execution of code does not make it possible to conclude that the covered code has been tested effectively. Therefore, more profound techniques are needed to determine the effec- tiveness of a test suite in terms of fault detection capabilities. Such techniques exist (for example, mutation testing, or checked coverage) and provide more meaningful insights into test effectiveness. However, their applicability in practice is limited, for various reasons. Therefore, there is a need to strike a balance between easily computable but less valid techniques and more valid but overly complex techniques. 1.3 Research Goal The aim of this dissertation was to develop measures and techniques to better determine the effectiveness of a test suite with reasonable computational efforts. We wanted to come up with an approach that outperforms code coverage metrics in terms of validity and is, at the same time, less resource- intensive than currently used mutation testing approaches. We also sought to study what characteristics point to methods that exhibit a low fault risk and can therefore be deferred or excluded in quality assurance (QA) activities. Furthermore, we wanted to investigate how test case selection 16 1 | Introduction and prioritization approaches can be extended to further reduce the time to the first failure in a test suite execution, which would enable developers to investigate failures earlier. Our research focused on automated software tests in test suites that were manually implemented by developers. Automated tests are critical for continuous integration (Hilton et al., 2017) and are becoming ever more important. We studied test suites of libraries and systems implemented in Java and investigated them in respect to their capabilities to detect faults. We focused on Java, because it is among the most popular programming languages (Chan, 2019; Diakopoulos and Cass, 2016; StackOverflow, 2019). Java belongs to the object-oriented languages and is strongly typed (Gosling et al., 2013). We assumed that our findings may also apply to other languages that exhibit these characteristics such as, for example, C#. 1.4 Contributions to Knowledge This dissertation makes the following contributions to knowledge. Conceptual • We present and define a novel mutation operator at the method level.1 The purpose is to identify pseudo-tested methods, which are methods that are covered by at least one test case, none of which can detect when the whole logic is removed from the method. • We define the minimal stack distance as a measure in the context of tests to quantify the proximity between methods and test cases. • We define a set of metrics and create a machine-learning model to predict pseudo-tested methods without the need to execute a costly mutation analysis. • We create a machine-learning model based on source-code metrics to identify methods whose code can be considered to be too trivial to test because they contain hardly any faults. 1 I presented a preliminary version of this mutation operator in Niedermayr (2013). 1.4 | Contributions to Knowledge 17 • We devise a hybrid test case selection and prioritization approach that additionally incorporates test effectiveness information to reduce the time to the potentially existing first test failure in a test suite execution. Evaluations • We conducted a mutation analysis with the presented mutation opera- tor on 19 study objects and showed that they all exhibit pseudo-tested methods. • We studied the characteristics of pseudo-tested methods and showed that they are relevant and should be tested more thoroughly. We also identified measures that exhibit a moderate correlation with pseudo- testedness in some study objects. • We conducted an empirical study with 21 study objects and showed that our machine-learning model can successfully predict pseudo-tested methods. • We conducted an empirical study with six study objects and showed that methods exist that are too trivial to test. We also presented the performance of machine-learning classifiers to predict these methods. Implementations • We developed a new mutation analysis tool, which implements the presented mutation operator to identify pseudo-tested methods. • We extended the existing mutation testing tool Pitest (PIT) by a new feature to compute a full mutation matrix and submitted it as a pull request, which was merged into the main branch. • We implemented a dynamic analysis to compute the minimal stack distance measure between the methods and the test cases. • We extended the hybrid test case selection and prioritization approach in the software-quality analysis suite Teamscale such that it additionally considers test effectiveness information. 18 1 | Introduction 1.5 Previously Published Material Parts of the contributions presented in this thesis have been published in: • Rainer Niedermayr, Elmar Juergens, and Stefan Wagner. Will My Tests Tell Me If I Break This Code? Published in: Proceedings of the 1st International Workshop on Continuous Software Evolution and Delivery (CSED’16). ACM, 2016. • Jakob Rott, Rainer Niedermayr,1 Elmar Juergens, and Dennis Pagano. Ticket Coverage: Putting Test Coverage into Context. Published in: Pro- ceedings of the 8th Workshop on Emerging Trends in Software Metrics (WETSoM’17). IEEE, 2017. • Rainer Niedermayr, Tobias Röhm, and Stefan Wagner. Poster: Identifi- cation of Methods with Low Fault Risk. Published in: Proceedings of the 40th International Conference on Software Engineering Companion (ICSE’18 Companion). ACM, 2018. • Rainer Niedermayr and Stefan Wagner. Is the Stack Distance Between Test Case and Method Correlated With Test Effectiveness? Published in: Proceedings of the 23rd International Conference on Evaluation and Assessment in Software Engineering (EASE’19). ACM, 2019. • Rainer Niedermayr, Tobias Röhm, and Stefan Wagner. Too Trivial To Test? An Inverse View on Defect Prediction to Identify Methods with Low Fault Risk. Published in: PeerJ Computer Science (5). PeerJ, 2019. • Roman Haas, Rainer Niedermayr,2 and Elmar Juergens. Teamscale: Tackle Technical Debt and Control the Quality of Your Software. Pub- lished in: Proceedings of the 2nd International Conference on Technical Debt (TechDebt’19 Tools Track). IEEE, 2019. 1 I authored and reviewed drafts of the paper and approved the final draft. 2 I reviewed drafts of the paper and approved the final draft. 1.5 | Previously Published Material 19 1.6 Structure of Dissertation The remainder of this dissertation is organized as follows: • Chapter 2 provides the background on the main topics of this disserta- tion. It presents an overview of the testing terminology, describes ex- isting techniques for evaluating test suites, and explains used machine- learning techniques. • Chapter 3 presents the state of the art in this research area. It discusses related work regarding test effectiveness, defect prediction, and test case selection and prioritization. • Chapter 4 introduces the concept of pseudo-testedness, describing the idea and its advantages, and drafting its realization. • Chapter 5 describes pseudo-tested methods and their characteristics, explains that they are present in many projects, and shows their rele- vance. • Chapter 6 introduces a measure to describe the proximity between test cases and methods. It presents a machine-learning classifier, which uses this proximity measure along with further easily computable measures, and shows that pseudo-tested methods can successfully be predicted without mutation analysis. • Chapter 7 describes how methods can be identified that do not neces- sarily need to be tested due to a low fault risk. These methods can be skipped from a mutation analysis to make it even faster and its results more relevant. • Chapter 8 shows how test case selection and prioritization approaches can be enhanced by including information about test effectiveness. • Chapter 9 summarizes and discusses this dissertation and its limita- tions. It also discusses which future work could be undertaken on the basis of the completed work. 20 1 | Introduction Ch ap te r 2 Background This chapter provides an overview of the background to this dissertation. It introduces definitions for tests and their types, defines faults and related terms, describes code coverage metrics and mutation testing, and explains machine- learning techniques used in this dissertation. 21 2.1 Testing Terminology This section defines the testing terminology used in this dissertation. Fig- ure 2.1 presents an overview of the most important terms and their relations. 2.1.1 Test Cases and Test Suites A test case (also referred to as test) executes functions of a system (or a library) and compares the computed result or the observed behavior with the expected one. A test case will pass if the system behaves as expected; otherwise, it will fail (Zelkowitz, 2003). Thereby, a test case aims to detect faults and ensure the correctness of the implementation. A test case implicitly also checks the absence of thrown exceptions for a given program flow (Fowler, 2004). A test case usually consists of actions and preconditions to prepare the system under test, actions and input data to trigger the execution of the intended computations, an oracle to determine the test verdict by validating computed results and observed behavior, and actions for the tear-down (Zhi and Garousi, 2013). A test case can be either automated or manual. An automated test case is defined in the source code as a sequence of method calls and assertions, or specified as steps and conditions in other formats that can be interpreted by a test runner. Such a test case can be executed without human interaction (Taipale et al., 2011). Automated test cases can either be implemented by developers or generated automatically from the source code using corre- sponding tools (Fraser and Arcuri, 2011). A manual test case, by contrast, is performed by a human (Taipale et al., 2011) and may be based on a semi- formal test case description. This dissertation focuses solely on automated software tests that were created by developers. A test suite is “a set of several test cases for a component or a system under test” (Homès, 2013). In object-oriented programming languages, test cases defined in the code are enclosed by a test class, which groups semantically 22 2 | Background Figure 2.1: Overview of the testing terminology of automated tests. related test cases and allows set-up procedures to be shared. A parameterized test is a special variant of an automated test case that is specified once in the code and executed multiple times with different input parameters (Tillmann and Schulte, 2005). 2.1.2 Test Oracle A test oracle determines whether a test passes or not (Barr et al., 2015; Naik and Tripathy, 2008). An automated test’s oracle usually consists of assertions (Li and Offutt, 2017). A test assertion (also referred to as assertion) is a means of comparing an expected value with a computed value or observed behavior (Green and Kostovarov, 2013). Assertions in the form of method invoca- 2.1 | Testing Terminology 23 tions are most common (e.g., assertEquals or assertNotNull). Deviation between an expected and an actual value results in a test failure. 2.1.3 Test Verdict The test verdict is the outcome of the execution of a test case. A test case’s verdict is successful if the test case passes without violating any assertions, without causing any (unexpected) exceptions or errors, and without exceed- ing a possibly specified time limit. Otherwise, the verdict of an executed test case is failed. Some test frameworks, for example, JUnit and TestNG, further differentiate between a test failure, which is caused by a violated assertion, and a test error, which is caused by an exception or an error thrown in the code under test (Langr et al., 2015). We make no distinction between test failure and test error in the following. Depending on the test framework, further possible test verdicts may exist. For example, a test case that is known to be failing or flickering may be temporarily disabled by a developer so that it is not executed. It would still appear in the execution report of the test suite and its verdict would be ignored. Ignored test cases are not relevant within the context of this dissertation and are considered as if they were not present. 2.1.4 Test Levels Test cases may be categorized based on their intended scope and the thereof derived goal. A unit test examines a small unit of code in isolation (Runeson, 2006); that is, it usually focuses on a single method or a class and its execu- tion does not involve databases or other systems. The goal of a unit test is to ensure that the code under test behaves correctly in isolation (Elbaum et al., 2006). Since a unit test executes only a small amount of code, its execution is fast and the effort to examine a failure and localize the underlying fault is low (Osherove, 2009). A component test deals with the next-largest scope and examines a component (module) of a system in isolation (Jin and Offutt, 1998). Next, an integration test tests the interplay among different compo- 24 2 | Background nents or systems and aims to identify problems at their boundaries (Beizer, 1990); that is, it ensures that the modules communicate correctly based on the same assumptions. A system test examines a whole, integrated software system (Jin and Offutt, 1998), which may consist of several components. Such tests often trigger the execution of a large functionality and compare the end result (which can be, for example, aggregated data, a report, or a log file) with the expected one (Elbaum et al., 2006). Unlike a unit test, a system test usually covers many methods of a system, and thus, it executes a lot of code. Consequently, a system test’s execution time is relatively long. In addition, changes to any of the covered code may require adaptions in the test case, resulting in considerable maintenance efforts. Higher-level tests are also more prone to non-determinism problems (Fowler, 2012b). Fur- thermore, the effort involved in debugging a system test and localizing the cause of a test failure may also be significant due to the amount of covered code and the involvement of different components. This also applies to tests that are performed through the user interface (Vocke, 2018). They require especially high maintenance efforts because “graphical user interfaces tend to change frequently and test scripts have to be adapted to these changes” (Berner et al., 2005). In practice, “the distinction among integration testing, system testing, and user acceptance testing often blurs” (Li and Offutt, 2017). It is common, especially in open-source projects, that developers do not categorize auto- mated tests at all and implicitly consider all tests as unit tests or distinguish only between unit tests and higher-level tests. The well-known build tool Maven1 provides only two execution phases for tests by default: one for unit tests and one for integration tests (ASF, 2019). Figure 2.2 presents the concept of the test pyramid, which was originally proposed by Cohn (2010). The test pyramid sketches the desired extent of test levels in terms of the number of tests and required execution time. It expresses that the number of tests at lower levels, such as, unit tests, should be proportionally high because these tests are small, fast, and relatively easy 1 https://maven.apache.org 2.1 | Testing Terminology 25 https://maven.apache.org slower faster more isolated more integrated System Tests Unit Tests Component Tests Integration Tests Figure 2.2: The test pyramid (following Cohn (2010)). to analyze in case of failures. By contrast, higher levels of the pyramid, such as, integration or system tests, should contain proportionally fewer tests (Fowler, 2012b; Wacker, 2015). Tests at higher levels are useful because they can detect integration problems that cannot be identified by unit tests, but they are much more expensive in terms of execution time, required maintenance, and debugging efforts. 2.1.5 Test Tools A test framework is a software tool to support the writing and running of automated test cases (Hamill, 2004). It comprises functionality to execute tests and report the results. Well-known test frameworks for Java are JUnit1 and TestNG.2 They are primarily intended for unit tests, but they can be and are commonly used to execute tests of other levels as well. Examples of Java 1 https://junit.org 2 https://testng.org/doc/index.html 26 2 | Background https://junit.org https://testng.org/doc/index.html test frameworks targeting higher levels of the test pyramid are JBehave,1 FitNesse,2 Citrus,3 and Selenium.4 Further libraries support and facilitate the development of automated tests by providing additional assertion methods (e.g., Hamcrest,5 assertJ,6 and others), or by providing mechanisms to create test doubles in the form of mock objects (e.g., Mockito,7 JMockit,8 and others). 2.1.6 Test and Application Code We define test code as the part of the code of a system (or a library) that is used solely for testing and is not included in releases deployed to production environments. Test code comprises preparation methods executed before the tests (to initialize test data and set up environments), test cases (to perform the tests), tear-down methods executed after the tests (to reset the state), and further utilities to support testing (e.g., custom assertion methods). By contrast, we define application code as the code of a system (or a library) that is running in production. The application code does not comprise experimental or sample code, does not overlap with the test code, and is the subject that is tested by the test cases. Code coverage is measured based on the application code. 2.1.7 Regression Testing Regression testing is a testing activity to “provide confidence that newly introduced changes do not obstruct the behaviors of the existing, unchanged part of the software” (Yoo and Harman, 2012). Hence, it aims to detect regression faults that are introduced during the evolution of a system. 1 https://jbehave.org 2 http://docs.fitnesse.org 3 https://citrusframework.org 4 https://www.seleniumhq.org 5 http://hamcrest.org/JavaHamcrest 6 https://joel-costigliola.github.io/assertj 7 https://site.mockito.org 8 https://jmockit.github.io 2.1 | Testing Terminology 27 https://jbehave.org http://docs.fitnesse.org https://citrusframework.org https://www.seleniumhq.org http://hamcrest.org/JavaHamcrest https://joel-costigliola.github.io/assertj https://site.mockito.org https://jmockit.github.io Figure 2.3: Relation between fault, defect, and failure. 2.2 Error, Fault, Defect & Failure An error is a “human action that produces an incorrect result” (IEEE, 2010) and a fault is a “manifestation of an error in software” (IEEE, 2010). Hence, a fault is an incorrect step or data definition in the code of a software. A regression fault (or software regression) corresponds to a fault in functionality from a previous version of a software and is caused by bugfixes and new functionality in a newer software version (Agrawal et al., 1993a). A defect is a fault that is detected during the use of a released software product (IEEE, 2010); that is, it is detected after the implementation and testing phase. A fault may cause failures. A failure is an “event in which a system or system component does not perform a required function within specified limits” (IEEE, 2010); hence, a failure is a deviation from the specified behavior. Figure 2.3 illustrates the relation among fault, defect, and failure. The RIPR model by Li and Offutt (2017) defines four criteria that are necessary for a failure to be observed. It is an extension of the RIP model, which was independently developed by Morell (1984) and Offutt (1988) in the 1980s. To be able to detect a fault, the fault needs to be reached; that is, be executed by a test case (reachability). Next, the execution of the faulty location must cause an incorrect program state (infection). Furthermore, the infected state must propagate to an incorrect final state or output (propaga- tion). Finally, a tester or a test oracle (e.g., an assertion) must observe the incorrect part of the final state or output (revealability). 28 2 | Background 2.3 Code Coverage Code coverage is a metric that expresses which proportion of application code of a software project is executed when running all test cases (Zhu et al., 1997). It can be computed at different levels. Method coverage (or function coverage) corresponds to the proportion of methods that are (partially or completely) executed by test cases out of all methods of the application code. Statement coverage measures which proportion of the executable statements are invoked at least once during testing (Hayhurst et al., 2001). It is the most used coverage criterion in practice (Mathur, 2013). Similarly, line coverage measures the proportion of executed lines out of all coverable lines (Tikir and Hollingsworth, 2002). Branch coverage measures the proportion of branches that are executed by the test cases (Homès, 2013). Decision coverage measures the proportion of decisions that are executed by the test cases (Homès, 2013), in which a decision is compound of one or more con- ditions. One hundred percent decision coverage requires that each decision is evaluated to both true and false (Hayhurst et al., 2001). The difference to branch coverage results from the fact that a branch may not necessarily exist for both outcomes of a decision (i.e., an else-branch may not be present). Condition coverage is more fine-grained and measures whether each condi- tion in a decision is evaluated to both possible outcomes (Hayhurst et al., 2001). Modified condition/decision coverage (MC/DC) measures “if every condition within a decision has taken on all possible outcomes at least once, and every condition has been shown to independently affect the decision’s outcome” (Rajan et al., 2008). For highly critical software in the avionics industry, a test suite that satisfies full MC/DC coverage of the source code is required (RTCA, 1992). Finally, path coverage measures the proportion of the execution paths from an entry point to an exit point (e.g., all paths within a method) that are executed during testing (Zhu et al., 1997). Coverage can also be applied at other levels outside the source code. For example, ticket coverage expresses which proportion of the methods added or modified during the implementation of a ticket (issue) have been tested (Rott et al., 2017). 2.3 | Code Coverage 29 When we refer to the term code coverage in this dissertation, we mean coverage at the method level (unless specified otherwise). We use the following definitions. Let M be the set of the methods of the application code and let T be the corresponding test suite. We define a method m ∈ M as covered if the test suite T contains at least one test case t that executes at least one of the statements in the body of m. We define the test-case specific coverage of a test case t ∈ T as the set of the methods that are covered by t. We define the overall coverage of an application as the union of the test-case specific coverage of all test cases t ∈ T . 2.4 Mutation Testing Mutation testing is an established technique to assess test suites (Offutt and Untch, 2001). It was first proposed by Lipton (1971) in the 1970s and formalized by DeMillo et al. (1978) and it has been studied extensively since then (Jia and Harman, 2011; Papadakis et al., 2017; Usaola and Mateo, 2010). The general idea behind mutation testing is to generate mutants by introducing faults into a program and checking if the tests can detect (kill) the faults. Mutation testing is based on two assumptions: the competent programmer hypothesis and the coupling effect hypothesis (Zhu et al., 1997). According to the competent programmer hypothesis of DeMillo et al. (1978), programmers are competent and tend to “create programs that are close to being correct.” In practice, this hypothesis may not be valid for large programs, but it suffices for mutation testing that the hypothesis holds with respect to an individual fault (Gopinath et al., 2014b). The consequence of the competent programmer hypothesis is that most faults are small and can be corrected by a few syntactical changes (Jia and Harman, 2011). The coupling effect claims that complex faults are coupled to simple faults in such a way that a test suite 30 2 | Background capable of detecting small faults is sensitive enough to detect more complex faults (DeMillo et al., 1978). The coupling effect has been investigated theoretically by Wah (2000) and Wah (2003) as well as empirically by Offutt (1992) and found to be valid. 2.4.1 Terminology A mutation operator is a deterministic transformation rule that generates a mutant by applying syntactical changes to the original program (King and Offutt, 1991). For example, a mutation operator may replace an addition with a subtraction, negate a condition, or remove a statement (as long as the code remains syntactically valid; that is, compilable). Mutations can be performed on the source code or on the byte code. Modern mutation testing tools operate on the byte code to avoid the need for a compilation, which is slow and requires access to libraries that are declared as dependencies. After a mutant is created, test cases are executed to check whether they can detect the fault, which was introduced by the mutation. State-of-the-art mutation testing tools run all test cases once before the actual mutation analysis and record which test case covers which method. This enables a tool to select the relevant test cases to examine a mutant so that the test execution can be limited to test cases that cover the altered code. A mutant is said to be killed if at least one test case of the test suite fails due to the changes; otherwise it is said to have survived or be alive (Zhu et al., 1997). A mutation may be killed by a test case by a failing assertion in the test or by a failing implicit check in the source code (e.g., a NullPointerException, or an ArithmeticException caused by a division through zero, or a thrown IllegalArgumentException). An equivalent mutant is—despite syntactical changes—semantically equiv- alent to the original program such that no possible change in behavior can be observed (Jia and Harman, 2011). Consequently, such a mutant does not represent an injected fault and cannot be killed by any test case; Listing 2.1 presents an example. Equivalent mutants cannot be detected automatically 2.4 | Mutation Testing 31 because the equivalence of two functions is generally not decidable (Budd and Angluin, 1982). 1 public int computeFactorial(int n) { 2 int result = 1; 3 for (int i = n; i > 1 i >= 1; i--) { 4 result = result * i; 5 } 6 return result; 7 } Listing 2.1: Example of an equivalent mutant. A mutation operator like PIT’s “Conditionals Boundary Mutator,” which replaces > with ≥, will create an equivalent mutant in this method. Although the body of the loop will be executed once more often after the mutation, the outcome will not be influenced by multiplying result with one in the last pass. The outcome of a mutation analysis is a list of the mutations with their test verdict. A further aggregated measure is the mutation score (or mutation adequacy score), which corresponds to the proportion of killed mutants out of all created mutants (Jia and Harman, 2011). A test suite is considered mutation adequate if its mutation score achieves 100% (Offutt et al., 1996a). 2.4.2 Benefits and Downsides By inserting faults into a program and checking whether test cases can detect them, mutation testing assesses the fault detection capabilities of a test suite. Andrews et al. (2005), Frankl et al. (1997), and Just et al. (2014a) provided empirical evidence for that and showed that mutation testing outperforms coverage-based metrics as an indicator of test effectiveness. However, mutation testing suffers from two major drawbacks, which is why it is not widely used in practice (Ivanković et al., 2018; Jia and Harman, 2011; Zhu et al., 2018). First, mutation testing is computationally complex. Many mutants may be created for each method and, in the worst case, all test 32 2 | Background cases need to be executed for each mutant to determine whether a mutant can be killed or not. Second, equivalent mutants are a problem because they cannot be detected automatically (Offutt and Pan, 1997) and distort the results. Grün et al. (2009) identified equivalent mutants as an important problem because they are surprisingly common. Equivalent mutants lower the mutation score and force developers to needlessly analyze mutants in order to figure out which part of the code needs to be tested more thoroughly and how this can be achieved. According to Schuler and Zeller (2013b), a developer requires an average of 15 minutes to determine whether a mutant is equivalent or not. Similarly, Ivanković et al. (2018) reported a duration of 11.7 minutes per mutant. Thereby, equivalent mutants threaten the developer’s acceptance of mutation analysis results. A further obstacle to a wider use in industry is the mutation testing tools’ lack of integration with software development infrastructures and processes (Madeyski et al., 2014). In particular, there is no clear methodology for using the results of a mutation analysis. Most developers will ignore the results if they are not presented in an appealing way in tools that the developers already use in their daily work. Furthermore, the mutation score as such is not actionable and the sheer number of mutants overwhelms developers. In order to be beneficial for developers, mutation testing tools need to be executed within continuous integration, focus on recently changed code, present findings in an understandable way in an established tool, and ideally give hints on how to fix the problems. Petrović and Ivanković (2018) reported about the integration of mutation testing into Google’s development workflow. At Google, an incremental mutation analysis is triggered when a pull request is created. A limited number of mutants focusing on changed code are presented to the developers in the code review tool (see Section 3.3.3). 2.4 | Mutation Testing 33 2.4.3 Tools Many mutation testing tools have been developed for various programming languages. Commonly known tools for the programming language Java are Pitest (PIT),1 Javalanche,2 Major,3 Judy,4 and MuJava.5 The focus in this section is on PIT because it is the best-known and most mature mutation testing tool for Java applications (Delahaye and Du Bous- quet, 2013; Gopinath et al., 2017). Its code is open-source and maintained by an active community (Coles et al., 2016). Furthermore, it integrates with build tools, such as, Maven and Gradle. PIT has been used in several empir- ical software engineering studies (e.g., in Ahmed et al. (2016), Gopinath et al. (2015), and Gopinath et al. (2016)). The mutation analysis in PIT works as follows. First, PIT scans all classes in the system under test to identify possible mutation points and stores their location along with the intended mutation operator. Next, PIT runs all tests once to perform a line coverage analysis so that it knows the test-case specific coverage of each test at the line level. It also records the duration of each test case. PIT then analyzes all mutants that are covered by at least one test case. To do so, based on the previously identified mutation points, the tool applies the intended mutation operator to the byte code in order to generate a mutant one after another (Coles et al., 2016). The resulting mutant is kept in memory instead of writing it to the disk. Afterwards, a new Java Virtual Machine (JVM) is started for the test execution, and covering test cases are executed against the mutant. The test cases are prioritized by a heuristic, which takes a test’s execution speed, its line coverage, and naming conventions into account (Coles, 2019a). The analysis of a mutant aborts as soon as the first test case kills the mutant. A mutant may also be killed by a time-out or a memory error during testing; for example, when a mutation introduces an endless loop. Overall, PIT applies several optimizations to 1 http://pitest.org 2 https://github.com/david-schuler/javalanche 3 http://mutation-testing.org 4 http://madeyski.e-informatyka.pl/tools/judy 5 https://cs.gmu.edu/~offutt/mujava 34 2 | Background http://pitest.org https://github.com/david-schuler/javalanche http://mutation-testing.org http://madeyski.e-informatyka.pl/tools/judy https://cs.gmu.edu/~offutt/mujava reduce the analysis duration; for example, it operates at the byte code, selects the tests to run against the mutants, and minimizes the number of mutant executions (Coles et al., 2016). The mutation operators used in PIT are designed to generate hard-to-kill mutants, which comprise a minimal number of equivalent mutants (Coles, 2019c). The seven operators that are enabled by default are: • Conditionals Boundary Mutator: replaces < with ≤, > with ≥, and vice versa • Increments Mutator: replaces increments with decrements, and vice versa • Invert Negatives Mutator: replaces the sign of numeric variables • Math Mutator: replaces binary arithmetic operations (e.g., * with /) • Negate Conditionals Mutator: replaces conditional operators (e.g., == with !=) • Return Values Mutator: changes return values (e.g., dynamically re- turns 1 if the original return value is 0, or 0 otherwise) • Void Method Calls Mutator: removes calls to void methods Finally, PIT provides an incremental mutation analysis as an experimental feature (Coles, 2019b). PIT tracks changes to code and tests and keeps results from previous mutation analyses. This information is used in future analyses to infer the mutation testing verdict of mutants that are located in unchanged code so that it is not necessary to conduct any tests for them. The incremental analysis makes a few assumptions and optimizations, which “introduce a degree of potential error into the analysis” (Coles, 2019b). For example, to decide whether the behavior of a class has changed, PIT only considers changes to the byte code of this class, its super classes, and outer classes; it does not consider dependencies to other classes that interact with this class. In addition, changes to logic or data defined outside the Java code, such as, test data or code in other programming languages, are not tracked at all. 2.4 | Mutation Testing 35 2.5 Machine Learning Machine-learning algorithms analyze existing data with the goal of deriving mathematical models to make predictions or decisions (Kobayashi et al., 2011). Below, we explain how predictive machine-learning classifiers can be evaluated and present two algorithms. 2.5.1 Performance Evaluation Machine-learning models with a binary outcome are usually evaluated by computing their precision and recall. Precision expresses the proportion of correctly predicted items of a given label out of all items that were pre- dicted with this label. Hence, precision addresses the purity in retrieval performance; in other words, it is “a measure of effectiveness in excluding nonrelevant items from the retrieved set” (Buckland and Gey, 1994). It is computed as true positives true positives + false positives . Recall expresses the proportion of cor- rectly predicted items of a given label out of all items that actually have this label. Recall “can be viewed as a measure of effectiveness in including rele- vant items in the retrieved set” (Buckland and Gey, 1994) and is computed as true positives true positives + false negatives . The F-score (also known as F1-score or F-measure) combines precision and recall and is computed as 2 · precision · recall precision + recall . To evaluate the performance of a machine-learning model, the underlying data set needs to be separated into training data, which is used to create the model during the learning phase, and test data, which is used to assess the model. The most common technique for that is 10-fold cross-validation in which the data set is split into 10 disjunct partitions of (nearly) equal size (Arlot and Celisse, 2010). 9 partitions are used for training and the 10th partition is used for the performance evaluation (e.g., by computing precision and recall). This is repeated for each partition so that each one is used exactly once for testing. The performance results are then averaged over the 10 partitions. Figure 2.4 illustrates this technique. Cross-project validation is another technique that is commonly used in soft- ware engineering studies to separate training and test data for evaluations. 36 2 | Background TRAINING DATA TEST DATA Project X Project X Project X Project X Project X Project X Project X Project X Project X Project X Figure 2.4: 10-fold cross-validation. The data of one project is split into 10 partitions. The classifier is trained on 9 partitions and tested on data of the 10th partition. This is repeated for all partitions. TEST DATA Project A 100% Project F 100% Project B 100% Project C 100% Project D 100% Project E 100% TRAINING DATA Figure 2.5: Cross-project validation. The machine-learning model is trained on all but one project, and evaluated against the remaining project. This is repeated for all projects. A prediction model is trained on one or more projects (study objects) and tested on another unseen project. The aim of cross-project validation is to measure how generalizable a trained prediction model is; that is, how well it can be applied to other projects. This is relevant when no (precise) training data is available to create a project-specific model, as it is often the case in defect prediction. Generalizable models from other projects or companies can be an alternative in this scenario (Zimmermann et al., 2009). Figure 2.5 illustrates the cross-project validation technique. 2.5 | Machine Learning 37 2.5.2 Algorithms In this dissertation, we mainly use Random Forest and Association Rule Mining when we employ machine-learning techniques. 2.5.2.1 Random Forest Random forest is a supervised machine-learning algorithm for classification and regression, and was proposed by Breiman (2001). Random forest belongs to the ensemble learning methods based on decision trees; that is, the algorithm generates many independent decision trees as predictors and aggregates their results (Liaw and Wiener, 2002). Dietterich (2000) found that ensemble classifiers are often more accurate than any of the individual classifiers that form an ensemble. A random forest classifier creates a large number of independent trees and adds different layers of randomness to each tree. For each tree, a random sample of the training data is selected. Then, at each node of the tree, a subset of the variables (features) is randomly selected. The tree node is split using the best among the considered variables, unlike in standard trees where the best variable out of all variables is used for the split (Liaw and Wiener, 2002). To determine the best split, the Gini Index is commonly used, which measures variable impurity with respect to misclassifications (Tat, 2017). Each tree grows to the maximum depth using a combination of variables and is not pruned (Pal, 2005). The number of generated trees and the number of variables considered at each tree node is parameterized. When performing classification of new data, the prediction results of the different trees are aggregated by applying unweighted majority voting (Liaw and Wiener, 2002). The random forest classifier also supports regression; in this case, prediction results are aggregated by computing the average (Liaw and Wiener, 2002). Random forest classifiers do not overfit with an increasing number of trees (Liaw and Wiener, 2002) because of the law of large numbers (Feller, 1968). They can handle unbalanced data as well as incomplete data with missing 38 2 | Background values (Pal, 2005), and support categorical data (Pal, 2005). Furthermore, random forest classifiers provide an estimation of a variable’s relative im- portance by permuting data for a variable and observing the increase in prediction error (Liaw and Wiener, 2002). The computation of a random forest model can easily be parallelized (Breiman, 2001) because the model’s individual trees are independent. 2.5.2.2 Association Rule Mining Association rule mining is a machine-learning technique for identifying rela- tions between variables in a large dataset. It was introduced by Agrawal et al. (1993b). A dataset contains transactions consisting of a set of items that are binary attributes. An association rule represents a logical implication of the form { antecedent } → { consequent } and expresses that the consequent is likely to apply if the antecedent applies. Antecedent and consequent both consist of a set of items and are disjoint. The support of a rule expresses the proportion of the transactions that contain both antecedent and consequent out of all transactions. The support of an item X with respect to all trans- actions T is defined as supp(X ) = |t∈T : X⊆t| |T | . It is related to the significance of the itemset (Simon et al., 2011). The confidence of a rule expresses the proportion of the transactions that contain both antecedent and consequent out of all transactions that contain the antecedent. The confidence of a rule X → Y is defined as conf(X → Y ) = supp(X∪Y ) supp(X ) . It can be considered as the precision (Simon et al., 2011). A rule is redundant if a more general rule with the same or a higher confidence value exists (Bayardo et al., 1999). Amajor advantage of association rule mining is the natural comprehensibil- ity of the rules (Simon et al., 2011). Other commonly used machine-learning algorithms, such as support vector machines (SVM) or Naive Bayes classifiers, generate black-box models, which lack interpretability. Even decision trees can be difficult to interpret due to the subtree-replication problem (Simon et al., 2011). Another advantage of association rule mining is that the gained rules implicitly extract high-order interactions among the predictors. Association Rule Mining is primarily used for the market basket analyses 2.5 | Machine Learning 39 (Brin et al., 1997). It has also been successfully applied in defect prediction studies (Czibula et al., 2014; Ma et al., 2010; Song et al., 2006; Zafar et al., 2012). 40 2 | Background Ch ap te r 3 State of the Art This chapter presents an overview of related work to this dissertation. It discusses related work in the areas test effectiveness, defect prediction, and test case selection and prioritization, and identifies research gaps. 41 3.1 Code Coverage Code coverage metrics measure the proportion of code that is executed by test cases. Although code coverage does not assess whether a test suite adequately checks the observed behavior, it has been proposed as an indicator of test effectiveness. Several studies have been conducted to investigate whether it is valid to use code coverage for that, by investigating whether coverage at different levels correlates with a test suite’s fault detection capabilities. The studies provide conflicting evidence on this issue. Schwartz et al. (2018) suggested that the fault types used in the studies are one reason for the contradictory results because some types of faults are more difficult to detect than others. Below, we briefly summarize studies that confirm or disprove that code coverage is a valid indicator of test effectiveness. 3.1.1 Studies Confirming Coverage as Effectiveness Indicator An early study on the validity of coverage was conducted by Wong et al. (1994). They showed that the correlation between fault detection effective- ness and block coverage is higher than between effectiveness and size of the test set. They concluded that test cases that do not add additional coverage are likely ineffective in detecting faults. Similarly, Hutchins et al. (1994) showed that suites achieving high coverage levels are better at detecting faults than other randomly composed test suites of the same size. However, they remarked also that “100% code coverage alone is not a reliable indi- cator of the effectiveness.” To similar conclusions came Chen et al. (1995), Del Frate et al. (1995), Frankl and Iakounenko (1998), Frankl et al. (1997), and Horgan et al. (1994). Andrews et al. (2006) conducted an empirical study on an industrial program with known faults. Their results showed that more demanding coverage criteria lead to larger test suites that detect more faults. Similarly, Mockus et al. (2009) revealed that an increase in coverage exponentially increases test efforts and linearly reduces field problems. They suggested 42 3 | State of the Art that “code coverage is a sensible and practical measure of test effectiveness.” Namin and Andrews (2009) studied the relationship between size, cov- erage, and fault-finding effectiveness of test suites. They found that size and coverage are important for effectiveness and suggested a nonlinear relationship between them. Gligoric et al. (2013) and Gligoric et al. (2015) conducted a study with Java and C programs. According to their results, branch coverage is the best predictor of mutation score and should be used to compare different test suites. By contrast, Gopinath et al. (2014a) determined that statement coverage is the best predictor of mutation kills, outperforming block, branch, and path coverage. Kochhar et al. (2015) analyzed two large software systems with real bugs and found that statement and branch coverage correlate with the effectiveness in detecting bugs. The correlation was moderate in one project and strong in the other one. More recently, Bach et al. (2017) studied on a large industrial SAP system whether covered code exhibits fewer future bugs than uncovered code. They analyzed 16,000 real bugs, found that the studied relationship is statistically significant, and regarded coverage “as a meaningful metric to estimate the adequacy of testing.” 3.1.2 Studies Disproving Coverage as Effectiveness Indicator Several studies came to different conclusions. For example, Briand and Pfahl (1999) found no causal dependency between any coverage criterion and defect coverage. Some years later, Rajan et al. (2008) investigated systems from the civil avionics domain. They showed that the “MC/DC metric is highly sensitive to the structure of the implementation and can therefore be misleading as a test adequacy criterion.” They also stated that “these criteria can easily be ‘cheated’ by restructuring a program to make it easier to achieve the desired coverage.” Wei et al. (2010) conducted an empirical study in which they found that 3.1 | Code Coverage 43 “branch coverage is not a good indicator for the effectiveness of a test suite.” To similar conclusions came Staats et al. (2012) who investigated branch and MC/DC coverage criteria. They stated that both coverage criteria are only weak effectiveness indicators and therefore unsuitable for determining test suite adequacy. A well-known study by Inozemtseva and Holmes (2014) on Java programs found that “high levels of coverage do not indicate that a test suite is effective.” Furthermore, Inozemtseva and Holmes discovered that the type of coverage had little effect on the correlation. Similarly, Hemmati (2015) suggested that statement coverage is a weak criterion, and Ahmed et al. (2016), Kochhar et al. (2017), and Tengeri et al. (2016) found that coverage is not a good predictor of the expected number of defects. More recently, Antinyan et al. (2018) evaluated the adequacy of unit test coverage at Ericson. According to their results, the correlation of statement, decision, and function coverage with defects is weak. They concluded that “current unit test coverage measures do not seem to be any tangible help in producing defect-free software.” Finally, several practitioners (Benoit, 2014; Burns, 2019; Bytes, 2016; Fowler, 2012a; Lee, 2016; Mansoor, 2016; Marick, 1997; Mols, 2017; Seemann, 2015; Skinner, 2010; Xls, 2017; Zimmermann, 2017) critically discussed code coverage in blog posts. While they accepted that coverage can generally be useful for finding untested code, they all considered its widespread use as a quality target as highly questionable. They argued that code coverage is a misleading metric giving a false sense of confidence, and presented examples of that. They all suggested not to use it as a stipulated quality target. 3.2 Checked Coverage & Assertion Coverage Checked coverage and assertion coverage are further coverage measures, which take test oracles into account and aim to measure a test suite’s fault detection capabilities. 44 3 | State of the Art 3.2.1 Checked Coverage Checked coverage was proposed by Schuler and Zeller (2011) and expresses which proportion of executable lines are checked by test assertions. That is, “statements that are executed, but whose outcomes are never checked, would be considered uncovered” (Schuler and Zeller, 2013a). Their proposed implementation uses dynamic backward slicing. In the first step, the execution of each test case is traced and stored to a trace file. In the second step, a dynamic slice is created for each test assertion and statements are identified that influence the value checked in the assertion. The proportion of lines that are in at least one dynamic slice out of all executable lines constitutes the outcome. 3.2.2 Assertion Coverage Assertion coverage is a similar measure proposed by Besenreuther (2014) and “indicates which executed lines contribute to values checked by test assertions.” His approach to compute this measure performs run-time tracing of test cases. It “builds the dependency graph during test execution, and the line executions done inside assertion functions or methods are used as a starting point for traversing the graph. All lines that occur in nodes that are reached during the traversal are considered assertion covered” (Besenreuther, 2014). One challenge of this approach is the memory consumption, which can be excessive depending on the covered scope of a test case. It will be especially high when many values have a long life-time or are far apart from test assertions. In the study by Besenreuther, up to 1.7% of the tests could not be analyzed due to the memory consumption. He states that “the share might be higher on more complex test suites.” Another challenge regarding the implementation of such an approach are test cases invoking multi-threaded code. Each thread needs to be assigned to an individual tracer and tracers need to share the dependency graph and intermediate results among each other. 3.2 | Checked Coverage & Assertion Coverage 45 Furthermore, the outcome may become slightly inaccurate if certain parts of the analyzed code cannot be instrumented such that dependencies are missed. For example, native methods in Java code are not compiled to the byte code and cannot be instrumented. 3.2.3 Comparison Both approaches aim to be more valid than traditional code coverage metrics and therefore take test oracles into account. Both are dynamic analyses and need to execute the whole test suite once. They differ in their analyzed scope: checked coverage is based on exe- cutable lines, while assertion coverage is based on executed lines. Furthermore, while checked coverage in the proposed form considers only assertions as oracles, assertion coverage additionally takes expected exceptions into account (Besenreuther, 2014). However, both approaches do not consider checks within the application code (e.g., parameter validations). This can be considered as problematic because Schuler and Zeller (2013a) showed that test cases from which all assertions are removed still kill over 50% of the mutants killed by the original tests. The approaches also differentiate themselves regarding the design of the computation. While checked coverage uses dynamic backward slicing, assertion coverage applies run-time test tracing. “Dynamic slicing has a substantial run-time overhead compared to regular test execution” (Besen- reuther, 2014) because writing the trace file is expensive due to the I/O and compression overhead. Therefore, different as expected, checked coverage does not outperform modern mutation testing tools in terms of performance (Schuler and Zeller, 2011). Assertion coverage, which “monitors the origin of all values and establishes all inter-dependencies in the code during test execution” (Besenreuther, 2014), is more efficient than checked coverage, however, it requires more main memory. Finally, a drawback of both approaches compared to mutation testing is that a statement considered as “checked covered” respectively “assertion covered” may still contain faults. This is because assertions do not necessarily 46 3 | State of the Art uncover all faults. Zhang and Mesbah (2015) investigated assertion methods and found that there is a substantial difference between the effectiveness of different types. According to their results, assertTrue/assertFalse are more effective than assertions of type assert(Not)Equals, which are more effective than ones of type assert(Not)Null. Listing 3.1 presents a code example in which a test case covers all state- ments of the method createRectangle(. . .) and performs an assertion on the returned result. Although all statements of the method have an influence on the object to be asserted, the test case will not detect (subtle) faults in the code because it only asserts that the object is not null. 1 public static Rectangle createRectangle(double area , ,→ double aspectRatio) { 2 if (area < 0 || aspectRatio <= 0) { 3 throw new IllegalArgumentException (); 4 } 5 double width = determineWidth(area , aspectRatio); 6 double height = determineHeight(area , aspectRatio); 7 return new Rectangle(width , height); 8 } 9 10 @Test 11 public void testCreateRectangle () { 12 assertNotNull(createRectangle (20.0, 1.5)); 13 } Listing 3.1: Test case with a not very effective assertion. Another example of a test case with weak assertions is one that invokes a method returning a list and only checks whether the list as such is not empty or matches a specified length, without performing checks on the list elements. Even assertEquals assertions may not always validate an object in a perfect way. This is because such an assertion uses the equalsmethod of the particular object’s class to determine whether two objects are considered equal. An equals method does not necessarily compare the whole state of an object but may consider only some of the fields in the comparison. Hence, deviations in fields that are not checked remain undetected. 3.2 | Checked Coverage & Assertion Coverage 47 The validity of mutation testing does not rely on the effectiveness of assertion statements. 3.3 Mutation Testing Mutation testing takes fault detection capabilities into account. Therefore, it is not surprising that many studies demonstrated that mutation testing is a good indicator of test effectiveness. This has, for example, been shown in the empirical studies of Andrews et al. (2005), Chekam et al. (2017), Daran and Thévenod-Fosse (1996), Frankl et al. (1997), Gopinath et al. (2014a), Hutchins et al. (1994), Just et al. (2014a), Li et al. (2009), Mathur and Wong (1994), Offutt et al. (1996b), Papadakis et al. (2018), and Ramler et al. (2017). Just et al. (2014a) also confirmed the validity of mutation testing because they found that mutants are valid substitutes for real faults. Consistent with this observation is the empirical evidence provided by Andrews et al. (2006) and Daran and Thévenod-Fosse (1996) showing that the mutation score correlates with actual failure rates. In the following, we briefly summarize related work addressing mutation testing’s computational complexity and the problem of equivalent mutants, describe the use of mutation testing in practice, and present related work on pseudo-testedness. 3.3.1 Addressing the Computational Complexity Below, we summarize work on effort reductions, incremental mutation test- ing, and models to predict mutation testing verdicts. 3.3.1.1 Effort Reductions Researchers have suggested several approaches to reduce the computational complexity of a mutation analysis. Offutt and Untch (2001) classified these approaches as do fewer, do smarter, and do faster. Do fewer approaches 48 3 | State of the Art comprise the use of a smaller, representative set of mutation operators (Namin et al., 2008; Offutt et al., 1993; Offutt et al., 1996a), sampling of mutants (Acree Jr., 1980), mutants clustering (Ji et al., 2009), and higher order mutation, in which multiple mutation operators are applied at once (Jia and Harman, 2008). The most prominent do smarter approach is weak mutation, in which a mutant is immediately evaluated after its execution point instead of checking it at the end of a test execution (Howden, 1982; Jia and Harman, 2011). Do faster approaches comprise further run-time optimization techniques to speed up the generation and execution of mutants (e.g., byte-code mutants (Ma et al., 2005; Schuler et al., 2009), aspect- oriented mutation (Bogacki and Walter, 2006), or parallel mutation testing (Fleyshgakker and Weiss, 1994)). Jia and Harman (2011) later grouped these approaches into the reduction of the generated mutants (“do fewer”) and the reduction of the execution costs (combining “do faster” and “do smarter”). 3.3.1.2 Incremental Mutation Testing Zhang et al. (2012) proposed “regression mutation testing” to reduce efforts by incrementally updating mutation testing verdicts. Their approach com- pares control-flow graphs of two program versions to identify edges that may lead to different test behavior, and decides based on the outcome which mutants need to be re-assessed. They evaluated their approach on six study objects with five revisions each, and the revisions contained up to eight changed files. The reported reduction rate is between 0.08% and 100%. A similar concept was presented by Cachia et al. (2013). Their approach works by isolating test cases that invoke changed methods from the remaining test cases. However, when identifying these test cases, the approach does not consider interactions between methods. Their preliminary evaluation on the project Apache Commons CLI Library with 5 k lines of code (LOC) showed that speed improvements between 88% and 91% can be achieved. Bajada et al. (2015) extended this approach by considering the control flow to more precisely identify the effects of changes between two versions of a 3.3 | Mutation Testing 49 software. Their study on two small study objects revealed that numerous relevant mutants were generated that were skipped by the basic approach. They found that the costs for the extended approach are considerably higher than for the basic approach, but concluded that it remains advantageous compared to full mutation testing when the increment is small. They did not assess how many mutants that are affected by changes were erroneously skipped. The mutation testing tool PIT provides an experimental feature to perform incremental mutation testing on Java applications (see Chapter 2.4.3). Its performance has not been empirically validated yet. 3.3.1.3 Predicting Mutation Testing Results Prediction models have been employed in a few mutation testing studies. Namin et al. (2008) used linear models and Jalbert and Bradbury (2012) applied machine-learning models to predict the overall mutation score with- out executing a mutation analysis. Both did not perform predictions on individual mutants. Strug and Strug (2012) and Strug and Strug (2018) used machine learn- ing to reduce the number of mutants to be executed. They calculated the structural similarity of mutants and predicted based on results of similar mutants whether a given test would detect a mutant or not. However, their approach still requires a mutation analysis of a subset of mutants. The most related work to our machine-learning model for pseudo-tested methods is from Zhang et al. (2018) who predicted the mutation testing verdict of individual mutants with promising precision and recall values. However, it is difficult to judge their results because they also included mutants that are not covered by any test case. These mutants cannot be killed and are therefore trivial to predict based on line coverage. In Chapter 6, in contrast to their work, we predict the mutation testing verdict of a method and not of a single mutant, exclude methods that cannot be killed since they are not covered, and include the proposed minimal stack distance measure in the prediction model. 50 3 | State of the Art 3.3.2 Addressing Equivalent Mutants Budd and Angluin (1982) proved that the equivalence of two programs is generally undecidable. Consequently, it is not possible to fully automatically detect equivalent mutants. Since equivalent mutants distort the results and the manual analysis of mutants is labor-intensive, researchers have suggested a number of heuristics to uncover them. Baldwin and Sayward (1979) proposed an approach, which uses compiler optimization techniques to identify equivalent mutants. The idea behind that is that some equivalent mutants exhibit the same code after applying optimization or de-optimization rules to them. Offutt and Pan (1996) and Offutt and Pan (1997) devised a constraint-solving approach, which analyzes a mutant’s path conditions. Other researchers used program slicing to assist the detection of equivalent mutants (Harman et al., 2001; Hierons et al., 1999; Voas and McGraw, 1997). Grün et al. (2009) measured the impact of mutants on program execution and suggested that mutants with higher impact exhibit a greater “killability” and are less likely equivalent. More recently, Papadakis et al. (2015) incorporated their “Trivial Compiler Equivalence (TCE)” approach into the MiLu mutation testing tool. They claimed that it is the first tool that supports a fully automated detection of (some of the) equivalent mutants. Kintis et al. (2017) conducted an empirical study on TCE and reported that this technique can uncover approximately half of all equivalent mutants in Java. 3.3.3 Use In Practice Below, we briefly summarize research that focuses on the practical applica- bility of mutation testing. Nica et al. (2011) analyzed the performance of three mutation testing tools (MuJava, Jumble, and Javalanche) and concluded that mutation testing is too slow to be used in real-world software projects. Another comparison of five mutation testing tools, including PIT, was conducted by Delahaye and Du Bousquet (2013). They showed that all but one tool were able to 3.3 | Mutation Testing 51 complete the analysis for every study object. However, they pointed out that the tools need a lot of improvements to be ready for the use in real- world projects. The mutation testing tool PIT was also assessed by Klischies and Fögen (2016). They stated that the analysis is “fast enough for small to medium sized projects such as utility libraries,” but expressed strong concerns with regard to applicability to larger projects due to the required run-time. The maturity of mutation testing and different strategies to reduce the run-time overhead were investigated by Možucha and Rossi (2016). They suggested that selective mutation operators, second order mutation, and multi-threading can help increase the applicability. According to them, the obtained results are influenced by the use of these strategies such that a trade- off between speed and result quality needs to be found. They concluded that “mutation testing is mature enough to be more widely adopted.” Ramler et al. (2017) reported the results of a case study on mutation testing conducted with an engineering company developing safety-critical systems. The investigated system was implemented in C and comprised 60,000 LOC. The mutation analysis generated 75,043 mutants out of which 63.8% were killed by unit tests. The engineers investigated a sample of 200 live mutants and found at least 24 of them to be equivalent and at least 12 to be duplicated. According to the study, the analysis provided valuable hints on how to improve the test suite, and the engineers identified two new faults in the code when improving the tests. However, the mutation analysis took 4,000 hours computing time. Another case study on a complex real-world project was conducted by Ahmed et al. (2017). They applied mutation testing to a module of the Linux kernel and found mutation testing to be a useful tool because it helped them uncover two faults, although the module is “well tested and heavily used.” The mutation analysis took 3,499 hours, whereof 30 minutes each were needed to compile a mutated version. They discarded mutants that did not compile or were considered as not interesting and thereby reduced the number of mutants to be analyzed from 3,169 to 380. 10% of the mutants were found to be equivalent and 20% to be duplicated. 52 3 | State of the Art More recently, Petrović and Ivanković (2018) presented how mutation testing is employed at Google. The development process at Google specifies that code changes go through a review process before they are merged into the main branch of the repository. When a code diff is sent for review, an incremental coverage analysis is conducted to identify the set of covered lines that concern changes. Then, the mutation analysis is triggered. It first filters out lines with statements that are considered as not interesting (e.g., logging statements). It then generates at most one mutant for each remaining line, in which the mutation operator is randomly selected from the set of applicable operators for the given line. Finally, unit tests are executed against the mutants, and surviving mutants are presented to the developers in the code review tool. Developers can give feedback on the mutants to improve the exclusion of uninteresting mutants. Ivanković et al. (2018) revisited this case study by Petrović and Ivanković and identified challenges for a widespread adoption of mutation testing. First, they found that “unproductive mutants” exist, which are either not relevant, equivalent, or redundant. Developers do not want to spend time on them. Second, they pointed out that a developer’s workflow is commit-centered such that mutation testing needs to be integrated into that workflow. Third, more mutants are generated than developers can analyze in a reasonable amount of time. The challenge is to present the most relevant mutants to developers. 3.3.4 Pseudo-Testedness Vera-Pérez et al. (2017) also investigated pseudo-testedness and replicated our study published in Niedermayr et al. (2016). Pseudo-tested methods equally exist in all their study objects, even in ones with high coverage. Thereby, they confirmed our observation that pseudo-tested methods are common. They further studied the mutation score of pseudo-tested methods that is achieved when conducting an analysis with traditional mutation operators. They found that the mutation score of these methods is not always 0%, but it is substantially lower than the one of the remaining covered methods. 3.3 | Mutation Testing 53 Nonetheless, pseudo-tested methods exist that reach high mutation scores due to “trivial exception-raising mutants.” Their study objects contain 63 pseudo-tested methods with 100% mutation score; approximately 54% of these have only one or two mutants, but one method has 69 mutants, which are all killed by thrown exceptions. They manually analyzed pseudo-tested methods with void and boolean return type, and identified misplaced or missing oracles, too weak oracles, and missing test input as issues causing these methods to be pseudo-tested. Finally, Vera-Pérez et al. conducted developer interviews to get more insights into the practitioner’s view on pseudo-tested methods. According to the interviews, developers considered flaws identified by these methods as easy to understand and confirmed their relevance. The developers accepted pull requests that were provided during this study to improve the testing state of pseudo-tested methods. However, when they only received information about the problem without pull request, they did not always improve the test suite due to limited resources and other pending tasks. According to the developers, pseudo-tested methods are especially relevant and deserve additional testing efforts when methods concern the core functionality of a project or are widely used within a project. By contrast, methods that are automatically generated or concern debugging or logging functionalities belong to the ones considered as less relevant. Delplanque et al. (2019) coined the term “rotten green tests,” which are passing test cases that contain assertions, but at least one assertion is never executed. Such tests give developers a false sense of confidence because they contribute coverage without performing all intended checks. Delplanque et al. believe that rotten green tests are a possible cause for pseudo-tested methods. 3.4 Defect Prediction The idea behind defect prediction is to predict code areas that are especially fault-prone (Catal and Diri, 2009; Hall et al., 2012). Defect prediction allows 54 3 | State of the Art software engineers and testers to focus quality-assurance efforts on these areas and thereby supports a more efficient resource allocation (Menzies et al., 2007; Weyuker and Ostrand, 2008). The prediction models can be built using code metrics (D’Ambros et al., 2012; Menzies et al., 2007; Nagappan et al., 2006; Zimmermann et al., 2007), change metrics (Hassan, 2009; Kim et al., 2007; Nagappan and Ball, 2005), or a variety of further metrics (such as code ownership (Bird et al., 2011; Rahman and Devanbu, 2011), developer interactions (Lee et al., 2011; Meneely et al., 2008), dependencies to binaries (Zimmermann and Nagappan, 2008), mutants (Bowes et al., 2016), code smells (Palomba et al., 2016), and others). Defect prediction is usually performed at the component, package or file level (Bacchelli et al., 2010; Nagappan and Ball, 2005; Nagappan et al., 2006; Scanniello et al., 2013). More fine-grained prediction models have been proposed to narrow down the scope for quality-assurance activities. Kim et al. (2008) presented a model to classify code changes. Hata et al. (2012) applied defect prediction at the method level and showed that fine-grained prediction outperforms coarse-grained prediction at the file or package level if efforts to find the faults are considered. Giger et al. (2012) also investigated predictions at the method level and concluded that a random forest model operating on change metrics can achieve good performance. More recently, Pascarella et al. (2018) replicated this study and confirmed the results. However, they reported that a more realistic inter-release evaluation of the models shows a dramatic drop in performance with results close to that of a random classifier, and concluded that method-level bug prediction is still an open challenge. It is considered difficult to achieve sufficiently good data quality at the method level (Hata et al., 2012; Shippey et al., 2016); publicly available datasets have been provided in Giger et al. (2012), Just et al. (2014b), and Shippey et al. (2016). Cross-project defect prediction predicts faults in projects for which no historical data exists by using models trained on data of other projects (Xia et al., 2016; Zimmermann et al., 2009). He et al. (2012) investigated the usability of cross-project defect prediction. They reported that this type of prediction works only in few cases and requires careful selection of train- 3.4 | Defect Prediction 55 ing data. Zimmermann et al. (2009) also provided empirical evidence that cross-project prediction is a serious problem. They stated that projects in the same domain cannot be used to build accurate prediction models without quantifying, understanding, and evaluating process, data and domain. Sim- ilar findings were obtained by Turhan et al. (2009), who investigated the use of cross-company data for building prediction models. They found that models using cross-company data can only be “useful in extreme cases such as mission-critical projects, where the cost of false alarms can be afforded,” and suggested using within-company data if available. While some recent studies reported advances in cross-project defect prediction (Xia et al., 2016; Xu et al., 2018; Zhang et al., 2016), it is still considered as a challenging task. In Chapter 7, we identify methods that we consider as “too trivial to test”. While a lot of research has been conducted to predict fault-prone artifacts, our work is the first that explicitly focuses on methods with a low fault risk. 3.5 Test Case Selection and Prioritization Regression testing is an activity to ensure that conducted changes do not harm the existing behavior of a software (Yoo andHarman, 2012). A common procedure for regression testing is to execute all existing test cases of a test suite (retest-all). However, as software evolves, the number of automated test cases increases over time such that the execution time of the whole test suite rises. Consequently, it is often not feasible or too costly to execute the whole test suite after each change. It is sometimes even not possible to execute the all tests before an upcoming release. Therefore, various approaches have been developed and studied to reduce the efforts for regression testing (Graves et al., 2001). The main approaches are test suite minimization, test case selection, and test case prioritization. Latter two are related to our work in Chapter 8. Test case selection techniques aim to reduce regression testing efforts by deriving an appropriate subset of existing test cases (Rothermel and Harrold, 56 3 | State of the Art 1996); that is, these techniques determine which minimal set of test cases needs to be re-executed to check the behavior of the software after changes (Engström et al., 2010). Unlike test suite minimization, test case selection techniques do not permanently remove tests from a test suite (Rothermel et al., 1998). Test case prioritization techniques schedule test cases in such an order that test cases considered more important (in respect to a given goal) are executed earlier in the test suite execution (Rothermel et al., 2001). The prioritization goals can be to detect faults faster in the testing phase (Catal and Mishra, 2013; Rothermel et al., 1999), to increase overall code coverage as soon as possible (Elbaum et al., 2002), or to cover important features earlier (Rothermel et al., 2001). The vast majority of existing research literature deals with either the selection or the prioritization of test cases, but does not combine both (Silva et al., 2016). To the best of our knowledge, the first approach that com- bines selection and prioritization was presented by Wong et al. (1997). It performs a test selection based on modified code followed by a prioritization of the remaining test cases, which considers a test case’s increasing cost per additional coverage. In contrast to our work, they did not include test effectiveness information. Singh et al. (2010), Suri and Singhal (2011), and Walcott et al. (2006) presented test prioritization approaches that additionally incorporate a time constraint for the test execution. Thereby, their approaches implicitly also conduct a test selection by excluding lower-priority test cases that do not fit into the time frame. However, the selection does not take code changes (since the previous test execution) into account. Silva et al. (2016) combined selection and prioritization in a hybrid ap- proach, which is conducted in five stages. Their approach first maps features to software classes to determine their relevance. Next, it calculates the criti- cality of classes based on coupling, complexity, and relevance. Afterwards, it computes the criticality of tests by taking into account what classes they cover. It then identifies test cases that cover at least one changed class and applies an Ant Colony Optimization algorithm to select the set of the most critical tests that can be executed within available time. Finally, tests are 3.5 | Test Case Selection and Prioritization