Toward a generic framework for computing subsystem interfaces

One aspect of reverse engineering deals with the recovery of high-level design information from source code. In this process, source code analysis is used to extract the components and dependencies that comprise a software system. Clustering algorithms are then used to group related software components into composite components, called subsystems. The product of this process is a subsystem decomposition hierarchy. This paper describes work in progress of a technique for computing the interfaces (e.g., exported contents) of subsystems that were created during the reverse engineering process. These computed interfaces often reveal to software developers unexpected and undesirable interactions between software components, which is often the result of long-term ad hoc software maintenance practices. We realize that there is no single de nition of a subsystem interface and that a variety of styles of subsystem interfaces are used in practice. For example, in some systems, a subsystem interface may de ne the contents of a subsystem that are accessible to other subsystems. In other systems, a subsystem interface may de ne the contents of a subsystem that have permission to access other subsystems. Thus far we have developed style-speci c algorithms for computing the interfaces of subsystems. Separately, we have developed a visual formalism, called ASF, that enables designers to de ne styles of subsystem interfaces with precision. In the long term, we hope to be able to generate stylespeci c algorithms directly from ASF speci cations and, hence, develop a generic framework for computing subsystem interfaces. Topic Area: Architecture Recovery and Re-engineering 1 Motivation and Background The cost of maintaining a software system over a long period of time far exceeds its initial cost of speci cation, design, and implementation. A signi cant portion of the maintenance cost is attributed to the time required by new software maintainers to understand systems to a degree that they can modify, extend, and correct the functionality of these systems in a reliable way. Developers need high-level structural information to be able to navigate through the numerous software components, their interfaces, and their interconnections. Without this structural information, developers may become overwhelmed by the amount of detail present in the source code. As source code is often the only reliable speci cation available to software developers, a signi cant body of research in reverse engineering is devoted to techniques for recovering high-level structural information from system source code [2]. These techniques rely on rst gathering information about the source code components (e.g., variables, procedures, classes, modules) and dependencies between these components (e.g., variable references, procedure and method invocations, class inheritance, module importation) using source code analysis. In the bottom-up techniques of M uller et al. [5] and Schwanke et al. [10], related source code components are clustered, using a variety of criteria [5], into composite components, called subsystems [9]. Subsystems are, in turn, recursively clustered into higher level subsystems, and so on, until a single subsystem containing only the topmost subsystems is created. In the top-down technique of Murphy et al. [6], software engineers specify multiple views of the software structure manually at any level of detail, and use tools to detect any inconsistencies between the proposed structure and the actual source code structure. Ossher's [7] approach also uses multiple views of software structure. In particular, a grid is used to represent two views of the system structure simultaneously. Each view of the grid represents a di erent system decomposition. In addition to the two views, a variety of constraints can be imposed on each view or even across views. Much progress has been made in our ability to automate the process of decomposing a software system into a hierarchy of subsystems. Our research complements existing reverse engineering techniques by providing algorithms for computing the interfaces of the subsystems that are created during the reverse engineering process. Unlike a typical procedural interface { which is composed of a set of variables { or a typical module or class interface { which is composed of a set procedures { a subsystem interface is composed of a set of modules, classes, or other subsystems. Hence, just as exported (visible) procedures comprise the interface of modules and classes, the interface of subsystems typically consist of exported modules, classes, and other subsystems. Subsystem interfaces are typically complex from many years of ad hoc maintenance and often feature several unexpected and undesirable design decisions [1]. As we will show in Section 2, and have shown more extensively elsewhere [3], the de nition of a subsystem interface can vary signi cantly. Therefore, designers must be able to de ne precisely what a subsystem interface means before attempting to determine the interfaces of any newly created subsystems. We have developed a visual formalism, called ASF [3], to allow designers to de ne, among other things, a variety of styles of subsystem interfaces. In Section 3, we describe the ASF speci cation of one of the subsystem interface styles used in the examples of Section 2. We conclude by outlining the progress we have made (Section 4), as well as our long-term plans to create a generic (style-independent) framework for computing subsystem interfaces (Section 5). 2 Examples of Di erent Subsystem Interfaces Styles In Figure 1 we present three examples of di erent styles of subsystem interfaces. The top of Figure 1 shows a set of modules (dark rectangles) and the import dependencies between them (solid arrows). These modules have been clustered into subsystems (white rectangles). Note that the rst style is a trivial one, since there are no constraints on the dependencies between these modules. For example, there is nothing that speci es that module F cannot depend on module B. If designers want to be able to control the access to modules and subsystems using information hiding principles [8], additional dependencies to specify the interfaces of the subsystems would have to be employed. For example, the middle of Figure 1 introduces the ES (export supplier) dependency for specifying the supplier interface of subsystems. In this second style, the supplier interface of subsystem SS4 is module F. Similarly, the supplier interface of subsystem SS3 is module G and subsystem SS4. In this style, a subsystem or module is considered accessible only if its parent subsystem exports it as a supplier. Hence, in the second style, module D can be accessed by module F because the former is exported from subsystem SS5. However, module D cannot be accessed by modules outside of subsystem SS4 because subsystem SS5 is not exported from subsystem SS4. If designers want be able to control which modules can access other modules in addition to which modules can be accessed by other modules, additional dependencies to specify client interfaces would have to be employed. For example, the bottom of Figure 1 introduces the EC (export client) dependency for specifying the client interface of subsystems. In this third style, the client interface of subsystem SS2 is module A. Similarly, the client interface of subsystem SS1 is module C and subsystem SS2. Hence, in the third style, module A can access module C because subsystem SS2 exports module A as a client. However, module B cannot access modules outside of its parent subsystem because it is not exported as a client. Next, we show how the second style of Figure 1 is de ned using the ASF formalism. The third style, along with several other styles, has been described elsewhere [3]. 3 Formal De nition of the Export Suppliers Style Figure 2 presents the ASF rules that de ne the Export Suppliers Style. An ASF speci cation consists of a nite set of logic rules, which are presented visually. Each rule is de ned by a nite set of entities and relations. Entities are used to represent software components (e.g., subsystems), while relations are used to represent dependencies (e.g., EC, ES) and the nesting of software components. Each ASF rule is represented as a rectangle with a label on its top-left corner. These rectangles contain other rectangles (entities) and arrows (relations). The only relation that is not represented using an arrow is the containment relation, which is depicted as the nesting of entity rectangles. Each ASF rule contains a single dashed arrow. The semantics of the dashed arrows depend on the kind of ASF rule. For example, Permission rules, labelled PERMIT, are used to specify the context under which entities and relations may exist. De nition rules, labelled DEFINE, are used to de ne (derive) new relations based on patterns of entities and relations. A fundamental assumption for the Export Suppliers Style is that the contents of subsystems are not, by default, visible to subsystems in a di erent subtree of the subsystem decomposition hierarchy. Export Supplier (ES) dependencies are used to expose otherwise hidden subsystems. The Export Supplier Style supports a single dependency called ES. The permission rule states that subsystems may export their child subsystems. The de nition rule states that subsystems and their descendants can access their proper siblings as well as the exported descendants of their proper siblings. Note that the double-headed arrow indicates the re exive transitive closure of the ES relation and that rectangles with a double frame indicate re exive transitive containment. Also, note that proper siblings are shown as distinct subsystems contained (nested visually) in the same subsystem. The crossed arrow represents the negation of a relation, which in this case, is on the built-in equality (=) relation.