Arbitrary order of tests in WMethodEqOracle

[icezyclon]

Problem:
Experiments using the same initial conditions may not be reproducible due to different order of test_set in WMethodEqOracle.

Explanation:
In find_cex of the WMethodEqOracle class, the test_set is generated from iterating over sets.
The order of theses sets, especially transition_cover is arbitrary and may not have the same order - and in turn the same iteration sequence - every time. (It depends on implementation details).
This in turn, influences the order of elements in test_set and finally, when shuffle or sort(key=len,...) is called, the order may be different which will change the order of resulting cex and the trace of the experiment.

Solution:
I propose sorting the test_set first according to elements in the alphabet and only then shuffling or sorting respectively.
This should work because the Python sort is stable, aka. it will keep the order of elements of equal lengths for the second sort.
This will also allow the seeding of shuffle to always produce the same order (this is not the case at the moment).

        test_set = []
        for seq in product(transition_cover, middle, hypothesis.characterization_set):
            inp_seq = tuple([i for sub in seq for i in sub])
            if inp_seq not in self.cache:
                test_set.append(inp_seq)

        test_set.sort()  # sort sequences first, then shuffle or sort by len will be deterministic
        if self.shuffle:
            shuffle(test_set)
        else:
            test_set.sort(key=len, reverse=True)

Time complexity:
shuffle: O(n)
sort: O(n * log(n))

An additional sort will add O(n * log(n)) complexity to the given operation:
sort + shuffle: O(n * log(n)) + O(n) = O(n * log(n))
2 * sort: 2 * O(n * log(n)) = O(n * log(n))

Time complexity of shuffle will be increased by a factory of log(n) while the complexity in the case of shuffle = False will not change.

Downside:
This solution will require that letters in alphabet are comparable via < and <=.
The first sort will require, that letters are compared to each other to order them relative to each other.
This could be an edge case if letters in alphabet are custom classes (instead of letters or numbers) which would then require a custom equality operator. If such an equality operator does not exist, this would raise a TypeError.
This requirement does not exist at the moment, because the sort by length does not require direct comparison of letters.

[emuskardin]

Thank you for pointing that out, great catch.

I will think of a solution next week. Then again, this was an additional feature (as all test cases will be executed anyway, just in different order). Than you for the proposed solution, but introducing possible TypeError's is something that bothers me, as it would hinder average user experience. W-Method could use a redesign anyway to make it more efficient, so when that gets on my list I will ensure reproducibility.

Edi

[icezyclon]

No problem. I am using my own WMethodOracle at the moment, so it isn't really urgent.
I haven't tried the other oracles yet, but this problem (with the arbitrary order of set elements) could also prevent reproducibility in other oracle types...
It might be prudent to at least check the other oracles and if seeding them actually ensures the exact same order of operations 👍

[emuskardin]

Hi,
the solution was way simpler than expected. In the end it was a simple oversight, when creating 'transition_cover' I created a set. By simply creating a list, determinism is ensured as iterating over a list is constant.

Thanks again,
Edi