#  Bug or not Bug? Analysing the Reasons Behind Metamorphic Relation
Violations

Alejandra Duque-Torres2, Dietmar Pfahl2, Claus Klammer3 and Stefan Fischer3
2Institute of Computer Science , University of Tartu, Tartu, Estonia
E-mail: {duquet<EMAIL_ADDRESS>3Software Competence Center Hagenberg
(SCCH) GmbH, Hagenberg, Austria
E-mail: {claus.klammer<EMAIL_ADDRESS>
###### Abstract

Metamorphic Testing (MT) is a testing technique that can effectively alleviate
the oracle problem. MT uses Metamorphic Relations (MRs) to determine if a test
case passes or fails. MRs specify how the outputs should vary in response to
specific input changes when executing the System Under Test (SUT). If a
particular MR is violated for at least one test input (and its change), there
is a high probability that the SUT has a fault. On the other hand, if a
particular MR is not violated, it does not guarantee that the SUT is fault
free. However, deciding if the MR is being violated due to a bug or because
the MR does not hold/fit for particular conditions generated by specific
inputs remains a manual task and unexplored. In this paper, we develop a
method for refining MRs to offer hints as to whether a violation results from
a bug or arises from the MR not being matched to certain test data under
specific circumstances. In our initial proof-of-concept, we derive the
relevant information from rules using the Association Rule Mining (ARM)
technique. In our initial proof-of-concept, we validate our method on a toy
example and discuss the lessons learned from our experiments. Our proof-of-
concept demonstrates that our method is applicable and that we can provide
suggestions that help strengthen the test suite for regression testing
purposes.

###### Index Terms:

Metamorphic testing, metamorphic relation, association rule mining, passive
testing.

##  I Introduction

Software testing is a crucial stage in the software development life cycle as
it ensures the software’s proper operation and quality. One of the most
significant challenges in software testing is the test oracle problem. A test
oracle determines the System Under Test’s (SUT) output for a given input. The
test oracle problem occurs when the SUT lacks an oracle or when creating one
to verify the computed outputs is practically impossible [1]. Metamorphic
Testing (MT) is a software testing approach proposed by [2] [2] to alleviate
the test oracle problem.

In contrast to traditional testing techniques, MT examines the relations
between input-output pairs of consecutive SUT executions rather than the
individual outputs. The relations between SUT inputs and outputs in MT are
known as Metamorphic Relations (MRs). MRs specify how the outputs should vary
in response to specific input changes [3]. When an MR is violated for at least
one test input and its change, there is a strong likelihood that the SUT has a
fault. However, the absence of violation does not ensure that the SUT is
fault-free. As a result, the suitability of the MRs employed significantly
impacts the effectiveness of MT [3].

In current practice, the identification and selection of MRs are made
manually, requiring a deep understanding of the SUT and its problem domain.
The requirement for domain knowledge makes automatic MR identification
challenging [3, 4]. Another critical challenge is the need to distinguish
automatically whether a particular MR violation is due to a fault in the SUT
or because the MR does not satisfy or fully fit a specific
statement/method/function of the SUT for certain test data. In current
practice, interpreting an MR violation is an entirely manual effort. It is
important to highlight that the cost, in terms of time and resources, of the
MT approach is related to the amount of MRs used [5, 6]. Thus, as the number
of MRs grows, the number of test cases may grow exponentially. As a result,
the execution time and the time needed for manual inspection of MR violations
will also increase.

Some approaches indirectly reduce the manual effort required to interpret the
meaning of an MR violation. For instance, [7] [7] provides quantitative
suggestions/guidance for developing automated means of selecting/prioritising
MR for cost-effective MT. [5] [6, 5] proposed two MR prioritisation approaches
to improve MT’s efficiency and effectiveness. These approaches use (i) fault
detection information and (ii) statement/branch coverage information to
prioritise MRs. [8] [8] suggested strategies to clean MRs by deleting
duplicate or redundant MRs. These approaches offer indirect help since by
prioritising or reducing the set of MRs, the number of test cases will be
reduced as well. Thus, the manual effort of inspection through the violated
MRs is less.

Motivated by the above, we ask ourselves the following research question: How
can MRs be refined based on test data?. To answer this question, we developed
a method for refining MRs that suggest whether a detected MR violation results
from a fault in the SUT or arises from the fact that the MR does not apply to
the used test data. Our method assumes that a predefined set of MRs is
provided and uses the concepts of fuzz testing, passive testing, and rule
mining.

First, our method uses a fuzzer to feed random data to the SUT. Second, it
performs the necessary input transformations following the indications of the
MRs. Third, similar to passive tests, logs are produced with information
related to inputs, outputs, and whether or not MRs are violated. Those logs
are used to feed a mining algorithm. Our method employs association rule
mining (ARM). In our context, the purpose of ARM is to extract interesting
relationships between the inputs and whether or not the MR is violated. ARM is
an unsupervised machine learning (ML) method [9]. ARM algorithms attempt to
find relationships or associations between categorical variables in large
transactional datasets [10]. We were particularly interested in understanding
whether the information provided by the resulting model helps in deciding
whether there is a fault or whether the MR does not fully fit the specific
method/function/statement when the violation occurs.

In our initial proof-of-concept, we validate our method on a toy example and
discuss the lessons learned from our experiments. Our proof-of-concept
demonstrates that our method is applicable and can provide suggestions that
help strengthen the test suite for regression testing purposes. We published
the replication package to facilitate future research.

The rest of the paper is structured as follows. Section II presents the main
concepts used in our research. In Section III, we describe the proposed
method. In Section IV, we present our results and discuss threats to validity.
Section V presents the related work. Finally, we conclude the paper in Section
VI.

##  II Background

This section presents the key concepts used in our research. Section II-A
introduces the MT approach. Section II-B provides a brief description of test
data generation techniques, and Section II-C gives a brief introduction to
ARM.

###  II-A Metamorphic Testing

MT is a software testing approach that alleviates the test oracle problem. MT
aims to exploit the internal properties of a SUT to either check its expected
outputs or generate new test cases. Figure 1 shows the MT basic workflow.
Overall, MT works by checking the relation between the inputs and outputs of
multiple executions of the SUT. Such relations are called MRs. MRs specifies
how the outputs should change according to specific variations made to the
input. Overall, MT follows four major steps:

  1. 1.

Create a set of initial tests or source test cases.

  2. 2.

Identify an appropriate list of MRs that the SUT should satisfy.

  3. 3.

Create follow-up test cases by applying the input transformations required by
the identified MRs in Step 2 to each source test case.

  4. 4.

Execute the corresponding initial and follow-up test case pairs.

  5. 5.

Check if the source tests and follow-up tests output change matches the change
predicted by the MR.

The final step needs further interpretation of the MT workflow output based on
the Non-violation of MRs. When a Non-violation is presented, it is not
guaranteed that the SUT is implemented correctly. However, if an MR is
violated for specific test cases, it must be a fault in the SUT, assuming the
MR is defined correctly.

Figure 1: MT basic workflow

###  II-B Test Data Generation

In software testing, test data corresponds to the input data used during test
execution. Test data is used for positive testing, verifying that functions of
the SUT generate anticipated outputs for given inputs, and negative testing,
examining the SUT’s capacity to handle atypical, extraordinary, or unexpected
inputs [ref]. Inadequately constructed testing data could only cover some
potential test cases, which would be detrimental to the software’s quality.

Our method does not attempt to add something new in test data generation
techniques. Instead, we take advantage of Fuzz Testing for generating test
data. Fuzz Testing, often known as “fuzzing,” is a software testing approach
involving injecting erroneous or random data, or “FUZZ,” into software systems
to find coding errors and security flaws. Fuzz testing involves injecting data
using automated or somewhat automated methods and evaluating the system for
various exceptions, such as system failure or malfunction of built-in code,
etc [11].

Overall, fuzzing consists of three components, i.e., input generator,
executor, and defect monitor [11]. The input generator provides the executor
with several inputs, and the executor runs target programs on the inputs.
Then, fuzzing monitors the execution to check if it discovers new execution
states or defects (e.g., crashes). Fuzzing can be divided into Generation-
based and Mutation-based fuzzing. Mutation-based fuzzing alters existing data
samples to create new test data. Generation-Based fuzzing defines new data
based on the system’s input or the target SUT function. It starts generating
input from scratch based on the specification.

Figure 2: Overview of the method for refining MRs based on rule mining

###  II-C Association Rule Mining

ARM is a rule-based unsupervised ML method that allows discovery relations
between variables or items in large databases. ARM has been used in other
fields, such as business analysis, medical diagnosis, and census data, to find
out patterns previously unknown [10]. The ARM process consists of at least two
major steps: finding all the frequent itemsets that satisfy minimum support
thresholds and generating strong association rules from the frequently derived
itemsets by applying a minimum confidence threshold.

A large variety of ARM algorithms exist. [12]. In our experiments, we use the
Apriori algorithm from Python3 Efficient-Apriori library [13]. It is well
known that the Apriori algorithm is exhaustive; it finds all the rules with
specified support and confidence. In addition, ARM doesn’t require labelled
data and is, thus, fully unsupervised. Below we define important terminology
regarding ARM:

Itemset: Let Xi be items, then I ={X1,…, Xk} is an Itemset of k different
items, with k $>$ 1.

Association rule: Consider a dataset $D$, having $m$ different types of items
and $n$ transactions defined by the itemsets constructed from the items. An
association rule exposes the relationships between the elements of the
itemsets in the set of $n$ transactions.

Support: The support of an association rule involving itemsets X and Y is the
percentage of transactions in dataset D that contain itemsets X and Y. The
support of an association rule $X\rightarrow Y$:

$support(X\rightarrow Y)=support(X\cup Y)=P(X\cup Y)$

Confidence: The confidence is the percentage of transactions in the dataset D
with itemset X that also contains the itemset Y. The confidence is calculated
using the conditional probability, which is further expressed in terms of
itemset support: $confidence(X\rightarrow Y)=P(Y|X)=support(X\cup
Y)/support(X)$

Lift: Lift is used to measure the frequency of the occurrence of $X$ and $Y$
together if both are statistically independent of each other. The lift of rule
$(X\rightarrow Y)$ is defined as $lift(X\rightarrow Y)=confidence(X\rightarrow
Y)/support(Y)$.

A lift value of 1 indicates that $X$ and $Y$ appear as frequently together as
they appear individually under the assumption of conditional independence.

##  III Method

Figure 2 presents an overview of the method for refining MRs based on rule
mining. In general, the proposed method comprises two phases. Phase I is in
charge of identifying the degree of applicability of the set of MRs selected.
It is important to highlight that our method does not cover the selection of
appropriate MRs. We assume that there is already a predefined set of several
MRs. Phase II uses the refined MRs to create or improve the test suite for
future SUT versions. Thus, the output of this phase could be seen as a
regression test suite. Each phase is thoroughly described below:

###  III-A Phase I

Phase I comprises three modules: Test Data Generation Module (TDG Module),
Metamorphic Test Module (MT Module) and Analyser Module. Overall, the TDG
Module produces the test data that will feed the SUT and the MT Module. In the
MT Module, the test data is transformed based on the indications of each MR;
then, such transformed data is executed against the SUT. Both SUT outputs, the
output produced with test data and the transformed test data, are executed
against SUT, are checked against the MRs in the MR Checker. Then, the test
data and the results of the MR Checker Module are organised and stored in a
Log file. The Log file is used in the Analyser Module, where processed and
refined MRs based on rules are extracted. These modules, their internal
settings and their activities are detailed below:

####  III-A1 TDG Module

This module generates the test data, which will feed the SUT. It is important
to note that our method does not try to add something new in the field of test
data generation techniques. As we explained in Section II-B, our method uses
fuzzing testing to generate test data. Overall, the basic fuzzing workflow
involves three basic components, input generator, executor, and defect
monitoring. There are open-source tools that can be used in this module.
However, it is necessary to consider the SUT’s application domain. For
instance, fuzzers such as SPIKE proxy, Peach Fuzzer, and OWASP WSFuzzer are
highly recommended for security purposes in web systems. Also, the programming
language must be considered when selecting the fuzzer. For instance, OSS-Fuzz,
Google’s open-source fuzzing platform, supports Java and Python language for
finding security vulnerabilities, stability issues, and functional bugs.
Regardless of the Fuzzer used, this module’s most important is storing the
generated test data.

####  III-A2 MT Module

Overall, this module is responsible for performing the test data
transformation based on the changes in the inputs specified by the MRs,
executing the transformed test data, and checking if the test data and the
transformed test data outputs match the change predicted by the MRs. This
module has three main activities, Set of MRs, Test data transformations, and
MR Checker.

  * •

Set of MRs: It is important to note that our approach does not involve the
initial selection of the MRs. Our approach assumes the prior existence of a
predefined set of MRs.

  * •

Test data transformation: This activity is in charge of transforming the test
data according to the change specified by each MR. To the best of our
knowledge, no tool performs this activity automatically, i.e., the translation
of input change described by the MR and its meaning into code. Thus, this is
considered to be a manual task.

  * •

MR Checker: This activity is responsible for checking that both outputs, test
data and transformed test data match the change predicted by the corresponding
MR.

Once the test data is generated, transformed, and compared by the MR Checker,
i.e., the verdict of the MR Checker is ready, a Log file is produced with the
following information: execution ID, test data, function call, and the MR
Checker verdict per MR.

####  III-A3 Analyser Module

The Analyzer Module is in charge of discovering interesting relations between
test data and whether or not a certain MR has been violated. This module has
three main activities, Pre-processing, Tester feedback, and Rule mining. Below
we describe each activity in detail as well as their internal process:

  * •

Pre-processing: This activity is responsible for ensuring that the data is
correct, consistent and usable. Also, it shows the tester an initial summary
of the percentage of violations and not violations per each MR and function
call. This activity has three main functions: data quality, clean, and summary
report. The data quality function is responsible for checking that Log has no
missing data, as well as removing the rows that are not needed or inconsistent
rows. The clean removes duplicate entries. The Summary report is based on the
percentage of violations and no-violation per MRs. Also, it provides the
tester with the ability to inspect some random sample values and atypical
values. This is done to increase confidence in the suitability of the MRs.

  * •

Tester feedback: This activity is in charge of qualifying MR’s verdict based
on the summary report provided by the Pre-processing activity. Here the tester
needs to perform two checks when there is an incorrect and correct behaviour
of the MR Checker output:

    * a)

Incorrect behaviour: The tester evaluates whether there is an obvious fault in
the SUT. Phase I should be repeated as long the fault is present.

    * b)

Correct behaviour: In the correct behaviour there are two possibilities.

      * b.1)

MR not violated which represents a positive test.

      * b.2)

MR violated which represents a negative test.

If specific MR is violated 100% of the time, we assume that the MR does not
apply to the tested function. On the other hand, if it is not violated 100% of
the time, we assume that the MR matches the tested function. In both cases,
the tester can directly decide whether to include them in the Rule file. Those
100% violations could be used as negative tests and the 100% of no violations
as positive tests. We also look at the atypical values; for instance, if the
MR was violated or not violated only 10% of the time.

  * •

Rule mining (predefined data type relations): This activity is responsible for
generating the rule set by discovering interesting relationships between the
test data and whether or not a particular MR has been violated. This activity
has three internal steps:

    * 1)

Encoding: This step is in charge of preparing the data according to the
requirements of the rule mining algorithm. For example, Apriori [14], which is
the algorithm used in this paper, works only with categorical features. Thus,
this component categorises and generalises the numerical inputs into string
representations.

    * 2)

Rule generation: This step is responsible for generating the set of rules
using the Apriori ARM algorithm.

    * 3)

Data type relation: This step is in charge of generalising the data based on
its data type relation. This data type is predefined. For example, the test
data for SUT can be generalised using partial order theory. The partial order
defines a notion of comparison between at least two elements, e.g., inputa and
inputb. The two elements inputa and inputb can be in any of four mutually
exclusive relationships to each other:

inputa $<$ inputb

inputa = inputb

inputa $>$ inputb

inputa and inputb are incomparable

The latter relationship is not present in our data.

###  III-B Phase II

Phase II is in charge of generating the test suite for regression testing
purposes. Overall, this phase takes the Log, which has the test data generated
and takes the Log with the set of rules for generating the final test suite.

##  IV Results and Discussion

This section presents and discusses the preliminary results of our approach.
Let’s consider the Algorithm 1 as the SUT. Algorithm 1 is a program that
computes three basic arithmetic operations, addition, subtraction, and
multiplication between two integers. The full set of data generated during our
experiments, as well as all scripts, can be found in our GitHub
repo111https://github.com/aduquet/VST2023-BugORNOTbug.

Algorithm 1 Calculator()

1:procedure AddSub(int a, int b)

2: function add(a, b)

3: return a + b

4: function sub(a, b)

5: return a - b

6: function mul(a, b)

7: return a * b

###  IV-A Phase I

####  IV-A1 Test Data Generation Module

In this module, we create a fuzzer based on a random number generator. For
this, we use the NumPy random function in Python. A total of 100 random
numbers, elements of {0, 1, 2, …, 9}, were generated for inputa and inputb,
following a uniform distribution. Since, for some MRs, a constant is needed,
it was generated only once and reused every time it was needed. Figure 3 shows
the histogram of the generated test data, i.e., inputa and inputb.

Figure 3: Distribution of data generated for inputa and inputb

####  IV-A2 MT Module

  * •

Set of MRs: Table I describes the set of MRs for Algorithm 1. For our SUT, we
take advantage of the generic rules of arithmetic to build a set of four MRs
that may apply to the SUT. MR2, MR3, and MR4 need a constant $k$. That
constant was randomly generated only once and reused each time it was needed.

TABLE I: Set of MRs for Algorithm 1

MR | Change in the input | Expected output
---|---|---
MR1 | Permute the inputs | Remain equal
MR2 | Multiply by a positive constant $k$ $>1$ | Increase
MR3 | Adding a positive constant $k$ to each operand | Remain equal
MR4 | Subtracting a positive constant $k$ from each operand | Remain equal

  * •

Test data transformation Table II shows how the inputs are transformed
following the MR indications.

  * •

MR Checker: Table III shows how the MR Checker checks the outputs following
the expected output predicted by the MRs and gets the verdict, i.e., not
violated or violated for our SUT.

TABLE II: Test data transformations of the test data according with the MRs
described in Table I for Algorithm 1

MR | Input change | Test data (inputa, inputb) | transformed test data (T-inputa, T-inputb)
---|---|---|---
MR1 | Permute the inputs | †inputa = a, inputb = b | T-inputa = b, T-inputb = a
MR2 | Multiply by a positive constant $k$ $>1$ | T-inputa = a * $k$ , T-inputb = b * $k$
MR3 | Adding a positive constant $k$ to each operand | T-inputa = a + $k$ , T-inputb = b + $k$
MR4 | Subtracting a positive constant $k$ from each operand | T-inputa = a - $k$ , T-inputb = b - $k$
† a, b are elements of {0, 1, 2, …, 9}

TABLE III: MR Checker verdict example according with the expected outputs
predicted by the MRs described in Table I for Algorithm 1

MR | Expected output | Test data | transformed test data | MR Checker | Verdict
---|---|---|---|---|---
MR1 | Remain equal | †inputa = a | T-inputa = b, T-inputb = a | SomeFunc(inputa,inputb) == SomeFunc(T-inputa, T-inputb) | True: No-Violated
MR2 | Increase | T-inputa = a * $k$ , T-inputb = b * $k$ | SomeFunc(inputa,inputb) $<$ SomeFunc(T-inputa, T-inputb)
MR3 | Remain equal | †inputb = b | T-inputa = a + $k$ , T-inputb = b + $k$ | SomeFunc(inputa,inputb) $==$ SomeFunc(T-inputa, T-inputb) | False: Violated
MR4 | Remain equal | T-inputa = a - $k$ , T-inputb = b - $k$ | SomeFunc(inputa,inputb) $==$ SomeFunc(T-inputa, T-inputb)
† a, b are elements of {0, 1, 2, …, 9} |  |
SomeFunc refers to a function call of the class, i.e., ADD, SUB or MUL in Algorithm 1 |  |

TABLE IV: MR Checker output example

id | (inputa,inputb) | Func Call | MR1 | MR2 | MR3 | MR4
---|---|---|---|---|---|---
0 | (0,0) | add | ✓ | ✗ | ✗ | ✗
1 | (1,1) | sub | ✓ | ✗ | ✗ | ✗
2 | (2,1) | mul | ✓ | ✗ | ✗ | ✗
… | … | … | … | … | … | …
299 | (9,9) | add | ✓ | ✓ | ✗ | ✗
✓: Not violate, ✗: Violated |  |  |

####  IV-A3 Analyser Module

  * •

Pre-procesing: Figure 4 shows an example of the summary report for Algorithm
1, i.e., not violated or violated, with a controlled input space.

  * •

Tester feedback: Figure 4 shows the percentage of MR not violated and violated
per function call. From the first line, which belongs to the ADD function, we
can see that for MR3 and MR4, there are 100% violations. In this case, we
assume that MR3 and MR4 do not apply to the SUM function. However, we have two
options: include a test (negative test) for all test data or not include it.
on the other hand, MR1 and MR2 present 100% and 99% of not violation
respectively. After inspecting random samples to check, we can conclude that
MR1 and MR2 completely match the ADD function. This means that MR1 and 99% of
MR2 will be directly included in the set of rules to build positive tests in
phase II. The 1% violation is a particular case for MR2 in the ADD function,
which occurs whenever inputa and inputb are equal to 0.

Figure 4: Summary report for the tester feedback

In the second line of pie charts in the Figure 4, which belongs to the SUB
function, you can see the opposite behaviour of MR3 and MR4 compared to the
ADD function. For these MR we have 100% non-violations. This indicates that
the MRs fully match the SUB function. Like MR1 and MR2 in the ADD function,
MR3 and MR4 can go directly as a positive test for the SUB function in phase
II. We can’t say to much about MR1 and MR2 for SUB function. These MRs, i.e.,
MR1 and MR2, are the ones who we are interested to analyse with the rule
mining.

The results from MUL function are in the third line of the pie charts in the
Figure 4. In this function, one can see that MR1 and $MR_{3}$ behave the same
as in the ADD function, which means that MUL also fully matches MR1 and can be
included directly in the final rules. It similarly happens with MR3; it has
the same behaviour as the ADD function, meaning we can treat it in the same
way as MR3 for ADD function. The 11% of the violated cases in MUL function for
MR2 occurs whenever inputa or inputb are equal to 0. Here one could assume
that we have other particular case in the test data. It indicates that we can
use the this particular case to create a negative MR2 test for MUL. It cannot
be the same as in the ADD function since in the MUL function, these violations
occur when either inputa or inputb is 0, and in ADD function, both inputs must
be equal to zero. From the information in Figure 4 one can assume the
following:

    * a)

MR1 applies to ADD and MUL function for all the test data.

    * b)

MR2 applies to the SUB function for almost all the test data, but when inputa
== inputb == 0, MR2 must be used as a negative test.

    * c)

MR3 and MR4 does not apply to the ADD function.

    * d)

MR3 and MR4 applies to the SUB function for all the test data.

    * f)

MR3 does not apply to the MUL function.

  * •

Rule mining: We apply the Apriori algorithm with minimal support and maximum
confidence thresholds, i.e., 0.2 and 1. We created the data type relation in
the following way:

inputa $<$ inputb

inputa = inputb

inputa $>$ inputb

Table V shows the final set of detected rules. The first three rules are the
ones that were directly inferred from the Tester Feedback. The other three
rules are the output of the ARM. Table V shows that the relation a$<$b has the
largest support. This is due to the amount of samples that fall in that range.
The lower support belongs to the relation a $==$ b, meaning that not many
samples fall into that range.

TABLE V: Final set of rules

RHS | LHS | conf | sup | lift
---|---|---|---|---
(’a $==$ b $==$ 0’, ADD) | MR2 = Violated |  |  |
(’a $==$ b’, SUB) | MR2 = Not violated |  |  |
(’a $==$ 0’ or ’b $==$ 0’, MUL) | MR$2$ = Violated |  |  |
(’a $<$ b’, SUB) | MR2 = Violated | 1.0 | 0.46 | 1.639
(’a $>$ b’, SUB) | MR2 = Not violated | 1.0 | 0.32 | 2.564
(’a $==$ b’, SUB) | MR2 = Violated | 1.0 | 0.06 | 1.639
RHS: Right Hand Side, LHS: Left Hand Side |

###  IV-B Phase II

With the information assumed in the feedback tester step and the Table V, one
can create a test suite for regression testing purposes. Figure 5 shows an
example of test code for the SUB function using MR1 and the ADD function using
MR2. The full example can be found in our GitHub repository.

Figure 5: Example test suit using refined MRs

###  IV-C Remarks on effectiveness

In terms of MRs selection, our method cannot be worse than any existing method
that manually create MRs. First, our method reuses the already created MRs.
Second, our method can add more MRs by refining the existing ones with
specific test data. Regarding the inspection of the truthfulness of the test
output, i.e., whether or not the MR is violated, it is important to note that
using our approach, whatever the results of throwing data against the set of
MRs, it will always be the same situation if the MRs have been manually
created. In fact, it is part of the MT approach to inspect such results, i.e.,
whether or not the MR is violated.

The advantage of our approach is that it can provide hard facts on which MRs
out of the set of MRs can and cannot be applied. In this regard, our approach
reduces the time spent in selecting MRs, which is a manual and very time-
consuming task. The downside of our approach is the time required for setup,
the runtime of MRs against the test data, and manual inspection. However, the
execution of the MRs with the test data can be automated, and the manual
inspection is performed only once.

In terms of the effectiveness of our approach to finding defects, we face the
same problem as any testing approach. It is well known that there is an open
and old discussion about the dependency of test data and test cases. Any
approach that uses MR can only find fault with them if the test data is chosen
wisely. The proper selection of test data is planned to be explored in the
future.

###  IV-D Threats to validity

In the context of our proof-of-concept validation, two types of threats to
validity are most relevant: threats to internal and external validity.

####  IV-D1 Internal validity

We used a well-known program as a proof-of-concept and the most common ARM
algorithm to achieve internal validity. It is not fully clear in which
situations the ARM is the best choice for our method. Future research in the
direction of evaluating different ARM algorithms and feature selection needs
to be done.

####  IV-D2 External validity

With regard to external validity, our study is rather limited since we only
use one well-understood class in our experiments. Thus, the actual scope of
the effectiveness of our proposed method is yet to be determined.

####  IV-D3 Construct validity

In this paper, we used the NumPy package, in particular its random function,
to generate the test data. The usage of these third-party libraries represents
potential threats to construct validity. To avoid this, we verified that the
results produced by the random function are uniform by manually inspecting the
generated distributions.

##  V Related Work

Since MT was introduced in 1998 by [2] [2], MT has been demonstrated to be an
effective technique for testing in a variety of application domains. Several
studies have shown MT as a strong technique for testing the “non-testable
programs” where an oracle is unavailable or too difficult to implement [15,
16, 17, 18, 17]. Also, MT has been demonstrated to be an effective technique
for testing in a variety of application domains, e.g., autonomous driving [19,
20], cloud and networking systems [21, 22], bioinformatic software [23, 24],
scientific software [25]. However, the efficacy of MT heavily relies on the
specific MRs employed and its interpretation of the meaning of MR violations.

As we mentioned before, some approaches indirectly reduce the manual effort
required to interpret the meaning of an MR violation through prioritisation.
For instance, [7] [7] provides quantitative suggestions/guidance for
developing automated means of selecting/prioritising MR for cost-effective MT.
[5] [6, 5] proposed two MR prioritisation approaches to improve MT’s
efficiency and effectiveness. These approaches use (i) fault detection
information and (ii) statement/branch coverage information to prioritise MRs.
[8] [8] suggested strategies to clean MRs by deleting duplicate or redundant
MRs. These approaches offer indirect help since by prioritising or reducing
the set of MRs, the number of test cases will be reduced as well. Thus, the
manual effort of inspection through the violated MRs is less.

##  VI Conclusion and future work

We presented a new ARM-based method for refining MRs that suggest whether a
detected MR violation results from a fault in the SUT or arises from the fact
that the MR does not apply for the used test data. Our method assumes that a
predefined set of MRs is provided and uses the concepts of fuzz testing and
ARM. Our method consists of two phases. The purpose of Phase I is to evaluate
the level of applicability of the chosen set of MRs.

In phase I, there are three main modules: TDG Module, MT Module, and Analyser
Module. The TDG Module generates the test data that will be sent to the MT
Module and SUT. According to each MR’s instructions, the test data is changed
in the MT Module before being run against the SUT. In the MR Checker, the
output from running test data and the transformed test data against SUT are
compared to the changes predicted by the MRs. The test data and the MR Checker
Module’s results are then organised and saved in a Log file. The Analyser
Module uses the Log file to process and improve MRs according to relations
test data and whether or not the MR is violated.

Phase II is in charge of analysing the final set of rules and creating the new
test suite. In our proof-of-concept, we used a toy example, a program that
computes three basic arithmetic operations, addition, subtraction, and
multiplication between two integers. We show step by step the execution of our
method and its expected outputs from each module.

An advantage of our method is that it can be applied not on the SUT with only
integer inputs and outputs but on the class under test where we can have any
inputs. Also, of mixed types of data. Thus, our method can be generalised for
inputs of any type, not only for integers. It removes some limitations on the
type of SUT that can be analysed. The weakness of our method is the need for
manual feedback from the tester. However, compared with the manual effort
already needed in the MT approach, we consider that the effort needed in our
approach is less. We must manually translate the rules into assertions (test
code) to generate the final test suite. For efficiency reasons, it would be
better to have an automatic translation of the rules generated into test code.
Unfortunately, there is no simple way to do this.

Given the limitations of our study, more experiments have to be conducted to
test our proposed method empirically. We are currently focusing on extending
our experiments in three directions. First, we will add more MRs in the
initial set of MRs to test the sensitivity of our method with regard to the
filtering MRs that have no relation to the SUT. We will systematise this by
using the relation between the input type and the MR. Second, we will apply
our proposed method to more SUT. Third, we will do a mutation analysis to
evaluate the effectiveness of our approach.

## Acknowledgement

This research was partly funded by the Estonian Center of Excellence in ICT
research (EXCITE), the IT Academy Programme for ICT Research Development, the
Austrian ministries BMVIT and BMDW, the Province of Upper Austria in the frame
of the Software Competence Center Hagenberg (SCCH), and grant PRG1226 of the
Estonian Research Council.

## References

  * [1] Alejandra Duque-Torres, Dietmar Pfahl, Anastasiia Shalygina and R. Ramler  “Using Rule Mining for Automatic Test Oracle Generation”  In _8th International Workshop on Quantitative Approaches to Software Quality (QuASoQ@APSEC)_ , 2020
  * [2] Tsong Y Chen, Shing C Cheung and Shiu Ming Yiu  “Metamorphic testing: a new approach for generating next test cases”  In _Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, Tech. Rep. HKUST-CS98-01_ , 1998
  * [3] Alejandra Duque-Torres, Dietmar Pfahl, Rudolf Ramler and Claus Klammer  “A Replication Study on Predicting Metamorphic Relations at Unit Testing Level”  In _2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)_ , 2022, pp. 709–719  DOI: 10.1109/SANER53432.2022.00088
  * [4] Alejandra Duque-Torres, Dietmar Pfahl, Claus Klammer and Stefan Fischer  “Using Source Code Metrics for Predicting Metamorphic Relations at Method Level”  In _2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)_ , 2022, pp. 1147–1154  DOI: 10.1109/SANER53432.2022.00132
  * [5] Madhusudan Srinivasan and Upulee Kanewala  “Metamorphic relation prioritization for effective regression testing”  In _Software Testing, Verification and Reliability_ 32.3, 2022, pp. e1807  DOI: https://doi.org/10.1002/stvr.1807
  * [6] Madhusudan Srinivasan  “Prioritization of Metamorphic Relations Based on Test Case Execution Properties”  In _2018 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)_ , 2018, pp. 162–165  DOI: 10.1109/ISSREW.2018.000-5
  * [7] Yuxiang Cao, Zhi Quan Zhou and Tsong Yueh Chen  “On the Correlation between the Effectiveness of Metamorphic Relations and Dissimilarities of Test Case Executions”  In _2013 13th International Conference on Quality Software_ , 2013, pp. 153–162  DOI: 10.1109/QSIC.2013.43
  * [8] Bo Zhang, Hongyu Zhang, Junjie Chen, Dan Hao and Pablo Moscato  “Automatic Discovery and Cleansing of Numerical Metamorphic Relations”  In _2019 IEEE International Conference on Software Maintenance and Evolution (ICSME)_ , 2019, pp. 235–245  DOI: 10.1109/ICSME.2019.00035
  * [9] Ling Zhou and Stephen Yau  “Efficient association rule mining among both frequent and infrequent items”  In _Computers and Mathematics with Applications_ 54.6, 2007, pp. 737–749
  * [10] S.. Solanki and J.. Patel  “A Survey on Association Rule Mining”  In _2015 Fifth Int’l Conf. on Advanced Computing Communication Technologies_ , 2015, pp. 212–216
  * [11] Xiaogang Zhu, Sheng Wen, Seyit Camtepe and Yang Xiang  “Fuzzing: A Survey for Roadmap”  In _ACM Comput. Surv._ 54.11s New York, NY, USA: Association for Computing Machinery, 2022  DOI: 10.1145/3512345
  * [12] Rakesh Agrawal and Ramakrishnan Srikant  “Fast Algorithms for Mining Association Rules in Large Databases”  In _Proc. of the 20th Int’l Conf. on Very Large Data Bases_ , VLDB ’94  San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1994, pp. 487–499
  * [13] Glen McCluskey  “Efficient-apriori documentation”, 2018
  * [14] Akshita Bhandari, Ashutosh Gupta and Debasis Das  “Improvised Apriori Algorithm Using Frequent Pattern Tree for Real Time Applications in Data Mining”  In _Procedia Computer Science_ 46, 2015, pp. 644–651
  * [15] Sergio Segura, Gordon Fraser, Ana B Sanchez and Antonio Ruiz-Cortés  “A survey on metamorphic testing”  In _IEEE Transactions on software engineering_ 42.9 IEEE, 2016, pp. 805–824
  * [16] Tsong Yueh Chen, Fei-Ching Kuo, Huai Liu, Pak-Lok Poon, Dave Towey, T.. Tse and Zhi Quan Zhou  “Metamorphic Testing: A Review of Challenges and Opportunities”  In _ACM Computing Surveys_ 51.1 New York, NY, USA: Association for Computing Machinery, 2018  DOI: 10.1145/3143561
  * [17] Christian Murphy, G. Kaiser, Lifeng Hu and L. Wu  “Properties of Machine Learning Applications for Use in Metamorphic Testing”  In _In Proceedings of the 20th International Conference on Software Engineering & Knowledge Engineering (SEKE)_, 2008
  * [18] Sergio Segura, Dave Towey, Zhi Quan Zhou and Tsong Yueh Chen  “Metamorphic Testing: Testing the Untestable”  In _IEEE Software_ 37.3, 2020, pp. 46–53  DOI: 10.1109/MS.2018.2875968
  * [19] Mengshi Zhang, Yuqun Zhang, Lingming Zhang, Cong Liu and Sarfraz Khurshid  “DeepRoad: GAN-based metamorphic testing and input validation framework for autonomous driving systems”  In _33rd IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2018, pp. 132–142  IEEE
  * [20] Zhi Quan Zhou and Liqun Sun  “Metamorphic Testing of Driverless Cars”  In _Communications of the ACM_ 62.3 New York, NY, USA: Association for Computing Machinery, 2019, pp. 61–67  DOI: 10.1145/3241979
  * [21] Pablo C Canizares, Alberto Núnez, Juan Lara and Luis Llana  “MT-EA4Cloud: A methodology for testing and optimising energy-aware cloud systems”  In _Journal of Systems and Software_ 163 Elsevier, 2020, pp. 110522
  * [22] Zhirui Zhang, Dave Towey, Zhihao Ying, Yifan Zhang and Zhi Quan Zhou  “MT4NS: Metamorphic Testing for Network Scanning”  In _6th IEEE/ACM International Workshop on Metamorphic Testing (MET)_ , MET’21, 2021, pp. 17–23  DOI: 10.1109/MET52542.2021.00010
  * [23] Madhusudan Srinivasan, Morteza Pourreza Shahri, Indika Kahanda and Upulee Kanewala  “Quality Assurance of Bioinformatics Software: A Case Study of Testing a Biomedical Text Processing Tool Using Metamorphic Testing”  In _IEEE/ACM 3rd International Workshop on Metamorphic Testing (MET)_ , MET’18  Gothenburg, Sweden: Association for Computing Machinery, 2018, pp. 26–33  DOI: 10.1145/3193977.3193981
  * [24] Morteza Pourreza Shahri, Madhusudan Srinivasan, Gillian Reynolds, Diane Bimczok, Indika Kahanda and Upulee Kanewala  “Metamorphic testing for quality assurance of protein function prediction tools”  In _IEEE International Conference On Artificial Intelligence Testing (AITest)_ , 2019, pp. 140–148  IEEE
  * [25] Zedong Peng, Upulee Kanewala and Nan Niu  “Contextual Understanding and Improvement of Metamorphic Testing in Scientific Software Development”  In _15th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM)_ , 2021, pp. 1–6