Inference and Abstraction of Communication Protocols
Fides Aarts · 2009
Abstract. In this master thesis we investigate to infer models of stan-dard communication protocols using automata learning techniques. One obstacle is that automata learning has been developed for machines with relatively small alphabets and a moderate number of states, whereas communication protocols usually have huge (practically infinite) sets of messages and sets of states. We propose to overcome this obstacle by defining an abstraction mapping, which reduces the alphabets and sets of states to finite sets of manageable size. We use an existing imple-mentation of the L * algorithm for automata learning to generate ab-stract finite-state models, which are then reduced in size and converted to concrete models of the tested communication protocol by reversing the abstraction mapping. We have applied our abstraction technique by connecting the Learn-Lib library for regular inference with the protocol simulator ns-2, which provides implementations of standard protocols. By using additional re-duction steps, we succeeded in generating readable and understandable models of the SIP protocol. 1