Generating Models of Communication Protocols from Test Data using Abstraction Techniques
Fides Aarts & Johan Uijen
Uppsala University and Radboud University, Nijmegen.
- Date and Time
Thursday, August 20th , 2009 at 13.30
Model-based techniques for verification and validation of communication
software require a model of the system under test (SUT), as a reference for
its intended behavior. However, in practice many such software systems lack
such a correct model. We consider the problem of generating a model of
communication protocols by observing its external behavior when interacting
with its environment. This approach is useful, e.g., when source code is not
available, in regression testing, etc.
In this master thesis we consider the problem of using automata learning
techniques to infer models of entities of standard communication protocols.
One obstacle is that automata learning has been developed for automata with
finite alphabets and a moderate number of states, whereas practical
communication protocols have huge (practically infinite) sets of
messages and sets of states. We propose to overcome this obstacle by requiring the
user of our technique to supply an abstraction mapping which reduces that
alphabets and sets of states to finite sets of manageable size. We
use an existing implementation of the L* algorithm for automata learning
to generate abstract finite-state models, which are then converted to
models of the tested communication protocol by reversing the abstraction
We have implemented our abstraction technique by connecting the LearnLib
implementation of the L* algorithm, and the ns-2 tool for protocol
We have used it to generate models of entities in the ns-2 implementation of
the SIP and TCP protocols.