kBehavior
|
kBehavior |
|
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.
A report with details of the algorithm is available from the report page of the LTA.
The Tool
An early Java prototype of the kBehavior algorithm has been developed in the Laboratory of Test and Analysis of the University of Milano Bicocca. The prototype is provided as an extension that can be manually added to the JFLAP tool (a Java package of graphical tools providing basic features related to Formal Languages and Automata Theory that has been developed at the Duke University). Installation can be performed by downloading the ZIP file by the link below and then extracting the content in a temporary folder. The extracted grammarInference and META-INF folder must be inserted in the root of the JFLAP.jar package that must be renamed to kbInference.jar. The other files must be placed in the folder that stores the kbInference.jar. The inference algorithm can be executed over the exampleTrace.txt file by executing the infer.bat file.
The prototype implementation, even if executing an incremental algorithm, works with an input trace file. A version for on-line analysis of component based systems is under development.
Download
The tool is available under the LGPL licence at the following links:
Contacts
Leonardo Mariani (reference contact)