Dynamic analysis is based on collecting data as the program runs. However, raw traces tend to be too voluminous and too unstructured to be used directly for visualization and understanding. We address this problem in two phases: the first phase selects subsets of the data and then compacts it, while the second phase encodes the data in an attempt to infer its structure. Our major compaction/selection techniques include gprof-style N-depth call sequences, selection based on class, compaction based on time intervals, and encoding the whole execution as a directed acyclic graph. Our structure inference techniques include run-length encoding, contextfree grammar encoding, and the building of finite state automata. KEY WORDS Software understand, Program tracing, Dynamic program analysis Software understanding requires inferring the behavior of software systems. Static techniques do this by analyzing the program's code, while dynamic techniques are based on running the program, coll_ecting data as it runs, and then analyzing the resultant data. In the dynamic case, there are inherent tradeoffs concerning the amount of collected data, the types of analyses that can be performed on them, and the overhead of collection. We regard frameworks suitable for dynamic analysis as having three parts. The bottom layer, closest to the program, is a suite of tools for gathering information as a program executes. The middle layer selects relevant portions of the data, which it later compacts and analyzes, effectively building a model of it. The top layer, closest to the user, displays these models. We are in the process of building such a framework. The first part is described in [ 171, but we also briefly review it in section 2. The bulk of this paper discusses our 0-7695-1050-7/01 $10.00 0 2001 IEEE middle layer tools. We envision the top layer as having at least the capabilities of our previous tools [ 151, but with enhanced abilities for specifying meaningful visualizations "on demand", as the task arises. The purpose of the middle layer is to build models of the collected data. There are two reasons to build a model: first, it is impossible to visualize the raw data, because of the volume and complexity of it, and $econd, a model can be used to automatically check properties of the traces. We want our models to be useful in at least the following tasks: Summarizing parts of a program execution. Such summaries would allow us to show the execution at multiple levels of detail, helping the user to navigate through it. 0 Modeling class behavior. We can track the outside calls to methods invoked on all objects of a specific class. If we have a suite of programs that use the class correctly, we can use the abstractions generated by the execution analysis as a model of how the class should be used. 0 Modeling library usage. We can view a whole library as an object and track all external calls to it. This would allow us to build a model of correct library usage and test future users of the library against the model. Detecting unusual events. After we have a model for the program behavior, we should be able to find events that do not conform to that model. Such events are often significant in that they represent exceptional conditions. For example, if a program executes one sequence of synchronization steps almost all the time, but occasionally executes an alternate sequence, this denotes a potential problem. 0 Checking against existing models. If we already have a model of aspects of the behavior of a system, say, from the specifications process, then we should be able to efficiently check whether the model produced by the traces is conforming to the original one. We also see here the opportunity of building models of design patterns and then verifying that a program implements them correctly. This is especially useful for behavioral patterns [8], which are hard to specify otherwise [16]. 221
A comparable technique is described in REF .
Encoding program executions
Proceedings of the 23rd International Conference on Software Engineering. ICSE 2001
Proceedings of the 23rd International Conference on Software Engineering. ICSE 2001
Computer Science