Uppsala University Department of Information Technology

Technical Report 2008-024

Regular Inference for Communication Protocol Entities

Therese Bohlin and Bengt Jonsson

September 2008

Abstract:
Existing algorithms for regular inference (aka automata learning) allows to infer a finite state machine model of a system under test (SUT) by observing the output that the SUT produces in response to selected sequences of input. In this paper we present an approach using regular inference to construct models of communication protocol entities. Entities of communication protocols typically take input messages in the format of a protocol data unit (PDU) type together with a number of parameters and produce output of the same format. We assume that parameters from input can be stored in state variables of communication protocols for later use. A model of a communication protocol is usually structured into control states. Our goal is to infer symbolic extended finite state machine models of communication protocol entities with control states in the model that are similar to the control states in the communication protocol. In our approach, we first apply an existing regular inference algorithm to a communication protocol entity to generate a finite state machine model of the entity. Thereafter we fold the generated model into a symbolic extended finite state machine model with locations and state variables. We have applied parts of our approach to an executable specification of the Mobile Arts Advanced Mobile Location Center (A-MLC) protocol and evaluated the results.

Available as PDF (169 kB, no cover)

Download BibTeX entry.



Uppsala Universitet