1 Introduction↩︎

Testing identifies bugs during software development and evolution, and it typically accounts for half of the development expenses [1]. To automate testing, multiple methods have been proposed that automatically generate or mutate inputs [2], [3], on which a so-called test oracle is applied to determine whether the program’s execution behavior is expected [4].

Metamorphic testing is a popular methodology to tackle the test oracle problem [5], [6]. It has been applied successfully in various domains, such as database systems [7], [8], compilers [9]–[11], and Satisfiability Modulo Theory (SMT) solvers [12]–[14]. Metamorphic testing has been proposed as a methodology to test untestable systems, that is, systems for which it is difficult to specify the exact behavior that is expected. Rather than providing a concrete expected output for a given input, metamorphic testing uses a test input \(t_a\) to derive a new input \(t_b\), for which a test oracle can be provided that checks whether their outputs \(O_a\) and \(O_b\) comply with a relation, which is called Metamorphic Relation. While metamorphic testing can be used to validate non-functional properties such as performance [15] or information leakage [16], we focus on correctness in this paper.

When designing metamorphic testing methods, it is crucial to be able to assess their effectiveness, especially for the researchers who develop such methods. According to our study on ten representative metamorphic testing methods, the most widely used metric to evaluate metamorphic testing methods is the number of found bugs. However, this metric can only be measured a posteriori, that is, after all the bugs found by metamorphic testing have been fixed, as identifying unique bug-inducing test cases for incorrect-output bugs is an open problem [17], [18]. This is an issue for researchers, who might want to gauge the potential of a metamorphic relation, before conducting a large-scale testing campaign, which often spans over multiple months [19]. Additionally, the quality of target programs can affect the number of unique bugs as a metric because an effective testing method cannot find many bugs in a well-tested program. Existing a priori metrics, which can gauge the potential of a method before conducting a large-scale testing campaign, have been sparsely adopted. Code coverage is not often used, presumably because it more precisely captures how effective a test input generator is. Mutation testing, despite advances in improving its efficiency [20], is still often prohibitively expensive to use in practice.

In this paper, we propose Metamorphic Coverage (MC), a simple and practical metric for evaluating the quality of metamorphic testing methods. We believe that a test input pair \(t_a\) and \(t_b\) is typically most effective in finding bugs when the inputs exercise different code paths, since a faulty location might be covered by \(t_a\) or \(t_b\), but not the other, resulting in potential violations of the metamorphic relation. Therefore, our idea is to examine the difference in the code exercised by \(t_a\) and \(t_b\) to measure the quality of metamorphic relations and metamorphic testing methods. MC is a coverage metric based on code coverage, which can be any coverage criteria, such as line coverage. Unlike the number of bugs, which is a posteriori metric, MC is a priori metric that can be measured before conducting a bug-finding campaign. Compared to other coverage metrics, MC can more accurately measure the effectiveness of metamorphic relations. Compared to mutation testing, MC is a lightweight method as it does not require additional execution effort. ]

int calculate_difference(int x, int y) {
    if (x > y) {
        return x - y;
    } else {
        return y - x + 1; // &\bugsymbol& y - x;
    }
}

[lst:intro] shows a motivating example. The function calculates the absolute difference between two numbers. We consider two metamorphic relations. \(R_1\): if \(t_a=(x, y)\) and \(t_b=(y, x)\), \(O_a=O_b\), indicating swapping both input numbers should output the same result. \(R_2\): for an integer \(c\), if \(t_a=(x, y)\) and \(t_b=(x + c, y + c)\), \(O_a=O_b\), indicating a constant added to both input numbers should output the same result. For given inputs \(x\) and \(y\), if \(x \neq y\), \(t_a\) and \(t_b\) of \(R_1\) cover the if and else branches respectively, while \(t_a\) and \(t_b\) of \(R_2\) cover the same if or else branch. Given \(t_{a1}=(2,3)\), \(t_{a2}=(6,2)\) and \(c=1\), \(R_1\) derives \((3,2)\) and \((2,6)\), and \(R_2\) derives \((3,4)\) and \((7,3)\). Both \(R_1\) and \(R_2\) cover all code lines: \(Cov(t_a) \cup Cov(t_b) = \{2-7\}\). However, only \(R_1\) can identify the bug in line 5, which is caused by redundant +1. Thus, line coverage cannot distinguish the bug-finding effectiveness of both relations. Suppose MC is based on line coverage, the code covered by MC is \(\textsl{MC}(t_a, t_b) = Cov(t_a) \triangle Cov(t_b) = \{3,5\}\) for \(R_1\) and \(\varnothing\) for \(R_2\). This suggests that \(R_1\) has a higher MC and better bug-finding effectiveness than \(R_2\), corresponding to our intuition that a relation is more effective in finding bugs when the inputs execute different code paths.

The intuition that the effectiveness of a metamorphic testing method depends on whether the inputs on which the metamorphic relations are defined cover disjoint portions of the code is not new. We believe most metamorphic testing methods are designed based on this intuition [8], [9], [21]. However, this intuition was only informally observed, claimed, or studied on small, artificial metamorphic relations and programs [22]–[24]. We systematically evaluated it on widely used metamorphic testing approaches. We also propose to utilize this intuition in other scenarios, such as guidance-based fuzzing.

We evaluated MC on five metamorphic testing methods. The results show that MC is strongly correlated to the bugs found by metamorphic testing methods, since the code covered by MC overlaps with the fixes of 50 of 64 bugs found by the five metamorphic testing methods. MC is 4\(\times\) more sensitive than line coverage to distinguish method effectiveness and has the same magnitude of time consumption as line coverage. We used MC as guidance for generating test cases, and it could help the metamorphic testing methods NoREC [8] and TLP [7] in finding 41% more bugs than code coverage. This finding has potentially broad implications, enabling efficient feedback-driven test-case generators for metamorphic testing. The artifact is available at https://figshare.com/s/7d3a5e04c69b06204b7e.

Overall, we make the following contributions:

• We propose MC, a novel method to evaluate metamorphic testing methods by measuring the differential code coverage of a pair of test inputs.

• We implemented and evaluated MC in a comprehensive study on five metamorphic testing methods. The fixes of 50 of 64 bugs found by these methods overlap with the code measured by MC.

2 Background↩︎

Code coverage. Code coverage is the percentage of the source code of a program executed by a particular testing method or test suite. An assumption is that a testing method that covers more code can find more bugs, so code coverage is typically used to assess a testing method’s adequacy. Multiple code coverage criteria have been proposed [25], and in this paper, we consider the following common coverage criteria:

• Line coverage, which measures the percentage of source code lines that have been executed;

• Statement coverage, which measures the percentage of instructions that have been executed;

• Branch coverage, which measures the percentage of control-flow branches (e.g. in if or switch-case statements) that have been executed.

• Function coverage, which measures the percentage of functions that have been executed.

To evaluate a metamorphic relation, typically, the cumulative coverage of executing all pairs of \(t_a\) and \(t_b\) is measured [8], [13]. In [lst:intro], line coverage is 100% (6/6) as all lines have been executed: \(\{2-7\}\). Statement coverage is the same as line coverage, because each line only has one statement. Branch coverage is 100% (2/2), because both branches in lines 3 and 5 have been executed. The function calculate_difference() is executed, so the function coverage is 100% (1/1). Code coverage cannot distinguish both metamorphic relations as both have the same coverage.

Mutation testing. Mutation testing (also known as mutation analysis) is another methodology for assessing the adequacy of a test suite by injecting mutations into programs [26], [27], and measuring whether the test suite or testing method can identify them as bugs. Mutation testing requires a set of predefined mutation operators \(\{m|m \in M\}\), such as mutating an arithmetic operator \(-\) to \(+\), or removing a function call. We apply \(M\) to a program \(P\), and obtain a set of program mutations \(\{m(P)|m \in M\}\), each of which slightly differs from \(P\) and aims to simulate a bug. Given a test suite \(X\), if any test \(x \in X\) fails when running a \(m(P)\), then \(m(P)\) is said to be killed by \(X\), which we denote as \(kills(m(P), x)\). Otherwise, \(m(P)\) is said to survive for \(X\). We expect that \(X\) can kill more of \(\{m(P)|m \in M\}\), so the adequacy of the test suite \(X\) is defined by the mutation score, which is computed as the fraction of program mutations killed: \(\frac{|\{m(P)|m \in M \& \exists x \in X:kills(m(P), x)\}|}{|\{m(P)|m \in M\}|}\). To evaluate the quality of metamorphic relations, mutation testing can be used to examine how many simulated bugs can be identified as bugs by the metamorphic relations. In [lst:intro], suppose the bug in line 5 is a mutation, executing any input violates \(R_1\). This mutation is killed and the mutation score is 100% (1/1). The mutation score is typically deemed a good indication of the fault detection ability of a test suite [25], [28]. However, injecting mutations to simulate bugs is time-intensive [29], because the program needs to be recompiled and executed for each mutant.

3 Metamorphic Evaluation Study↩︎

As a motivating study, we investigated what metrics were used to evaluate popular metamorphic testing methods.

Studied metamorphic testing methods. As shown in 1, we chose ten representative metamorphic testing methods. They were published in well-known academic conferences of programming languages and software engineering during the past 10 years (2014–2024). Referentially Transparent Inputs (RTI) [30] and Metamorphic Object Detection (MetaOD) [31] test AI systems. Equivalence Modulo Inputs (EMI) [9] and HirGen [21] test the compilation correctness of compilers. Non-optimizing Reference Engine Construction (NoREC) [8] and Ternary Logic Partitioning (TLP) [7] test the query processing functionality of Database Management Systems (DBMSs). YinYang [13] and Skeletal Approximation Enumeration (SAE) [32] test Satisfiability Modulo Theory (SMT) solvers, which are used to determine whether there exists an assignment to variables that satisfy a given formula. Excessive Data Exposure Fuzzing (EDEFuzz) [33] and Metamorphic Relation Output Patterns (MROP) [34] test whether Web applications return complete and correct content. To study how these metamorphic testing methods were evaluated, we carefully examined the papers describing the ten metamorphic testing methods.

Results. The column Metrics in 1 shows the four identified evaluation metrics used for evaluating the ten studied metamorphic testing methods. Bugs refers to the number of found bugs in the real world. Time represents the execution throughput. Overall, Bugs is the most prevalent and important evaluation metric as it was used to evaluate all metamorphic testing methods. Three methods EMI, HirGen, and NoREC were evaluated by Bugs only. Code Coverage and Mutation Score are not commonly used, and we believe that the reason for this is the accuracy of code coverage and time cost for mutation testing. For example, concerning code coverage, in NoREC [8], the authors claimed that “code coverage is not particularly useful for fuzzing DBMS, since high coverage for the core components (e.g., the query optimizer) can be achieved quickly.” TLP and YinYang measure line coverage, while SAE measures line, function, and branch coverage. Only MROP reported a mutation score. We suspect that other approaches did not adopt mutation testing due to the high execution time needed to compute it. It shows that only the number of bugs, as a a posteriori metric, is widely used, and no a priori metric is widely used—we understand an a priori metric as one that eschews an extensive testing campaign that requires developers to fix reported issues to measure the metric’s effectiveness. Additionally, we found that half of the studied methods were evaluated by throughput, which shows that testing efficiency is also an important factor for metamorphic testing methods.

4 Approach↩︎

We propose Metamorphic Coverage (MC), a novel metric for evaluating the quality of metamorphic testing methods by measuring the differential code executed by pairs of test inputs. For a pair of test inputs \(t=(t_a, t_b)\), our intuition is that a bug can be observed if it affects the execution of either \(t_a\) or \(t_b\) but not the other, implying that \(t\)s that cover more differential code are more likely to find bugs.

We define Metamorphic Coverage (MC) as follows: For an ordered pair of test inputs \(t=(t_a, t_b)\), the code covered by metamorphic coverage is \(\textsl{MC}(t) = Cov(t_a) \:\triangle\: Cov(t_b) = (Cov(t_a) \cup Cov(t_b)) - (Cov(t_a) \cap Cov(t_b))\), in which \(\triangle\) represents the differential coverage and \(Cov(t_a)\) and \(Cov(t_b)\) represent the code covered by code coverage—any concrete code coverage metric, such as line and branch coverage can be used—of executing \(t_a\) and \(t_b\) in the target system. Subsequently, for conciseness, we refer to \(Cov(t_a) \triangle Cov(t_b)\) as differential coverage. Suppose \(T=\{t_1, t_2, ..., t_k\}\), the code covered by metamorphic coverage is \(\textsl{MC}(T) = \bigcup_{i=1}^{k}(\textsl{MC}(t_i))\). 1 illustrates how to compute MC, and we explain the concrete steps to measure MC for each \(t\) and to combine them as follows.

Step 1: collecting coverage. Given a pair of test inputs \(t=(t_a, t_b)\), we first execute the target program passing them as inputs, and measure their executed code for code coverage \(Cov(t_a)\) and \(Cov(t_b)\) separately. \(Cov()\) can be any metric, including line \(Cov_{line}()\), branch \(Cov_{branch}()\), and function coverage \(Cov_{function}()\). MC is not restricted to any specific coverage metrics. In 1, we show the example by \(Cov_{line}()\) because it is straightforward to understand. Unless specified, \(Cov()\) is short for \(Cov_{line}()\). In 1, \(Cov(t_a) = \{2, 4, 5, 6, 7\}\), and \(Cov(t_b) = \{2, 3, 4, 6, 7\}\).

Step 2: deriving MC* for \(t\).* We calculate the code covered by MC by measuring the differential coverage \(Cov(t_a) \:\triangle\: Cov(t_b)\). In 1, \(\textsl{MC}(t) = \{3, 5\}\).

Step 3: deriving MC* for \(T\).* Step 2 measures the tested program parts, and we combine all \(\textsl{MC}(t)\) by unioning them to derive \(\textsl{MC}(T)\) for measuring the tested program parts. In 1, \(T\) includes two pairs of test inputs. The MC for the other pair of test inputs is \(\{5\}\), so \(\textsl{MC}(T) = \{3, 5\}\).

Advantages. MC is effective and lightweight in evaluating the quality of metamorphic testing methods. MC considers the code that is validated by metamorphic relations, instead of all executed code. Therefore, MC is more sensitive to distinguishing the quality of different metamorphic testing methods than code coverage. Computing MC does not require recompiling the program, which is necessary for mutation testing, so MC is more lightweight than mutation testing. MC is slightly more expensive than code coverage as computation effort is required to derive differential code coverage.

Limitations. MC is not an absolute indicator of bug-finding effectiveness. First, bugs can be found even if MC is zero. Suppose we have a one-line C program int output = input + 1000;. A possible metamorphic relation is that if an input \(t_a\) is bigger than another input \(t_b\), \(t_a\)’s output must be bigger than \(t_b\)’s output. A bug occurs if \(t_a\) is too big so that \(t_a+1000\) overflows. However, in this case, MC is zero, as both cases execute the same code. However, in ¿sec:subsec:Q1?, we will show that this situation is not prevalent in practice. Second, an MC score of 100% does not mean the target program is tested thoroughly. If \(t_a\) covers all code, while \(t_b\) does not trigger any program logic, MC is 100%. Typically, we expect executing both inputs to trigger different logic, so that we can compare them to find bugs. If either input does not trigger any logic, no logic is evaluated and the metamorphic relation is too weak.

Implementation. We implemented MC for the C/C++ programming language. For step 1, we measured code coverage by gcov,¹ which is the most widely used source code coverage analysis tool for C/C++. For step 2, we derive the coverage difference by implementing a plugin in gcovr,² which is a popular utility for managing gcov. gcovr supports multiple formats to store, analyze, and visualize code coverage. We used the JSON format to store the code coverage collected from step 1, because it is a structured format that facilitates machine processing. In step 2, our plugin derives a new coverage file in the same format of JSON, so that we can leverage gcovr to visualize and analyze MC without additional implementation effort. The plugin was implemented in around 100 lines of Python code, suggesting that its low implementation effort might make the approach widely applicable.

5 Evaluation↩︎

To evaluate the effectiveness and efficiency of MC for evaluating metamorphic testing methods, we seek to answer the following questions:

Q.1 Effectiveness.

Can MC evaluate the bug-finding capability of metamorphic testing methods?

Q.2 Sensitivity.

To what extent can MC distinguish the bug-finding capability?

Q.3 Efficiency.

What is the performance overhead of MC?

Q.4 MC-guided Fuzzing.

Can MC-based feedback guide test case generation?

Q.5 Configuration Sensitivity Analysis.

How does MC perform under different configurations?

Evaluated metamorphic testing methods. Within the studied methods in 1, we chose five metamorphic testing methods whose source code and bug lists are publicly available for evaluation and analysis of the effectiveness of MC based on found bugs. The chosen methods test three important categories of programs: DBMSs, compilers, and SMT solvers.

For DBMSs, we chose NoREC and TLP. TLP includes five metamorphic relations for testing the five SQL features: aggregate functions, the queries containing the clauses DISTINCT, WHERE, GROUP BY, and HAVING. We named them \(TLP_{a}\), \(TLP_{d}\), \(TLP_{w}\), \(TLP_{g}\), and \(TLP_{h}\).

For compilers, we chose HirGen [21]. We identified two metamorphic relations in HirGen: \(HirGen_{opt}\) and \(HirGen_{mut}\), both of which were illustrated in Section 3.3.2 of its paper [21]. Although EMI found more bugs than HirGen, we did not consider EMI, because its source code is not available and its bug reports include minimized bug-inducing test inputs, which we cannot use to evaluate MC.

For SMT solvers, we chose YinYang [13] and SAE [32]. We identified two metamorphic relations in YinYang: \(YinYang_{sat}\) and \(YinYang_{unsat}\), both of which realize YinYang for testing satisfied and unsatisfied formulas.

Tested programs for evaluated metamorphic testing methods. Each metamorphic testing method may be applied to more than one target program, for which we chose commonly tested programs. For DBMSs, we chose SQLite and DuckDB, which were tested by NoREC and TLP. SQLite is the most widely deployed DBMS,³ and DuckDB is a successor of SQLite. For compilers, we chose TVM [35], which was tested by HirGen. For SMT solvers, we chose Z3 [36] and CVC4 [37], which were tested by YinYang and SAE. TVM is a popular deep-learning compiler that optimizes the performance of AI modules. Z3 and CVC4 are the two most popular SMT solvers that regularly achieve high ranks in SMT competitions.⁴ The chosen programs are written in C/C++, for which we can leverage mature code coverage tools, such as gcov.

Versions of tested programs. For Q1, we used SQLite (version 3.29.0), DuckDB (commit: a09d2f4 and bc9f086), TVM (commit: 124813f), Z3 (version 4.8.13), and CVC4 (commit: 16c2fe5), which correspond to the major versions in which the bugs from the bug lists were found. For Q2, Q3, and Q5, we used the latest versions supported by these metamorphic testing methods: SQLite (commit c66c77), DuckDB (version 0.5.1), TVM (commit 124813f), Z3 (version 4.13.0), and CVC4 (commit 40eac7f). For Q4, we used the last versions of programs in which the metamorphic testing methods can find bugs: SQLite (commit: 3a461f) and DuckDB (version 0.5.1).

Seeds for evaluated metamorphic testing methods. The evaluated metamorphic testing methods require seed inputs from which new test cases are generated. We used the default seeds used in the evaluation of each method. Specifically, YinYang and SAE adopt the conventional SMT-LIB 2 benchmark as seeds, while other methods implement custom generators to construct suitable seeds, since they require specific input structures. For example, NoREC mandates the presence of a WHERE clause, but does not support queries with GROUP BY, which makes conventional test suites such as TPC-DS unsuitable for its evaluation.

Baselines. We compared MC against line coverage and mutation score. We measured line coverage by gcov, and mutation score by Mull [38]. Mull is a state-of-the-art mutation testing framework that enhances performance by injecting faults into programs during compilation and enabling them respectively through environment variables. We used the 18 default mutators in Mull, including arithmetic and comparison mutations. Mull identified 19,360, 14,363, 10,396, 6,628, and 21,068 mutations for SQLite, DuckDB, TVM, Z3, and CVC4, respectively. By comparing with them, we gain insights into the benefits of MC against code coverage and mutation score metrics for evaluating metamorphic testing methods.

Experimental infrastructure. We conducted all experiments on an AMD EPYC 7763 processor that has 64 physical and 128 logical cores clocked at 2.45GHz. Our test machine uses Ubuntu 22.04 with 512 GB of RAM, and a maximum utilization of 60 cores. We repeated experiments 10 times for statistically significant results.

Q.1 Effectiveness↩︎

We investigated whether the bug fixes overlap with the differential code, as examined by MC, and whether MC is correlated with the number of bugs. Overlap indicates that MC covers at least one line of the bug fix. A significant overlap and strong positive correlation would support the applicability of MC in evaluating the bug-finding effectiveness of metamorphic testing methods. We evaluated both based on the historical bugs found by the evaluated metamorphic testing methods.

Preprocessing test cases. We observed that the bug reports of NoREC, TLP, and YinYang include minimized bug-inducing test inputs, which were reduced to a single bug-inducing input, lacking the second input as well as metamorphic relation, preventing us from directly evaluating MC. [lst:convertion] shows an example bug found by NoREC. Lines 1–4 show the minimized test input, in which only one query exists, while NoREC requires a pair of queries to validate the metamorphic relation. To address this in a best-effort manner and apply MC, we manually converted the test cases to trigger the bug using the proposed metamorphic relations. For example, we converted the query in line 4 into a pair of queries in lines 6–7 according to the metamorphic relation of NoREC—the first query is a subquery of the second query and both queries should return the same result. Therefore, \(t_a\) includes lines 1–4 and 6, and \(t_b\) includes lines 1–4 and 7. Such conversion steps were not always possible, due to information lost during minimization. For example, for NoREC and TLP some test cases lacked WHERE clauses needed for conversion. We successfully converted 27 bugs for SQLite and 20 bugs for DuckDB. For YinYang, we requested 14 original bug-inducing test inputs that include metamorphic relations from the authors. For HirGen, the metamorphic relations were explicit in all bug-inducing test inputs, so we directly used them. For SAE, most bugs were crash bugs, and we did not find any bug-inducing test inputs for the metamorphic relations. Last, we processed the test inputs only when the buggy behaviors could be reproduced and their corresponding bug fixes could be found in bug reports or were provided by authors.

CREATE TABLE t0(c0);
INSERT INTO t0(c0) VALUES (NULL);
CREATE INDEX i0 ON t0(1) WHERE c0 NOT NULL;
SELECT * FROM t0 WHERE (t0.c0 IS FALSE) IS FALSE;
------------------------@$\Downarrow$@------------------------
SELECT COUNT(*) FROM t0 WHERE (t0.c0 IS FALSE) IS FALSE;
SELECT SUM(count) FROM (SELECT ((t0.c0 IS FALSE) IS FALSE) as count FROM t0) as asdf;

Bug fix overlap. 2 shows the number of bugs and the relations of their fixes to MC. Within the total of 65 bug fixes, 50 bug fixes overlap with MC. 76.9% of bug fixes are directly located in the code of MC, showing a strong correlation between both. These bugs, whose fixes do not overlap with differential code, occur because buggy functions are called in different code locations.

CREATE TABLE t0(c0);
INSERT INTO t0(c0) VALUES (NULL);
CREATE INDEX i0 ON t0(1) WHERE c0 NOT NULL;
SELECT COUNT(*) FROM t0 WHERE (t0.c0 IS FALSE) IS FALSE; -- {0}
SELECT SUM(count) FROM (SELECT (t0.c0 IS FALSE) IS FALSE as count FROM t0) as asdf; -- {1}

--- src/expr.c
+++ src/expr.c
@@ -5034,11 +5034,11 @@
 switch( p->op ){
...
  case TK_TRUTH: {
   if( seenNot ) return 0;
   if( p->op2!=TK_IS ) return 0;
-  return exprImpliesNotNull(pParse, p->pLeft, pNN, iTab, seenNot);
+  return exprImpliesNotNull(pParse, p->pLeft, pNN, iTab, 1);
  }
...
}

An example of the relation overlapping. [lst:example1] shows a bug-inducing test input for a bug found by NoREC. The queries in lines 4 and 5 return inconsistent results, which violate NoREC. Lines 15 and 16 show the code fix. The gray color represents the code covered by MC. The bug’s root cause was an incorrect assumption that \(x\) is always not null for the expression (x IS FALSE) IS FALSE. This assumption is specified by the last parameter of the function exprImpliesNotNull and is executed for the first query in line 15. The second query evaluates the expression differently and does not execute line 15. The code of MC covers the bug fix in line 15, which is only executed for the first query.

CREATE TABLE t0(c0 TEXT PRIMARY KEY);
INSERT INTO t0(c0) VALUES ('');
SELECT COUNT(*) FROM t0 WHERE (t0.c0, TRUE) > (CAST('' AS REAL), FALSE); -- {0}
SELECT SUM(COUNT) FROM (SELECT ((t0.c0, TRUE) > (CAST('' AS REAL), FALSE)) IS TRUE as count FROM t0) as asdf; -- {1}

--- src/expr.c
+++ src/expr.c
@@ -68,10 +68,13 @@
char sqlite3ExprAffinity(Expr *pExpr){
...
+  if( op==TK_VECTOR ){
+    return sqlite3ExprAffinity(pExpr->x.pList->a[0].pExpr);
+  }
   return pExpr->affExpr;
}
...
aff = sqlite3ExprAffinity(pExpr->pLeft);
...
pCol->affinity = sqlite3ExprAffinity(p);

An example of the relation non-overlapping. [lst:example2] shows another bug-inducing test input for the bug 6ef984af found by NoREC. Similarly, NoREC finds this bug, because the queries in lines 3 and 4 return inconsistent results. This bug’s root cause was a missed case in the function sqlite3ExprAffinity as fixed by lines 11–13. Although this function is executed for both queries, it is called in different code locations. In line 17, the function call is executed for both queries, and does not trigger the is executed only for the second query, and triggers the special case in line 11, so that the bug is observed.

Bug correlation. Based on the bugs listed in 2, we randomly sampled varying numbers of bugs to form multiple sets. For each set, we measured line coverage and MC, repeating this process 50 times. 2 illustrates the relationship between the number of bugs in each set and the corresponding line coverage and MC scores. Visually, MC increases more steeply than line coverage as the number of bugs grows. To quantify this observation, we computed the Pearson Correlation Coefficient (PCC) [39] between each metric (line coverage and MC) and the number of bugs, as reported in 3. PCC measures the linear correlation between two variables, ranging from \(-1\) to \(1\), with higher values indicating stronger positive correlation. Overall, MC shows a stronger positive correlation with the number of bugs than line coverage as the PCC of MC is above 0.9 for both SQLite and DuckDB. Compared with line coverage, MC improves the PCC by an average of 0.13. We excluded TVM and CVC4 from the analysis due to an insufficient number of bugs. The mutation score was not included in 2, as it consistently approaches 100%—each test case typically triggers buggy behavior, making the metric uninformative in this context.

Q.2 Sensitivity↩︎

We evaluated the sensitivity and metric value range of MC for evaluating metamorphic testing methods and compared that with line coverage and mutation score. Sensitivity refers to the capability of differentiating test inputs and was proposed to evaluate various coverage metrics in fuzzing techniques [40]. We used the sensitivity of the various metrics to assess this aspect. Metric value range refers to the possible value range of a metric. In Q1, we showed that differential code is strongly related to bug fixes, which are in the tested program logic. Considering that line coverage subsumes MC, if MC is smaller than line coverage, MC can represent the bug-finding effectiveness in finer granularity.

Methodology. We measured MC, line coverage, and mutation scores for the test inputs generated by the evaluated metamorphic testing methods. First, we ran each metamorphic testing method to randomly generate 100 pairs of test inputs as a test suite. 100 is a widely accepted setting for test suite size and has been used for previous work [28]. 100 is also a reasonable number, as each coverage data produced by gcov requires one minute on average on our machine. We repeated this generation 10 times to generate 10 test suites and measured the average code coverage, mutation score, and MC. To measure line coverage and MC, we first measured the line coverage for each test input of a test suite, and then calculated the cumulative coverage as the line coverage and the differential coverage as MC for the test suite. For mutation score, although Mull already implements various optimizations by injecting all mutations during compilation without the need for recompilation, the time overhead is still significant due to the number of mutants. To measure the mutation scores in a feasible time budget, we ran Mull in 50 parallel threads, which do not depend on each other. We deemed a mutation to be killed only when the results violate the metamorphic relation. For each testing method, we re-implemented the metamorphic relation within Mull, so that it can identify whether the execution results violate the metamorphic relation. Most testing methods directly produce pairs of inputs, while only YinYang fuses two inputs into one and examines their consistency, so its testing iteration involves three test inputs. To construct pairs of inputs, we merge the first two test inputs as \(t_a\) and deem the third input as \(t_b\).

Challenges of measuring mutation scores. Measuring mutation scores for real-world metamorphic testing methods faces practical issues. \(HirGen_{opt}\) and SAE had a high false alarm rate, incurring a 100% mutation score, which was meaningless, so we ignored their mutation scores. \(HirGen_{opt}\) detects bugs by checking consistencies before and after optimizations. However, some optimization strategies are incompatible with specific models, and incur errors violating the metamorphic relation. We reported the false alarm issue to the authors of HirGen, and they confirmed our findings. SAE examines whether a pair of test inputs are satisfied or unsatisfied at the same time, while we observed that executing the second test input may return multiple results, instead of one. We raised GitHub issues to ask the authors of SAE, but have not received any response as of the time of writing this paper. For \(YinYang_{sat}\) and \(YinYang_{unsat}\) on Z3 and CVC4, the mutation score is around 0.01%. The reason is that YinYang validates the results only when the first test inputs return the same SAT or UNSAT results. A random mutation can easily cause either input to become invalid or both inputs to return inconsistent results, and YinYang does not work for such mutated programs.

Sensitivity. To quantify the sensitivity of various metrics, we evaluated the Coefficient of Variation (CV) for 4. CV [41] measures the variability of data independently of the absolute numbers and is defined as the ratio of the standard deviation \(\sigma\) to the mean \(\mu\), \(CV={\frac{\sigma }{\mu }}\). If a metric has a higher value of CV, it is more sensitive than other metrics to distinguish the quality of test suites.

5 shows our results. Across the five programs, the average CV of MC is 0.24, which is 4\(\times\) higher than the CV of line coverage, which is 0.06. For each program, the CV of MC is bigger than mutation score, and the line coverage. For mutation scores, we evaluated the average value across SQLite and DuckDB, because mutation scores for other programs are not fully available. The results show that MC is significantly more sensitive to differentiating metamorphic relations than line coverage and also outperforms the mutation score.

Metric value range. 4 shows average line coverage, mutation score, and MC across 10 randomly generated test suites by metamorphic testing methods. Overall, MC is 6\(\times\) smaller than line coverage. Considering that MC is a subset of line coverage and is strongly correlated to the found bugs, MC can quantify bug-finding capability in finer granularity. The relatively small size of MC suggests that a significant portion of the program remains untested, highlighting the potential for discovering new metamorphic relations to improve testing.

Q.3 Efficiency↩︎

While our major questions are about the evaluation effectiveness of MC, performance overhead is also an important consideration for evaluation metrics, as a high overhead might limit a metric’s applicability. We evaluated the execution time of MC, line coverage, and mutation score based on the same experimental set-up and data in Q2. We derived the execution time by multiplying the actual execution time by 50\(\times\) as we ran Mull in 50 parallel threads.

Results. 6 shows the average execution time for measuring line coverage, mutation score, and MC across 10 test suites in Q2. Overall, measuring MC consumed the same magnitude of time as measuring line coverage, and 359x less time than measuring mutation score. Mutation score consumes significant time due to its computation complexity. This is particularly noticeable on CVC4, which consumes the most time, because a random mutation can easily cause CVC4 to hang. We set a timeout of 10 minutes for Mull to solve this issue. Compared to mutation score, MC is more lightweight, because it consumes much less time and does not require test oracles for validating metamorphic relations. Compared to line coverage, MC is a more efficient method, because it can represent the checked code by a metamorphic testing method, but only moderately increases execution time.

Q.4 MC-guided Fuzzing↩︎

Multiple fuzzing methods use metrics, such as branch coverage [42] and code execution count [43], as guidance to generate or mutate test inputs and have found a large number of bugs. Apart from evaluating the effectiveness of metamorphic testing methods, we evaluated whether MC can be used as guidance to generate more diverse test inputs increasing the likelihood of finding bugs.

Methodology. For the evaluated metamorphic testing methods, NoREC and TLP involve a test input generation process, while HirGen, YinYang, and SAE require user-provided test inputs as \(t_a\) for deriving \(t_b\), so we evaluated whether MC can help NoREC and TLP generate diverse test inputs. NoREC and TLP are implemented in SQLancer, which generates test inputs by Query Plan Guidance (QPG) [44]. Given a database, QPG randomly generates queries and examines their query plans. If no new unique query plan has been seen for a fixed number of iterations, QPG mutates the database and continues to randomly generate queries on the new database. For a fair comparison, we used QPG as a reference and reused its test input generation workflow. Specifically, we replaced QPG as a feedback mechanism with code coverage and MC, and mutated the database if the coverage was not increased for a fixed number of iterations. We reused the instrumentation component of AFL++ [45] to collect branch coverage and derived MC. We refer to both methods as Code Coverage Guidance (CCG) and Metamorphic Coverage Guidance (MCG), respectively.

Results. 3 shows the average number of bugs found by CCG, MCG, and QPG. DuckDB terminated before 24 hours due to crash bugs. For \(TLP_{a}\) in SQLite, all guidance techniques found more than 100 bug-inducing test cases in five minutes, so it cannot distinguish the contributions of guidance, and we excluded it. Overall, more bugs were found in DuckDB than in SQLite, so the gap between guidance is clearer in DuckDB. On average, CCG found 4.4 bugs, MCG found 6.2, and QPG found 6.5 bugs in 24 hours. MCG outperforms CCG on 10 of 11 targets. The result shows that MCG can help metamorphic testing methods generate more diverse test inputs for finding bugs. The only exception is \(TLP_{a}\) in DuckDB, in which most found bugs are unexpected errors. Unexpected errors refer to unhandled exceptions in programs, such as assertions, and can be found by a test input, instead of a pair of test inputs. SQLancer can find these unexpected errors by checking error information without NoREC and TLP. Therefore, CCG helps find more bugs. MCG outperforms QPG on 5 of 11 targets. This is unsurprising, as QPG was designed as a domain-specific feedback metric based on the insight into how DBMSs execute test inputs, while MC can be applied to any metamorphic testing approach, and thus eschews additional domain-specific insights.

Q.5 Configuration Sensitivity Analysis↩︎

Various code coverage metrics. We evaluated the sensitivity of MC using different kinds of code coverage metrics. As we explained in 4, MC is not restricted to line coverage, so we evaluated whether MC performs similarly under branch and function coverage. Specifically, we reused the same experimental set-up and data in Q2, and examined the CV of MC based on branch and function coverage.

Results. 7 shows the CV of MC based on branch and function coverage. On average, MC’s CV is 2.3\(\times\) more than branch coverage’s CV, and 5.7\(\times\) more than function coverage. Similar to 5, MC is significantly more sensitive than line, branch, and function coverage to distinguish the quality of metamorphic testing methods. The result shows that MC consistently outperforms code coverage irrespective of at what granularity it is applied.

Test suite size. For Q2, we evaluated MC based on test suites of 100 test inputs. To answer whether different test suite sizes affect the sensitivity of MC, we examined the CV of MC based on test suite sizes of 50 and 200, which are similar to the sizes used in the previous work [28]. Due to the resource limitation, we did not consider a bigger size.

Results. 8 shows the CV of MC based on test suite sizes 50 and 200. We observed that the results are close to the results in 5 that MC is around 4\(\times\) more sensitive than line coverage. It shows that test suite sizes have no significant effect on the experiments’ results. The observation that test suite size has no significant impact on metric evaluation is consistent with previous work [28], [46].

6 Discussion↩︎

Path to adoption. We believe that MC has the potential for wide adoption. From a conceptual perspective, MC is easy to understand, as it calculates the differential code executed by pairs of test inputs. From an implementation perspective, MC is easy to implement as we implemented MC in around 100 lines of Python code for the C/C++ programming language. From an applicability perspective, MC can be implemented on top of existing widely-used coverage measurement tools in other languages, such as JaCoCo for Java, or Coverage.py for Python. From an empirical perspective, our study on widely-used metamorphic relations and systems suggests the effectiveness of MC.

Improving metamorphic testing methods. MC could be used to identify metamorphic relations for code that is not covered by existing metamorphic relations. From our evaluation, we found that most metamorphic testing methods focus on specific features, so their MC is small (i.e., all evaluated metamorphic testing methods have an MC of less than 5%). For future research on metamorphic testing methods, we believe that systematically designing metamorphic relations to fill MC gaps could significantly improve the bug-finding capability.

int abs(int x) {
    if (x < 0)
        return -x;
    else if (x == 0)
        return 3; // Bug
    else
        return x;
}

Metamorphic relation design guided by MC. Metamorphic relation design is largely a manual and creative task, making it difficult to isolate MC as a quantifiable factor in an automated experiment. Rather, we show an example to show how MC guides the design of new metamorphic relations. In [lst:design], suppose we start with Metamorphic Relation 1 (MR1): \(abs(x) == abs(-x)\). For example, \(abs(3) == abs(-3)\) and \(abs(0) == abs(-0)\). MR1 covers the first and third branches (i.e., lines 2, 3, 6, and 7) differently, so its MC covers the two branches without the second branch at lines 4 and 5. To fill this gap, we need a metamorphic relation in which one test case takes the x == 0 branch while the other takes a different branch. This means the two inputs must include zero and a non-zero value. We can propose Metamorphic Relation 2 (MR2): \(abs(x) \geq abs(0)\). For instance, \(abs(3) \geq abs(0)\) or \(abs(-5) \geq abs(0)\). In this case, MC covers all branches, and MR2 exposes the bug, as \(abs(2) < abs(0)\).

**MC* on metamorphic relations with multiple inputs and outputs.* In 1, we defined MC based on metamorphic relations expressed as test pairs \(t=(t_a, t_b)\), where \(t_a\) and \(t_b\) each correspond to a single input. However, some relations require multiple inputs in either \(t_a\) or \(t_b\). For example, YinYang, evaluated in 5, defines \(t_a\) using two inputs. In such cases, we treat the union of the code coverage from all inputs in \(t_a\) as the coverage of \(t_a\). This step would not affect the effectiveness of MC, as it aims to capture the differential coverage between \(t_a\) and \(t_b\), reflecting the likelihood of exposing violations of the metamorphic relation.

Threats to Validity. The evaluation of MC faces potential threats to validity. A concern is internal validity, that is, the degree to which our results minimize systematic error. MC was compared to other metrics based on randomly generated test suites. The randomness process may limit the reproducibility of our results. To mitigate the risk, we repeated all experiments 10 times to account for potential performance fluctuations. The other concern is external validity, that is, the degree to which our results can be generalized to and across other metamorphic testing methods. We selected five representative metamorphic testing methods in three commonly tested domains. According to our study, metamorphic testing methods follow similar testing mechanisms, suggesting that our results generalize to other metamorphic testing methods.

7 Related Work↩︎

Metamorphic testing. Several studies present a comprehensive overview of metamorphic testing [6], [47], [48]. As shown in 1, we investigated the evaluation metrics of ten metamorphic testing methods, which have cumulatively found thousands of bugs. However, in this work, rather than studying existing metamorphic relations or proposing a new one, our core contribution is a novel coverage metric to evaluate metamorphic testing methods and a comprehensive evaluation thereof.

Evaluating metamorphic relations. Empirical studies were conducted to investigate the effectiveness of metamorphic relations. These include case studies by Chen et al. [23] on the shortest path program, by Asrafi et al. [24] on two small programs with manually crafted metamorphic relations, and by Guderlei et al. [49] on two small programs with manually crafted metamorphic relations. The authors of the above studies consistently observed that the metamorphic relations that cause different software execution behaviors should have high fault detection ability. However, the concept of “difference” between executions was not clearly defined. Cao et al. [22] studied various notions of difference and bug-finding effectiveness. However, all of the above papers studied metamorphic relations specifically designed for the study, rather than metamorphic relations that have demonstrated their bug-finding capabilities on important and well-tested systems. Unlike these works that focus on empirical analyses, in this work, we quantitatively define a metric to evaluate the quality of metamorphic testing methods and evaluate them on widely used programs and effective metamorphic relations, both of which have been tested in the real world. We also propose a MC-guided fuzzing to utilize MC to increase the likelihood of finding bugs.

Oracle coverage. Some metrics have been proposed to evaluate test oracles, mostly assertions, which typically check invariants when executing a single test input. Koster et al. [50] proposed state coverage, which measures the percentage of the output-relevant variables checked by an assertion. Vanoverberghe et al. [51] improved state coverage to measure the percentage of only program variables that are read by the assertion. Schuler et al. [52], [53] proposed checked coverage, which measures the percentage of statements checked by an assertion based on all statements that influence the assertion by control flow or data flow. Hossain et al. [54] proposed to reduce the total space of checked coverage by measuring only the statements that influence at least one value checked by the assertion. In this work, we propose MC to evaluate metamorphic testing, which compares discrepancies between two test inputs instead of an input.

Coverage criteria. A large body of work considers the relationship between coverage criteria and fault detection. Gligoric et al. [25] examined the correlations of various coverage to mutation testing and concluded that branch coverage and intra-procedural acyclic path coverage perform best to predict the mutation score, which is assumed to be a silver criterion for evaluating test suites. Gopinath et al. [55] further studied the problem and concluded that statement coverage performs best. Inozemtseva et al. [56] investigated the correlation between various coverage criteria and the mutation score for different random subsets of test suites and found a low to moderate correlation between coverage and effectiveness when the number of test inputs in the suite is controlled for. Kakarla [57] and Inozemtseva [58] demonstrated a linear relationship between mutation score and various coverage criteria for individual programs. Wei et al. [59] examined branch coverage as a quality measure showing that branch coverage behavior was consistent across many runs, while fault detection varied widely. Existing work mainly focuses on evaluating the correlation of various coverage criteria to mutation scores. In contrast, in this work, we propose a novel coverage criterion MC for evaluating metamorphic testing.

8 Conclusion↩︎

In this paper, we have proposed a novel coverage metric, Metamorphic Coverage (MC), to evaluate the quality of metamorphic testing methods. The core idea of MC is that a bug can be observed if the faulty code path is executed by a test input, but not the other test input. Therefore, if a metamorphic testing method covers more differential code between the execution of pairs of test inputs, it is more likely to find bugs. The results show that MC is strongly correlated to the bugs found by metamorphic testing methods as the code covered by MC overlaps with the fixes of 50 of 64 bugs found by the five metamorphic testing methods. MC is 4\(\times\) more sensitive than line coverage in distinguishing the quality of metamorphic testing methods and is similarly lightweight in terms of time consumption as line coverage. Despite these promising results, MC is no panacea, similar to code coverage, as achieving a high MC is possible even if the metamorphic test oracle has low bug-finding effectiveness and vice versa. In the future, we believe that MC can be broadly applied to assess metamorphic testing methods and improve test-case generation by using MC as a metric in feedback-guided automated testing.

References↩︎