HIERARCHICAL DELTA DEBUGGING FOR DEVELOPER-WRITTEN C# UNIT TESTS By Skylor Wixom A thesis Submitted to the faculty of the MSCS Graduate Program of Weber State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE in Computer Science August 14, 2026 Ogden, Utah Approved: Date: 09/29/2026 Committee Chair, Arpit Christi, Ph.D. 9/29/2026 Committee member, Kyle Feuz, Ph.D. Sept 29, 2026 Committee member, Bradley Peterson, Ph.D. ACKNOWLEDGMENTS I would like to thank my committee chair, Dr. Arpit Christi, for proposing this work, for the meetings that shaped the experiment and the analysis, and for reviewing every draft of this thesis. I would also like to thank my committee members, Dr. Kyle Feuz and Dr. Bradley Peterson, for their time and their feedback. Thanks as well to David Weber, whose tool and thesis this work extends, and to my family for their patience while I finished it. ii ABSTRACT A failing unit test usually runs more code than the fault it exposes. Failure-inducing and failure-preserving test case reduction helps developers in debugging and also in automatic fault localization. ReduSharptor, by Weber and Christi, reduces failing C# unit tests using the Delta Debugging (DD) algorithm. ReduSharptor uses the statement as its reduction unit. In this thesis, we implement the Hierarchical Delta Debugging (HDD) algorithm for test reduction as ReduSharptor.HDD and evaluate it on open source C# test projects. HDD exploits the hierarchical nature of the Abstract Syntax Tree (AST) of the program as generated by the Roslyn C# compiler to accurately reduce tests. We implement a top-down reduction approach in the HDD implementation, where the top-level statements are considered for reduction first, before moving to the next level in the AST. We evaluate the HDD algorithm on 32 synthetic mutation failures of developer-written unit tests from five open source projects by comparing it to a human-generated ground truth. The implementation achieves a 62.3% reduction in terms of statements with 97.1% precision and 95.9% recall; every disagreement came from a failure with more than one minimal set of statements. We further compare HDD with DD on five tree-structured tests, whose tree structure comes from conditional statements, loops and similar constructs. In three of these cases the HDD-based implementation achieves better reduction than DD. iii TABLE OF CONTENTS Page ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Reducing Failing Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ReduSharptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 3 4 5 5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Delta Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hierarchical Delta Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Other Reduction Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Statement-Level Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ReduSharptor and the Reducibility of C# Tests . . . . . . . . . . . . . . . . . . . . . . . . Test Reduction and Fault Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . Failure Preservation in Reducers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mutation Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8 9 10 10 11 12 12 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 3.2 3.3 3.4 3.5 3.6 3.7 Requirements on the Reduced Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cost of a Candidate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Statement Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Top-Down Traversal and Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Failure Preservation Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Working Copy and Run Record . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Relation to ReduSharptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 13 13 15 15 16 17 ReduSharptor.HDD: Usage, Architecture and Implementation . . . . . . . . . . . . . . . . 18 4.1 4.2 4.3 18 19 20 20 20 21 21 Introduction 1.1 1.2 1.3 1.4 1.5 1.6 2 3 4 Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Workspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Statement Hierarchy and Candidate Rendering . . . . . . . . . . . . . . . . . . . . 4.3.3 Delta Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.4 Reducer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 5 4.3.5 4.3.6 4.3.7 Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Run Record . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example Run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 22 22 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Subjects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Test Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bug Seeding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tool Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gold Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 25 26 27 27 28 5.1 5.2 5.3 5.4 5.5 5.6 6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Applicability (RQ1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Accuracy (RQ2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Inaccuracy (RQ2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Failure Preservation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tool Comparison (RQ3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Statement Categories (RQ4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 33 34 37 38 39 Threats to Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.1 7.2 7.3 7.4 43 44 46 46 6.1 6.2 6.3 6.4 6.5 6.6 7 8 Construct Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Internal Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . External Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Further Work and Conclusion 8.1 8.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 50 v LIST OF TABLES Table 1 Author Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 1 4.1 Source files of ReduSharptor.HDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.1 5.2 5.3 Subject projects and pinned commits . . . . . . . . . . . . . . . . . . . . . . . . . . . . Experiment setup commits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The 32 experiment tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 24 26 6.1 6.2 6.3 6.4 6.5 Reduction results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Run cost and verdicts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Comparison with the gold standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HDD against DD on the RQ3 tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Statement categories and removals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 32 33 38 40 vi LIST OF FIGURES Figure Page 1.1 A statement DD cannot reach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1 Statement hierarchy from inspect mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.1 4.2 Command line of ReduSharptor.HDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . Candidate trace of the ShouldReadHeaders run . . . . . . . . . . . . . . . . . . . . . . . 18 22 6.1 6.2 6.3 DelayTest1: original, tool and gold standard . . . . . . . . . . . . . . . . . . . . . . . . PNTRS against PTRS over all 32 tests . . . . . . . . . . . . . . . . . . . . . . . . . . . PrNTRS against PrTRS over the 14 tree-bearing tests . . . . . . . . . . . . . . . . . . . 36 42 42 vii Contribution of Authors The following authors contributed to the manuscript: Skylor Wixom (SW), Arpit Christi (AC). Table 1: Author Contributions Task Conception Data Collection Empirical Analysis Final Draft Thesis SW, AC SW SW SW, AC 1 CHAPTER 1 Introduction A failing unit test tells a developer that something is wrong. It does not tell them where. Before a fault can be fixed it has to be found, and that search is called fault localization. The difficulty is that a failing test rarely runs only the faulty code. It sets up objects, calls methods, checks values, and most of that work has nothing to do with the fault. Every statement that does not matter is one more thing the developer has to read and rule out. If the test can be made smaller while it still fails the same way, there is less to search. Smaller failing tests also help automated fault localization, which ranks program elements by how often failing runs execute them [1]. 1.1 Reducing Failing Tests The traditional way to reduce a failing input automatically is Delta Debugging (DD), introduced by Zeller and Hildebrandt [2]. DD splits the input into parts and tries smaller configurations, keeping any configuration that still fails. It keeps splitting until it reaches a result where removing any single remaining part makes the failure go away. That result is called 1-minimal. DD treats its input as a flat list. That works well when the input really is a list, like the lines of a file or the characters of a string. Program code is not flat. A loop or an if statement holds other statements inside it, and those statements can hold more. Program-statement-based DD implementations like ReduSharptor [3] see a whole loop as a single statement, so they can only keep the entire loop or remove the entire loop. They cannot reach inside and remove one statement from the body. Misherghi and Su proposed Hierarchical Delta Debugging (HDD) to solve this [4]. HDD runs DD on one level of the syntax tree at a time. Whatever survives a level is opened up, and the level below it gets reduced next. 1.2 ReduSharptor Weber and Christi built ReduSharptor, a tool that reduces failing C# unit tests written by developers [3, 5]. It uses the Roslyn compiler API to read a test into a syntax tree and treats the statement as the unit of reduction, because pieces smaller than a statement mostly produce code that does not compile. It then runs DD over the statements directly inside the test method. ReduSharptor does not descend into nested code. A statement that contains other statements, which the authors call a Tree statement, is handled as one unit. They made that choice on purpose. In a formative study of 100 tests from 10 projects, a Tree statement appeared directly under the method body in only 3.30% of 2 cases [3], so DD looked cheaper and accurate enough in practice. The same work also points to the gap. Weber and Christi note that most of their false negatives, statements the tool should have removed but kept, came from Tree statements [3]. Weber’s thesis names HDD as the main piece of further work [5]. A later study by Christi and Weber looked at what reduction actually removes and found that NonTree statements are removed in far larger numbers, and with a higher probability, than Tree statements [6]. Figure 1.1 shows the problem on a small constructed example. Suppose a bug in cart.Add stores the wrong name, so the assert on line 6 fails. Statement 7 comes after the failure and can be removed. Statement 5 has nothing to do with the name, but it sits inside the loop, and DD can only remove the loop as a whole, which would take the failing assert with it. Statement 2 is not needed either, but removing it breaks the build because statement 5 still uses coupon. DD stops with statements 1 through 6. HDD removes statement 7 at the top level, opens the loop and removes statement 5, and then, once coupon is no longer used, a second pass over the top level removes statement 2. The reduced test is statements 1, 3, 4 and 6. Of the seven statements, DD removed one, a 14.3% reduction; HDD removed three, a 42.9% reduction, and its reduced test is two statements smaller than DD’s. [Fact] public void AddedItemIsInCart() { var cart = new Cart(); var coupon = new Coupon("SAVE10"); cart.Add("apple"); foreach (var item in cart.Items) { cart.Apply(coupon); Assert.Equal("apple", item.Name); } Assert.Equal(1, cart.Count); } // 1 // 2 // 3 // 4 // 5 // 6 // 7 Figure 1.1: A constructed test in which DD cannot reach a statement inside a loop 1.3 Approach In this thesis, we implement the HDD algorithm for test reduction. The new tool, ReduSharptor.HDD, uses the Roslyn compiler API to build the same statement hierarchy. It implements the standard HDD algorithm of Misherghi and Su [4], working from the top of the tree to the bottom. First, the DD algorithm is applied to the top-level statements of the test method. Once a complete pass of DD is done and nothing more can be removed, the tool moves to the next level and repeats the process. We continue the process until the root of the abstract syntax tree (AST) is reached, which in our case is the bottom-most level that contains program 3 statements. The statement stays the unit of reduction, so the first change from the original is the hierarchy. We kept the original DD tool unchanged so it can serve as the baseline. The second change is how a candidate test gets judged. ReduSharptor, like the Delta Debugging tools before it, decides whether a candidate still fails from the pass or fail result of the test run, so a candidate that fails for a different reason still counts as failing. ReduSharptor.HDD records a fingerprint of the original failure, the full name of the test and the failure message the test framework reports, and accepts a candidate only when the target test fails with that same fingerprint. Chapter 3 explains the oracle. Whether comparing the message makes the reductions more accurate than a pass or fail check is a question the experiments answer directly: the two tools run on the same failing tests in RQ3, and the reduced test each one produces is checked against the original failure. We evaluate the tool on failing tests written by the developers of the same five open source projects Weber and Christi used [3]: language-ext, Umbraco-CMS, Fleck, BizHawk and Skclusive.Mobx.Observable. We do not write any of the tests ourselves. Each test fails because of a mutant seeded into the product code, and each mutant is saved as a diff against a fixed commit so the experiments are reproducible. For every test we also build a gold standard to compare the tool against. Chapter 5 describes how the tests and mutants were chosen. 1.4 Research Questions This thesis answers four research questions. RQ1 How applicable is the approach? Can ReduSharptor.HDD reduce mutant-seeded failing tests successfully? RQ2 How do the reductions compare with the gold standard? How accurate are the results using the standard measures of precision and recall? RQ3 Does HDD improve on the DD based approach? On five tree structured tests, how do the final test size and the preserved failure compare between ReduSharptor.HDD and the original ReduSharptor? RQ4 How does the category of a statement affect reduction? How are Tree and NonTree statements reduced, using the six measures defined by Christi and Weber [6]? RQ3 is a limited comparison on five tests chosen because they contain nested code. It is meant to show what happens on those tests, not to serve as a general benchmark of HDD against DD. 4 1.5 Summary When a unit test fails, the developer has to find the fault, and the test usually runs far more code than the fault touches. Reduction cuts a failing test down to the statements it needs to keep failing the same way, so there is less to read. The traditional DD-based implementations treat the test as a flat list of statements and reduce them using a systematic process while preserving the failure. Such implementations work on flat structures and cannot work on the hierarchical structures present in the program, such as if statements, while loops and for loops. We extended one DD-based implementation, proposed by Weber and Christi, so that it considers and reduces the hierarchical structures in the program and the statements within them, and checks each smaller test by the message it fails with, not only by whether it fails. The thesis implements an HDD algorithm to reduce program statements. To measure the accuracy of the reduction, we compare its result with a gold standard that we created by hand. The gold standard follows the same tree traversal as the algorithm, but at each level it uses a different reduction step: it removes statements one at a time while preserving the failure, puts a statement back when its removal does not preserve the failure, and continues until the test is minimal as judged by human intuition. The HDD-based reduction comes at a cost. It has to consider and process the hierarchical structures in the program, and each reduction attempt compiles the project and runs the test. Over the 32 tests a run took about seven minutes on average, with a median of three minutes, a minimum of under half a minute and a maximum of 24 minutes. So the additional cost of our implementation is reasonable. Precisely, the tool reduced all 32 developer-written failing tests from five open source projects, removing 62.3% of their statements. Against the gold standard it reached 97.1% precision and 95.9% recall, matching exactly on 25 tests. On the five tests with nested code it produced a smaller test that still fails in the original way where the flat tool could not, and it never accepted a test that fails for a different reason. And once nested statements can be opened, a statement’s category no longer predicts whether it will be removed. 1.6 Contributions This thesis makes the following contributions. 1. An HDD reducer for failing C# unit tests, built on Roslyn next to the original ReduSharptor, that reduces one statement level at a time from the top down and repeats until nothing more can be removed. 2. A failure preservation oracle that accepts a candidate only when the target test and the candidate have the same failure fingerprint. 3. An evaluation of test reduction for 32 distinct failures over five open source projects. The failures were created using standard mutation operators. 5 4. A comparison of results between the DD and HDD implementations for five failures across open source projects. 6 CHAPTER 2 Related Work This chapter covers the work this thesis builds on. We start with the two algorithms at the center of it, Delta Debugging and Hierarchical Delta Debugging. Then we go through the reduction tools that came after them, the argument for reducing at the statement level, ReduSharptor and the study of what it removes, and the link between reduction and fault localization. The chapter ends with two topics the experiments depend on: how a reducer decides that a smaller test still fails the same way, and mutation testing, which is where the seeded bugs in this thesis come from. 2.1 Delta Debugging Zeller and Hildebrandt introduced Delta Debugging (DD) as a way to take an input that makes a program fail and shrink it automatically [2]. The input is treated as a set of parts, and a test function runs the program on any subset of those parts. The outcome is pass, fail, or unresolved. Unresolved covers the cases where the test cannot say either way, such as an input that is no longer valid. Their minimizing algorithm, ddmin, starts by splitting the input into two subsets. It tests each subset on its own and then the complement of each subset, meaning everything except that subset. If a subset still fails, ddmin keeps only that subset and starts over with two pieces. If a complement still fails, ddmin keeps the complement and splits it into one fewer piece. If nothing fails, it doubles the number of pieces and tries again. It stops when the pieces are single elements and no single removal still fails. Algorithm 1 gives the procedure. The result is 1-minimal: taking out any one remaining part makes the failure go away. In the worst case the number of tests grows with the square of the input size. 7 Algorithm 1 ddmin, the minimizing Delta Debugging algorithm [2]. c is a failing configuration, n the number of pieces to split it into, and test returns FAIL, PASS or UNRESOLVED. start with n = 2 1: procedure ddmin(c, n) 2: if |c| = 1 then 3: return c 4: end if 5: split c into n pieces c1 , . . . , cn of about equal size 6: for each piece ci do 7: if test(ci ) = FAIL then 8: return ddmin(ci , 2) reduce to the piece 9: end if 10: end for 11: for each piece ci do 12: if test(c \ ci ) = FAIL then 13: return ddmin(c \ ci , max(n − 1, 2)) 14: end if reduce to the complement 15: end for 16: if n < |c| then 17: return ddmin(c, min(|c|, 2n)) 18: end if 19: return c increase granularity 1-minimal DD is greedy. It keeps the first smaller failing configuration it finds and never goes back. A 1-minimal result is therefore not always the smallest possible input, and when a failure has more than one minimal set of parts, the order in which parts are tried decides which one the algorithm reaches. This matters later in the thesis: Chapter 5 fixes one order for the gold standard reductions because of it. 2.2 Hierarchical Delta Debugging DD works best when the parts of the input are independent, like lines in a log or characters in a string. Many failing inputs have structure instead. HTML and XML files are trees, and so is program code. When DD runs over the lines of a program it tries many subsets that break the syntax, and each of those costs a test that can only come back unresolved. Misherghi and Su proposed Hierarchical Delta Debugging (HDD) for inputs like these [4]. HDD parses the input into a tree and works on it one level at a time, starting at the root. At each level it runs ddmin over the nodes at that level, removes the nodes that are not needed along with everything under them, and moves down to the next level. Because whole subtrees are removed together, far fewer of the candidates it tries are broken. A large subtree that is not needed is removed in one step, before any test is spent on the nodes inside it. Algorithm 2 gives the procedure. One pass from top to bottom is not always enough. Removing something deep in the tree can make a node higher up unnecessary after HDD has already moved past that level. 8 Repeating the whole pass until a pass removes nothing gives a result that is 1-tree-minimal, where no single remaining node can be removed and still fail. The repeated version is called HDD*. Algorithm 2 Hierarchical Delta Debugging [4]. tagNodes collects the nodes of the tree at one level, and prune removes from that level every node that ddmin did not keep, together with the subtree under it. HDD* repeats HDD until a pass removes nothing. 1: procedure HDD(tree) 2: level ← 0 3: nodes ← tagNodes(tree, level) 4: while nodes ̸= 0/ do 5: minconfig ← ddmin(nodes, 2) 6: prune(tree, level, minconfig) 7: level ← level + 1 8: nodes ← tagNodes(tree, level) 9: end while 10: 11: procedure HDD*(tree) 12: repeat 13: before ← size of tree 14: HDD(tree) 15: until size of tree = before The price is more tests than DD; Weber and Christi describe DD as O(n2 ) and HDD as O(n3 ) [3]. 2.3 Other Reduction Techniques Much of the later work builds on DD and HDD, either to make reduction faster or smaller, or to fit it to a specific kind of input. Regehr et al. built C-Reduce to shrink C programs that crash or miscompile in C compilers [7]. Reducing C programs raised a problem DD alone does not handle: a reduced program can start relying on undefined behavior, which makes it a bad bug report even though the compiler still fails. They called this the test case validity problem. Herfert et al. proposed Generalized Tree Reduction (GTR) [8]. Instead of only deleting nodes, GTR can also replace a node with a smaller node that fits in the same place in the tree, so it can shrink an input in ways deletion cannot. Hodován and Kiss revisited HDD itself [9]. They observed that the shape of the tree HDD works on depends on the grammar used to parse the input, and that an extended context free grammar gives flatter, better balanced trees than a standard one. They built their version into a tool called picireny, which parses inputs with ANTLR grammars. Sun et al. noticed that many reducers spend most of their time on candidates that are not even syntactically valid, and each of those still has to be compiled or run before it can be thrown away. Their tool, Perses, uses 9 the grammar of the language to generate only syntactically valid candidates [10]. Gopinath et al. built on Perses with DDSET, which reduces a failing input and then generalizes it into a pattern that describes a whole family of failing inputs [11]. Binkley et al. took a different route with Observational Based Slicing (ORBS) [12]. ORBS deletes lines of a program and keeps a deletion whenever the program still behaves the same on the values it observes. It does not need to understand the language at all, which is both its strength and its cost. Stepanov et al. built Reduktor to reduce bugs in the Kotlin compiler [13]. They found that general, language independent reducers had trouble on real Kotlin code because they do not account for the rules and dependencies of the language. Wang et al. proposed Probabilistic Delta Debugging, which gives each element a probability of being removable and updates it using the results of earlier tests, so the most likely removals are tried first [14]. They later applied the same idea to abstract syntax trees [15]. Most of these tools are built to work on many languages through a grammar. That makes them general, but it also means they know the syntax of a language and not much else. A candidate can be perfectly valid syntax and still not compile, because a variable it uses was removed or a method call lost an argument it needs. For source code where every candidate has to be compiled before it can be tested, those candidates are expensive. 2.4 Statement-Level Reduction Christi et al. used HDD together with statement deletion to reduce programs rather than tests, cutting away low priority features so software could run with fewer resources [16]. Later work by Christi and Groce added heuristics to choose what to try removing first [17]. Across that work they argued that reduction is most useful at the level of whole statements. Pieces smaller than a statement, like part of an expression, mostly produce code that does not compile. ReduSharptor takes that position for C# tests [3]. In Roslyn, a statement is any node of type StatementSyntax or a type derived from it. Removing a whole statement can still break the build, for example when a later statement uses a variable the removed one declared, but there are far fewer ways to break it than there are when removing lines, tokens or arbitrary tree nodes. This matters because building is the slow part, as Chapter 3 shows. 2.5 ReduSharptor and the Reducibility of C# Tests ReduSharptor is the tool this thesis extends [3, 5]. It takes a C# test file, the name of a failing test and the test project, and it reduces the failing test in place. It reads the test with Roslyn, collects the statements directly inside the test method, and runs DD over them. For each candidate it writes the smaller test back, builds the 10 project, and runs the test. A candidate that fails to build is dropped. A candidate whose test fails is kept. Weber and Christi evaluated ReduSharptor on 30 failing tests from five open source C# projects: language-ext, Umbraco-CMS, Fleck, BizHawk and Skclusive.Mobx.Observable. To make the tests fail, they took real bug fix commits from those projects and applied them in reverse. They compared the tool’s output against their own gold standard reductions and reported 96.58% precision and 96.45% recall [5]. ReduSharptor does not go inside Tree statements. Christi and Weber later defined the two categories formally [6]. A TreeStmt is a statement that has at least one other statement below it, like an if, a loop or a lambda passed as an action. A NonTreeStmt has no statement below it. A block, the pair of braces holding a list of statements, is never removed by itself, because removing the block node can leave Roslyn with code that is not valid. Only the statements inside a block are candidates for removal. Using those categories, Christi and Weber studied what ReduSharptor actually removed from the same 30 tests [6]. The tests held 759 statements, an average of 25.3 per test, of which 24.4 were NonTree and 0.9 were Tree. On average 71.87% of each test was removed. They measured the reduction with six numbers: the absolute and percentage reduction size for all statements (ARS and PRS), for Tree statements (ATRS and PTRS), and for NonTree statements (ANTRS and PNTRS). The average PNTRS was 70.44% and the average PTRS was 1.43%, and a paired Wilcoxon signed rank test found the difference significant (V = 465, p = 1.825 × 10−6 ), with NonTree statements removed about 50 times more. They also compared the probability that a statement of each category gets removed, using only the tests that had at least one Tree statement. The difference was significant there too (V = 99, p = 0.02877), with a NonTree statement about 1.7 times more likely to be removed. These are the measures we use for RQ4. There is one detail about the study that matters for this thesis. Every reduction in it came from ReduSharptor, which can only remove a Tree statement whole. It never removes a statement from inside one. The study describes what DD removes from C# tests, and it could not show what happens to the statements nested inside Tree statements. A reducer that descends into those statements can answer that question. 2.6 Test Reduction and Fault Localization Reducing a failing test helps more than the developer reading it. Christi et al. showed that running DD on failing tests before spectrum based fault localization, which ranks program elements by how often failing and passing tests execute them, improves the localization [1]. Vince et al. went further and showed that the intermediate test runs a reducer produces along the way are useful for fault localization as well, and not only the final reduced test [18]. 11 2.7 Failure Preservation in Reducers Every reducer depends on its test function, the check that decides whether a candidate still fails the way the original did. DD’s pass, fail and unresolved outcomes assume that “fail” means the same failure [2]. In practice a smaller input can fail for a completely different reason. C-Reduce’s test case validity problem is one version of this [7], and a unit test has its own ordinary versions. ReduSharptor judges a candidate by whether the test run fails [3], which cannot tell the original failure from a new one; Chapter 3 explains the oracle we use instead. 2.8 Mutation Testing Mutation testing makes small changes to a program, called mutants, to check whether a test suite notices them. Jia and Harman’s survey covers how the field developed and the standard operators used to create mutants, such as replacing one relational operator with another or one arithmetic operator with another [19]. Mutants are also used outside of judging test suites, as controlled stand ins for real faults when evaluating debugging and testing tools. The failing tests in this thesis come from mutants. Weber and Christi created their failures by reversing real bug fixes [5]. For the new tests in this work we seed each bug with a standard mutation operator instead, so the choice of bug comes from an established list and not from us. Chapter 5 lists the operators and explains how each mutant was chosen and recorded. 12 CHAPTER 3 Design This chapter explains the decisions behind ReduSharptor.HDD and why we made them. Most of them follow from two facts: a reduced unit test has to compile and run, and every candidate the reducer tries costs a build and a test run. Chapter 4 describes the code that carries these decisions out. 3.1 Requirements on the Reduced Test When reduction is used to shrink a compiler bug report, a piece of source that does not even compile can still be useful. That is not the case here. The reduced test is meant to be read and run by a developer looking for a fault, so it has to be a real test: it has to compile, it has to run, and it has to fail in the same way the original did. Any candidate that does not compile is thrown away, and any candidate that fails in a different way is thrown away too. Weber and Christi took the first position for ReduSharptor [3]; the second is new in this work and is the subject of Section 3.5. 3.2 Cost of a Candidate Every candidate is a modified copy of the test file. Before the target test can run, the test project has to be rebuilt, and for a real project that is the slow part. Weber and Christi measured about 11 seconds per build for language-ext [3]. On the experiment machine a candidate took between about 10 and 75 seconds depending on the project, because each candidate rebuilds the whole test project before the one test runs; Chapter 5 gives the numbers. The number of candidates, not the cost of any one of them, is what the design can control. Every choice below follows from it. 3.3 Statement Hierarchy The unit of reduction is the statement, exactly as in ReduSharptor. In Roslyn that is any node of the StatementSyntax class or a class derived from it. We kept this for three reasons. First, Weber and Christi argued, and earlier work by Christi et al. found, that pieces smaller than a statement mostly produce candidates that do not compile [3, 16]. Second, the six measures for RQ4 are defined over statements, and they split statements into the two categories this hierarchy is built from [6]. Third, if the unit stays the same, then the only thing that separates ReduSharptor.HDD from the original tool is the hierarchy, which keeps the RQ3 comparison clean. The hierarchy is the nesting of statements inside other statements. Level 0 holds the statements directly 13 inside the test method’s body. A statement that has statements below it, such as an if, a loop, a try, a local function, or a call that takes a lambda with a block body, is a Tree statement, and the statements inside its blocks form the next level. A statement with nothing below it is a NonTree statement. These are the same TreeStmt and NonTreeStmt categories Christi and Weber defined, so the classification the reducer walks is the bookkeeping RQ4 reports on [6]. Blocks are not units. Christi and Weber note that removing a block node can leave Roslyn with a tree that no longer produces valid code, so a block is only a container, and the units are always the statements inside it [6]. The same goes for the other wrappers a statement can sit inside: an else clause, a catch clause, or the body of a lambda. The tool looks through all of them until it reaches statements. One consequence is that a statement without braces around it, such as the return in if (x) return;, is not a unit on its own. It can only go when its parent goes. A gold standard reduction has to follow the same rule, or it could remove something the tool never tries. Figure 3.1 shows the hierarchy the tool prints for ConcurrentBeginWritesSecondFails, a real test from Fleck and one of the five used for RQ3. Nineteen of its twenty statements are NonTree. The one Tree statement is a call to BeginWrite whose callback is a lambda with two statements in its body. DD sees that call as one unit. ReduSharptor.HDD sees the call at level 0 and its two inner statements at level 1. Statement hierarchy for ConcurrentBeginWritesSecondFails: L0 [NonTree] var m = new Mock<Stream>(MockBehavior.Strict); L0 [NonTree] var q = new QueuedStream(m.Object); L0 [NonTree] var a = new MockAsyncResult("A"); L0 [NonTree] var b = new MockAsyncResult("B"); L0 [NonTree] var c = new MockAsyncResult("C"); L0 [NonTree] var trace = new StringBuilder(); L0 [NonTree] m.SetupBeginWrite(a, trace); L0 [NonTree] m.SetupEndWrite(a, trace); L0 [NonTree] m.SetupBeginWrite(b, new ApplicationException("**ERROR**"), trace); L0 [NonTree] m.SetupBeginWrite(c, trace); L0 [NonTree] m.SetupEndWrite(c, trace); L0 [NonTree] q.BeginWrite(a.Data, 0, a.Data.Length, q.EndWrite, null); L0 [Tree] q.BeginWrite(b.Data, 0, b.Data.Length, ar => { var ex = Assert.Thro... L1 [NonTree] var ex = Assert.Throws<ApplicationException>(() => q.EndWrite(ar)); L1 [NonTree] trace.AppendFormat("EndWrite({0})", ex.Message); L0 [NonTree] q.BeginWrite(c.Data, 0, c.Data.Length, q.EndWrite, null); L0 [NonTree] a.Complete(trace); L0 [NonTree] c.Complete(trace); L0 [NonTree] Assert.That(trace.ToString(), Is.EqualTo("BeginWrite(A) Complete(A)... L0 [NonTree] m.VerifyAll(); Totals: 20 statements | NonTree (#NTN): 19 | Tree (#TN): 1 | deepest level: 1 Figure 3.1: The statement hierarchy of ConcurrentBeginWritesSecondFails in Fleck, as printed by the tool’s inspect mode 14 3.4 Top-Down Traversal and Repetition The reducer works one level at a time, starting at level 0. At each level it first tries one candidate that removes every remaining statement on that level. If that candidate preserves the failure, the whole level goes in one step. Otherwise it runs ddmin over the statements of that level, with every other level held as it currently is. Whatever survives is kept, and the reducer moves down to the statements inside the surviving Tree statements. When it has gone through every level, one sweep is done. One sweep is not enough. Removing a statement deep in the tree can make a statement higher up unnecessary after the reducer has already passed that level. In the example in Chapter 1, the declaration of coupon could only go once the statement inside the loop that used it was gone. The reducer therefore repeats whole sweeps until a sweep removes nothing. This is the HDD* variant of Misherghi and Su’s algorithm, and its result is 1-tree-minimal: no single remaining statement can be removed and still preserve the failure [4]. We chose top-down for two reasons. It is the published algorithm, coarsest level first, and it is the cheaper order for a hierarchical reducer: candidates are the cost, and a coarse deletion at a high level removes a whole subtree before any candidate is spent on the statements inside it. A bottom-up order would spend its most expensive work on the insides of subtrees that a coarser pass would have deleted whole. During the experiments we considered a different order: inside-out, removing the uses of a variable before its declaration, so that fewer candidates fail to build. That order cannot change the result. A candidate that fails to build puts its statements back and nothing else happens, and only a candidate that preserves the failure changes the test. As long as the failure has one minimal set of statements that produce it, every order converges on that set. What the order changes is the number of build failures along the way, and those are common: on the RQ3 test in Figure 3.1, 97 of 178 candidate verdicts were build failures. A use-beforedeclaration order within a level would be a worthwhile optimization, and Chapter 8 lists it as further work. When a failure has more than one minimal set, order does decide which one survives, which is why the gold standard reductions in Chapter 5 follow one fixed order for every test. 3.5 Failure Preservation Oracle ReduSharptor accepts a candidate whenever dotnet test reports a failure. That cannot tell the original failure apart from a new one. If removing a statement makes a later assert fail instead, or leaves a variable null so that a different line throws, the test still fails and the candidate is still accepted. Reduction then follows the new failure, and the result may have nothing to do with the bug. A generic “it failed” is not enough; the failure has to happen at the same place, for the same reason. Before it reduces anything, the tool records a fingerprint of the original failure. It builds the working copy, runs the one target test with a filter on its full name, and reads the result from the TRX file the test runner 15 writes, never from the exit code. The fingerprint is the full name of the test together with the failure message the test framework reports, with runs of whitespace collapsed to single spaces so that formatting cannot break a comparison. For an assert failure the message carries the expected and actual values. For an exception it carries the exception type and its message. Stack trace line numbers are left out on purpose, since they shift every time a statement is removed. If the copy does not build, or the test passes, the tool stops, because the mutant is not seeded. Every candidate is then judged against that fingerprint and gets one of six verdicts. Preserved means the target test failed with the fingerprinted message, and it is the only verdict that accepts a candidate. TestPassed means the failure is gone. DifferentFailure means the test failed with another message. BuildFailed means the candidate did not compile. TestMissing means the target test did not appear in the results, which happens when a candidate removes something the test discovery needs. InfraError covers a crashed test host, a missing results file, or a timeout, with a limit of three minutes on a build and two on a test run. A build failure or an infrastructure error is never counted as a preserved failure. Ddmin proposes the same configuration more than once, so the tool caches every verdict by the content of the candidate and answers a repeat from the cache without a build or a test run. On the test in Figure 3.1, 80 of 178 candidates were answered that way. One escape hatch was planned. If a test’s failure message turned out to change from run to run, the rule was to fall back to the exception type alone for that test and record the change. Chapter 5 says whether any test needed it. 3.6 Working Copy and Run Record The tool never writes to the original project. Before a run it copies the whole working tree of the subject project, without its build output, into a folder for that run. Every candidate is written into the copy’s test file, and every build and test run works on the copy. Each candidate is generated from a pristine parse of the copy’s test file, never from the previous candidate, so a bad step cannot corrupt the next one. The run folder is also the record of the run. It holds the reduced working copy, snapshots of the original and the reduced test, the fingerprint and every TRX file the oracle read, a log of every candidate with the statements it tried to remove and its verdict, and a CSV with one row per candidate giving its sweep, level, verdict, whether the cache answered it, and how long it took. One folder per bug is the reproducible record behind that bug’s row in the results, and the candidate counts for RQ3 come straight from the CSV. 16 3.7 Relation to ReduSharptor Two things separate ReduSharptor.HDD from ReduSharptor: the hierarchy, and the fingerprint oracle. Everything else is deliberately the same. The unit is the statement, the search at each level is ddmin, the projects and the kind of tests are the ones Weber used, and the original tool is kept unchanged in the same solution so it can be run on the same tests for RQ3. Chapter 6 reports what each of the two differences did to the results. 17 CHAPTER 4 ReduSharptor.HDD: Usage, Architecture and Implementation This chapter describes the tool that carries out the design in Chapter 3. It is a console program named ReduSharptor.HDD, written in C# on .NET 8, and it lives in the same solution as the original ReduSharptor so that both tools can be run on the same tests. The original tool is not modified. We wrote ReduSharptor.HDD as a new program rather than editing the original, because the design changes the search, the oracle and the file handling all at once, and because the original has to stay exactly as published to serve as the baseline for RQ3. 4.1 Usage The tool takes the same four arguments as ReduSharptor plus an optional fifth: the path to the test file, the name of the failing test method, the path to the test project, an output folder, and the target framework passed to dotnet test, which defaults to net45. The output folder has to be outside the subject project, because the tool copies the project into it. Figure 4.1 shows the command line. ReduSharptor.HDD <testFilePath> <testMethodName> <testProjPath> <outputDir> [targetFramework] testFilePath testMethodName testProjPath outputDir targetFramework Flags: --inspect exit. --verbose Full path to the .cs file containing the failing test. Name of the failing test method. Full path to the .csproj of the test project. Folder (outside the subject project) where run folders are created. Optional. Framework passed to dotnet test. Defaults to net45. Print the test’s statement hierarchy (levels, Tree/NonTree) and Also print each candidate’s attempted removals on the console. Figure 4.1: Command line of ReduSharptor.HDD Two flags change what the tool does. --inspect parses the test, prints its statement hierarchy in the form shown in Figure 3.1, and exits without copying or changing anything. We used it to find candidate tests for the experiments, since it reports a test’s statement count, its number of Tree and NonTree statements, and its deepest level without running anything. --verbose mirrors each candidate’s attempted removals onto the console while a run is going. Without it, the console shows one line per candidate with its verdict, and the full detail goes to the run log. The tool needs the mutant to already be in place. It is pointed at the subject project with the bug seeded 18 in the product code, and it confirms before reducing that the target test fails there. It does not seed mutants or apply diffs; that is part of the experiment process in Chapter 5, not of the tool. Visual Studio launch profiles carry the same arguments for running the tool from the debugger, one profile for a normal run and one for inspect mode. 4.2 Architecture A run goes through six steps in order. 1. Copy. The tool finds the root of the subject project by walking up from the test project to the nearest folder that holds a solution file, and copies that whole tree, minus build output and version control folders, into a new run folder named after the test and a timestamp. 2. Parse. It locates the test method in the copy’s test file with Roslyn and builds the statement hierarchy from Chapter 3, tagging each statement with its level and whether it is Tree or NonTree. 3. Fingerprint. It builds the copy, runs only the target test, and records the failure fingerprint. If the copy does not build or the test passes, the run stops here. 4. Reduce. The reducer walks the hierarchy top-down, level by level, running ddmin over each level and repeating whole sweeps until one removes nothing. Every candidate it proposes goes to the oracle. 5. Judge. For each candidate the oracle writes the candidate’s statements into the copy’s test file, builds, runs the target test, reads the TRX result, and returns one of the six verdicts. Verdicts are cached by candidate content. 6. Record. The reduced test is left in the copy, snapshots of the original and reduced test are saved, and the log, the candidate CSV and the summary are written. Each step is one source file, and Table 4.1 lists them. The split keeps the algorithm, the Roslyn transformation code, the test execution and the experiment record apart where practical. The only dependency beyond the .NET base libraries is the Roslyn package, Microsoft.CodeAnalysis.CSharp 4.11.0, so the tool builds and runs as a single project with no preprocessing step and no external scripts, the same property Weber and Christi set for the original [3]. 19 Table 4.1: The source files of ReduSharptor.HDD and what each one does File Job Program.cs WorkspaceManager.cs StatementTree.cs Ddmin.cs HddReducer.cs Oracle.cs RunLog.cs Arguments and flags; wires the steps together; prints the run summary Copies the subject project into the run folder; owns every path Finds the test method; builds the hierarchy; renders candidates The ddmin algorithm over a list of statements The level walk and the repeated sweeps; calls ddmin per level Fingerprint, build, single-test run, TRX parsing, verdicts, cache The per-candidate log, the CSV and the summary 4.3 Implementation 4.3.1 Workspace WorkspaceManager makes the working copy and hands back the four paths the rest of the run uses: the run folder, the working copy, the copy’s test file and the copy’s test project. It skips bin, obj, .git and .vs while copying. For a project the size of Fleck the copy takes under a second and a few megabytes; for BizHawk, whose solution sits at the root of a 626 MB tree, it takes longer, but it is still small next to a single candidate’s build. The copy is what gets built and tested from then on. The original project is read once during the copy and never written. 4.3.2 Statement Hierarchy and Candidate Rendering StatementTree does the Roslyn work. FindTestMethod searches the whole syntax tree for a method with the given name, so it does not depend on the namespace style or the class layout of the file. Build produces the hierarchy as a tree of StatementNode objects, each holding its syntax node, its level and its children. It enumerates the statements directly under a node by looking through blocks, else and catch clauses, invocation arguments and lambda bodies until it reaches StatementSyntax nodes, then recurses into each of those to build the next level. A node with children is a Tree statement. GetFullTestName derives the namespace-qualified name of the test, which the oracle uses to run that one test and nothing else. Candidates are rendered by a TestFileRewriter that keeps a pristine parse of the copy’s test file. To produce a candidate it takes the set of statements to remove, drops those nodes from the pristine tree with Roslyn’s RemoveNodes, and writes the result to the copy’s test file. Because every candidate starts from the pristine parse, removals at different levels combine safely, and no candidate is ever built on top of a previous one. When a statement is removed, everything under it goes with it. 20 4.3.3 Delta Debugging Ddmin.Reduce is the minimizing Delta Debugging procedure of Zeller and Hildebrandt [2], ported from the original ReduSharptor’s FindSmallestFailingInput. It splits the current list into sections, tests each section alone and then each complement, shrinks to the first configuration that preserves the failure, doubles the number of sections when nothing does, and stops when the number of sections would exceed the number of items. It is generic over the item type and takes the oracle as a function, so it knows nothing about statements or levels. One deliberate difference from the original: the split distributes items evenly across sections. The original’s GetDividedSections uses integer division and puts the remainder into the last section, which matters for RQ3 and is discussed in Chapter 6. 4.3.4 Reducer HddReducer.Reduce is the loop from Chapter 3. For each sweep it goes level by level, collecting the statements at that level that are still alive, meaning neither they nor any ancestor has been removed, and whose parent is a block. At each level it first judges one candidate that removes the whole level; a level with a single statement can only shrink this way, because ddmin never proposes the empty configuration. If that is rejected, it hands the level’s statements to Ddmin.Reduce with a judging function that writes a candidate keeping only the given subset of that level, with every other level held in its current state. Whatever ddmin keeps stays, and the rest is marked removed. When a sweep ends with nothing removed, the reducer stops and reports the sweep count, the number of statements before and after, and the Tree and NonTree counts of both. 4.3.5 Oracle Oracle runs the build and the test. CaptureFingerprint builds the copy, runs the target test with dotnet test filtered on its full name and a TRX logger, and stores the test’s name with the whitespacenormalized message from the TRX file. CheckCurrentState does the same for a candidate and maps the outcome to one of the six verdicts of Section 3.5. The test is run with --no-build, since the build was already run and judged on its own, and the exit code of dotnet test is ignored on purpose, because the TRX file is the evidence. Every TRX file is kept in the run folder under the candidate’s label. Builds are limited to three minutes and test runs to two, enforced by a process runner that reads output asynchronously and terminates the whole process tree on timeout; the original tool’s timeout was set to five seconds but a blocking read on the process output kept it from taking effect. The cache sits in front of the oracle. A candidate is keyed by the rendered content of its test file, and a repeat is answered from the cache with no build and no test run. On the trace in Figure 4.2, seven of twelve 21 candidates were answered that way; across the 32 runs the share is just under half. 4.3.6 Run Record RunLog writes three files into the run folder. run.log lists every candidate with the exact statements it tried to remove, its verdict and whether the cache answered it. candidates.csv has the same information as one row per candidate, with the sweep, the level, how many statements were kept out of how many, the verdict, the cache flag and the duration in milliseconds; the candidate counts for RQ3 come from this file. summary.txt holds the run identity, the oracle statistics, the wall time and the tool’s own computation of the six RQ4 measures. That last block is labeled as a cross-check only. The analysis of record for RQ2 and RQ4 is the workbook analysis described in Chapter 5, made against the gold standard, and the tool’s numbers exist so that those results can be checked against them, not the other way around. 4.3.7 Example Run Figure 4.2 shows the complete candidate trace of the first experiment bug, ShouldReadHeaders in Fleck, a five-statement flat test whose mutant makes the first assert fail. The twelve lines exercise every part of the system. The first candidate is the whole-level prune, which removes all five statements; with no assert left the test passes, so ddmin starts. Removing the last two asserts preserved the failure and the test shrank to three statements; removing the Connection assert as well preserved it again, and the test was two. At the final granularity each survivor was tried alone: the parse without an assert passes, and the assert without the parse does not build. The two candidates after that were the same two configurations proposed again, and the cache answered them. The second sweep went over the two survivors, and every one of its five candidates had been seen before, so it cost nothing. The result is two statements, and no smaller failing test exists. Sweep 1, level 0: 5 statements [cand_001] keep 0/5 -> TestPassed [cand_002] keep 3/5 -> Preserved [cand_003] keep 2/5 -> Preserved [cand_004] keep 1/5 -> TestPassed [cand_005] keep 1/5 -> BuildFailed [cand_006] keep 1/5 -> BuildFailed [cand_007] keep 1/5 -> TestPassed Sweep 2, level 0: 2 statements [cand_008] keep 0/2 -> TestPassed [cand_009] keep 1/2 -> TestPassed [cand_010] keep 1/2 -> BuildFailed [cand_011] keep 1/2 -> BuildFailed [cand_012] keep 1/2 -> TestPassed whole level removed: no assert, test passes Key1 and Origin asserts removed; shrink to 3 Connection assert removed too; shrink to 2 parse alone: no assert, test passes Host assert alone: ’request’ undefined cache: same candidate as cand_005 cache: same candidate as cand_004 cache cache cache cache cache Final: 5 -> 2 statements. 12 candidates: 5 evaluated, 7 from the cache. Figure 4.2: The candidate trace of the ShouldReadHeaders run, with a note on each verdict 22 CHAPTER 5 Experiments This chapter describes how the evaluation was set up: the subject projects, how the tests were chosen, how each one was made to fail, how the tool was run, how the gold standard was built, and what was measured. The aim is that every number in Chapter 6 can be traced back to a recorded diff, a run folder and a gold standard log, and that someone else could rebuild the experiment from this chapter. 5.1 Subjects We used the same five open source C# projects Weber and Christi used, so that RQ1 and RQ2 repeat their evaluation on the same kind of subjects [5]: language-ext, a functional programming library; UmbracoCMS, a content management system; Fleck, a WebSocket server; BizHawk, a multi-system emulator; and Skclusive.Mobx.Observable, a port of MobX to C#. They span a small library of a few thousand lines to a code base of well over a million, and they use three test frameworks: NUnit in Fleck and Umbraco-CMS, xUnit in language-ext and Skclusive.Mobx.Observable, and MSTest in BizHawk. Each project was pinned to one commit for the whole experiment, and every mutant is a diff against that commit. Table 5.1 lists the commits, the test project the tool was pointed at, and the target framework passed to dotnet test. Skclusive.Mobx.Observable had not been updated since its 5.2.0 release in 2020, and its tests targeted a .NET version that is no longer available, so its test project was retargeted to .NET 8. Fleck’s tests targeted several frameworks and were run on net45. The other three were taken at the head of their main branch when the experiment reached them. Table 5.1: Subject projects and the commit each one was pinned to Project Commit Test project Framework Fleck Skclusive.Mobx.Observable language-ext BizHawk Umbraco-CMS 1eb1862 Fleck.Tests net45 295c7b8 (5.2.0) Observable.Tests net8.0 2f0e3628 (2026-07-29) LanguageExt.Tests net10.0 e828062 (2026-09-12) BizHawk.Tests.Client.Common net48 667678157dc (2026-09-11) Umbraco.Tests.UnitTests net10.0 A few changes had to be made to the subjects so that the tools could build and run them, none of which touch the code under test. They are committed on top of the pinned commits as experiment setup, below the mutant diffs, and Table 5.2 lists them. Two are for ReduSharptor.HDD: Skclusive’s retarget, and a test adapter package that language-ext’s test project lacked. Two are for the environment: BizHawk ships two source generators as prebuilt DLLs that the experiment machine’s application control policy refused to load, 23 so they were rebuilt from the source in the same repository; and Umbraco’s build computes its version from the git history, which the tool’s working copy does not have, so a build targets file makes that step a no-op only when no .git folder is present. The rest are for the original ReduSharptor, which is run in Chapter 6 for RQ3: it passes no framework flag to dotnet test, so Fleck’s test project was single-targeted to net45 for the comparison, and it cannot parse a file that uses a file-scoped namespace, so the two test files it had to read in language-ext and Umbraco-CMS were converted to block-style namespaces, which changes indentation and nothing else. Table 5.2: Experiment setup commits, applied below the mutant diffs Project Change and reason Skclusive language-ext Test project retargeted to net8.0; the original target has no runtime xUnit VSTest adapter added so dotnet test discovers tests; DelayTests.cs given a block-style namespace for the original tool’s parser The two source generators rebuilt from the repository’s own source, since the shipped DLLs were blocked by application control Version step made a no-op when no .git folder exists; ContentTypeTests.cs given a block-style namespace for the original tool’s parser Test project single-targeted to net45 so the original tool, which passes no framework flag, builds and runs it BizHawk Umbraco-CMS Fleck The runs for bugs 13 to 32 and the RQ3 comparison were all made on one machine: an Intel Xeon W-2104 at 3.20 GHz with 32 GB of RAM running Windows 11 Pro for Workstations, with the .NET SDK 10.0.400. The first twelve bugs were run in August on a different machine, and the two of them in the RQ3 set were run again on the experiment machine with the same result. Per candidate, a build and test run took about 10 seconds on Fleck, Skclusive.Mobx.Observable and BizHawk, 40 to 75 seconds on language-ext, and about 33 seconds on Umbraco-CMS. A complete run, from the first build to the written summary, took 6 minutes 46 seconds on average over the 32 runs and 3 minutes 9 seconds at the median, from 23 seconds on the smallest Fleck test to 24 minutes 23 seconds on bug 27. Twenty of the 32 finished in under five minutes and six took more than fifteen: four on Umbraco-CMS, the 121-evaluation run of TestObserveValue, and bug 13, where six test-host hangs each ran to the two-minute timeout. The times for bugs 1 to 12 are from the August machine; the two runs repeated on the experiment machine took 11 minutes 2 seconds and 8 minutes 42 seconds there against 4 minutes 16 seconds and 3 minutes 13 seconds in August, so the experiment machine is the slower of the two. On the five RQ3 tests, run with both tools on the experiment machine, the original tool took 46 minutes 30 seconds in total and ReduSharptor.HDD 48 minutes 4 seconds. 24 5.2 Test Selection Every test in the experiment is an existing test written by the developers of its project. We did not write or modify any test. We set that rule so that the choice of tests could not be tuned to the tool. Weber and Christi made their tests fail by reversing bug fix commits. We could not reuse their failing tests, because the exact source changes were not recorded, and the projects have moved on since. Instead we made each test fail by seeding a mutant into the product code it exercises, as described in the next section. To find candidates we ran the tool’s inspect mode, described in Chapter 4, over the tests of each project. For each test it reports the statement count, the number of Tree and NonTree statements and the deepest level, which is what the selection needs. From those reports we picked six tests per project, following Weber’s structure of five projects and six tests each. In each project the tests with the most and deepest Tree statements were taken first, and the remaining slots were filled with flat tests of varied sizes whose asserts compare values. Those criteria set the pool; within the pool the picks were arbitrary and made before any run, and no test was chosen for how the tool did on it. The one rule applied after a run is reducibility, and the three swaps it caused are reported in Chapter 7. The strongest tree test in each project was marked as that project’s RQ3 test. Four rules shaped the picks. Each test is a single test method with no parameter cases, so that one run of the tool judges exactly one execution of the test. A test only counts if it is reducible: after the mutant is seeded and the tool is run, at least one statement has to be removed. A test the tool cannot reduce says nothing about accuracy. Tests whose asserts check a boolean flag were avoided where a value assert was available, because a flag assert fails with the same message no matter which mechanism broke, which makes a weak fingerprint and lets a different failure pass as the same one. Finally, the five RQ3 tests each had to be reducible, have more than five statements, contain at least one Tree statement, and carry a mutant from one of the standard operators described in Section 5.3. The first two bugs, both in Fleck, predate the rule on mutation operators: a wrong variable name in the request parser for ShouldReadHeaders, and a dropped letter in a string literal for ShouldRespondToCompleteRequestCorrectly. Both are real developer-written tests, and we kept them as the first two experiment bugs, so the full set is those two plus the 30 new tests, 32 in all. RQ1 and RQ2 report over all 32. Table 5.3 lists the 32 tests with their project, size, Tree statement count and the operator used to seed each one. Fourteen of the tests contain at least one Tree statement; the other eighteen are flat. 25 Table 5.3: The 32 experiment tests. Stmts is the statement count; #TN the number of Tree statements; the five RQ3 tests are starred. IN is Invert Negatives, RV is Return Values. 5.3 ID Project Test 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ShouldReadHeaders ShouldRespondToCompleteRequestCorrectly ShouldGenerateServerHandshake ConcurrentBeginWrites ConcurrentBeginWritesSecondFails ⋆ ShouldReadHeadersFromRequest ShouldProvideAdditionalHeaders ConcurrentBeginWritesFirstEndWriteFails TestBasic TestComputed TestComputedValuesAndAction TestAllowModificationInComputed ⋆ GeneralRespectsMarkerBinding DelayTest1 ⋆ MassAddRemoveTest MapAddInOrderTest MapAddInReverseOrderTest FetchBack EqualsTest ExtendsMovie AllOperationsRespectBatching AssertNoMissingCores MarkersUnaffectedByMovieExtension Last Correct WhenReservedGreaterThanCurrent ⋆ Can Reset Dirty Properties Cascades Into Property Types ⋆ Can Deep Clone Content Type With Reset Identities Domain Binding Culture Does Not Overwrite Existing Segment Context HandleAsync ApplyTokenResponse BackOfficeClient RedactsBothTokens CreateUrlSets WithMultipleMedia ReturnsAllMediaUrlInfos CreateUrls WithMultipleUrls ReturnsAllUrls TestObserver TestObserveValue Fleck Fleck Fleck Fleck Fleck Fleck Fleck Fleck Skclusive Skclusive Skclusive Skclusive BizHawk language-ext language-ext language-ext language-ext language-ext language-ext BizHawk BizHawk BizHawk BizHawk BizHawk Umbraco-CMS Umbraco-CMS Umbraco-CMS Umbraco-CMS Umbraco-CMS Umbraco-CMS Skclusive Skclusive Stmts #TN Operator 5 13 13 15 20 15 18 15 10 10 18 20 16 10 10 20 18 10 9 13 13 6 13 8 16 11 14 15 13 11 63 35 0 0 0 0 1 0 0 0 0 0 4 7 0 2 1 0 0 0 0 4 1 3 0 2 4 3 1 0 0 0 3 3 pre-standard pre-standard AOR ROR ROR RV RV AOR RV RV RV LCR IN ROR AOR RV ROR IN ROR ROR ROR LCR IN RV ROR IN ROR IN RV RV IN IN Bug Seeding Each test was made to fail by one change to the product code it exercises. For the operators we did not define our own set. We took the standard mutation operators described in Jia and Harman’s survey of mutation testing [19] and used that as the standard: every change from bug 3 on is an instance of one of them. The operators used are relational operator replacement (ROR), such as == to !=; arithmetic operator replacement (AOR), such as + to -; logical connector replacement (LCR), && to ||; Invert Negatives, flipping a sign or a boolean; and Return Values, replacing a method’s return with null, a constant or an empty value. We adopted this rule after the first bugs were seeded so that no mutant could be questioned as hand picked to suit the tool. The operators come from the literature, not from this experiment, so if the set is biased the bias is not ours. For each test the procedure was the same. Run the test on the clean project and confirm it passes; a test that fails on clean code is not a valid fixture. Find the product method the test exercises by following the calls from the test body, and apply one operator at one site. Run the test again and confirm it fails, and read the failure message, which becomes the fingerprint. Save the change with git diff as a patch file named for 26 the bug and the test. Restore the project. Every one of the 32 mutants exists as such a patch against the pinned commit, so any bug can be re-seeded with git apply and the whole experiment can be rebuilt. This closes a gap in the earlier evaluation, whose reversed commits were not recorded. Where a choice of site remained, we preferred a mutant whose failure is a value comparison, because the expected and actual values in the message identify the failure. A weak message, such as a bare null reference exception, was accepted only where the executed path admits exactly one source for it, so that no other statement could produce the same message. Some operators had no live site in some projects. Skclusive.Mobx.Observable’s value paths have no site for LCR or Invert Negatives that changes an observable result, and in Umbraco-CMS two mutant designs would not compile because the project turns nullable warnings into errors, so a different operator was used at a different site. Each such case is recorded with the bug. 5.4 Tool Execution With the mutant seeded, the tool was run as described in Chapter 4, with the test file, the test name, the test project and framework from Table 5.1, and an output folder outside every project. Two checks were made on every run. First, the tool has to reduce something, or the test is invalid and swapped. Second, the statement count the tool reports has to match the count inspect mode gave when the test was picked; a mismatch means the test file the tool read was not the pristine developer test. That check caught one tainted run, where an editor had overwritten a statement in the test file before the run; the file was restored and the run repeated. The two RQ3 tests that were first run on a different machine were run again on the experiment machine and produced the same reduced test, statement for statement. 5.5 Gold Standard In previous work, researchers have used manual reductions or transformations of test or program input, performed by researchers or developers, for accuracy evaluations and comparisons [3, 5, 20, 21, 22, 23, 24, 25, 26, 27]. Such manual transformations have been used for both empirical analyses and case studies. We continue to use similar manual reductions to establish a gold standard for evaluation and comparison. For RQ2, every reduction is compared against a gold standard: the same test reduced by the first author, with the same mutant seeded, by the method below. Measuring a reducer’s precision and recall against a manually produced reduction of the same test is how ReduSharptor was evaluated [3, 5], and we keep that design. The process follows the tool’s own rules. The reduction is greedy, and when a failure has more than one minimal set of statements, the order of attempts decides which one survives. A gold standard reduction that walked a different path could disagree with the tool without either of them being wrong. The gold 27 standard therefore follows the tool’s rules, the same unit, the same oracle, whole Tree statements first, level order and a fixpoint pass, and one fixed statement order for every test, top to bottom. That fixed order is not ddmin’s candidate order, and the two can end in different places only when a failure has more than one minimal set of statements. Where the two agree, that agreement says the tool searched correctly and judged correctly. Where they disagree, the disagreement is real, and Chapter 6 explains each one. The walk follows the tool’s traversal, top down and one level at a time, but not its search within a level. The tool runs ddmin over a level, splitting the level’s statements into pieces and complements and testing those. The manual walk does not divide the level at all. It attempts one statement at a time: remove it, build, run the test, and either keep it out or put it back before the next statement is tried. The method is the same for every test. First run the unchanged test once and record its failure message; that is the reference every kept removal has to reproduce exactly. Then go top to bottom through the statements at the top level, one at a time: comment the statement out, save, build, run the one test, and read the result. If the message is the same, the statement stays out. If the test passes, fails differently, or does not build, the statement goes back. A Tree statement is attempted whole first, with everything inside it. If it is removed, its inner statements go with it and are never attempted on their own. If it has to go back, its inner statements are attempted one at a time as the next pass, after the current level is finished, because the tool sweeps a whole level before it descends. A statement without braces around it is not attempted on its own, since the tool never does that either. When the bottom is reached, the whole walk repeats over the survivors, and it stops when a complete pass removes nothing. If the tool’s result shows a set of statements removed that no single removal in the walk could explain, that set is attempted together as one step and logged as a pair. Every attempt is logged as one line, with the statement, the verdict and whether it stayed out. The hygiene matters as much as the rules: build before every run, so the verdict comes from the code as it currently is and not from a stale binary; read the verdict only from the run that just finished; and when several different attempts all return the same unexpected message, suspect that an earlier removal is doing the failing and go back to check it. The surviving statements, with the comments stripped, are the gold standard for that test. The tool’s reduced test is not studied until the gold standard is finished. 5.6 Measurement For each test we record the original and reduced statement counts, and, from the direct comparison of the tool’s reduction with the gold standard on the same path, three counts: • True positives (TP): statements the tool removed that the gold standard also removed. • False positives (FP): statements the tool removed that the gold standard kept. 28 • False negatives (FN): statements the gold standard removed that the tool kept. Precision is TP/(TP+FP) and recall is TP/(TP+FN). The three counts are made statement by statement, never derived by formula from the size columns. Weber’s published precision and recall were computed differently in his workbook, so this thesis does not compare its numbers with his directly. For RQ4 we record, per test, the counts and measures defined by Christi and Weber [6]: the number of Tree and NonTree statements in the original test, with the Tree statements broken down into conditionals, loops and actions; the number of each category removed; the absolute and percentage reduction sizes overall (ARS, PRS), for Tree statements (ATRS, PTRS) and for NonTree statements (ANTRS, PNTRS), where the three percentages all use the test’s total statement count as their denominator; and the probability of removal per category, PrNTRS and PrTRS, which divide the removed count by the category’s count and are undefined for tests with no Tree statement. The statistical treatment mirrors theirs: a Shapiro-Wilk test for normality, then a paired Wilcoxon signed rank test with box plots. For RQ3, each of the five starred tests was reduced by both tools from the same mutant, and we record the size of each reduced test, whether the two reduced tests are the same, whether each reduced test still fails with the original failure, and the number of candidates each tool built and tested. The original tool judges a candidate by the exit code of dotnet test, so whether its reduced test preserves the original failure was checked by reading its failure message afterward. The tool computes the RQ4 measures itself in each run’s summary, and those numbers were used only to cross-check the workbook counts. The record of authority for every count in Chapter 6 is the analysis workbook, filled manually. 29 CHAPTER 6 Results This chapter reports what the experiment produced, in the order of the four research questions: whether the tool ran to completion on every test (RQ1), how its reductions compare with the gold standard (RQ2), how it compares with the DD tool on the five starred tests (RQ3), and how a statement’s category affected what was removed (RQ4). Every count comes from the analysis workbook described in Chapter 5, which we filled manually, and every candidate count comes from the run folders. Where a number needs an explanation, the explanation is here; what the numbers mean for the claims of this thesis is left to Chapter 7 and Chapter 8. 6.1 Applicability (RQ1) RQ1 asks how applicable the approach is: can ReduSharptor.HDD reduce mutant-seeded failing tests successfully? The tool was run on all 32 tests, one seeded mutant each, and it finished every run and produced a reduced test that still failed with the original failure message. No run ended in an unhandled exception. Two environment events happened during the runs, and both were absorbed by the oracle’s verdicts rather than stopping the tool: on GeneralRespectsMarkerBinding six candidates tripped a Debug.Assert inside BizHawk’s own code, which on .NET Framework opens a dialog and hangs the test host until the oracle’s timeout kills it, and on MarkersUnaffectedByMovieExtension one candidate’s rebuilt test assembly was refused by the machine’s application control policy, so the test was missing from the result. Both are recorded as their own verdicts (InfraError, TestMissing), and in both cases the tool treated the candidate as not preserving the failure and went on, which is the same call a person would make for a candidate that crashes the test host. Two runs did not reach a result and were started again in a fresh folder: the first run of ExtendsMovie stopped at the fingerprint step, before any candidate, when the same policy refused the freshly built product assemblies and the test produced no result, and the first run of GeneralRespectsMarkerBinding was stopped manually at its first InfraError so that the cause could be found. Both reruns completed, and only the reruns are counted. Table 6.1 lists the size of every test before and after reduction. The 32 tests hold 496 statements, and the tool removed 309 of them, leaving 187. The mean reduction per test is 57.9% of the test’s statements, the median is 60.0%, and pooled over all statements the reduction is 62.3%. The spread is wide, from 6.7% to 90.5%, and it tracks the shape of the test rather than the project or the operator. The two 6.7% cases, ConcurrentBeginWrites and ConcurrentBeginWritesFirstEndWriteFails, both assert on a whole execution trace that every setup statement feeds, so the only removable statement is the 30 VerifyAll call after the assert. The 90% cases are tests built from many independent repetitions of the same call, where the mutant breaks all of them and one repetition is enough to keep the failure. Weber reported a mean of 72% over his 30 tests [5]; the set here is smaller on average (15.5 statements per test against roughly 25 in his) and was picked for value asserts and for Tree statements, so the two means are not measuring the same population, and we do not read anything into the gap. Table 6.1: Reduction results for the 32 tests. Sizes are statement counts; the five RQ3 tests are starred. ID Test 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ShouldReadHeaders ShouldRespondToCompleteRequestCorrectly ShouldGenerateServerHandshake ConcurrentBeginWrites ConcurrentBeginWritesSecondFails ⋆ ShouldReadHeadersFromRequest ShouldProvideAdditionalHeaders ConcurrentBeginWritesFirstEndWriteFails TestBasic TestComputed TestComputedValuesAndAction TestAllowModificationInComputed ⋆ GeneralRespectsMarkerBinding DelayTest1 ⋆ MassAddRemoveTest MapAddInOrderTest MapAddInReverseOrderTest FetchBack EqualsTest ExtendsMovie AllOperationsRespectBatching AssertNoMissingCores MarkersUnaffectedByMovieExtension Last Correct WhenReservedGreaterThanCurrent ⋆ Can Reset Dirty Properties Cascades Into Property Types ⋆ Can Deep Clone Content Type With Reset Identities Domain Binding Culture Does Not Overwrite Existing Segment Context HandleAsync ApplyTokenResponse BackOfficeClient RedactsBothTokens CreateUrlSets WithMultipleMedia ReturnsAllMediaUrlInfos CreateUrls WithMultipleUrls ReturnsAllUrls TestObserver TestObserveValue Total Mean Original Reduced Removed % Removed 5 13 13 15 20 15 18 15 10 10 18 20 16 10 10 20 18 10 9 13 13 6 13 8 16 11 14 15 13 11 63 35 2 2 10 14 8 10 11 14 3 4 10 10 5 6 6 2 2 5 1 3 4 1 2 5 8 4 3 3 9 9 6 5 3 11 3 1 12 5 7 1 7 6 8 10 11 4 4 18 16 5 8 10 9 5 11 3 8 7 11 12 4 2 57 30 60.0 84.6 23.1 6.7 60.0 33.3 38.9 6.7 70.0 60.0 44.4 50.0 68.8 40.0 40.0 90.0 88.9 50.0 88.9 76.9 69.2 83.3 84.6 37.5 50.0 63.6 78.6 80.0 30.8 18.2 90.5 85.7 496 15.5 187 5.8 309 9.7 57.9 Table 6.2 shows what each of the 32 runs cost; for bugs 5 and 12 the row is the experiment-machine rerun, which matched the August run in every count. A candidate is one configuration ddmin proposed; it was either evaluated, meaning built and tested, or answered from the cache because the same source had been judged before. The cache answered 1,427 of the 2,864 candidates across the 32 runs, just under half, which is the repetition ddmin produces at its finer granularities and in the second sweep. The number of sweeps is the number of top-to-bottom passes the tool made before a pass removed nothing; all but two runs needed two, and none needed more than three. The verdict columns give the oracle’s answer for every candidate, cache 31 hits included. Build failures are the most common verdict on every test with more than a few statements, because ddmin proposes removing declarations before the statements that use them; the passed and preserved columns are the search itself; and the different-failure column, the candidates that still failed but with another message, is discussed in Section 6.4. Table 6.2: Run cost and verdicts for the 32 runs. Evaluated candidates were built and tested; cached ones were answered from an earlier identical candidate. Infra counts the six InfraError verdicts on bug 13 and the four TestMissing verdicts on bug 23. ID Candidates Evaluated Cached Sweeps Preserved Passed Diff. failure Build failed Infra 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 12 22 147 128 178 110 145 128 55 64 107 163 162 67 51 14 14 87 7 38 98 4 35 34 99 39 129 74 106 118 170 259 5 10 72 69 98 55 70 69 26 34 54 84 79 39 26 7 7 44 6 15 48 3 15 15 46 15 66 35 55 59 90 121 7 12 75 59 80 55 75 59 29 30 53 79 83 28 25 7 7 43 1 23 50 1 20 19 53 24 63 39 51 59 80 138 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 3 3 1 7 2 3 1 4 4 3 5 8 3 2 4 4 4 4 4 7 2 4 1 3 2 11 6 2 2 11 14 6 12 68 28 48 41 57 28 18 18 30 56 31 28 24 6 6 23 3 14 33 2 9 19 25 16 49 22 34 29 53 61 0 0 52 29 26 0 0 29 1 0 12 3 17 0 0 0 0 0 0 2 5 0 0 0 0 0 0 0 1 1 16 25 4 7 24 70 97 67 85 70 32 42 62 99 100 36 25 4 4 60 0 18 53 0 18 14 71 21 69 46 69 86 90 159 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 Total 2,864 1,437 1,427 66 136 897 219 1,602 10 On RQ1, then: ReduSharptor.HDD worked on five open source projects, 32 different mutants, five mutation operators, three test frameworks and four .NET target frameworks. It processed 496 statements across the 32 developer-written tests, completed every reduction, and handled the two environment failures it met as verdicts rather than crashes. Based on this information, we claim that the tool is highly applicable for C# projects and tests. Similar applicability criteria were used in previous research [3, 20]. The cost of a run is set by the subject’s build time and the test’s statement count, as Chapter 5 noted, and the run with the most evaluations, TestObserveValue at 121, took under twenty minutes, while the longest by the clock, bug 27 at 24 minutes for 66 evaluations, was set by Umbraco’s build time rather than its candidate count. 32 6.2 Accuracy (RQ2) RQ2 asks how the reductions compare with the gold standard: how accurate are the results using the standard measures of precision and recall? Table 6.3 compares the tool’s reduction of each test with the gold standard for the same test, made by the method of Section 5.5 with the same mutant seeded. The Gold standard column is the number of statements the gold standard removed, and the three counts are the direct statementby-statement comparison: true positives are statements both removed, false positives are statements the tool removed and the gold standard kept, and false negatives are statements the gold standard removed and the tool kept. Table 6.3: Comparison with the gold standard. Gold standard is the number of statements the gold standard removed. TP is the number of statements both the tool and the gold standard removed, FP is the number the tool removed and the gold standard kept, and FN is the number the gold standard removed and the tool kept. ID Test Gold standard TP FP FN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ShouldReadHeaders ShouldRespondToCompleteRequestCorrectly ShouldGenerateServerHandshake ConcurrentBeginWrites ConcurrentBeginWritesSecondFails ShouldReadHeadersFromRequest ShouldProvideAdditionalHeaders ConcurrentBeginWritesFirstEndWriteFails TestBasic TestComputed TestComputedValuesAndAction TestAllowModificationInComputed GeneralRespectsMarkerBinding DelayTest1 MassAddRemoveTest MapAddInOrderTest MapAddInReverseOrderTest FetchBack EqualsTest ExtendsMovie AllOperationsRespectBatching AssertNoMissingCores MarkersUnaffectedByMovieExtension Last Correct WhenReservedGreaterThanCurrent Can Reset Dirty Properties Cascades Into Property Types Can Deep Clone Content Type With Reset Identities Domain Binding Culture Does Not Overwrite Existing Segment Context HandleAsync ApplyTokenResponse BackOfficeClient RedactsBothTokens CreateUrlSets WithMultipleMedia ReturnsAllMediaUrlInfos CreateUrls WithMultipleUrls ReturnsAllUrls TestObserver TestObserveValue 3 11 3 1 12 5 7 1 7 6 8 10 11 8 4 18 16 5 8 10 9 5 11 3 8 7 11 12 4 2 57 30 3 11 3 1 12 5 7 1 7 6 8 10 11 3 3 17 15 5 7 8 9 5 11 3 8 7 11 10 4 2 57 30 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1 0 1 2 0 0 0 0 0 0 0 2 0 0 0 0 Total 313 300 9 13 Over the 32 tests the tool removed 309 statements, of which 300 were also removed in the gold standard, and the gold standard removed 13 statements the tool kept. That gives a precision of 300/309 = 97.1 percent and a recall of 300/313 = 95.9 percent. With 97.1% precision and 95.9% recall, we claim that the reductions of ReduSharptor.HDD are highly accurate. On 25 of the 32 tests the two reductions were 33 identical, statement for statement. The seven tests where they differed are 14, 15, 16, 17, 19, 20 and 28, and Section 6.3 goes through each of them. The agreement on the 25 needs to be read for what Section 5.5 says it is. The tool and the gold standard are bound to the same oracle, unit, traversal and fixpoint rule, and both are 1-minimal when they finish, so they can differ only where a failure has more than one minimal set of statements, and a value assert normally gives a unique one. A perfect match therefore says that the tool searched correctly and judged correctly under its own rules; it does not measure the reduction against a standard formed independently of them, which is the independence that produced Weber’s disagreements [5]. The seven disagreements are where the method could still tell the two apart, and they are analyzed in Section 6.3 and Section 6.4. 6.3 Inaccuracy (RQ2) Every one of the seven disagreements has the same cause: the failure admitted more than one minimal set of statements, and the order of attempts decided which set survived. In six cases the two minimal sets have the same size, so the tool’s reduction is as small as the gold standard and each false positive is paired with a false negative. In no case did either reduction lose the failure; both reduced tests fail with the reference message. Two mechanisms produce the non-unique sets. When two statements can each produce the reference failure and the oracle cannot tell them apart, whichever is attempted first while the other is still present is judged as preserved and is removed, and the other is then retained. This happened on six tests, all of them tests whose assert message carries no value. • DelayTest1 (14). Figure 6.1 shows the original test beside the tool’s six-statement reduction and the gold standard’s two-statement reduction. The test has two asserts, Assert.True(v == 0) inside the first loop and Assert.True(v == 1) at the end, and xUnit reports both as Assert.True() Failure Expected: False. The mutant makes the first assert fail. ddmin True Actual: removed the final assert inside a larger chunk before it ever tried Subscribe alone, and from then on the first assert was the only source, so the tool ended at 6 statements. The gold standard walk, top to bottom, tried Subscribe first; with the final assert still present the failure moved to it with an identical message, so Subscribe was removed, then both loops, and the walk ended at 2 statements, var v = 0; and Assert.True(v == 1);. This is the one disagreement where the two sizes differ: TP 3, FP 1, FN 5. It is also the one case where the gold standard lost the fault: its two-statement survivor fails on the unmutated code too. • MapAddInOrderTest (16) and MapAddInReverseOrderTest (17). Each test is a map followed by seventeen to nineteen Find calls that all throw the same System.Exception : 34 Broken under the mutant. The tool kept the first Find; the gold standard walk removed them from the top, the failure sliding to the next one each time, and kept the last. On test 17 the walk was stopped earlier than the last line, because on the shrunken map one particular lookup threw an IndexOutOfRangeException instead of Broken and so was retained. TP 17, FP 1, FN 1 and TP 15, FP 1, FN 1. • EqualsTest (19). Two adjacent Assert.False lines fail with the same text under the mutant; the tool kept the first, the gold standard the second. TP 7, FP 1, FN 1. • ExtendsMovie (20). Four lambdas each exercise the mutated undo path and each throws the same ArgumentOutOfRangeException. The tool kept the second lambda with its inner call; the gold standard kept the fourth. TP 8, FP 2, FN 2, the pairs being a lambda and the statement inside it. • HandleAsync ApplyTokenResponse BackOfficeClient RedactsBothTokens (28). The test reads two cookies and unprotects both; with the handler never called, Unprotect(null) on either cookie throws the same ArgumentNullException. The tool kept the access-token pair of statements, the gold standard the refresh-token pair. TP 10, FP 2, FN 2. MassAddRemoveTest (15) is the one case with a different mechanism. Under the mutant, Remove grows the map’s count instead of shrinking it, and the failing assert compares the count with a counter max that is decremented in the same loop. Removing Remove alone keeps the failure and so does removing max-- alone, but removing both makes the test pass. The tool’s chunk order dropped Remove first; the gold standard walk tried Remove while an earlier assert still guarded it, put it back, and dropped max-- instead. Both reductions have 6 statements. TP 3, FP 1, FN 1. Nothing about the message is at fault here: the two survivors are different tests that fail for the same reason. 35 The original test, 10 statements var span = TimeSpan.FromMilliseconds(500); var till = DateTime.Now.Add(span); var v = 0; delay(() => 1, span).Subscribe(x => v = x); while( DateTime.Now < till ) { Assert.True(v == 0); Thread.Sleep(10); } while (DateTime.Now < till.AddMilliseconds(200)) { Thread.Sleep(10); } Assert.True(v == 1); Reduced by the tool, 6 statements var span = TimeSpan.FromMilliseconds(500); var till = DateTime.Now.Add(span); var v = 0; delay(() => 1, span).Subscribe(x => v = x); while( DateTime.Now < till ) { Assert.True(v == 0); } Gold standard, 2 statements var v = 0; Assert.True(v == 1); Figure 6.1: DelayTest1 in language-ext, the test where the tool and the gold standard disagreed most. Both asserts fail with the same xUnit message, so the order of attempts decided which one survived. Six of the seven would not have happened if the fingerprint knew which assert had failed. In DelayTest1, where the tool reduced 10 statements to 6 and the gold standard reduced them to 2, the two results would have been exactly the same if each assert had a clear and different assert message. The message is the failure’s identity as the test framework reports it, and on a flag assert or a shared exception the message carries no identity; a fingerprint that also carried the failing line would have held the failure at the first assert in tests 14, 16, 17, 19, 20 and 28 and the gold standard would have reached the tool’s answer as well. Chapter 8 takes this up as further work. Test 15 is out of reach of any oracle, because both survivors preserve the same failure by any measure; only a convention about which alternative to prefer, such as keeping the statement that calls the mutated code, would decide it, and that is a rule for the gold standard rather than a feature of the reducer. 36 6.4 Failure Preservation Chapter 1 named the fingerprint oracle as the second change from the earlier tool, which judged a candidate by the exit code of dotnet test and so accepted any failure as the failure. The run data measures how often that difference mattered. A candidate judged DifferentFailure is one that built, ran, and failed, but with another message: exactly the candidate an exit-code oracle accepts and this oracle rejects. Table 6.2 shows 219 such candidates across the 32 runs, in 14 of them. Reading their messages, they are of two kinds. Most are exceptions thrown by a later statement once its setup was removed: null references and null arguments on ShouldGenerateServerHandshake (52 in all, a dozen of them handshake strings of another length instead) and on the two ConcurrentBeginWrites trace tests (29 each), strict-mock exceptions on ConcurrentBeginWritesSecondFails (26), an index exception on GeneralRespectsMarkerBinding (17). The rest are the test’s other asserts failing once the path to the fingerprinted one was cut, or the same assert failing with another value: 25 and 16 on the two large Skclusive tests, 12 on TestComputedValuesAndAction. On the other 18 runs the count is zero, among them ShouldProvideAdditionalHeaders, a test whose fingerprint is a bare null reference exception accepted at seed time only because its path admits one source for it, and whose zero different-failure verdicts bear that out. Every one of the 219 is a candidate that, under an exit-code oracle, would have been kept as a smaller failing test that no longer reproduces the seeded failure, and once accepted it would have steered the rest of the search. Section 6.5 shows the consequence end to end: on two of the five RQ3 tests the DD tool returned a smaller test than ReduSharptor.HDD, and in both the smaller test fails with a different failure that its exit-code oracle could not see. Judged by size alone, DD wins those two; judged by whether the reduced test still shows the seeded bug, it does not. The data therefore supports the claim that comparing the message makes the reduction more accurate, where accurate means that the reduced test reproduces the failure it was reduced for. The limit of the claim is the message’s own information. A message that carries no value, as in the six disagreements above, is a weaker identity than one that does, and a message can be preserved while the fault is lost, which is the next point. Preserving the failure’s identity is not the same as preserving the fault’s coverage. In eight of the 32 tool reductions (9, 15, 21, 23, 25, 27, 28 and 31) the reduced test no longer executes the mutated code: the mutant made some statement’s effect invisible to the compared value, that statement became removable, and what remains fails with the reference message on the unmutated project too. TestBasic is the clearest small case: the mutant swallows every write to an observable, so the observed value is the initial one whether the write runs or not, and the write is removed. The gold standard made the same removals, because they are the 37 correct removals under the oracle; in DelayTest1 the gold standard lost the fault where the tool’s did not. We record this as a property of failure-preserving reduction rather than as tool error, and Chapter 7 weighs what it means for using a reduced test downstream. 6.5 Tool Comparison (RQ3) RQ3 asks whether HDD improves on the DD based approach: on five tree structured tests, how do the final test size and the preserved failure compare between ReduSharptor.HDD and the original ReduSharptor? For RQ3 the original ReduSharptor was run, unchanged except for the setup commits of Table 5.2, on the five starred tests with the same mutants, and Table 6.4 sets the two tools side by side. For ReduSharptor.HDD the cost is the number of candidates built and tested; for the DD tool it is the number of candidates it attempted, of which those that failed to build are counted as passing by that tool and skipped, and the rest were run. None of the five reduced tests is the same between the two tools. ReduSharptor.HDD preserved the failure fingerprint on all five tests. The DD tool did not preserve it on two, because it was not designed to preserve fingerprints: its oracle checks only that the test still fails. Table 6.4: HDD against DD on the five RQ3 tests. Sizes are statement counts, and Orig. is the original size. For DD, Tried is the number of candidates attempted and Run the number that built and were tested. The two Preserved columns say whether each tool’s reduced test fails with the original failure fingerprint. HDD ID Test DD Orig. Reduced Evaluated Preserved Reduced Tried Run Preserved 5 ConcurrentBeginWritesSecondFails 12 TestAllowModificationInComputed 14 DelayTest1 24 Last Correct WhenReservedGreaterThanCurrent 25 Can Reset Dirty Properties Cascades Into Property Types 20 20 10 8 16 8 10 6 5 8 98 Yes 84 Yes 39 Yes 15 Yes 46 Yes 6 14 10 8 6 90 58 12 4 65 44 No 17 Yes 5 Yes 2 Yes 17 No Three separate effects account for the differences. The first is descent. On TestAllowModificationInComputed DD removed three top-level units and stopped at 14, because the action lambda that holds most of the test is one unit to it and cannot go without the failure. ReduSharptor.HDD descended into that lambda and removed three whole Tree statements inside it, which took it to 10. On Last Correct WhenReservedGreaterThanCurrent DD removed nothing at all: the test’s three top-level units are a constant, a state source and a lambda, the first two cannot go without breaking the build, and the lambda cannot go without the test passing. ReduSharptor.HDD removed a loop and a call inside the lambda and reached 5. These two are the case HDD was built for, and the tree statements it opened are exactly the ones Weber’s own inaccuracy analysis pointed at. The second is the baseline’s splitting. DelayTest1 has seven top-level statements, and DD also removed nothing, although dropping the final assert alone still fails. The reason is in the baseline’s ddmin, 38 which divides the statement list by integer division and pours the remainder into the last section: at granularity four, seven statements became three singles and one block of four holding the delay, both loops and the final assert; the complement of that block removes the assert together with the loops and the test passes; and at the next granularity, eight, there are more sections than statements and the search stops. ReduSharptor.HDD’s ddmin splits evenly, so it proposed the final assert on its own and removed it, then descended into the second loop. This effect has nothing to do with hierarchy and would apply to a flat test of the same length. The third is the oracle. On the remaining two tests DD’s result is smaller, and in both it is smaller because the exit-code oracle accepted a different failure, as Section 6.4 describes. ConcurrentBeginWritesSecondFails was reduced to 6 by removing the write whose callback raises the seeded exception, after which the trace assert fails instead; Re- duSharptor.HDD kept 8, including that write, because every candidate without it failed differently. Can Reset Dirty Properties Cascades Into Property Types was reduced to 6 by removing the statement that adds the un-grouped property type, after which the first Assert.Multiple fails on an empty list; ReduSharptor.HDD kept 8 and its final Assert.Multiple with the nested loop and assert that the seeded failure lives in. On cost, ReduSharptor.HDD built and tested more candidates on four of the five tests, which is what opening the tree costs: every inner statement is a new unit to try. The one exception is test 25, where DD attempted 65 candidates and ran 17 against ReduSharptor.HDD’s 46 evaluations, because its accepted different failure sent it down a shorter path. On the five tests where the two tools can be compared, then, ReduSharptor.HDD produced a strictly smaller test that preserves the failure on three, and on the other two it produced the only reduced test that preserves the failure. That is the answer to RQ3 on this set, and Chapter 7 says why five tests do not make it a benchmark. 6.6 Statement Categories (RQ4) RQ4 asks how the category of a statement affects reduction: how are Tree and NonTree statements reduced, using the six measures defined by Christi and Weber [6]? Table 6.5 gives, per test, the number of NonTree and Tree statements, the Tree statements split by kind, the number of each category removed, the two percentage measures over the test’s total statement count, and the two removal probabilities over the category’s own count. No test in the set has a conditional statement as a unit, so that column is left out: the 39 Tree statements are 13 loops and 26 action statements, that is, lambdas passed to a call, and the 14 tests that carry them are marked by a non-zero Tree count. 39 Table 6.5: Statement categories and what was removed, per test. #NTN and #TN are the NonTree and Tree counts; ANTRS and ATRS the numbers removed; PNTRS and PTRS the percentages of the test’s statements; PrNTRS and PrTRS the percentages of the category, undefined where the test has no Tree statement. ID #NTN Loop Action #TN ANTRS ATRS PNTRS PTRS PrNTRS PrTRS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 5 13 13 15 19 15 18 15 10 10 14 13 16 8 9 20 18 10 9 9 12 3 13 6 12 8 13 15 13 11 60 32 0 0 0 0 0 0 0 0 0 0 1 0 0 2 1 0 0 0 0 0 0 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 3 7 0 0 0 0 0 0 0 4 1 0 0 1 2 0 1 0 0 0 3 3 0 0 0 0 1 0 0 0 0 0 4 7 0 2 1 0 0 0 0 4 1 3 0 2 4 3 1 0 0 0 3 3 3 11 3 1 11 5 7 1 7 6 6 7 11 3 4 18 16 5 8 7 9 2 11 2 6 5 11 12 4 2 55 27 0 0 0 0 1 0 0 0 0 0 2 3 0 1 0 0 0 0 0 3 0 3 0 1 2 2 0 0 0 0 2 3 60.0 84.6 23.1 6.7 55.0 33.3 38.9 6.7 70.0 60.0 33.3 35.0 68.8 30.0 40.0 90.0 88.9 50.0 88.9 53.8 69.2 33.3 84.6 25.0 37.5 45.5 78.6 80.0 30.8 18.2 87.3 77.1 0.0 0.0 0.0 0.0 5.0 0.0 0.0 0.0 0.0 0.0 11.1 15.0 0.0 10.0 0.0 0.0 0.0 0.0 0.0 23.1 0.0 50.0 0.0 12.5 12.5 18.2 0.0 0.0 0.0 0.0 3.2 8.6 60.0 84.6 23.1 6.7 57.9 33.3 38.9 6.7 70.0 60.0 42.9 53.8 68.8 37.5 44.4 90.0 88.9 50.0 88.9 77.8 75.0 66.7 84.6 33.3 50.0 62.5 84.6 80.0 30.8 18.2 91.7 84.4 – – – – 100.0 – – – – – 50.0 42.9 – 50.0 0.0 – – – – 75.0 0.0 100.0 – 50.0 50.0 66.7 0.0 – – – 66.7 100.0 Total Mean 457 13 26 39 286 8.9 23 0.7 52.6 5.3 61.6 53.7 Two comparisons come out of the table, and they answer different questions. The first is volume. Of the 309 statements removed, 286 were NonTree and 23 were Tree. Per test, the mean PNTRS is 52.6% and the mean PTRS is 5.3%, and the medians are 51.9 and 0.0. A Shapiro-Wilk test rejects normality for PTRS (W = 0.58, p < 0.001), so, as Christi and Weber did, we used a paired Wilcoxon signed rank test, which puts the difference well beyond chance (W = 4, p = 1.2 × 10−6 , n = 32). Figure 6.2 shows the two distributions. This reproduces their finding that reduction removes NonTree statements in far greater volume, and it has to: 457 of the 496 statements are NonTree, and eighteen of the tests have no Tree statement at all, so their PTRS is zero by construction. Their baseline reported a mean PNTRS of 70.44% against a mean PTRS of 1.43%; the PTRS here is about four times theirs, which is the descent showing up in the totals, but the volume comparison is dominated by how many statements of each kind a test has, not by how the reducer treats them. We therefore partially confirm Christi and Weber’s result 40 that leaf statements are reduced in significantly higher volume than Tree statements, though the factor is significantly different in our case, about 10 to 1 against about 49 to 1 in theirs. The factor is affected by the fact that HDD works better on tree-structured input. The second is probability. The removal probabilities ask the question the volume cannot: given a statement of each kind, how likely was it to be removed? Over the 14 tests with at least one Tree statement, the mean PrNTRS is 61.6% and the mean PrTRS is 53.7%, with medians of 60.2 and 50.0; pooled over all statements, 286 of 457 NonTree statements were removed (62.6%) against 23 of 39 Tree statements (59.0%). Shapiro-Wilk does not reject normality for either (p = 0.62 and p = 0.07), but with 14 pairs we kept to the same Wilcoxon test for comparability, and it finds no difference (W = 42, p = 0.81). Figure 6.3 shows the two distributions overlapping. Christi and Weber found the opposite under DD: a NonTree statement was about 1.7 times as likely to be removed as a Tree statement (p = 0.029), a gap they attributed to the tool treating a Tree statement as one unit. On this set, with a reducer that opens Tree statements, the gap is not there. We do not confirm Christi and Weber’s result here: in our results the probability of removal is similar for Tree and NonTree statements, while a NonTree statement was 1.7 times as likely to be removed in theirs. This result is also affected by the fact that HDD works better on tree-structured input than DD. Eleven of the 14 tree-bearing tests had at least one Tree statement removed, and three (5, 22 and 32) had every one of them removed; the three where none was removed (15, 21 and 27) are tests whose single loop or lambda holds the failing assert and so cannot go, while its inner statements did. Two cautions belong with that result. The probability comparison rests on 14 tests and 39 Tree statements, which is enough to show that the earlier gap does not reappear but not enough to bound how large a difference could still hide; and the Tree statements here are loops and lambdas only, because no conditional appeared as a unit in the tests the selection produced. Both are taken up in Chapter 7. What the data does say is that the category of a statement no longer predicts whether reduction will remove it once the reducer can see inside it, which is the answer to RQ4 this thesis set out to test. 41 Percent of the test's statements removed 100 80 60 40 20 0 PNTRS PTRS Percent of the category removed Figure 6.2: Percentage of each test’s statements removed, by category, over all 32 tests (PNTRS against PTRS) 100 80 60 40 20 0 PrNTRS PrTRS Figure 6.3: Probability of removal by category over the 14 tests with a Tree statement (PrNTRS against PrTRS) 42 CHAPTER 7 Threats to Validity This chapter asks what could make the results of Chapter 6 mean less than they appear to, under the four headings Weber used [5]: whether the measures measure what the research questions ask, whether the experiment itself introduced bias, whether the results carry beyond this set, and whether someone else could get the same numbers. Where a threat was foreseen and a rule was set against it, the rule is named; where it was not, the threat is stated as it stands. 7.1 Construct Validity Do the measures reflect what the research questions ask? Precision and recall measure the implementation, not an independent judgment. Section 6.2 says why the tool and the gold standard were bound to agree, and the consequence for RQ2 is that the 97.1% precision and 95.9% recall certify the search and the oracle under the tool’s own rules, and no more. We chose that binding on purpose, for the reason in Section 5.5; the cost is that this thesis has no gold standard formed by someone who did not know the tool’s rules, and Chapter 8 lists one as further work. Weber’s precision and recall were computed differently in his workbook, so the two sets of numbers are not compared. A statement is the unit throughout: the tool removes statements, the gold standard removes statements, and every count in Chapter 6 is a count of statements. Two reductions of the same size can be very different tests, as DelayTest1 in Figure 6.1 shows, and a removed Tree statement takes its whole body with it while counting as one. The category measures of Section 6.6 address the second point; the first is a limit of any size-based measure of reduction and this thesis inherits it from the earlier work. Failure identity is not fault coverage. On eight of the 32 tests the reduced test no longer runs the mutated code (Section 6.4). Those reductions are correct by the measure, and the gold standard made the same removals, but a reduced test that fails on the unmutated project is of no use for locating the fault, which Chapter 1 gave as the purpose of reduction, so the measure over-counts success for that purpose in eight cases. The operator and site choices in Section 5.3 preferred fingerprints that are a value the mutant changes rather than one it merely fails to change, which keeps the fault, and eight is what remained. The message is the identity the framework reports. Six of the seven disagreements came from asserts whose message carries no value (Section 6.3). The selection rule against flag asserts kept this out of most of the set, but one starred test, DelayTest1, carries a flag assert because it was the strongest tree test in its project, and language-ext’s Assert.True style put four more in. A weak message was also accepted where 43 the executed path admits one source for it, as on ShouldProvideAdditionalHeaders, and that run’s zero different-failure verdicts support the reasoning but do not prove it in general. The planned escape hatch of Section 3.5, a fingerprint of the exception type alone for a test whose message changes between runs, was never needed, so its effect on the measures is untested. The category measures inherit their definitions. PNTRS, PTRS, PrNTRS and PrTRS are Christi and Weber’s, used so that Section 6.6 can be set against their result. PrTRS is undefined on the eighteen tests with no Tree statement, so the probability comparison rests on 14 tests and 39 Tree statements, and those 39 are 13 loops and 26 lambdas with no conditional among them. The finding that the removal-probability gap is gone is a finding about loops and action statements in this set; it says nothing about if statements, which never appeared as a unit directly under a test body in the tests the selection produced. 7.2 Internal Validity Did the experiment introduce bias? We chose the mutants. The operator set comes from the literature, as Section 5.3 says, and that removes the choice of what kind of change to make. It does not remove the choice of where to make it. For each test we picked one site in the product code the test exercises, and Section 6.1 shows that the position of the fault in the compared value bounds how much of the test can be removed: a corruption at the front of a compared string leaves the setup removable, a corruption at its end keeps it. We did not pick sites to improve the reduction numbers, and the operator rule limited what a site could be, but a different site would have given a different percentage, and the spread in Table 6.1 is partly the spread of our choices. The first two bugs predate the operator rule and their mutants are a wrong variable name and a dropped letter in a string literal; both are disclosed in Section 5.2 and both reduced with perfect agreement, so their effect on RQ2 is nil, but they are not instances of a standard operator. The tests were chosen, and some were replaced. Tests were picked from the inspect reports for their Tree statements and value asserts, and a pick that failed the validity screen was replaced by the next candidate. Three picks were irreducible under their mutant and were swapped out: in each the test had a single assert whose compared value every statement feeds, so that no removal could keep the failure, and the corruption sat at the end of the compared value. That shape predicts irreducibility, and the set that remains is biased away from it, which means the reduction percentages of Section 6.1 describe reducible tests and not developer tests in general. Two pairs in the set are near-twins: ConcurrentBeginWrites and ConcurrentBeginWritesFirstEndWriteFails differ only in their mutant and both reduced to the same one removable statement, and MapAddInOrderTest and MapAddInReverseOrderTest are the same shape with the keys reversed. Each pair is closer to one sample than two, and the RQ2 and RQ4 44 totals count them as two. Every gold standard reduction was made by the first author, who also built the tool whose results it was compared with. The same-path rule was set so that the gold standard could not be steered by knowledge of what the tool did: the statement order is fixed, top to bottom, the verdicts come from the build and the test run and not from our reading, and the tool’s reduced test was not opened until the gold standard was finished. The rule does not change that the person judging the tool knew how it worked. What limits the risk is that the verdict of every attempt is mechanical, a message compared with a reference, so the only judgment left to the analyst was the order, and the order was fixed in advance. The gold standard’s order is not ddmin’s order. Every disagreement in Section 6.3 comes from that difference, and the difference was chosen: a gold standard that replayed ddmin’s own candidate order would have matched the tool on all seven and shown nothing. The cost is seven pairs of false positives and false negatives that are not errors, reported as such. The environment intruded twice. Section 6.1 records six candidates on one BizHawk test that hung the test host on a Debug.Assert dialog and were judged InfraError after the oracle’s timeout, and four on another that were judged TestMissing when the machine’s application control policy refused a rebuilt test assembly. Both verdicts count as not preserving the failure. For the first that is correct, since a candidate that crashes the product code under test has not reproduced the failure; for the second it is an accident of the machine, and the affected candidate kept no assert and would have passed, so the reduction was unaffected, but that was checked after the fact rather than guaranteed. The same policy refused BizHawk’s shipped source generators, which had to be rebuilt from the repository’s own source as experiment setup, and one mutant’s first form was refused as a product assembly and had to be written in an equivalent form. None of these changed a test’s result, and all are recorded with the bug. The oracle caches a verdict by the content of the candidate, so a test whose outcome could vary from run to run would have its first verdict reused. DelayTest1 reads the clock and sleeps, and MassAddRemoveTest builds its map from a hundred thousand keys generated fresh on every run. Both behaved deterministically here, on the tool and in the gold standard, because the compared values do not depend on the timing or the keys under these mutants, and the reference message of each was reproduced on every preserved candidate; but the cache would not have caught a verdict that differed on a rerun. The oracle’s build and test timeouts are a second place where a slow machine could turn a preserving candidate into an InfraError; no such case was observed outside the dialog hangs above. The first twelve bugs were run on one machine and the rest on another, as Section 5.1 now states. The two starred tests among the first twelve were run again on the experiment machine and produced the same reduced test statement for statement, with the same candidate counts, which is evidence that the tool’s result 45 does not depend on the machine; the other ten were not rerun. 7.3 External Validity Do the results carry beyond this set? The subjects are the five C# projects of the earlier evaluation, chosen so that RQ1 and RQ2 would repeat it on the same ground, and the tests are 32 developer-written tests from them, with three test frameworks and four target frameworks between them. That is a wider spread of frameworks than the earlier work, and a narrower one than C# testing in general. The tool is built on Roslyn and on dotnet test, so nothing here says anything about another language; the algorithm and the oracle design would carry, the implementation would not. The tests were picked for reduction. As the previous section says, the set is biased toward reducible tests with value asserts, and toward Tree statements: 14 of 32 tests carry one, against 3.30% of tests in Weber and Christi’s formative study [3]. The reduction percentages therefore over-state what the tool would remove from an arbitrary failing test, and the RQ4 result over-represents the tests where HDD has anything to open. The result has to be read as conditional: when a failing test has a Tree statement, this is what descending into it did. How often a failing test has one is the earlier study’s question, and its answer, rarely, still stands. Seeded faults are not developer faults. Every failure here is one standard-operator change at one site, and the failure it produces is deterministic and single-sourced. Real faults can span several sites, fail intermittently, or fail differently on different runs, and a message-matching oracle is more exposed on those than an exit code is: a message that varies between runs would reject preserving candidates as different failures. The escape hatch of Section 3.5 exists for that case and was not exercised. Weber’s faults were reverted fix commits, which are closer to developer faults in origin but were not recorded; the seeded mutants trade that realism for reproducibility. RQ3 is five tests. The comparison with DD was limited to five tree-structured tests, one per project. Of the three effects Section 6.5 separates, two, the baseline’s uneven splitting and its exit-code oracle, are properties of that implementation rather than of DD as an algorithm, so the comparison is between two tools and not two algorithms; a DD implementation with an even split and a message oracle would leave only the descent, on the two tests where nothing could be removed at the top level. Five tests show the mechanism; they do not measure how often it matters. 7.4 Reliability Could someone else repeat this and get the same numbers? Every input is recorded. Each subject is pinned to a commit, each setup change is a commit on top of 46 it, and each of the 32 mutants is a diff against the pinned commit, all in our repositories. The tool, the 32 mutant diffs, the run folders, the gold standard walks and the analysis workbook are public at https: //github.com/SkylorWixom/ReduSharptor. Any bug can be re-seeded with git apply, the tool run on it, and the run compared with its run folder. The two reruns of Section 6.5 are the evidence that a repeated run reproduces the reduced test exactly. The gold standard reductions are logged. Every attempt of every gold standard walk is one line in the analysis workbook, with the statement, the verdict and whether it stayed out, and the surviving test is recorded beside the tool’s. The counts in Table 6.3 were made by comparing those two columns statement by statement, and the workbook, not the tool’s own summary, is the record of authority for every count in Chapter 6. The tool’s summary was used only to cross-check the workbook counts; its original, reduced, NonTree and Tree counts agree with the workbook on all 32 tests. The candidate costs of Section 5.1 and the wall times are properties of one machine and one SDK version, and a different machine would give different times and, in the timeout cases above, possibly different verdicts. The reduced tests themselves, and so every count in Chapter 6, do not depend on timing on any test in this set, as the two cross-machine reruns show. The statistics of Section 6.6 were computed by a script over the workbook’s rows, so a change to a count changes the tests and figures with it. 47 CHAPTER 8 Further Work and Conclusion 8.1 Further Work The results of Chapter 6 and the threats of Chapter 7 point at the same few things, and this section takes them in the order of how much each would change. The first is a fingerprint that knows which assert failed. Six of the seven disagreements in Section 6.3 came from a message that two statements could produce, and the reference message of those tests carries no value: Assert.True() Failure Expected: True Actual: False, or a bare exception type. The test framework knows more than the message says. The TRX file the oracle reads carries a stack trace, and the trace names the line of the assert that failed. A fingerprint made of the message and the failing line would have told the two asserts of DelayTest1 apart, held the failure where the mutant put it, and the gold standard would have reached the tool’s answer as well, on every one of those six tests. The change is small in the oracle and none in the search. It would make a flag assert almost as strong an identity as a value assert, and it would let tests whose asserts all share one message, which this experiment screened out, into a future set. The one thing it would not fix is MassAddRemoveTest, where two different statements each keep the same assert failing for the same reason; that case needs a rule about which to prefer, not a better oracle. The second is a check that the reduced test still finds the fault. On eight tests the reduced test fails on the unmutated project too. The tool cannot see that, because it only ever runs the mutated project; but the check is inexpensive and mechanical: after reduction, apply the reduced test to the clean commit, run it once, and report whether it passes. A reduced test that fails on clean code has preserved the message and lost the fault, and a developer using it to localize the fault should be told so. The report could stop there, or the tool could refuse the last removal that made the fault disappear and try the next candidate instead, which turns the second oracle into a constraint on the search. That second form changes what the tool reduces toward, from the failure’s identity to the fault’s coverage, and it needs a clean version of the project to run against, which a developer with a failing test has: the commit before the one that broke it. The third is fewer builds. Every candidate here cost a build, and 1,602 of the 2,864 verdicts across the 32 runs were build failures, most of them a declaration removed before the statements that use it. Two changes would cut that. The cheaper one is order: within a level, try the statements that use a variable before the statement that declares it, so that by the time the declaration is proposed its uses are already gone. That is 48 Christi’s inside-out suggestion applied within a level rather than across levels, and it does not change the result, since a build failure only ever puts a statement back; it changes how many candidates are spent finding out. The larger one is Weber’s: use control and data flow to skip candidates that cannot compile, or compile the test file alone against the built product assemblies instead of rebuilding the test project. The cache already answered half of the candidates in this experiment, and it would keep doing so under either change; the aim is to spend fewer of the other half. The fourth is Weber’s hybrid, which this work closes and then reopens. Weber proposed running DD on tests without a Tree statement and HDD on tests with one [5]. The tool built here does not need the split. On a test with no Tree statement the top level is the only level, the whole-level prune is one candidate, and the per-level ddmin is DD with an even split; eighteen of the 32 tests ran that way. The hybrid’s other half, the cost of descent, is real: on four of the five RQ3 tests ReduSharptor.HDD built and tested more candidates than the original tool, because every inner statement is a new unit. What would repay that cost is a way to know before descending whether a surviving Tree statement is worth opening. A Tree statement whose body holds the failing assert cannot be removed whole, and its inner statements are where the reduction is; a Tree statement whose body has no path to the compared value could be tried whole and, if it survives, left closed. That is a data-flow question again, and the same analysis that skips uncompilable candidates would answer it. The fifth is a gold standard from someone else. The gold standard reductions in this thesis were made by the first author, who also wrote the tool, under the tool’s own rules, for the reasons Section 5.5 gives. A second person reducing the same tests, told the oracle and the unit but not the traversal, would give a gold standard the tool’s rules did not shape, and the disagreements between that standard and the tool would measure something this thesis could not: whether the tool’s rules produce the reduction a person would want. Running that study on the 32 tests here needs nothing new, since every mutant is a recorded diff; it needs a second analyst and the gold standard logs to compare. The sixth is tests with conditionals and more Tree statements. The 39 Tree statements in this set are loops and lambdas, and no if statement appeared as a unit directly under a test body in the tests the selection produced. The RQ4 result, that the removal probability of a Tree statement is no longer below that of a NonTree statement once the reducer can open it, was measured on 14 tests. A set chosen to carry conditionals, and more tests with Tree statements in general, would say whether the result holds for the third kind and would give the probability comparison the power that 14 pairs cannot. Umbraco-CMS alone has many more tests with Tree statements than this set used, most of them parameterized, smaller than the selection rules allow, or dependent on integration setup this experiment kept out. The last is faults that do not come from a single mutant. Every failure here is one operator applied at 49 one site, deterministic and single-sourced. The next step toward developer faults is the one Weber took and did not record: reverse a real fix commit, save the reversal as a diff, and reduce the test that caught it. Some of those faults will span several sites, some will fail with a message that varies between runs, and those are the cases where the message oracle has to fall back to the exception type and the reduction has to be judged knowing that. The escape hatch of Section 3.5 exists for them and has not yet been used. 8.2 Conclusion This thesis started from one assumption: that a hierarchical reducer, one that can open a nested statement and reduce what is inside it, is applicable to the unit tests C# developers write, is accurate, and does a better job than the flat reducer it extends. We built that reducer, ReduSharptor.HDD, gave it an oracle that compares the failure message rather than the exit code, and answered four research questions with it. Based on those answers, we conclude the following. On applicability (RQ1), the tool reduced every one of the 32 developer-written failing tests from five open source projects and three test frameworks, removing 62.3% of their statements. It is highly applicable to C# projects and tests. On accuracy (RQ2), measured against a gold standard reduction of every test, the tool reached 97.1% precision and 95.9% recall. Its reductions are highly accurate. On the comparison with the DD based approach (RQ3), qualitatively, on the five tests with nested code, the hierarchical tool went inside the statements the flat tool could only remove whole and produced a smaller test that still fails in the original way, and it never accepted a reduction that fails for a different reason. It does a better job on the tests it was built for. On the category of a statement (RQ4), NonTree statements are removed in significantly larger amounts than Tree statements, but the probability that a statement is removed is about the same for the two categories once the reducer can open a Tree statement. Taken together, hierarchical reduction of developer-written C# tests is applicable, accurate, and a better solution than flat reduction, and it does not take much longer: a run took about seven minutes on average. 50 References [1] A. Christi, M. L. Olson, M. A. Alipour, and A. Groce, “Reduce before you localize: Delta-debugging and spectrum-based fault localization,” in 2018 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW), Memphis, TN, USA, 2018, pp. 184–191. [2] A. Zeller and R. Hildebrandt, “Simplifying and isolating failure-inducing input,” IEEE Transactions on Software Engineering, vol. 28, no. 2, pp. 183–200, Feb. 2002. [3] D. Weber and A. Christi, “ReduSharptor: A tool to simplify developer-written C# unit tests,” International Journal of Software Engineering & Applications, vol. 14, no. 5, pp. 29–40, Sep. 2023. [4] G. Misherghi and Z. Su, “HDD: Hierarchical delta debugging,” in Proceedings of the 28th International Conference on Software Engineering, ser. ICSE ’06, 2006, pp. 142–151. [5] D. Weber, “Simplification of developer-written C# unit tests,” Master’s thesis, Weber State University, Ogden, UT, Dec. 2022. [6] A. Christi and D. Weber, “On reducibility of developer-written unit tests in C#,” in SOFTENG 2024: The Tenth International Conference on Advances and Trends in Software Engineering. IARIA, 2024, pp. 17–23. [7] J. Regehr, Y. Chen, P. Cuoq, E. Eide, C. Ellison, and X. Yang, “Test-case reduction for C compiler bugs,” in Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLDI ’12. ACM, 2012, pp. 335–346. [8] S. Herfert, J. Patra, and M. Pradel, “Automatically reducing tree-structured test inputs,” in Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, ser. ASE 2017, 2017, pp. 861–871. [9] R. Hodován and Á. Kiss, “Modernizing hierarchical delta debugging,” in Proceedings of the 7th International Workshop on Automating Test Case Design, Selection, and Evaluation, ser. A-TEST 2016. ACM, 2016, pp. 31–37. [10] C. Sun, Y. Li, Q. Zhang, T. Gu, and Z. Su, “Perses: Syntax-guided program reduction,” in Proceedings of the 40th International Conference on Software Engineering. Association for Computing Machinery, 2018, pp. 361–371. [11] R. Gopinath, A. Kampmann, N. Havrikov, E. O. Soremekun, and A. Zeller, “Abstracting failureinducing inputs,” in Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis, 2020, pp. 237–248. [12] D. Binkley, N. Gold, M. Harman, S. Islam, J. Krinke, and S. Yoo, “ORBS: Language-independent program slicing,” in Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2014, pp. 109–120. [13] D. Stepanov, M. Akhin, and M. Belyaev, “ReduKtor: How we stopped worrying about bugs in Kotlin compiler,” in 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2019, pp. 317–326. [14] G. Wang, R. Shen, J. Chen, Y. Xiong, and L. Zhang, “Probabilistic delta debugging,” in Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ser. ESEC/FSE 2021. New York, NY, USA: Association for Computing Machinery, 2021, pp. 881–892. [15] G. Wang et al., “A probabilistic delta debugging approach for abstract syntax trees,” in 2023 IEEE 34th International Symposium on Software Reliability Engineering (ISSRE). IEEE, 2023, pp. 763–773. 51 [16] A. Christi, A. Groce, and R. Gopinath, “Resource adaptation via test-based software minimization,” in 2017 IEEE 11th International Conference on Self-Adaptive and Self-Organizing Systems (SASO). IEEE, Sep. 2017, pp. 61–70. [17] A. Christi and A. Groce, “Target selection for test-based resource adaptation,” in 2018 IEEE International Conference on Software Quality, Reliability and Security (QRS), Jul. 2018, pp. 458–469. [18] D. Vince, R. Hodován, and Á. Kiss, “Reduction-assisted fault localization: Don’t throw away the byproducts!” in ICSOFT, 2021, pp. 196–206. [19] Y. Jia and M. Harman, “An analysis and survey of the development of mutation testing,” IEEE Transactions on Software Engineering, vol. 37, no. 5, pp. 649–678, 2011. [20] B. Wilber, T. D. Le, and A. Christi, “ReduJavator: A tool to simplify developer-written Java unit tests,” in 2024 IEEE International Conference on Data and Software Engineering (ICoDSE). IEEE, 2024, pp. 199–204. [21] A. Christi, A. Groce, and A. Wellman, “Building resource adaptations via test-based software minimization: Application, challenges, and opportunities,” in 2019 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW). IEEE, 2019, pp. 73–78. [22] D. Yang, Y. Lei, X. Mao, D. Lo, H. Xie, and M. Yan, “Is the ground truth really accurate? Dataset purification for automated program repair,” in 2021 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE, 2021, pp. 96–107. [23] M. Bointner, “Delta debugging for CUE configurations,” Ph.D. dissertation, Technische Universität Wien, 2025. [24] F. Tesarek, “Differential testing of static taint analysis tools,” Ph.D. dissertation, Technische Universität Wien, 2024. [25] S. Jiang, R. Santelices, M. Grechanik, and H. Cai, “On the accuracy of forward dynamic slicing and its effects on software maintenance,” in 2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation. IEEE, 2014, pp. 145–154. [26] R. Williams, T. Ren, L. De Carli, L. Lu, and G. Smith, “Guided feature identification and removal for resource-constrained firmware,” ACM Transactions on Software Engineering and Methodology (TOSEM), vol. 31, no. 2, pp. 1–25, 2021. [27] J. Klauke, T. Ohlmer, S. Schott, S. E. Ponta, W. Fischer, and E. Bodden, “A soundness and precision benchmark for Java debloating tools,” in Proceedings of the 2025 Workshop on Software Supply Chain Offensive Research and Ecosystem Defenses, 2025, pp. 64–73. 52