Can different learning runs of the same SUL end with different number of queries and steps even though I set a seed for reproducibility?

[andreastedile]

In my learning setup I fix a seed to ensure reproducible results, but they end with different values of Membership Queries, MQ Saved by Caching and Steps.

For example:

Experiment 1 oscillates between:

Learning Algorithm
 # Membership Queries  : 84
 # MQ Saved by Caching : 25
 # Steps               : 315
Equivalence Query
 # Membership Queries  : 380
 # Steps               : 1706

and:

Learning Algorithm
Learning Algorithm
 # Membership Queries  : 83
 # MQ Saved by Caching : 26
 # Steps               : 311
Equivalence Query
 # Membership Queries  : 380
 # Steps               : 1706

Experiment 2:

Learning Algorithm
 # Membership Queries  : 825
 # MQ Saved by Caching : 243
 # Steps               : 5167
Equivalence Query
 # Membership Queries  : 15862
 # Steps               : 109070

Learning Algorithm
 # Membership Queries  : 825
 # MQ Saved by Caching : 243
 # Steps               : 5187
Equivalence Query
 # Membership Queries  : 15862
 # Steps               : 109071

Learning Algorithm
 # Membership Queries  : 823
 # MQ Saved by Caching : 244
 # Steps               : 5177
Equivalence Query
 # Membership Queries  : 15862
 # Steps               : 109070

Learning Algorithm
 # Membership Queries  : 823
 # MQ Saved by Caching : 244
 # Steps               : 5157
Equivalence Query
 # Membership Queries  : 15862
 # Steps               : 109069

and others.

[mtappler]

It could happen due to hashing in Python. Did you set PYTHONHASHSEED (https://docs.python.org/3.4/using/cmdline.html#envvar-PYTHONHASHSEED)?

[andreastedile]

@mtappler Interesting take: I did not know about that. Unfortunately, it does not fix the issue.

[andreastedile]

It could be relevant to point out that the inputs to my SUL are custom objects that do not override __hash__.

[emuskardin]

All inputs should be hashable, and if they are not at least L* would break, not sure at the top of my head about the other algs.

[andreastedile]

I noticed that this happens with L# but not L* (run_Lsharp, run_Lstar).
Let me take some time to debug further.

[emuskardin]

In general you are discuraged in using that oracle, as it does not work with larger models, or if the actual model has more states than what you estimate. RandomW is usually considered one of the best w.r.t. the tradeoff between formal guarantees and practical feasibility.

Also if your models are big, then number of test cases explodes.

[andreastedile]

What if the number of states I estimated is correct and I can tolerate high times? I thought that WMethod provided good guarantees in this case.

[emuskardin]

Then there are no downsides, as long as the estimated number of states is low enough/or as you sid you can tolerate long learning times.

From experience, I am always wary of estimating max number of states manually, as implementation more often than not does not follow the specification, and interesting bugs/behaviour might be found only in cases where you test bit more. Eg. when a colleague of mine did her study on learning models from various Bluetooth implementations that all implement the same protocol, so should result in the same model, but they did not.

Eg. you have some protocol that should have 5 states.
You use W-Method, you get 5 states.

Maybe that is all there is to it.
But maybe the specific implementation reveals a bug only after doing 20 steps in some semi-random way, and then all of the sudden the learned model would not have 5 states, but maybe 15. In this case W-Method would be weaker than such oracle, e.g RandomWMethod, as your assumption about the max number of states was wrong.

Or you can just do both, do WMethod first, and then properly parameterized RandomW, and see if there is any differance.

[andreastedile]

When you say "as it does not work with larger models", are you referring to intractable computational complexity, or to another type limitation that I am not aware of?

[emuskardin]

It is just computational expensive/close to infeasible, as well as it will not search for any counterexamples longer than needed to verify the 'max_states'.

So iff your assumption of maximum number of states is wrong, then the resulting model will not necessarily capture the whole behaviour. While faster oracles like RandomW do not provide formal guarantees, but learn the more accurate model due to easier assumptions put on them.

So the decision is: do you want a "formally correct model" that might not actually conform to the ground truth, then use W method. If you want a model that offers limited/no guarantees, but has a high probability of matchin the ground truth: RandomW.

In my biased view, formal correctnes gains which W-Method provides offers no practical advantage when it comes to learning of real world implementations that are error prone/potentially buggy. It can even lead to less accurate model due to wrong assumptions about the maximum number of states.

In ideal world things would be different, but the world of software engineering is anything but ideal. :)

[emuskardin]

I think I have fixed. @mtappler @andreastedile

The issue might have been that oracles that use compute_characterization_set might break reproducibility due to that function doing some set-to-list conversion, which introduces randomness.

Let me know if the issue is resolved or if it persists.

You can update AALpy by deleting it and running:

pip install https://github.com/DES-Lab/AALpy/archive/master.zip

[andreastedile]

I have done a few runs and it is seems that I get consistent values!
Thanks.

[andreastedile]

Minimal reproducible example:

I have stripped the code down and obtained this:
https://github.com/andreastedile/pkcs11-learning/blob/master/tests/mock.py
which is completely equivalent to
https://github.com/andreastedile/pkcs11-learning/blob/master/learning/learn_wrap_and_decrypt_des_ecb.py
as they output the same traces.

PYTHONHASHSEED=1 python tests/mock.py

values are always the same: great!

PYTHONHASHSEED=1 python learning/learn_wrap_and_decrypt_des_ecb.py --so /usr/local/lib/opencryptoki/libopencryptoki.so --slot 3 --pin 1234 --name opencryptoki

values change over time...

Perhaps this has something to do with the interaction with PyKCS11, but will require more investigation.

[andreastedile]

So far fixed by 92ec71c