Examples

This section will provide various examples of usage for the gemtest framework.

To see a simple implementation testing the sine function using metamorphic tests, look at the example provided in the Quick-Start Guide.

An example implementation for the sine function using the general approach can be found in the Advanced Usage section.

Registering multiple SUTs

The knapsack example demonstrates how to register multiple SUTs in the same test suite.

Defining multiple SUTs especially makes sense if:

There are multiple algorithms available to solve the same problem (such as greedy and brute force for Knapsack).

The same transformations and relations can be used for the different SUTs.

Defining the Metamorphic Relation

To test the knapsack problem, we first define the following two metamorphic relations:

add = gmt.create_metamorphic_relation(name="add", data=knapsacks)
combine = gmt.create_metamorphic_relation(
    name="combine",
    data=knapsacks,
    number_of_sources=2,
    testing_strategy=gmt.TestingStrategy.SAMPLE,
    number_of_test_cases=10
)

Defining Transformations and Relations

We then define transformations and their corresponding relations for the add and combine relations.

@gmt.transformation(add)
@gmt.randomized('items_to_add', gmt.RandInt(1, 10))
def add_items(knapsack: Knapsack, items_to_add: int):
    knapsack.add_items(items_to_add)
    return knapsack

@gmt.relation(add)
def check_add_items(source_output: int, followup_output: int):
    return source_output <= followup_output

@gmt.general_transformation(combine)
def combine_knapsacks(mtc: gmt.MetamorphicTestCase):
    knapsack1, knapsack2 = mtc.source_inputs
    combined_max_weight = knapsack1.max_weight + knapsack2.max_weight
    combined_items = knapsack1.items + knapsack2.items
    return Knapsack(max_weight=combined_max_weight, items=combined_items)

@gmt.general_relation(combine)
def check_combine_knapsacks(mtc: gmt.MetamorphicTestCase):
    return mtc.source_outputs[0] + mtc.source_outputs[1] <= mtc.followup_output

Registering the SUTs

We define the first SUT using the greedy algorithm to solve the knapsack problem.

@gmt.system_under_test(add, combine)
def test_knapsack_greedy(knapsack: Knapsack):
    max_value, _ = greedy(knapsack)
    print(f"max value {max_value}: knapsack {knapsack}")
    return max_value

Additionally, we want to test a brute-force implementation and register a second SUT as follows:

@gmt.system_under_test(add, combine)
def test_knapsack_brute_force(knapsack: Knapsack):
    max_value, selected_items = brute_force(knapsack)
    print(f"max value {max_value}: knapsack {knapsack}")
    return max_value

Warning

The brute force implementation has exponential time complexity, and it is recommended to keep the brute force implementation commented out to reduce runtimes!

Reusing Parameters

As explained in the Decorator Section of the Advanced Usage Guide, Parameters generated by @randomized and @fixed are stored in the parameters dictionary of the individual Test Cases.

In some cases, it is necessary to reuse the parameters from the transformation functions. It is also advised to do so in many cases since it creates a stronger test oracle. The following simple Sine test example, similar to the general approach example, demonstrates how to use the various parameters.

Defining Parameters in the Metamorphic Relation

We can set the parameters in a dictionary and pass them as an argument when creating the metamorphic relation.

parameters = {"random_t": [1, 2, 3]}

mr_1 = gmt.create_metamorphic_relation(name='mr_1',
                                    data=range(100),
                                    testing_strategy=gmt.TestingStrategy.EXHAUSTIVE,
                                    number_of_sources=1,
                                    parameters=parameters,
                                    number_of_test_cases=10)

Contrary to using the @randomized and @fixed decorators, setting the parameters using the dictionary will result in multiple test cases being created.

Warning

The default TestingStrategy is EXHAUSTIVE, meaning that all combinations of inputs are tested. We will test for all possible parameter permutations! See the Testing Strategy Section in the Advanced Usage Guide!

Generating Parameters using Decorators

Using @randomized and @fixed decorators will store the parameters in the same dictionary. Make sure that you use a different key name for each parameter.

@gmt.general_transformation(mr_1)
@gmt.randomized('n', gmt.RandInt(1, 10))
@gmt.fixed('c', 0)
def dummy_general_transformation(mtc: gmt.MetamorphicTestCase, n: int, c: int):
    t = mtc.parameters['random_t']
    followup = mtc.source_input + 2 * (n * t) * math.pi + c
    return followup

The parameters n and c have to be passed as arguments in the dummy_general_transformation. To use parameters set during the creation of the metamorphic relation, pass the MetamorphicTestCase object and access the parameter using mtc.parameters['paramter_name'].

Reusing the Parameters in a Relation

With all the parameters being present in the MetamorphicTestCase object, we need to pass it as an argument in the dummy_general_relation. For example, in the transformation function we access parameters using mtc.parameters.

@gmt.general_relation(mr_1)
def dummy_general_relation(mtc: gmt.MetamorphicTestCase):
    n = mtc.parameters['n']
    c = mtc.parameters['c']
    t = mtc.parameters['random_t']
    result = mtc.source_output + n*t + c == pytest.approx(mtc.followup_output + n*t + c)
    return result

MaxFlow Solver Example reusing Parameters

This section provides another example of reusing parameters for a stronger test oracle. Here, we test various MaxFlow solvers, such as the Ford-Fulkerson Algorithm.

Setting the Parameters

We first need to define a dictionary containing our specified parameters:

scalar_dict = {"scalar": [2.0, 7.0, 10.0], "fraction": [0.5, 0.75]}

Note

Usually, for metamorphic testing, we would like to randomize these parameters as well. Here, they are fixed.

Defining the Metamorphic Relation

We then define the metamorphic relations, setting the source data and the parameters as well.

scale_cap = gmt.create_metamorphic_relation(name="scale_cap", data=graphs, parameters=scalar_dict)
scale_cap_ratio = gmt.create_metamorphic_relation(name="scale_cap_ratio", data=graphs, parameters=scalar_dict)

General Transformation and Relation

The parameters can be used in the general transformation when passing the MetamorphicTestCase object as input to the transformation function. You can access the parameters using mtc.parameters['key'], where the given key matches a key defined in your parameter dictionary.

@gmt.general_transformation(scale_cap)
def scale_capacities_params(mtc: gmt.MetamorphicTestCase):
    """
    Scales the Capacities in the Capacity Matrix by the scalars
    specified in the parameters dictionary.
    """
    network_graph = mtc.source_input
    scalar = mtc.parameters["scalar"]
    return network_graph.scale_capacities_params(scalar)

@gmt.general_transformation(scale_cap_ratio)
def scale_capacities_params(mtc: gmt.MetamorphicTestCase):
    """
    Scales the Capacities in the Capacity Matrix by the scalars
    specified in the parameters dictionary.
    """
    network_graph = mtc.source_input
    scalar = mtc.parameters["fraction"]
    return network_graph.scale_capacities_params(scalar)

The corresponding general relations then expect the MetamorphicTestCase object as input as well. You can use the parameters equivalently to how you used them in the transformation.

@gmt.general_relation(scale_cap)
def flow_scaled(mtc: gmt.MetamorphicTestCase):
    """
    Verifies that the maximum flow of the follow_up output is exactly scaled by the scalar
    used for increasing the capacities.
    """
    return gmt.approximately((mtc.source_output * mtc.parameters["scalar"]), mtc.followup_output)

@gmt.general_relation(scale_cap_ratio)
def flow_fraction(mtc: gmt.MetamorphicTestCase):
    """
    Verifies that the maximum flow of the follow_up output is exactly scaled by the scalar
    used for increasing the capacities.
    """
    return gmt.approximately((mtc.source_output * mtc.parameters["fraction"]), mtc.followup_output)

Warning

The default TestingStrategy is EXHAUSTIVE, meaning that all combinations of inputs are tested. See the Testing Strategy Section in the Advanced Usage Guide!

Sorting Lists Example

This section illustrates the two options for reusing parameters, either by generating parameters using @gmt.randomized or @gmt.fixed or by using predefined dictionaries. To see the full test suite, see the sorting example in the example folder. The stable test suites use generated parameters, while the unstable test suite utilizes predefined parameters.

Generated Parameters

This section illustrates how to apply metamorphic testing to sorting algorithms. Again, we will make use of reusable parameters.

The generated lists consist of value and identifier tuples and will be sorted by their values. The identifiers serve the purpose of keeping track of the exact element that is removed.

List Generation and MR creation

For this example, we generate lists of 20 elements. The values will be random integers from 1 to 100 with identifier strings, including the elements index. We can then specify the metamorphic relation by setting the data source and giving the relation a new name.

def generate_data_with_identifiers(n=20):
    """
    Data generation function, returns a list of tuples with random integers and unique identifiers.
    """
    data = []
    for i in range(n):
        value = random.randint(1, 100)
        identifier = f"id_{i}"
        data.append((value, identifier))
    return data

# Generate a list of lists by running the data generation function 20 times
generated_data = [generate_data_with_identifiers() for _ in range(20)]

remove_element_tight = gmt.create_metamorphic_relation("remove_element_tight", data=generated_data)

Transformation Function

In the transformation function, we use the gmt.randomized decorator to sample randomly from the list indexes. We create a follow-up input by excluding the sampled index from the original source list.

@gmt.general_transformation(remove_element_tight)
@gmt.randomized("id_to_remove", gmt.RandInt(0,19))
def remove_random_element(mtc: gmt.MetamorphicTestCase, id_to_remove: int):
    """
    Removes a random element from the source input list
    """
    identifier_to_remove = f"id_{id_to_remove}"

    source_input = mtc.source_input

    modified_input = [item for item in source_input if item[1] != identifier_to_remove]

    return [modified_input]

Relation Function

The source and follow-up outputs are the sorted lists. Removing the exact same identifier from the sorted source output list should result in precisely the same array as the follow-up output.

@gmt.general_relation(remove_element_tight)
def tight_oracle_removed_element(mtc: gmt.MetamorphicTestCase):
    """
    Verifies that the element with the specified identifier gets
    removed and the output is exactly the same otherwise.
    """
    source_output = mtc.source_output
    followup_output = mtc.followup_output

    id = mtc.parameters["id_to_remove"]

    identifier_to_remove = f"id_{id}"

    modified_source_output = [item for item in source_output if item[1] != identifier_to_remove]

    return modified_source_output == followup_output

System Under Test

The systems under test are three stable sorting algorithms. The stable property of those algorithms ensures that the elements maintain their relative order even when the values are equal. This property is essential for validating the equality of our outputs in the relation function. For unstable algorithms, comparing only equality in values would be necessary.

@gmt.system_under_test()
def test_insertionSort(list):
    result = insertionSort(list)
    return result


@gmt.system_under_test()
def test_mergeSort(list):
    result = mergeSort(list)
    return result


@gmt.system_under_test()
def test_radixSort(list):
    result = radixSort(list)
    return result

Predefined Parameters

List Generation, MR creation and defining the Parameters

Again, we generate the lists as in the previous example. Additionally, we create a dictionary that holds the parameters we want to use in our transformations and relations. The dictionary needs to be passed as an argument during the creation of the metamorphic relation.

def generate_data_with_identifiers(n=20):
    """
    Data generation function, returns a list of tuples with random integers and unique identifiers.
    """
    data = []
    for i in range(n):
        value = random.randint(1, 100)
        identifier = f"id_{i}"
        data.append((value, identifier))
    return data

# Generate a list of lists by running the data generation function 20 times
generated_data = [generate_data_with_identifiers() for _ in range(20)]

parameters_dict = {
"remove_index": [f"id_{random.randint(0, 19)}"]
}

remove_element_tight = gmt.create_metamorphic_relation(
"remove_element_tight", data=generated_data, parameters=parameters_dict
)

Transformation Function

In the transformation function, we use the gmt.randomized decorator to sample randomly from the list indexes. We create a follow-up input by excluding the sampled index from the original source list.

@gmt.general_transformation(remove_element_tight)
def remove_random_element(mtc: gmt.MetamorphicTestCase,):
"""
Removes a random element from the source input list
"""
identifier_to_remove = f"id_{remove_index}"

source_input = mtc.source_input

modified_input = [item for item in source_input if item[1] != identifier_to_remove]

return [modified_input]

Relation Function

The source and follow-up outputs are the sorted lists. Removing the exact same identifier from the sorted source output list should result in the same array as the follow-up output in terms of the list values.

@gmt.general_relation(remove_element_tight)
def tight_oracle_removed_element(mtc: gmt.MetamorphicTestCase):
    """
    Verifies that the element with the specified identifier gets
    removed and the output values are the same otherwise.
    """
    source_output = mtc.source_output
    followup_output = mtc.followup_output

    id = mtc.parameters["id_to_remove"]

    identifier_to_remove = f"id_{id}"

    modified_source_values = [
        item[0] for item in source_output if item[1] != identifier_to_remove
    ]

    followup_values = [item[0] for item in followup_output]

    # Check if the values match
    return modified_source_values == followup_values

System Under Test

The systems under test are three unstable sorting algorithms. Therefore, we can not guarantee equality in the identifiers for the two lists. The relation function verifies the equality of the sorted values instead.

@gmt.system_under_test()
def test_heapSort(list):
    return heapSort(list)


@gmt.system_under_test()
def test_quickSort(list):
    return quickSort(list, 0, len(list) - 1)


@gmt.system_under_test()
def test_selectionSort(list):
    return selectionSort(list, len(list))