Chapter 4 Software Reconnaissance
A Ph.D. Thesis by Andrew Le Gear
[Back to Home Page] [Previous Chapter] [Next Chapter]
“What is the difference between exploring and being lost?.”
-Dan Eldon, photojournalist.
Figure 4.1: Identifying Features from Running Systems.
Software Reconnaissance (The dynamic search method is another name for the technique (Rajlich and Wilde, 2002).) is a dynamic analysis technique, that, through the acquisition of coverage profiles (Ball, 1999), yielded by exercising carefully selected test cases on instrumented code (see section 4.2.1), allows mappings to be created (see sections 4.1) between program features and the software elements that implement them (Wilde and Scully, 1995). Figure 4.1 illustrates how Software Reconnaissance works at an abstract level.
The term program feature is understood as being a realised functional requirement that produces an observable result of value to the user (Eisenbarth, Koschke and Simon, 2001; Eisenbarth et al., 2003; Eisenbarth, Kosche and Simon, 2001). The software elements (In Norman Wilde’s seminal papers on Software Reconnaissance (Wilde et al., 1992; Wilde and Scully, 1995), he repeatedly refers to components. However, due to the potential confusion between this definition and the modern concept of components described in section 2.1, the term software elements is used in this thesis.), to which the features are mapped vary in granularity, depending upon the level of instrumentation, and may be branches of the decision tree (Wilde and Scully, 1995), individual statements (Wong et al., 1999) or procedures (Eisenbarth et al., 2003). The appropriate choice of granularity depends upon the context of use.
The mappings created between program features and code during Software Reconnaissance create a functionality view of software. Described more formally (Wilde et al., 1992), given a set of potentially overlapping functionalities (Feature and functionality are used interchangeably),
FUNCS ={f1, f2, ... , fN}
and a set of source elements,
ELEMS ={e1, e2, ... , eN}
it should be possible to construct an implements relation, IMPL, over FUNCS X ELEMS, revealing what functionalities are implemented by what source elements. The link that allows us to construct a relation, is the test case, since a test case Ti represents an execution scenario that may exhibit one or more functionalities,
F(Ti)={fi,1, fi, 2, ... }
and will also exercise a set of source elements which can be identified through instrumentation (see section 4.2.1),
E(Ti)={ei, 1, ei, 2, ... }
Put another way, we can define an EXERCISES relation over T X ELEMS where EXERCISES(t, e) is true if a software element e is exercised by a test case t and where
t is a set of test cases defined as,
T ={t1,t2,... ,tN}
Furthermore the relation EXHIBITS over T X FUNCS, may be defined, where EXHIBITS(t, f ) is true if test case t exhibits functionality f (Wilde and Scully, 1995). This type of analysis allows us to identify a number of interesting sets. These are discussed in the following subsections.
The set of common software elements refers to the source code that will always be executed regardless of the test case. This is illustrated in figure 4.2, where the large circles represent test cases and the small circles represent the software elements executed by them. The small, black circles are members of the set of common software elements, while the small, white circles are not. The set generally contains utility code of the system (Wilde and Scully, 1995). The set of common software elements, CELEMS, is defined as:
Figure 4.2: Common Software Elements.
The potentially involved software elements for a feature includes software elements exercised by any test case exhibiting the feature f. This is illustrated in figure 4.3 where the large ovals represent test cases and the small circles represent the software elements executed by them. The small, black circles are members of the set of potentially involved software elements. This set will include software elements directly involved in the implementation of f, however, it may also include elements that do not directly implement the feature f.
The set of potentially involved software elements also tends to be quite large as a percentage of the entire system for most features (Wilde and Scully, 1995). When trying to map from feature to location, the primary use of the set of potentially involved software elements is as a foundation for more refined sets. The set of potentially involved software elements, IELEMS, is formally defined as:
Figure 4.3: Potentially Involved Software Elements, shaded in black.
The set of indispensably involved software elements, IIELEMS, is a refinement of the set of potentially involved software elements. IIELEMS is the set of software elements exercised by all test cases exhibiting f. Figure 4.4 illustrates this set. The small, black circles are members of the set indispensably involved software elements and the small white circles are not. This yields a set the same size or smaller than that of the set of potentially involved components for the same feature.
However, the problem of scale remains when trying to locate the code that implements a specific feature (Wilde and Scully, 1995). The elements that solely implement the feature compared to the the size of the set is sometimes a small proportion. Again the set of indispensably involved software elements is more useful in defining more refined sets as described in the following sections. The set of indispensably involved software elements, IIELEMS, can itself be formally defined as:
Figure 4.4: Indispensably Involved Software Elements, are shaded in black.
The set of uniquely involved software elements, UELEMS, is a further refinement upon previously described sets. It contains software elements used only by the functionality f and no other. The set is arrived at by taking the set of software elements exercised by any test case exhibiting f except for any elements that are also exhibited by features that do not exhibit f. Figure 4.5 illustrates this set where the large ovals represent test cases and the small circles represent the software elements executed by them. The small, black circles are members of the set of uniquely involved software elements and the small white circles are not. The set can be defined as follows:
Figure 4.5: Uniquely involved software elements, are shaded in black.
It has been shown experimentally that UELEMS provides a useful starting point when trying to understand the implementation of a particular feature (Wilde and Scully, 1995; Wilde et al., 1992) and that IIELEMS provides a context for understanding when using UELEMS.
Obviously some form of instrumentation is required for software reconnaissance. Instrumentation is a dynamic software analysis technique that involves the inclusion of output statements in source code to help developers understand programs (Wilde, 1998). Several approaches to instrumentation exist, and have been comprehensively reviewed in (Wilde, 1998). An instrumented program, when run, will output a trace or profile of execution. A trace will show what was run during execution, and in what sequence. A profile will only show what was run during execution (Ball, 1999).
Early applications of Software Reconnaissance, which were concerned with finding general starting points for understanding specific program features, determined that instrumentation to the branches of the decision tree was necessary for optimal results (Wilde and Casey, 1996; Gunderson et al., 1995; Wilde et al., 2001; Wilde and Scully, 1995; Fantozzi, 2002). However, more recent variations of the technique use procedure level instrumentation (Eisenbarth et al., 2003; Eisenbarth, Koschke and Simon, 2001; Zhao et al., 2004) and statement level instrumentation (Wong et al., 1999). The former approach is used for feature mapping to source code by incorporating concept analysis while the latter focuses on software comprehension using execution slices.
Most influential to the ultimate outcome of the technique’s use is the user’s choice of test cases (Wilde and Casey, 1996). For example, if chosen carefully, no more than two test cases may be required (Rajlich and Wilde, 2002) -One test case exhibiting the feature and another that does not (Of course, this will mean that the involved and indispensably involved software elements sets will be the same), but the exact nature and amount of test cases will vary depending upon the technique’s use. In general, it has been experimentally shown that the fewer test cases used to identify a feature, the better the outcome of the technique (Wilde and Casey, 1996). Also, simply choosing existing test suites used in regression testing will not always suffice (Wilde and Casey, 1996). Test cases, for software testing purposes, are usually more complex since they tend to be attempting to reveal errors and therefore may exercise many features in a single test case (Eisenbarth et al., 2003). However, with the rise of new approaches to testing, such as unit testing and test case driven development (JUnit, 2006) the nature of test cases themselves are changing. In a publication from Eisenberg and Volder (Eisenberg and De Volder, 2005) the authors manage to successfully apply software reconnaissance using an existing suite of JUnit test cases.
In (Wilde et al., 1992) Norman Wilde published his seminal work on feature location and defined many of the fundamentals that would eventually become Software Reconnaissance. In this paper a feature location case study on a telecommunications switch application called PBX is presented. Even with feature location techniques at an early stage of research maturity, the study managed to return results with up to 50% accuracy. Such was the importance of the publication it received the “Most Influential Paper” accolade at the International Conference on Software Maintenance that year. However, the authors did draw the following conclusions from their experience:
•The technique cannot replace the knowledge of an informed human.
•The technique cannot identify source code responsible for a feature if it is always executed.
In 1995 Wilde and Scully published “Software Reconnaissance: Mapping Program Feature to Code” (Wilde and Scully, 1995) which defined and demonstrated Software Reconnaissance for the first time. Much of the functionality view of software described in section 4.1 is derived from this work. The authors describe a case study on a portion of a C compiler with 15 KLOC approx. and successfully demonstrated the feasibility of the approach. In particular they identify the set of unique software elements as a useful point for a software engineer to begin searching for the implementation of a feature of the system he is looking for.
In (Wilde and Casey, 1996) the authors evaluate Software Reconnaissance with the agenda of enabling technology transfer to industry. Three case studies on industrial or commercial systems are presented. The systems included:
•The visitor control program: An application for logging and issuing passes for visitors to a company.
•The graph display system: An XWindows graph display and browsing application.
•The test coverage monitor: A program that provides test coverage information when executing test cases.
Their experience in transferring the technique to industry allowed the authors to draw some interesting conclusions:
•Test cases should be as few and as simple as possible when implementing Software Reconnaissance.
•Software Reconnaissance is best applied to an unfamiliar system where focus on a single area is needed.
•The use of existing test cases as part of a regression testing suite is not suitable for applying Software Reconnaissance. New test cases, designed to exhibit specific features are needed.
•For any technology being transferred to industry, flexibility and portability are needed to enable industrial trials.
A means of visualising program traces to aid Software Reconnaissance is described in (Lukoit et al., 2000) using a tool call TraceGraph. The tool is applied in two case studies:
• JointSTARS which is a defence system from the US DoD and approximately 300 KLOC in size.
•The Mosaic web browser.
Based on observations from the studies the authors noticed:
•Only features that the user can control can be located using Software Reconnaissance.
•The quality of results will depend upon the test cases used.
•In some cases the human eye in conjunction with the visual representation provided by trace graph was able to replace the set difference operator of older Software Reconnaissance tools.
The type of Software Reconnaissance used in the case studies is a slight variation on the original Software Reconnaissance technique design for multi-threaded applications (Wilde et al., 1997). The instrumentor required must be able to return a single trace where many traces and processes exist. This extension to Software Reconnaissance was proposed as a solution to problems that practitioners were experiencing while applying Software Reconnaissance during a case study on a system called InterBase in (Gunderson et al., 1995).
In (Wilde et al., 2001) the authors compare Software Reconnaissance to a different static analysis feature location technique called the Dependency Graph method. The authors present a case study on a legacy FORTRAN application called CONVERT3, which was used by the U.S. Navy as a raytracer for modelling explosions. Two teams applied the techniques to find two features and observed the following differences with respect to the two feature location techniques:
•Because the dependency graph method forces the user to understand more of
the source code the technique may be more suitable for users who lack domain
knowledge regarding the system.
•Software reconnaissance requires far less browsing of the code to locate a feature.
•For large, infrequently changing programs Software Reconnaissance is a better
alternative to the Dependency Graph method.
In general the empirical evidence strongly suggests that Software Reconnaissance is a useful technique when trying to locate features in unfamiliar source code (Wilde and Scully, 1995; Wilde et al., 2001, 1997; Wilde and Casey, 1996; Wilde et al., 1998, 2003; Loeckx and Sieber, 1987; Wilde, 1998, 1994; Wilde et al., 1992; Fantozzi, 2002; Lukoit et al., 2000; Gunderson et al., 1995).
Other techniques that resemble Software Reconnaissance are used in other problem domains such as software architecture reconstruction (Yan et al., 2004; Riva and Deursen, 2001) and component recovery from legacy software (Eisenbarth et al., 2003; Eisenbarth, Koschke and Simon, 2001), which is discussed at greater length in section 3.5. Finally, the activities required to undertake a Software Reconnaissance resemble many debugging activities, with, of course, the crucial difference that Software Reconnaissance is attempting to locate features not faults (However, it could be argued that a fault is simply an undesired feature.) (Wilde and Scully, 1995; IEEE,1990).
[Back to Home Page] [Previous Chapter] [Next Chapter]
Component Reconn-exion by Andrew Le Gear 2006