Kazimiras Lukoit, Norman Wilde, Scott Stowell, Tim Hennessey

This technical report may be cited as SERC-TR-86-F, Software Engineering Research Center, Purdue University, 1398 Dept. of Computer Science, West Lafayette, IN 47906, February 2000.

1. Introduction

One of the more difficult problems for the maintainer of unfamiliar software is the location of the code that needs to be understood and changed. While in principle a maintainer should understand the entire system before making changes, in practice it is essential to use an "as-needed" strategy [KOEN.91]. The maintainer must first locate the code components that are needed for the specific change and then understand how they function in the context of the larger system.

Location is more difficult because it often involves contrasting views of the system. A programmer sees software as a collection of interacting components: source files, subroutines, data objects, lines of code, etc. However the end user sees the system as a provider of many different features. The features of a word processor, for example, might include loading files, cutting and pasting text, spell checking, etc. Program change requests are often given in terms of the features to be changed, which may not map clearly onto the code. Requirements traceability documentation should provide this mapping, but it is costly to keep up to date and thus is rarely present in maintenance situations.

One technique that has been developed to help locate features in code is Software Reconnaissance [WILD.95]. Software Reconnaissance is based on a comparison of traces from different test cases. The target program is instrumented to produce a trace of components executed as each test is run. Then test cases are run, some "with" and some "without" the desired feature. For example to locate the spell checker of a word processor, the programmer would run several tests that include a spell check and several others that do not. The "marker" components for the spell check feature are found by taking the set of components executed in the "with" tests and subtracting the set of components executed in the "without" tests.

Software Reconnaissance has been tried in case studies on a number of systems of different sizes, both in an academic setting and in industry [WILD.96, AGRA.98]. Results have generally been quite favorable:

1. The marker components are generally only a small fraction of the target program, and so help the maintainer to focus quickly on code that is likely to be important for the desired feature.
2. While the marker components are by no means all the code that the maintainer needs to study, they usually are close to the needed code and so provide good "places to start looking" for the as-needed strategy.
3. Generally only a few test cases are needed if they are well chosen. It is important to make the test cases "with" the feature as similar as possible to the test cases "without" the feature to avoid accidentally including irrelevant components in the trace.
4. The technique often provides insights into the target program that are surprising, even to programmers who have considerable experience with it.

Tools for Software Reconnaissance are now available, including the freeware Recon2 tool from the University of West Florida (http://www.cs.uwf.edu/~wilde/recon) and commercial testing and program comprehension tools such as cSudsÔ from Telcordia (http://xsuds.com).

However these case studies have also revealed problems with the usability of the Software Reconnaissance technique as currently implemented. A maintainer using the technique goes through a cycle such as the one shown in Figure 1. The maintainer has to switch back and forth between running tests, keeping track of trace files, setting up the analysis program so that it will know which traces exhibit each feature, and running the analysis program. While this process may be marginally adequate for batch programs, it is particularly awkward for long running or interactive programs such as a word processor or a web server. It takes considerable time to start up and terminate each test case, so the test-analyze cycle is quite time consuming.

Our conversations with practicing software engineers have clearly established that ease of use is an indispensable quality for program comprehension tools. Maintainers working under time pressure will fall back on easy to use text search tools such as grep unless more precise methods are made equally user friendly. Accordingly we have been developing a visually oriented feature location tool called TraceGraph that combines two concepts:

Just as an engineer uses an oscilloscope to see how a circuit responds to different inputs, a maintainer will be able to use TraceGraph to view how the program responds to different actions. TraceGraph will provide immediacy, with a rapid visual response to the maintainer's operations. TraceGraph also takes advantage of the human's ability to distinguish texture in images. It is easy for the eye to pick out a change in the execution of a component, even if it is represented only by a color change in a few pixels.

To explore the usability of the TraceGraph concept on real software, we have tested a user interface prototype in case studies of two, very different, large systems. The studies were not done in "real-time" since we needed to experiment with different colors and parameters in the TraceGraph display. Instead, a sequence of trace files was generated and stored for each target system. TraceGraph then read these files in order and painted out the display as if they were being generated in real-time. The results of these case studies are described in the next sections.

The first case study was intended to evaluate if TraceGraph could provide insight into features of a large real-time system. The study used trace data from the Joint Surveillance Target Attack Radar Subsystem (Joint STARS) developed by Northrop Grumman for the United States Department of Defense.

Joint STARS is an airborne targeting and battle management system which includes an EC-8 aircraft, a multi-mode radar system, mobile ground station modules, voice and data communications, control computers and workstations and a self-defense suite. The version of the Joint STARS software used in this study consisted of 7692 units totaling 363 K lines of code and divided into 233 processes running on a variable number of processors. The processes communicate by message passing.

In systems such as Joint STARS, understanding the process interactions is vital for understanding overall system design. In a previous study, we had used a variant of the Software Reconnaissance technique to recover design threads, data flow diagrams showing how the processes interact for a particular system feature [WILD.98]. That study used traces of inter-process messages collected in the Joint STARS test bed, which is a mockup of the interior of the EC-8 aircraft. Three test runs were made, each including tests of five Joint STARS features plus periods of system idle time. The start and stop times for each feature were noted. The result was approximately 8.2 M bytes of message trace data with 67,605 messages representing about 30 minutes of system operation.

We used part of this same message trace data for the TraceGraph case study. The trace was broken up into segments corresponding to about 5 seconds of Joint STARS execution. Each of these trace segments generated one vertical column on the TraceGraph display of Figure 3. Each horizontal row of rectangles represents a distinct message between two processes. As previously described, a rectangle is black the first time the message occurred, grey for each subsequent occurrence, and blank if the message did not occur.

Figure 3 shows a TraceGraph display covering two features of Joint STARS. Feature A is quite brief and executed completely within the 5 second period of column 9. The new messages are clearly visible as the black rectangles in that column. Feature B runs more slowly and its execution is spread across columns 15 to 23. Again, some new messages are shown by black rectangles while other gray rectangles represent messages that might be part of the feature or part of background processing.

The TraceGraph display seems to be effective for feature location in Joint STARS. It clearly identifies some messages that need to be investigated (the black rectangles) since they do not appear until the feature was executed. The maintainer can also visually identify other potentially interesting messages which cluster in the time period of the feature, even though they are sometimes executed at other times. Finally, the maintainer may also quickly eliminate many other methods that occur all the time.

The TraceGraph display also allows quick insight into other aspects of Joint STARS messaging. Many messages are periodic, and occur at a fixed interval. These provide the regular patterns across the screen which can be seen in Figure 3. The display provides a quick feel for the system's background periodic processing.

Note that the TraceGraph display allows the human eye to replace the Software Reconnaissance set difference operation to locate a feature. The differences between components executed "with" and "without" the feature can be easily distinguished by the pattern of the rectangles. The eye can also identify more complicated patterns, such as the periodic messages.

The second case study evaluated the usability of the TraceGraph display on a more detailed trace of each decision point in the code. In earlier studies we have found that detailed traces are often needed to locate features in old code since higher-level traces, can lose too much information [WILD.92]. Unfortunately, low level traces may be very large, so display techniques need to be carefully chosen.

The target system used was NCSA Mosaic, which is famous as one of the first web browsers to be widely distributed and used. Source code for the X Windows version is publicly available from www.ncsa.uiuc.edu and has been used in other case studies of program comprehension techniques (e.g. [JERD.97, CHEN.00]). The version we studied consisted of approximately 86 K lines of C code.

Mosaic was instrumented at the decision level using the Recon2 instrumentor, so that a trace record was generated each time the program executed a branch statement such as an "if" or a "while". The initial trace files were very large, over 94 MB of trace being generated just during Mosaic start up. However most of the trace records were duplicates generated by just a few inner loops. Recon2 functions to suspend and resume tracing were inserted at 11 points, thus reducing the trace file to just over 36 MB, which proved to be manageable when chopped into 5 second chunks for the display. One of the lessons for future versions of TraceGraph is that the maintainer should be provided with convenient facilities for eliminating tracing of such tight loops.

Figure 4 shows how TraceGraph displays the detailed traces from Mosaic. As can be seen from the size of the scroll bar, only a fraction of the trace is visible at once since there are many more components (rows) in a detailed trace. (Compare to the scroll bar of Figure 3.) However the newly executed components (black rectangles) are very easy to see so the maintainer can quickly scroll up or down to find them.

The display of Figure 4 shows TraceGraph when trying to locate the Mosaic feature "display a GIF image". Up to column 13 we have the traces for starting up Mosaic and navigating to a web page that has no images. Then at column 14 the maintainer has entered the URL for a page that does contain a GIF. The black rectangles show the code executed for the first time at that point.

To help in analysis, the maintainer can mouse on any of the rectangles to get a more detailed pop-up display as shown in Figure 5. (The selected rectangle is white in Figure 4). The pop-up display shows the actual records from the trace file. As can be seen the selected rectangle corresponds to taking the False branch of a decision on line 2820 of source file HTMLformat.c. A look at the code shows that that line is in a function called ImagePlace which, as its name indicates, draws an image on the page. This would clearly be one of the functions a maintainer would need to study to understand the "display a GIF image" feature. TraceGraph seems to be effective in locating important code for a feature relatively quickly, even for very large and detailed traces.

The literature on software visualization is now quite large, ranging from graphic techniques for animating algorithms as a teaching tool to systems for visualizing performance bottlenecks in large commercial programs. A good survey and taxonomy of the field is given by Price, Baecker and Small [PRIC.98]. In their classification, TraceGraph would probably be categorized as a General/Scalable system providing a Graphical view of Control Flow. (Unfortunately it would also be classified as Intrusive, since the production of a trace almost always has some impact on system performance.)

Pixel level displays, such as those used in TraceGraph, have been proposed in several software visualization systems, notably by Ball and Eick to visualize code statistics or the changes in a system between one version and another [BALL.96].

Numerous tools have been proposed for visualizing software to aid maintainers. Most such tools use static analysis, which parses the code and displays software structure without execution, for example [RAJL.88, CLEV.89, LINO.94]. A few more recent tools also use dynamic analysis for program comprehension. For example De Pauw, Kimelman and Vlissides describe a dynamic system for understanding object-oriented software that allows, among other things, visualization of inter-class calls and tracking of the number and parameters of object instances [DEPA.94].

One very interesting recent tool is ISVis by Jerding and Rugaber [JERD.97]. This tool provides visualizations using both static and dynamic analysis. After extraction of static information, such as a call graph and symbol table, the target system is instrumented and executed through several user defined scenarios to generate event traces, which are read into ISVis for analysis. ISVis allows for the definition of "actor" code components and for displays of the interaction events between actors. Jerding and Rugaber show how they have applied ISVis to the problem of locating where to insert a modification into a large system.

There are few other papers that address explicitly the problem of using visualization tools to locate the needed code for "as-needed" program comprehension. The general assumption seems to be that the maintainer will be able to identify some starting point, such as a variable or subroutine, and that the visualization tools will then let him or her navigate to the rest of the code that needs to be understood. This may not be a bad assumption in some cases. A maintainer will often have some prior knowledge about the program that can provide a starting point or, in the worst case, he or she can start at the main program and work down, a strategy that has been formalized by Chen and Rajlich [CHEN.00]. However prior knowledge may not be available, and top down exploration can be very time consuming, especially in poorly written code.

The main advantage of TraceGraph is that it should provide convenient answers to one specific problem: finding quick starting points for locating features in large, unfamiliar systems. Our experience with the similar Software Reconnaissance technique shows that it may also often provide insights and starting points that are unexpected, even for maintainers who are familiar with the target program.

Software maintainers are notoriously short of time to carry out the many tasks required to keep modern software in service. TraceGraph is intended to make it faster for them to locate code in large, long-running programs that need to be modified. The tool takes advantage of the human eye's ability to identify patterns in large amounts of information presented graphically. It also emphasizes quick feedback so that the maintainer can try different program inputs and get an immediate picture showing the target program's response.

We believe that the two case studies indicate that displays like TraceGraph can provide an effective means of locating features in programs, and that the results should be comparable with those of the slower Software Reconnaissance approach. The technique should be usable on a wide variety of traces produced by many different tools. Displays of this kind are good candidates to be included in software monitoring and debugging tools.

It is important to note the limitations that TraceGraph shares with Software Reconnaissance. First, it may only be used to locate features which the program's user can control. Most programs contain a significant amount of common code that is always executed on every non-trivial test. While a maintainer may need to locate some specific part of this common code, such as the symbol table handler in a compiler, neither TraceGraph nor Software Reconnaissance can help. Second, as for any dynamic analysis technique, the results depend to some extent on the test cases used. If a feature is sometimes handled one way and sometimes another, neither technique will find all of it unless the maintainer supplies inputs that cover both cases. On the other hand, both techniques will identify unwanted code components if the "with" tests accidentally include functionality that is absent in the "without" cases. Finally, both techniques only provide starting points for the exploration of code. The maintainer still needs to do the hard work of studying each identified component and understanding how it fits into the rest of the target system. Other analysis tools, such as those mentioned in the previous section, may then be very useful.

The current version of TraceGraph is still an early user interface prototype, but we plan to include a more finished tool as part of the Recon3 system currently under development.