arXiv CSopen access

Delta Debugging in the Absence of Test Oracles Through Metamorphic Testing

1

Delta Debugging in the Absence of Test Oracles Through Metamorphic Testing

arXiv:2607.00929v1 [cs.SE] 1 Jul 2026

Mingyue Jiang, Yongqiang Tian, Tsong Yueh Chen

Abstract—Delta debugging provides an automatic way to minimize a program input while preserving a certain property. However, its effectiveness fundamentally relies on the availability of test oracles to determine whether a reduced input still preserves the specific property. Consequently, the oracle problem substantially limits the applicability of existing delta debugging techniques, particularly for oracle-deficient programs where output correctness cannot be directly determined. To address this problem, this paper proposes a novel approach, DDMT, to enhance the applicability of delta debugging, especially facilitating its application to oracle-deficient programs. Our key insight is to redesign an oracle-independent test function and incorporate it into the reduction procedure of delta debugging such that the property-preservation validation can be accomplished without requiring a test oracle. To this end, DDMT employs the technique of metamorphic testing, which is a property-based and oracleindependent testing method. It establishes a metamorphic testingbased test function, using it as a replacement for the original test function adopted by delta debugging. The experiments evaluate DDMT on 66 subjects across both oracle-available and oracledeficient scenarios, with different delta debugging approaches. The results positively confirm that DDMT can enhance the applicability of delta debugging while often preserving or improving reduction effectiveness and query efficiency. Furthermore, compared to the relevant delta debugging approaches, DDMT is also able to achieve performance improvements with proper configurations. Index Terms—Delta debugging, Metamorphic testing, Oracle problem.

I. I NTRODUCTION

T

EST inputs are key artifacts for program debugging. A failure-causing input that reveals program failures can aid the debugging process in finding the bug, understanding the root cause of the bug, fixing the bug, and so on. However, such an input may be overly large and complex, because it may contain some information that is irrelevant to the cause of failure. The debugging of a program using such an input may be unnecessarily cumbersome and inefficient. Therefore, a simplified input that preserves the failure-revealing capability of the original input can facilitate more effective debugging. M. Jiang is with School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou, China (e-mail: [email protected]) Y. Tian is with Department of Software Systems & Cybersecurity, Monash University, Melbourne, Australia (e-mail: [email protected]) T. Y. Chen is with the School of Science, Computing and Emerging Technologies, Swinburne University of Technology, Hawthorn, VIC 3122 Australia (e-mail: [email protected]) Corresponding author: Yongqiang Tian Preprint — under review. This is the authors’ version. This research was partially supported by use of the Nectar Research Cloud, a collaborative Australian research platform supported by the NCRIS-funded Australian Research Data Commons (ARDC). It was also supported by the National Nature Science Foundation of China (Grant No.61802349).

Delta debugging (DD) [1], [2], [3] is a systematic approach towards the automated input simplification. It automatically reduces an input of the target software system into the essential minimum that still preserves the property of interest (e.g. the capability of revealing a specific type of failures). DD is traditionally built upon the ddmin algorithm, which follows a divide-and-conquer strategy by recursively partitioning inputs and eliminating irrelevant elements. To simplify program inputs, the algorithm repeatedly generates reduced candidate inputs and performs property-preservation validation on each candidate. The algorithm continues until no further reduction is possible, and returns the smallest candidate input found that still exhibits the property of interest. Since the inception of DD, it has attracted extensive research attention. On the one hand, it has been extended and adapted for a wide range of applications, such as isolating causeeffect chains for failure diagnosis [4], simplifying method calls for failure reproduction [5], simplifying GUI event traces [6], reducing event sequences of web applications [7], isolating bug-inducing and bug-fixing changes [8], debugging microservice systems [9] and AI-integrated systems [10], etc. On the other hand, considerable research efforts have focused on improving its effectiveness and efficiency through various optimization strategies. Recognizing that ddmin ignores the structural characteristics of inputs, HDD [11] exploits the hierarchical nature of program inputs and employs specific tree-based manipulators to reduce inputs. Similarly, GTR [12] combines ddmin with tree transformations to support the reduction of tree-structured inputs. Perses [13] further incorporates the formal syntax of programming languages into the reduction process, enabling more effective and syntax-aware program simplification. Recently, ProbDD [14] incorporates a probabilistic model into ddmin, in order to guide the reduction process using dynamically updated probability estimations. WDD [15] adopts a different perspective by assigning weights to input elements and leveraging the weight information to optimize the reduction procedure. Instead of directly simplifying inputs, GReduce [16] reduces the execution trace of a test input generator and re-executes the generator with the reduced trace, allowing validity-preserving input reductions. While existing techniques have made significant progress in improving reduction efficiency and minimization effectiveness, they have paid limited attention to the test oracle problem, leaving this important problem largely unresolved. To ensure that the reduced input preserves the property of interest, DD performs the property-preservation validation on every candidate input explored during the reduction process. Such validation is conducted through a test function, which requires

2

a test oracle to differentiate between passing and failing executions, so as to identify failure-causing inputs for further reductions. Consequently, the applicability of DD fundamentally depends on the availability of test oracles. Existing DD approaches are applied with explicit test oracles that exactly specify the expected behavior of the target program, including the observable failure-based oracle (i.e., program crash or a specific exit code) [1], [12], [17], [18], and output-based oracle (i.e., the expected output value) [19]. However, reliable test oracles are often unavailable, expensive to construct, or difficult to automate in practice, causing DD to suffer from the well-known test oracle problem [3], [20]. The test oracle problem significantly limits the applicability of existing DD techniques in oracle-deficient scenarios. Orthogonal to existing studies that focus on improving effectiveness and efficiency, this study targets the test oracle problem and aims to enhance the applicability of delta debugging without compromising its effectiveness and efficiency. To this end, we draw inspiration from metamorphic testing (MT) [21], [22], [23], a well-established technique for alleviating the test oracle problem. We propose DDMT, a novel delta debugging approach that systematically integrates ddmin with MT. The core insight of DDMT is to conduct MT rather than the conventional testing for property-preservation validation. Specifically, DDMT proposes an MT-based test function as an alternative to the one used in conventional DD. Moreover, it establishes systematic mappings between the original and the MT-based test functions, enabling the seamless integration of the latter into the overall reduction process. Instead of employing a test oracle, the MT-based test function leverages a metamorphic relation (MR) that encodes some necessary property of the target program. Accordingly, the property-preservation validation is conducted via MT with respect to a specific MR. Consequently, DDMT no longer relies on test oracles and thus is of better applicability than DD. On the other hand, owing to the fact that the result of property-preservation validation directly affects the partition and reduction decisions of DD, different test functions may provide varying degrees of support to the reduction process. More specifically, due to the discrepancies in the failurerevealing effectiveness of MT and the traditional testing, DDMT may adopt different partition decisions from that of DD, exploring a distinct set of candidate inputs and ultimately producing varying results. This further enables DDMT to exhibit better reduction performance with the support of effective MRs that have strong failure-revealing abilities. We evaluate DDMT on 66 subject programs across both oracle-available and oracle-deficient scenarios. The experiments employ two representative DD approaches: in the oracle-available scenario, ddmin is employed with the use of an explicit oracle for string or textual file reduction; in the oracle-deficient scenario, Perses [13] is applied with the support of benchmark-specific oracles for program reduction. Accordingly, DDMT and PersesDDM T (Perses with the integration of DDMT) are applied with the corresponding MRs in both scenarios. The results demonstrate that although without requiring test oracles, the overall performance of DDMT is comparable to that of ddmin in both scenarios. Particularly,

when equipped with effective MRs, DDMT exhibits promising performance, producing 12% to 37% smaller-sized inputs while involving 11% to 37% fewer test function queries for some subjects under investigation. In summary, this study makes the following key contributions. • We propose DDMT, a novel MT-based delta debugging approach to simplifying failure-causing inputs without requiring a test oracle, enabling input reductions in both oracle-available and oracle-deficient scenarios. • We extensively evaluate DDMT in different oracle situations, demonstrating that DDMT substantially improves applicability while often preserving or improving reduction effectiveness and query efficiency, and even achieves better performance with the use of effective MRs. • We implement DDMT, and publicize the replication packages for conducting delta debugging on a broad range of domains. The rest of the paper is organized as follows: Section II introduces the delta debugging approach. Section III presents the details of the proposed approach. Section IV explains the experimental setup, and Section V reports the experimental analysis results. Section VI discusses the limitations of the proposed approach, and also clarifies the threats to validity. Section VII presents and summarizes related studies, and Section VIII concludes the paper. II. D ELTA D EBUGGING Delta Debugging (DD) [1], [2], [3] is a classic, automated approach that uses a divide-and-conquer strategy to find the root cause of a failure. The family of DD approaches is built upon the ddmin algorithm, which minimizes a failure-causing input via recursive input partition and validation. A. The ddmin Algorithm The ddmin algorithm aims at simplifying a program input into a minimal one, which is minimal in size, but still preserves the same failure-revealing capability as the original input [1]. To this end, ddmin conducts a series of reductions, and this reduction procedure is assisted by a test function, which performs property-preservation validation to identify failurecausing inputs, guaranteeing the preservation of the failurerevealing capability of the resulting input. Let t be an arbitrary input of the target program P , and test be the test function determining the preservation of the failure-revealing capability for inputs. With reference to a test oracle o, the function test can be described as below. ( F , if P (t, o) → F ail; test(t, P, o) = (1) T , if P (t, o) → P ass. Specifically, function test executes P with t by referring to o, in order to judge whether the execution fails or passes. Accordingly, t is reported to be failing (denoted by F ) or passing (denoted by T ). A failing input reveals failures of a failed execution. The ddmin algorithm can be described as follows.

3

∀t, test(t, P, o) = F , ddmin : (t, P, o) → t′ , where t′ ∈ t, test(t′ , P, o) = F,

(2)

and ∀x ∈ t′ , test(x, P, o) ̸= F t′ is a program input that is minimal in size but still preserves the same failure-revealing capability as t. Starting with a given program input, ddmin first converts the input into a set of configurable elements with respect to a certain granularity, such as characters, lines, or tokens. After that, it processes the input via a finite number of runs, each of which consists of the following three steps. (1) Input reduction via partitioning. Following a partition granularity n (which is initialized to 0 and keeps updating during the input reduction procedure), the currently target input t is split into n inputs t′1 , ..., t′n that have comparable size. It should be noted that due to the partition, all of the resulting candidate inputs (namely, t′i , 1 ≤ i ≤ n) are of smaller size than t. Next, each of the candidate inputs is validated by applying the function test. If there exists at least one input, say t′i , on which test(t′i , P, o) = F , then t′i is set as the target input in the next run by applying Step (1). Otherwise, the complements of t′i are constructed and operated by following Step (2). (2) Input reduction via complementing. For′ each candidate input t′i , its complement input, namely, ti+ , is constructed ′ with respect to t (t′i ∪ ti+ = t). If there exists at least ′ ′ one complement input, say ti+ , on which test(ti+ , P, o) ′ = F , then ti+ is further partitioned in the next run with granularity n − 1 according to Step (1). Otherwise, the algorithm will change the granularity n for further manipulations by following Step (3). (3) Granularity adjustment. The granularity n is increased to min(|t|, 2n) (as long as n < |t|), and then this new granularity will be applied in the next run. When every candidate input resulting from Steps (1) and (2) is passing, and the increasing of granularity is failed, the algorithm terminates and returns the last failing input that has been operated. Obviously, the smaller the resulting input, the better. Moreover, if a smaller number of test functions is queried, then fewer candidate inputs would be handled, and thus less resources would be needed. Notably, the test function serves as a fundamental mechanism of ddmin, whose outcome is directly utilized to make the partition and reduction decisions. Therefore, its ability to identify failure-causing inputs will affect the reduction effectiveness and efficiency.

B. A Motivating Example For the purpose of illustration, consider the application of ddmin to a faulty version of program printtokens (a lexical analyzer program from the Siemens suite) as an example. This faulty version may incorrectly handle some comments (which are texts after ‘;’). For a given input containing 10 characters, ddmin finally reports a minimal failing input of

Fig. 1: The detailed procedure of applying ddmin to a faulty version of program printtokens. The test column reports the test outcome of individual inputs (the contents of which are highlighted in blue) in terms of passing or failing.

size 3 after handling a sequence of 22 candidate inputs. The detailed minimization process of ddmin is shown in Fig. 1, where each row reports a candidate input and the outcome of property-preservation validation. In run#1, the given input is partitioned into two candidate inputs of size 5. Since both inputs and their complements are passing (lines 1 – 2), the granularity is increased to 4. In run#2, four candidate inputs are constructed and they all pass (lines 3 – 6). As a result, their complements are constructed and validated. One of the complement inputs is failing (line 7). Thus, the algorithm continues with this failing input by using a granularity of 3. In run#3, the three candidate inputs resulting from partitioning are already processed (as shown in lines 4 – 6) and thus the results are directly utilized. Their complements are further constructed, the last one of which fails (line 10). Run#4 continues with granularity 2, while inputs resulting from both partitioning and complementing are already reported to be passing. Accordingly, the granularity is increased to 4, and the relevant inputs are constructed (lines 11 – 15), among which the first complement input fails. In run#6, the failing input is first partitioned into 3 candidate inputs, which are already processed and are all passing, and then the relevant complement inputs are also reported to be passing. As a result, the granularity is increased to 4 in run#7, where one of the complement inputs fails (line 20). Run#8 continues to handle this failing input with granularity 3. In this run, all candidate inputs after partitioning and complementing are passing, and the granularity can be no longer increased for the currently target input (because n is not smaller than the size of the currently target input). As a result, the last failing candidate input (at line 20) is returned as the output.

4

Obviously, for ddmin, the implementation of function test requires a test oracle, which is a mechanism that can tell the pass or fail of individual inputs [20]. Because of this, the ddmin algorithm may not be applicable when the test oracle is not available or is difficult or expensive to be applied. In other words, the delta debugging approach faces the oracle problem [3]. More importantly, it can also be observed from the ddmin algorithm and the illustrative example that the sequence of candidate inputs being operated is mainly determined by their testing results reported by the test function. For example, the 7th candidate input at line 7 of Fig. 1 is selected for further manipulation because all candidate inputs before it are reported to be passing. This further indicates that the failure-revealing effectiveness of the test function determines the selection of candidate inputs, and in turn affects the effectiveness and efficiency of the input reduction procedure. Intuitively, the more failure-causing inputs can be identified earlier, the less effort will be needed to identify the final minimal failure-causing input. Therefore, designing a new test function possessing the capability of alleviating the oracle problem as well as strong failure-revealing effectiveness can benefit the applicability, effectiveness and efficiency of DD. III. A PPROACH In light of the oracle problem confronted by delta debugging and the specific strength of metamorphic testing in alleviating the oracle problem, this study proposes to systematically integrate delta debugging with metamorphic testing. We propose DDMT, an MT-based delta debugging approach, which performs automatic input reductions without dependence on a test oracle. This section presents the details of our approach. We first introduce the general principles of metamorphic testing, and then explain the rationale and key mechanism of DDMT. Finally, we revisit the illustrative example to show the specificity of DDMT. A. Metamorphic Testing Metamorphic testing (MT) [21], [22], [23] is a testing strategy that can effectively alleviate the oracle problem. In MT, the necessary properties of the target program or algorithm are utilized and specified as the relationships among multiple inputs and their outputs, which are known as metamorphic relations (MRs). Unlike traditional testing strategies that employ an oracle for checking the correctness of the output of individual inputs, MT checks whether or not multiple relevant inputs and outputs satisfy an associated MR. Therefore, MT does not rely on a test oracle. An MR describes the operational relationships between source inputs and the relevant follow-up inputs, and also encodes the expected relationships among the corresponding source and follow-up outputs. A source input and its relevant follow-up inputs referring to an MR form a metamorphic group of inputs (MG) of the MR [23]. For a violating MG that reveals program failures, MT reports a violation of the MR (denoted by V ). For a non-violating MG that fails to reveal program failures, MT reports a satisfaction of the MR (denoted by S). An MR violation is an observable signal of the program failure.

B. Integration of Delta Debugging with Metamorphic Testing We propose a new algorithm, DDMT, that systematically combines the ddmin algorithm with MT. The core insight of DDMT is to use a newly designed test function that leverages MT rather than the conventional testing technique such that failure-causing inputs can be identified without using test oracles. Accordingly, the procedure of DDMT can be independent of a test oracle. DDMT focuses on an input, say t, with which a violation of an MR r can be revealed on the target program P . DDMT aims to generate a minimal input t′ from t such that the violation of r is still observable. That is, ∀t, mrtest(t, P, r) = V, DDM T : (t, P, r) → t′ , where t′ ∈ t, mrtest(t′ , P, r) = V,

(3)

and ∀x ∈ t′ , mrtest(x, P, r) ̸= V Notably, DDMT makes use of an MR rather than a test oracle. Moreover, instead of applying the function test originated from the ddmin algorithm, it employs an MT-based test function, mrtest, to conduct property-preservation validation. The function mrtest is able to identify failure-causing inputs, with mrtest(i, P , r) = V indicating that a failure is revealed by conducting MT with an input i. 1) MT-based Test Function: The core novelty of DDMT lies in a newly designed property-preservation validation function, mrtest, which determines whether or not a violation of a specific MR can be observed on a given input. The details of function mrtest are described as follows. ( mrtest(t, P, r) =

S,

if mt(t, P, r) → Satisf action;

V,

if mt(t, P, r) → V iolation.

(4) For a given input t, function mrtest validates it on the target program P against the MR r. As detailed in Algorithm 1, mrtest conducts MT on P by using r and t, where t acts as a source input for r. It first constructs a follow-up input w from t by following r (line 2). This yields an MG, say g = (t, w), for r. After that, it proceeds with g, namely, executing P on both inputs and collecting their outputs (lines 3 – 4), and finally checking the outputs against r (line 5). If g violates r, mrtest returns V (line 8), indicating that a violating MG can be constructed based on t, thereby revealing program failures by following the pipeline of MT. Otherwise, mrtest returns S (line 6), indicating that performing MT with t fails to reveal failures of P . Obviously, function mrtest no longer relies on a test oracle. According to the nature of MT, an MR violation can be observed when either the source input or the follow-up input is failing, as elaborated in Table I. Therefore, the two test functions, mrtest and test, may have different abilities to identify inputs that can reveal program failures, and thus providing varying degrees of support to the reduction process. Table II further compares possible outcomes between the two functions for the same input. Function test confirms the

5

Algorithm 1 MT-based test function 1: procedure MRTEST(t, P, r) 2: w ← r(t) // generation of follow-up input 3: a ← P (t) //source execution

b ← P (w) //follow-up execution if MRCheck(a, b, r) then return S else return V end if 10: end procedure 4: 5: 6: 7: 8: 9:

TABLE I: Possible cases for an MR violation: Even if the source input is passing, an MR violation may still be observed. An MG Source input Follow-up input Failing Failing Passing

Passing Failing Failing

An input in ddmin corresponds to an MG in DDMT. ddmin treats an input as a single unit for validation and manipulation, while DDMT handles each individual MG as a single unit for validation and manipulation. • A failing/passing input in ddmin corresponds to a violating/non-violating MG in DDMT. ddmin adopts the traditional testing, and thus an input is determined to be failing or passing. Nevertheless, DDMT applies MT, based on which an MG is reported to be violating or non-violating. • Validating inputs against a test oracle in ddmin corresponds to validating MGs against a respective MR in DDMT. For each candidate input, ddmin checks it by referring to a test oracle, while DDMT checks the relevant MG against the respective MR. • Reducing an input in ddmin corresponds to reducing a source input of an MG in DDMT. ddmin partitions an input to generate some candidate input. Correspondingly, DDMT splits a source input into candidate source inputs, based on which candidate MGs will be constructed and manipulated.

•

While both approaches share the divide-and-conquer based input reduction, the use of different test functions leads to several discrepancies. To begin with, they utilize different information. The input to both approaches involves the target program and an input. However, ddmin requires the use of a test oracle, while DDMT leverages an MR. In addition, the technical details of these two approaches are slightly different. Function mrtest consists of the construction of follow-up input, the source and follow-up executions, and the checking of MR

Violation Violation/Satisfaction Violation

TABLE II: Comparison between the failure-revealing effectiveness of functions test and mrtest. An input t Failing Passing

failure-revealing capability of an input t only if t is failing. Differently, by treating t as a source input, function mrtest may confirm a program failure via an MR violation if 1) t is failing, or 2) t is not failing but the relevant follow-up input is failing. This suggests that with the same program input, mrtest may have a higher chance to uncover program failures, thereby guiding the reduction process to make optimized decisions. 2) Correspondences and Differences between ddmin and DDMT: ddmin and DDMT both target the minimization of a program input that reveals program failures. They share the same reduction workflow but use different test functions to identify failure-causing inputs. Therefore, they have a series of correspondences, which are summarized in Table III and further clarified as follows.

Possible MT results

test(t, P, O)

mrtest(t, P, r)

F T

V/S V/S

TABLE III: The correspondences between ddmin and DDMT. Aspects

ddmin

DDMT

Input

(t, P, o)

(t, P, r)

Key activity

• Validating t on P against the test oracle o • Reducing t

• Validating an MG with t as the source input on P against the MR r • Reducing t

Output

A minimal input A minimal input reveals the same failure whose relevant MG as t. violates r

satisfaction, while function test involves only one program execution using the given input. Last but not least, ddmin outputs a minimal failing input that reveals the same failures as the original input, while DDMT provides a minimal source input with which the violation of the given MR is revealed. C. Revisiting the Motivating Example To explain the characteristics of DDMT, we revisit the illustrative example as shown in Fig. 1. We apply DDMT by using one MR that “adding some comments into the text to be analyzed should not affect the analysis result because comments are ignored by printtokens”. With the same given input (whose size is 10) and the MR, DDMT outputs a result of size 1 after handling a sequence of 4 candidate inputs. The detailed execution trace of DDMT is depicted in Fig. 2. In Run#1, the given input is partitioned into two candidate inputs, which are source inputs for constructing the relevant MGs. It is noted that the second candidate input is passing (which is constructed and tested by ddmin at line 2 of Fig. 1), while the relevant MG is violating (line 2 of Fig. 2). In other words, by focusing on the second candidate input, function test identifies it as passing, while function mrtest constructs a violating MG and thus reveals program failures. As a consequence, the execution trace of DDMT deviates from that of ddmin. That is, instead of increasing the granularity as ddmin does, DDMT continues to partition the second candidate input in Run#2 with granularity 2. Again, the candidate input constructed in Run#2, which is passing (as evidenced by the outcome of function test as shown at line 14 of Fig. 1), still yields a violating MG (line 3) and thus is further partitioned

6

Fig. 2: The procedure of DDMT for the motivating example. The mrtest column reports the outcome of function mrtest.

in Run#3. As a result, the last run finds and returns a 1-sized input whose MG reveals program failures. Obviously, DDMT is of better applicability than DD because it no longer relies on test oracles. Moreover, due to the distinctions between the failure-revealing effectiveness of functions test and mrtest, ddmin and DDMT exhibit different execution traces, yielding different debugging results. To summarize, instead of obtaining a minimal input revealing certain failure as ddmin does, DDMT aims at producing a minimal source input based on which the violation of a certain property is revealed. It should be noted that with the integration, the merit of MT lies in both alleviating the oracle problem and improving the effectiveness and efficiency of DD. As a reminder, though DDMT is originally designed to extend the applicability of ddmin to programs without test oracles, it should be clear that DDMT can still be applied even in the presence of test oracles. IV. E XPERIMENTAL SETUP We conducted a series of experiments by employing different delta debugging approaches and a diverse set of subject programs. To comprehensively evaluate DDMT, our experiments consider both oracle-available and oracle-deficient scenarios. Our experiments study the following research questions. RQ1. How well can DDMT perform as compared with ddmin that is equipped with available test oracle? This RQ investigates the reduction effectiveness and efficiency of DDMT in the oracle-available scenarios. There are two subquestions. • RQ1.1. How does the effectiveness and efficiency of DDMT vary across the usage of different MRs? • RQ1.2. To what extent can DDMT achieve performance improvements over ddmin? RQ2. How well can DDMT perform for debugging programs facing the test oracle problem? This RQ investigates the reduction effectiveness and efficiency of DDMT in the oracle-deficient scenarios.

testing research [24], [25], [26]. It consists of several small to medium-sized C programs, and each subject is accompanied by a correct version and multiple faulty versions with seeded defects. For these programs, the correct version can provide the expected output as a test oracle. We selected subject programs where the input contains either String or file parameters so that the tokenbased input reduction is feasible. We excluded subject programs for which the input is unable to be reduced. • Program compilers without available test oracles. We further selected subjects from previous studies on delta debugging [13], [14], [15], [27], where each subject consists of a program compiler and an input C program. There are mainly two categories of subjects, those demonstrating an observable failure of the compiler (e.g., the compilation of the input program ends with a crash or abnormal exit code), and those ending with a silent failure without any observable signals (i.e., the input program is compiled successfully but the resulting executable deviates from the expected program semantics). In the latter case, a test oracle is unavailable, and thus DD is unable to be applied without some auxiliary support.

A. Subjects and MRs

To apply DDMT, we reused MRs from existing publications in order to avoid any biases. For each subject program from the Siemens suite, we adopted three MRs (which are respectively referred to as MR1, MR2, and MR3 throughout the rest of this paper). The MRs for printtokens modify the input text by changing character cases and transforming certain tokens into identifiers or numeric tokens [24], [26]. The MRs for printtokens2 transform specific tokens into identifiers, and also manipulate comments [24], [26]. The MRs for replace focus on regular expressions, including brackets, escape characters, and specific regex patterns [25], [24]. The MRs for schedule involve substituting the quantum-expire command, the adding job command, and the block, unblock commands [25]. For C compilers, we adopted one existing MR, EMI [28], which transforms the original C program to generate equivalent variants, and expects all of them to produce the same outputs for a given set of test inputs.

In order to facilitate a direct comparison between ddmin and DDMT, we selected subject programs from the Siemens suite that have available oracles. On the other hand, to demonstrate the capability of DDMT in the absence of test oracle, we further selected program compilers for which no oracle is available for revealing semantic failures. • Siemens programs with expected outputs as test oracles. Siemens suite is a widely used benchmark in software

To facilitate comparisons between ddmin and DDMT, we kept only subject programs for which both approaches successfully reveal failures with a certain set of same inputs. As a result, a total of 66 faulty programs were selected, including 58 faulty programs from replace, printtokens, printtokens2, and schedule of the Siemens suite, and 8 clang/gcc compilers exhibiting silent failures. The information of these subjects are summarized in Table IV.

7

TABLE IV: Subject programs and test inputs. Subject

#Programs

#Failing inputs

Oracle Situation

printtokens printtokens2 replace schedule

7 10 32 9

525 2430 2100 766

With the expected output as an oracle

clang/gcc

8

8

Oracle unavailable

(a) Size.

B. Evaluation Metrics Both ddmin and DDMT target producing a minimal failurecausing input (the former results in a failing input, while the latter ends with an input that is the source input of a violating MG). According to this, their effectiveness mainly refers to the size of the resulting input. On the other hand, from the perspective of efficiency, it is reported that the time spent on querying the test function dominates about 98% of the total execution time of reduction procedure [12]. Then, a smaller number of queries (namely, the number of test or mrtest function invocations) indicates a better efficiency. Therefore, in this study, we followed existing studies [1], [14], [11], [13] to use three metrics, the size, the number of queries, and the time cost. We measured the size of inputs of Siemens programs using the number of characters, and measured the size of inputs of compilers using the number of tokens. Furthermore, we collected the number of invocations of function test for ddmin, and collected the number of invocations of function mrtest for DDMT. C. Implementations We directly applied ddmin and DDMT to Siemens programs, for conducting the token-level input reduction. For program compilers, we selected the state-of-the-art delta debugging technique for program reduction, Perses [13]. We further built PersesDDM T by adapting DDMT to Perses, using MR violations instead of manually specified oracles to decide whether a candidate program should be preserved during reduction. •

ddmin and DDMT. We adopted the implementation of ddmin proposed by the original authors (https://www.st.cs.uni-saarland.de/dd/) [1]. With reference to the oracle situations of Siemens programs, we implemented a function test to support ddmin. The function test runs a given input on the target program, and determines the pass or fail by comparing the actual output with the expected output, which is obtained via running the correct version of the target program with the same input. We implemented DDMT upon the implementation of ddmin. Specifically, we implemented each of our MRs, for supporting the automated follow-up inputs generation as well as the MR checking of source and follow-up outputs. Furthermore, we implemented function mrtest, which conducts MT on the target program using a given source input and the MR, and provides a satisfaction or violation as an output.

(b) Query.

(c) Time.

Fig. 3: Performance of DDMT with three different MRs on Siemens programs.

•

Perses and PersesDDM T . We adopted the implementation of Perses [13]. Specifically, to apply Perses to subjects having the test oracle problem, we re-implemented the function test by employing benchmark-specific oracles. Moreover, we implemented PersesDDM T based on a mrtest function and the implementation of EMI MR.

Our experimental equipment is an operating system with 8-core 16-thread Intel(R)Core(TM)i7-10700 CPU (2.90GHZ), 16 GB RAM, and Ubuntu Linux 16.04. V. R ESULTS AND A NALYSIS A. Evaluation results of Siemens programs In our experiments on Siemens programs, ddmin successfully reduces 5,821 failing inputs, and DDMT successfully reduces 44,097 inputs involved in violating MGs. When applying DDMT to Siemens programs, three MRs were utilized for each subject program. Therefore, we first report the performance of DDMT with respect to different MRs, based on which MRs exhibiting the best and worst performance for each subject program can be identified. Then, we conduct comparison analysis between ddmin and DDMT with the usage of the best and worst MRs, respectively. 1) Performance of DDMT with respect to different MRs: Fig. 3 reports the performance of DDMT in terms of the reduction effectiveness (the size of the resulting inputs) and efficiency (the number of queries and the time cost), respectively. A boxplot contains three boxes, each of which shows the distributions of the data for an MR. In a box, the red line inside it represents the median value of the data, and the ends of the box denote the upper and lower quartiles. It can be visually observed that for each of the subject programs, both effectiveness and efficiency of DDMT vary substantially with the use of different MRs. For each subject program, we further conducted the Wilcoxon rank-sum test [29] on the data from individual pairs

8

TABLE V: Comparison of the performance of DDMT with reference to different MRs. For two MRs A and B, A ≈ B indicates that two MRs are of comparable performance (pvalue ≥ 0.05), while A ≫ B means that A is of better performance than B (p-value < 0.05). Subjects

Size

Query

Time

printtokens

MR3≈MR2≫MR1

MR3≈MR2≫MR1

MR3≈ MR2≫MR1

printtokens2

MR3≫ MR2≫MR1

replace

MR3≫ MR2≫MR1

schedule

MR1≫MR2≫MR3

Best: MR2 Worst: MR1 MR3≫MR2≫MR1

(a) Comparison of the input size and the number of queries. MR3≫MR2≫MR1

Best: MR3 Worst: MR1 MR3≫MR2≫MR1

MR3≫MR2≫MR1

Best: MR3 Worst: MR1 MR1≈MR2≫MR3

MR1≈MR2≫MR3

Best: MR1 Worst: MR3

of MRs, to check whether or not there is a significant difference between them. The results are summarized in Table V. Among 12 comparisons on the size of the resulting inputs, 11 pairs of MRs exhibit significant differences (p-value < 0.05). Meanwhile, 10 pairs of MRs show significant differences in terms of the number of queries, and significant differences in time cost are also observed in 10 pairs of MRs. These results indicate that both the effectiveness and efficiency of DDMT are highly sensitive to the used MRs. This further consolidates the observation that MR is a key factor to the performance of MT-based approaches, as previously reported by prior studies [30], [31]. Based on the comparison results, we ranked the three MRs, and then identified the MRs with the best and worst performance with respect to each subject program. The results are reported in Table V. It can be observed that the ranks of MRs are quite similar across different metrics. Moreover, the performance of the best MR (ranked first) and the worst MR (ranked last) is always statistically different. This results suggest that a good MR can consistently achieve better reduction effectiveness with less resource consumptions. 2) Comparison between ddmin and DDMT with the use of the best and worst MRs: We then compared the performance of ddmin with that of DDMT. As aforementioned, DDMT shows varying performance when different MRs are utilized. Therefore, our comparison respectively analyzed DDMT with the best and the worst MRs (as reported in Table V). As a reminder, ddmin focuses on reducing a failing input, while DDMT focuses on reducing a source input whose MG of the given MR is violating. What’s more, as elaborated in Section III-B, a violating MG may not necessarily have a failing source input. As a result, the application of these two approaches may involve different target programs and inputs, and the application of DDMT using different MRs may also involve different target programs and inputs. Therefore, in order to fairly compare ddmin and DDMT (with an MR), we collected and analyzed the experimental results for a set of programs and inputs to which both approaches are successfully applied. That is, each comparison focuses on a target program and an input, which is associated with two groups of data

(b) Comparison of the input size, the number of queries, and the time cost.

Fig. 4: Detailed comparison results of DDMT and ddmin on the Siemens programs.

(including the size, the number of queries, and the time cost) from ddmin and DDMT, respectively. A total of 1,577 comparisons were conducted, including 528 comparisons on ddmin and DDMT using the best MR, and 1,049 comparisons on ddmin and DDMT using the worst MR. We performed the Wilcoxon signed-rank test [29] to statistically compare individual groups of data. Tables VI summarizes the overall performance of the two approaches by reporting the mean value, the statistical test result, and the improvements achieved by DDMT, in terms of each of the evaluation metrics. Additionally, Fig. 4 presents the details of comparison, namely, the percentage of comparisons where DDMT is better than, worse than, comparable to, or equivalent to ddmin. In a comparison, DDMT is regarded to perform better (worse) than ddmin if it yields better (worse) results with respect to all of given metrics; it is comparable to ddmin if it yields a better result for some metrics while yielding worse results for the others; and it is equivalent to ddmin if they produce the same results for all of the given metrics. The comparison between ddmin and DDMT with the usage of the best MR shows that DDMT often delivers positive improvements. As reported in Table VI (a), DDMT yields reduced inputs with smaller size than ddmin and achieves a statistically significant improvement in simplification effectiveness (p-value < 0.05), ranging from 12% to 37% across three out of the four subject programs. With regard to the efficiency, DDMT involves a comparable number of test function invocations to ddmin on printtokens2, while achieving improvements of 11% to 37% on the other three subject programs. Nevertheless, it always incurs higher time cost as compared with ddmin. Apart from the subject replace where DDMT exhibits a very tiny differences in time cost (0.19 vs 0.13 seconds), it requires much more time than ddmin to accomplish the task of input reduction. However, according to

9

TABLE VI: Overall comparison results of ddmin and DDMT on Siemens programs. The average size, number of queries and time are reported. ↑ represents the improvements achieved by DDMT, which is calculated by (X - Y)/X (X and Y respectively denote the values from ddmin and DDMT with respect to an evaluation metric). (a) Comparison between ddmin and DDMT using the best MR Size

Subjects printtokens printtokens2 replace schedule

ddmin 3.72 1.96 3.28 14.70

DDMT 2.43 2.24 2.89 9.30

p-value 4.32e-08 0.0003 0.0013 0.0148

Query ↑ 35% -14% 12% 37%

ddmin 30 21 19 221

DDMT 19 22 17 162

p-value 5.00e-09 0.1103 0.0006 0.1055

Time (seconds) ↑ 37% -5% 11% 27%

ddmin 0.08 0.06 0.13 1.36

DDMT 1.68 1.97 0.19 13.94

p-value 2.81e-19 2.55e-29 0.8190 0.002

↑ >-200% >-200% -46% >-200%

(b) Comparison between ddmin and DDMT using the worst MR Size

Subjects printtokens printtokens2 replace schedule

ddmin 2.29 2.00 2.91 14.05

DDMT 2.54 2.94 4.36 8.47

p-value 9.54e-06 7.99e-75 2.46e-10 6.79e-28

Query ↑ -11% -47% -50% 40%

ddmin 27 24 19 204

DDMT 23 34 29 116

the detailed analysis result as presented in Fig. 4, DDMT is better than ddmin in 58.5% of cases with reference to the input size and the number of queries (Fig. 4 (a)). When considering all of the three metrics, it performs better in 24.8% of cases, and it is comparable to ddmin in 35.4% of cases (Fig. 4 (b)). To summarize, with the support of good MRs, DDMT offers better simplification effectiveness and efficiency for the majority of programs and inputs, but overall incurring higher time overhead. In Table VI (b), the comparison results between ddmin and DDMT with the usage of the worst MR are reported. DDMT generally performs well on the subject program schedule, with positive improvements in both the size and the number of queries. On another subject program, printtokens, it yields inputs of larger size, while requiring a smaller number of test invocations. It is also observed that DDMT exhibits an explicit performance decrease on the other two subject programs, and it also incurs higher time overhead than ddmin on all of the subject programs. When inspecting the details of comparison results reported in Fig. 4, it is observed that DDMT performs no worse than ddmin in about 60% of cases in terms of both the input size and the number of queries (Fig. 4 (a)), while it yields better or comparable results in about 25% of cases when considering all three metrics. These results suggest that when ordinary or even ineffective MRs are applied, DDMT can still retain comparable performances to ddmin for a quite large number of programs and inputs. In summary, the application of ddmin and DDMT to the Siemens programs shows that DDMT is able to achieve promising effectiveness and efficiency as compared with ddmin. On one hand, the discrepancies between the results from DDMT and ddmin confirm that an oracle-based test function and an MR-based test function will guide the reduction procedure in different ways, leading to varying reduction results. On the other hand, although the performance of DDMT varies across different MRs, it exhibits significant performance improvements with the use of good MRs, and it still delivers better or comparable results for a considerable number of subjects even with an ordinary or ineffective MR. The results show

p-value 0.0003 5.76e-53 8.91e-11 2.32e-24

Time (seconds) ↑ 15% -42% -53% 43%

ddmin 0.09 0.06 0.05 1.31

DDMT 2.05 2.98 0.15 10.16

p-value 1.44e-26 3.73e-82 3.68e-31 2.94e-33

↑ >-200% >-200% >-200% >-200%

that DDMT improves applicability while often preserving or improving reduction effectiveness and query efficiency. These results further suggest that in the scenario where a test oracle is available, although ddmin is applicable, it is still worthwhile to use DDMT with properly identified MRs so as to enhance the minimization effectiveness as well as reduction efficiency. B. Evaluation results of program compilers We apply Perses and PersesDDM T to reduce input programs for gcc and clang compilers, where silent failures occur without observable signals. In this oracle-deficient scenario, Perses was configured with explicit benchmark-specific oracles, whereas PersesDDM T was configured with an MR. The detailed results are reported in Table VII. Averagely, both approaches exhibit comparable performance across all metrics. PersesDDM T demonstrates a slight improvement in input size (368 vs 369 tokens, a 0.1% decrease) and the number of queries (4623 vs 4666 queries, a 0.9% decrease), while incurring slightly higher time overhead (7,385 vs 7,351 seconds, a 0.5% increase). For minimization effectiveness, Perses and PersesDDM T consistently yield programs of identical size in 7 out of 8 cases, and PersesDDM T yields a smaller-sized program in the remaining one case. When inspecting the number of queries, PersesDDM T generally needs fewer test function invocations than Perses, as evidence by the 0.9% improvements achieved across all cases. Particularly, PersesDDM T shows explicit improvements in three cases, by requiring 9.6%, 6.3%, and 3.3% fewer queries. These results confirm the input reduction capability of DDMT, and also provide evidence to show that DDMT may explore a different set of candidate inputs due to the specific failure-revealing abilities of MT. The differences between the total time costs of these two approaches are marginal. Nevertheless, PersesDDM T consumes less time in 7 cases, while it requires relatively more time in one case. These results indicate that although the test function employed by DDMT requires more resources as the one utilized by ddmin, the optimization of the entire reduction process may decrease the number of test invocations, and in

10

TABLE VII: Comparison results of Perses and PersesDDM T on program compilers. Size

Subjects clang-21582 clang-23309 clang-26350 clang-27137 clang-31259 gcc-66186 gcc-66375 gcc-70127 Average

Perses 559 475 196 268 384 327 440 301 369

PersesDDM T 559 475 194 268 384 327 440 301 368

Query ↑ 0.0% 0.0% 1.1% 0.0% 0.0% 0.0% 0.0% 0.0% 0.1%

Perses 6468 2167 5374 10787 2480 2845 3469 3736 4666

turn leading to comparable time consumption to ddmin for most of subjects. To summarize, PersesDDM T and Perses show comparable performance on the evaluated compiler subjects. These results confirm the practical applicability of DDMT in scenarios facing the test oracle problem. Although PersesDDM T can be supported by benchmark-specific oracles in these scenarios, there remain difficulties in obtaining reliable and effective reference implementations. Consequently, DDMT is more broadly applicable and effective for programs where reliable test oracles or comparable implementations are unavailable. VI. D ISCUSSION Effectiveness and Cost Trade-off. Although DDMT achieves improvements in the size of resulting input and the number of queries, it incurs additional time overhead compared with ddmin. The overhead mainly arises from the difference between the procedure of function mrtest and that of function test. While the latter requires only one execution of the target program, the former involves the generation of the follow-up input, an additional execution of the program with the followup input, and the checking of the outputs from both executions. Experimental results show that the additional time cost is often accompanied by a noticeable improvement in input size and the number of queries, indicating that the overhead is largely justified by the gained reduction effectiveness. Moreover, DDMT remains fully automated, reducing manual effort and improving scalability compared with human-intensive processes. Therefore, the results suggest that DDMT achieves a practical trade-off between reduction effectiveness and time efficiency. Sensitivity to MRs. One limitation of DDMT is that its effectiveness and efficiency strongly depend on the quality of the employed MRs. As demonstrated in our experiments, different MRs lead to substantially different reduction results and reduction costs, further confirming the critical role of MR in DDMT. This limitation is inherited from MT itself, where the fault-detection capability is closely related to the strength and diversity of the selected MRs [30]. Nevertheless, this issue can be alleviated in practice because a large number of effective MRs have already been proposed by the research community for diverse application domains, including compilers [28], [32], scientific software [33], machine learning systems [34], web applications [35], and database systems [36]. Furthermore, prior studies have also investigated systematic methodologies and automated techniques for MR identification

PersesDDM T 6457 1959 5539 10791 2481 2666 3355 3734 4623

Time (seconds) ↑ 0.2% 9.6% -3.1% 0.0% 0.0% 6.3% 3.3% 0.1% 0.9%

Perses 10140 8404 7709 9764 5055 5355 6784 5600 7351

PersesDDM T 10117 8334 8204 9752 5006 5347 6745 5578 7385

↑ 0.2% 0.8% -6.4% 0.1% 1.0% 0.2% 0.6% 0.4% -0.5%

and generation [31]. Therefore, although DDMT relies on MRs, the growing body of MR-related research provides strong support for its practical applicability. Moreover, this observation also suggests that the effectiveness and efficiency of DDMT can be further enhanced via more powerful MRs. Threats to Validity. Threats to internal validity may arise from the implementation of DDMT. To mitigate implementation-related errors, we adopted the publicly released package of the baseline approaches. Moreover, we carefully validated the implementation of MRs and the function mrtest. Another threat concerns the selection of subject programs. Our evaluation was conducted on a finite set of programs and inputs, which may not be fully representative of the broad range of software systems encountered in practice. To reduce this threat, we included programs from both the Siemens suite and the benchmark of prior DD studies, across oracle-available and oracle-deficient scenarios. Nevertheless, further experiments on larger and more diverse benchmark suites are needed to strengthen the generalizability of the findings. Last but not least, the selected MRs may introduce selection bias. Since only a subset of all possible MRs can be evaluated, the observed superiority of certain MRs may not generalize to other unexamined MRs. To mitigate this threat, we collected MRs from existing literature and conducted comparisons analysis with respect to both the best and the worst MRs. VII. R ELATED W ORK A. Delta Debugging Approaches Delta debugging [1] is a technique proposed by Zeller and Hildebrandt for automatically simplifying program inputs. The core algorithm of delta debugging is ddmin, which can generate the smallest input that preserves the failure-revealing ability. Subsequently, a series of approaches are proposed by enhancing and extending ddmin. The Hierarchical delta debugging (HDD) [11] exploits the input structure to minimize failure-causing inputs. Modernizing HDD [37] improves HDDs by proposing extended standard context-free grammars. Coarse HDD [17] enables faster simplification of program inputs by filtering non-empty replacement fragments when visiting tree nodes, and it can also be used to accelerate simplification of original HDDs. HHDr [38] aims at improving the hierarchical minimization algorithm, which significantly reduces the time cost of getting the minimal result. Perses [13] exploits the formal syntax of programs and uses it to

11

guide the reduction process, enabling effective and efficient reduction for general programs. Motivated by the observation that traditional delta debugging explores the search space without exploiting information learned during the reduction process, ProbDD [14] adopts a statistical approach by maintaining probability distributions over components to predict which elements are more likely to be irrelevant. It introduces a probabilistic model to estimate the likelihood that individual program elements belong to the failure-inducing set and continuously updates these estimates based on testing outcomes. Experimental results show that ProbDD can significantly reduce the number of required tests while preserving reduction effectiveness. Driven by the strict grammatical constraints of target languages, Large language model-aided program reduction (LPR) [39] leverages LLMs to perform semantics-preserving transformations that expose additional reduction opportunities. It combines iterative LLMguided transformations with language-generic reduction and introduces a multi-level prompting mechanism to improve transformation accuracy. Evaluations show that LPR achieves substantially smaller reduced programs than existing state-ofthe-art approaches while maintaining competitive efficiency. WDD [15] addresses the limitation of prior delta debugging algorithms that treat program elements uniformly despite their varying sizes, resulting in suboptimal partitioning and reduction efficiency. It introduces a weight-based partitioning strategy that assigns weights according to element size and guides the reduction process accordingly. Experimental results show that WDD improves minimization efficiency and can substantially reduce the number of required test executions compared with traditional delta debugging approaches. In order to address the validity and efficiency limitations of traditional delta debugging approaches, GReduce [16] leverages the execution traces of test input generators to guide input reduction. It reduces generator executions instead of generated inputs directly, which ultimately preserves input validity and enables more effective and efficient reductions. Instead of primarily targeting at enhancing the effectiveness and efficiency, this study focuses on extending the applicability of delta debugging to programs without test oracles. We demonstrated that the proposed approach, DDMT, is not only feasible, but also effective in producing simplified program inputs. DDMT is mainly designed for ddmin, the core algorithm of delta debugging approaches. However, it should be obvious that DDMT can be similarly adapted to all of the delta debugging approaches discussed above. B. Integration of Metamorphic Testing With Other Methods MT has been integrated with various approaches, successfully extending the application of these approaches to programs without test oracles. In light of the need of test oracles in fault-based testing, Chen et al. [40] proposed to integrate fault-based testing with MT, in order to enhance fault-based testing by alleviating the test oracle problem. To facilitate automated program debugging, Chen et al. [25] proposed an MT-based approach, semi-proving, which is an integrated approach for program proving, testing and debugging. Xie et

al. [24] proposed the concept of metamorphic slice, which combines program slicing with MT. They further incorporated the metamorphic slice into spectrum-based fault localization, based on which the applicability of spectrum based fault localization has been significantly extended. In the filed of automated program repair, Jiang et al. [41] proposed an integration of test suite based automated program repair with MT, which enables the application of automated program repair techniques without using test oracles, extending the application of automated program repair techniques to a broader domain. Later, they further proposed an MT-based test suite construction method, for constructing effective input test suites for automated program repair [26]. In order to alleviate the oracle problem of combinatorial testing, Niu et al. [42] integrated MT into combinatorial testing such that the outcome of test cases can be automated checked. The enhanced approach is able to be applied to more widely test scenarios. To address the limited generalization of genetic programming in program synthesis under scarce labeled data, Sobania et al. [43] integrated MT with genetic programming to validate program behavior via user-defined relations over unlabeled inputs. The experimental results confirm the higher generalization rate of the integrated approach. This study demonstrates a new integration paradigm for MT, and also provides a feasible solution for enhancing the applicability of delta debugging approaches. On the other hand, apart from confirming that the integrated approach alleviates the test oracle problem, this study further reveals that the integration is of great benefit to the improvements in effectiveness and efficiency.

VIII. C ONCLUSION In this paper, we proposed a novel delta debugging approach, DDMT, which seamlessly incorporates the technique of metamorphic testing (MT) into the reduction process of the ddmin algorithm. With a newly designed MT-based test function, DDMT can be applied regardless of the availability of the test oracle, facilitating the application of delta debugging to a broader range of programs. Experimental evaluation on the Siemens suite and C compilers confirms the feasibility of DDMT, demonstrating its applicability across both oracle-available and oracle-deficient scenarios. Experimental results further show that although achieving better applicability, DDMT remains comparable to ddmin in terms of both effectiveness and efficiency, across a substantial number of subject programs and inputs. In future work, we plan to further improve the effectiveness and efficiency of DDMT by incorporating more effective MRs. We also intend to investigate the applicability of DDMT to large-scale software systems and more diverse testing scenarios.

DATA AVAILABILITY STATEMENT The implementation and benchmark of our work are publicly available for experiment replication [44].

12

R EFERENCES [1] A. Zeller and R. Hildebrandt, “Simplifying and isolating failure-inducing input,” IEEE Transactions on Software Engineering, vol. 28, no. 2, pp. 183–200, 2002. [2] A. Zeller, Why programs fail: a guide to systematic debugging. Morgan Kaufmann, 2009. [3] A. Zeller and R. Hildebrandt, “Simplifying and isolating failure-inducing input: A retrospective on delta debugging,” IEEE Transactions on Software Engineering, vol. 51, no. 3, pp. 820–824, 2025. [4] A. Zeller, “Isolating cause-effect chains from computer programs,” ACM SIGSOFT Software Engineering Notes, vol. 27, no. 6, pp. 1–10, 2002. [5] M. Burger and A. Zeller, “Minimizing reproduction of software failures,” in Proceedings of the 2011 International Symposium on Software Testing and Analysis, 2011, pp. 221–231. [6] L. Clapp, O. Bastani, S. Anand, and A. Aiken, “Minimizing GUI event traces,” in Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ser. FSE 2016, 2016, pp. 422–434. [7] M. Hammoudi, B. Burg, G. Bae, and G. Rothermel, “On the use of delta debugging to reduce recordings and facilitate debugging of web applications,” in Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ser. ESEC/FSE 2015, 2015, pp. 333–344. [8] X. Song, Y. Wu, S. Liu, B. Chen, Y. Lin, and X. Peng, “C2d2: Extracting critical changes for real-world bugs with dependency-sensitive delta debugging,” in Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis, 2024, pp. 300–312. [9] X. Zhou, X. Peng, T. Xie, J. Sun, W. Li, C. Ji, and D. Ding, “Delta debugging microservice systems,” in Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, ser. ASE 2018. New York, NY, USA: Association for Computing Machinery, 2018, pp. 802–807. [10] H.-N. Zhu, M. N. Mansur, M. Schäf, Z. Chen, T. Lepoint, and W. Visser, “Delta debugging for llm-integrated systems,” in Proceedings of the IEEE/ACM 48th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), 2026, pp. 70–80. [11] G. Misherghi and Z. Su, “HDD: Hierarchical delta debugging,” in Proceedings of the 28th International Conference on Software Engineering, 2006, pp. 142–151. [12] S. Herfert, J. Patra, and M. Pradel, “Automatically reducing treestructured test inputs,” in Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, 2017, pp. 861 – 871. [13] 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, 2018, pp. 361–371. [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, 2021, pp. 881–892. [15] X. Zhou, Z. Xu, M. Zhang, Y. Tian, and C. Sun, “Wdd: Weighted delta debugging,” in 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE), 2025, pp. 1592–1603. [16] L. Ren, X. Zhang, Z. Hua, Y. Jiang, X. He, Y. Xiong, and T. Xie, “Validity-preserving delta debugging via generator trace reduction,” ACM Transactions on Software Engineering and Methodology, vol. 34, no. 3, pp. 1–33, 2025. [17] R. Hodovan, Á. Kiss, and T. Gyimothy, “Coarse hierarchical delta debugging,” in 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME), Sep. 2017, pp. 194–203. [18] A. Groce, M. A. Alipour, C. Zhang, Y. Chen, and J. Regehr, “Cause reduction: Delta debugging, even without bugs,” Software Testing, Verification and Reliability, vol. 26, no. 1, pp. 40–68, Jan. 2016. [19] 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), Oct 2018, pp. 184–191. [20] E. T. Barr, M. Harman, P. McMinn, M. Shahbaz, and S. Yoo, “The oracle problem in software testing: A survey,” IEEE Transactions on Software Engineering, vol. 41, no. 5, pp. 507–525, 2015. [21] T. Y. Chen, S. C. Cheung, and S. M. Yiu, “Metamorphic testing: A new approach for generating next test cases,” Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, Tech. Rep. HKUST-CS98-01, 1998.

[22] S. Segura, G. Fraser, A. B. Sanchez, and A. Ruiz-Cortés, “A survey on metamorphic testing,” IEEE Transactions on Software Engineering, vol. 42, no. 9, pp. 805–824, 2016. [23] T. Y. Chen, F.-C. Kuo, H. Liu, P.-L. Poon, D. Towey, T. H. Tse, and Z. Q. Zhou, “Metamorphic testing: A review of challenges and opportunities,” ACM Computing Surveys, vol. 51, no. 1, pp. 4:1–4:27, Jan. 2018. [24] X. Xie, W. E. Wong, T. Y. Chen, and B. W. Xu, “Metamorphic slice: An application in spectrum-based fault localization,” Information and Software Technology, vol. 55, no. 5, pp. 866–879, 2013. [25] T. Y. Chen, T. H. Tse, and Z. Q. Zhou, “Semi-proving: An integrated method for program proving, testing and debugging,” IEEE Transactions on Software Engineering, vol. 37, no. 1, pp. 109 – 125, 2011. [26] M. Jiang, T. Y. Chen, Z. Q. Zhou, and Z. Ding, “Input test suites for program repair: A novel construction method based on metamorphic relations,” IEEE Transactions on Reliability, vol. 70, no. 1, pp. 285– 303, 2021. [27] M. Zhang, Z. Xu, Y. Tian, X. Cheng, and C. Sun, “Toward a better understanding of probabilistic delta debugging,” in 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE), 2025, pp. 2024–2035. [28] V. Le, M. Afshari, and Z. Su, “Compiler validation via equivalence modulo inputs,” ACM Sigplan Notices, vol. 49, no. 6, pp. 216–226, 2014. [29] M. D. Riina, C. Stambaugh, N. Stambaugh, and K. E. Huber, “Continuous variable analyses: T-test, mann–whitney, wilcoxin rank,” in Translational radiation oncology. Elsevier, 2023, pp. 153–163. [30] H. Liu, F.-C. Kuo, D. Towey, and T. Y. Chen, “How effectively does metamorphic testing alleviate the oracle problem?” IEEE Transactions on Software Engineering, vol. 40, no. 1, pp. 4–22, 2013. [31] R. Li, H. Liu, P.-L. Poon, D. Towey, C.-A. Sun, Z. Zheng, Z. Q. Zhou, and T. Y. Chen, “Metamorphic relation generation: State of the art and research directions,” ACM Transactions on Software Engineering and Methodology, vol. 34, no. 5, pp. 1–25, 2025. [32] D. Xiao, Z. Liu, Y. Yuan, Q. Pang, and S. Wang, “Metamorphic testing of deep learning compilers,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 6, no. 1, pp. 1–28, 2022. [33] Z. Peng, U. Kanewala, and N. Niu, “Contextual understanding and improvement of metamorphic testing in scientific software development,” in Proceedings of the 15th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM), 2021, pp. 1–6. [34] A. Dwarakanath, M. Ahuja, S. Sikand, R. M. Rao, R. J. C. Bose, N. Dubash, and S. Podder, “Identifying implementation bugs in machine learning based image classifiers using metamorphic testing,” in Proceedings of the 27th ACM SIGSOFT international symposium on software testing and analysis, 2018, pp. 118–128. [35] N. B. Chaleshtari, F. Pastore, A. Goknil, and L. C. Briand, “Metamorphic testing for web system security,” IEEE Transactions on Software Engineering, vol. 49, no. 6, pp. 3430–3471, 2023. [36] L. Lin, Q. Zhu, H. Chen, Z. Wang, R. Wu, and X. Xie, “Qtran: Extending metamorphic-oracle based logical bug detection techniques for multiple-dbms dialect support,” Proceedings of the ACM on Software Engineering, vol. 2, no. ISSTA, pp. 731–752, 2025. [37] R. Hodován and Á. Kiss, “Modernizing hierarchical delta debugging,” in Proceedings of the 7th International Workshop on Automating Test Case Design, Selection, and Evaluation, 2016, pp. 31–37. [38] Á. Kiss, R. Hodován, and T. Gyimóthy, “Hddr: a recursive variant of the hierarchical delta debugging algorithm,” in Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, 2018, pp. 16–22. [39] M. Zhang, Y. Tian, Z. Xu, Y. Dong, S. H. Tan, and C. Sun, “LPR: Large language models-aided program reduction,” in Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis, 2024, pp. 261–273. [40] T. Y. Chen, T. H. Tse, and Z. Q. Zhou, “Fault-based testing in the absence of an oracle,” in Proceedings of the 25th Annual International Computer Software and Applications Conference (COMPSAC’01), 2001, pp. 172–178. [41] M. Jiang, T. Y. Chen, F.-C. Kuo, D. Towey, and Z. Ding, “A metamorphic testing approach for supporting program repair without the need for a test oracle,” Journal of Systems and Software, vol. 126, pp. 127–140, 2017. [42] X. Niu, Y. Sun, H. Wu, G. Li, C. Nie, L. Yu, and X. Wang, “Enhance combinatorial testing with metamorphic relations,” IEEE Transactions on Software Engineering, vol. 48, no. 12, pp. 5007–5029, 2021. [43] D. Sobania, M. Briesch, P. Röchner, and F. Rothlauf, “Mtgp: Combining metamorphic testing and genetic programming,” in European Conference

13

on Genetic Programming (Part of EvoStar). Springer, 2023, pp. 324– 338. [44] “Experimental results. ddmt.” [Online]. Available: https://github.com/ymxl85/DDMT