Logo Disco

kBehavior

Logo LTA

Motivations

Several methodologies and testing techniques for both integrating and verifying the integration of component-based systems have been proposed. The effectiveness of these activities is strongly dependent from the understanding of both the system and its components. This understanding can be strengthened by using tools that automatically derive properties by observing the running systems.

Several techniques for inferring components' interaction protocols by mean of Finite State Automaton (FSA) have been already proposed. However, they often assume that rare behaviors correspond to unimportant or faulty executions. Moreover, most of existing algorithms for inferring protocols are non-incremental, therefore they require the whole set of observations to be available before they can be executed.

These assumptions can be violated in several contexts. In particular, the possible interpretations of rare behaviors are strongly dependent from the way the components are used. Moreover, non-incremental algorithms require the production of large trace files that are not acceptable in every environment.

Solution

We propose an incremental algorithm, named kBehavior, for inference of FSA from samples of components' behaviors. kBehavior explicitly represents all observations independently from their frequency. When a new behavior newb is presented, the extension of the current FSA fsa is performed by first identifying behaviors of minimal length k in newb that are already generated by subautomata of fsa. Then, fsa is suitably extended by adding branches that connect the different sub-automata in a way that the final automaton generates newb.

The Tool

An implementation of KBehavior is available for download. We provide a zipped folder containing a jar file with the implementation, a short manual in pdf format, and a folder with an example.

Download

The tool is available under the LGPL licence at the following links:

Contacts

Mauro Pezzè

Leonardo Mariani (reference contact)