LearnLib/learnlib

Inferring a Parameterized State Machine

bazali opened this issue · 8 comments

bazali commented

Hello Everyone!
I am newcomer in the field of Automata Learning. I am not sure whether its an appropriate forum to put such kind of query at this forum. Please guide me if there is a separate forum/research group/blog regarding queries of Model Learning/regular inference.
My question is very simple and as:
In Learnlib there is Implementation of Angluin's Algo and it is explained with an example. Then Nise modify it for Mealy Machine and its Implementation and running example is also available in Learnlib.

Is there any Implementation (in learnlib) of algorithm with running example/running project for inferring a pararmeterized system like communication protocol?

I am a newcomer and need your guidance please. Any link for a running example for it?

mtf90 commented

Dear @bazali,

what is your understanding of a 'parameterized system'? Do you want to model parameters in input words? For example, upon sending a packet with id 'x', the system should acknowledge the retrieval of the paket with id 'x' (just like in network portocols)?

Depending on how you model input words and their responses, this may already be possible with mealy machines. The Mapper interface allows you to define arbitrary transformations between 'abstract' input symbols (which will be used by the learning algorithm) and 'concrete' input symbols (which will be executed on the system under learning). So you could define a "correct acknowledgement" symbol, which will only be returned by the mapper, if the IDs of the packets actually match.

If you are interested in true parameter support, I would suggest having a look at register automata. There is also RALib (code at bitbucket) -- an extension of Learnlib -- that deals with modeling and learning register automata. (A little advertising: we are planning to reintegrate the work of RALib into the main Learnlib. However, the people behind this work are quite busy, so there is no concrete estimate when this will happen).

bazali commented

Yes, I am talking about the system like communication protocols. Thanks for your reply and valuable suggestion. It will help me alot. Further, Is there any running example/project available in Learnlib that used Mapper for transformation (abstract into concrete and vice versa)....? I want to understand the working of Mapper with a running example. Any running example as a Case Study available? Please.

mtf90 commented

We currently don't have an example specifically targeting the usage of Mappers. However, there exist some utility classes (e.g. MappedSUL, TestDriver) that utilize mappers and should demonstrate their basic usage. You may also find the wiki page helpful.

Previously the Mapper interface was mainly used in conjunction with SULs, which is why you will find a lot of occurrences in the corresponding maven modules. We recently split the old interface to a new, simpler Mapper interface and a SULMapper interface, which covers the SUL-specific semantics (exceptions, etc.)

If you still have questions regarding mappers, I can also create a small gist that explicitly demonstrates mapping for a concrete oracle.

bazali commented

Thanks for your valuable suggestions.
If you create a small gist that demonstrates mapping for a concrete oracle then i shall be grateful to you.
No hurry....take your time......
Thank you......

mtf90 commented

I uploaded an example for transforming input/ouput sequences here. You should be able to run this example, if you copy the class somewhere in the learnlib-examples module, where the other examples are. However, you'll need to add the following dependency to the pom.xml of the learnlib-examples module, because I used an example SUL from this module.

<dependency>
    <groupId>de.learnlib.testsupport</groupId>
    <artifactId>learnlib-learning-examples</artifactId>
    <scope>compile</scope>
</dependency>

While creating the example, I realized, that mappers alone are probably not sufficient enough for your task. In general, mappers are expected to be stateless and are currently used in this fashion throughout the learnlib. It is the combination of a specialized membership oracle and mapper (or just the membership oracle, if you want to put everything there) that allows to correctly handle the state of the SUL when transforming queries.

I added some JavaDoc for hinting you, where you could pick these ideas up, to handle network comminucation. However, keep in mind that this approach uses abstraction to capture a non regular property in a regular model, so it may sometimes feel unnatural. You should definitely also consider more complex models (such as register automata) where your required behaviour can be expressed more naturally.

bazali commented

Thank you so much. Your detailed mail help me alot now. I shall bring into your knowledge in case of any difficulty.
Once again thanks for your cooperation...........Issue Closed :)
Ali

mtf90 commented

Reagarding your questions:

  • From the top of my head, I don't know about any specific work of learning network protocols. However, a quick Google search on e.g. "tcp mealy abstraction" yielded three theses from Radboud University, which (at least from the titles) sound like they just suite your need (1, 2, 3). For a more general approach to abstraction (e.g. how to handle infinite domains such as numbers), I can suggest the work of Falk, Maik and Malte. (4, 5).

  • The gist link should work fine. To me, the error message "connection timed out" indicates some technical problems on the server-side. If something was wrong with the gist (or the URL) it would more likely be something like "file not found", etc. While visiting the URL, I noticed that github tries to automatically authenticate me with their OAuth mechanism. Maybe this is the culprit for you. Since this is a public gist, you could try to logout of github and visit the link again.

bazali commented