Grammatical Inference of Interobject Protocols

Problem

Understanding someone else's program is difficult. And if that program is written in an object-oriented language, dynamic message binding makes things even worse. Traditionally, most program understanding tools rely on static analysis of a program's source code to aid understanding. This research mini-project suggests another tack-use dynamic analysis of the program's execution trace. In particular, we would like to use execution traces to determine how the instances of the program's object classes communicate with each other-their interobject protocols.

Background

This project uses the ideas of grammatical inferencing to attack the problem. Grammatical inferencing is an active research area in machine learning. The idea is to try and infer a grammar from a sample of the strings in the grammar. Many interesting approaches have been taken to this problem including neural networks, genetic algorithms, and hidden Markov models.

Two tools are available for use by project participants. The first is ISVis, a program analysis tool that uses both static and dynamic analysis techniques to understand programs. ISVis was developed at Georgia Tech and is distributed publically as part of the Esprit de Corp Suite of tools from the MORALE project. The other tool is Balboa from the Universities of Colorado and New Mexico State. Balboa specifically uses grammatical inferencing to generate state machine (regular language) descriptions of event traces.

Deliverables

A 2500-word report (about 5 pages). Longer is OK, but not necessary. Address the following items:

• Use of ISVis to perform a preliminary architectural analysis of a moderate-sized software system.
• Use of Balboa on a variety of execution traces to infer state machines.
• Analysis of the effectiveness of this approach on understanding the software system.

Evaluation

Evaluation is based on the quality of your report.