A software system evolves as changes are made to accommodate new features and repair defects. Software components are frequently interdependent, so changes made to one component can result in changes having to be made to other components to ensure that the system remains consistent; this is called change propagation. Accurate detection of change propagation is essential for software maintenance, which can be aided by accurate prediction of change propagation. In this paper, we study change propagation in three leading open-source software products: Linux, FreeBSD, and Apache HTTP Server. We use association rules-based data-mining techniques to detect change-propagation rules from the product version history. These rules are evaluated with respect to different training data sets and different test data sets. We discuss the applicability of using association-rule mining for change propagation, and several related issues. We find that a challenging issue in association-rule mining, concept drift, exists in software systems. Concept drift complicates the task of change-propagation prediction and requires special approaches, different from currently-used techniques for predicting change propagation.

Embedded software development involves many knowledge acquisition (KA) tasks that collectively account for a significant proportion of development costs. This paper presents a pilot study that used case studies to investigate the extent to which knowledge acquired in learning tasks was used in developing a final product. Data obtained from the case studies were used to construct event chains, which trace the amount of time spent on KA tasks and the types of knowledge acquired in individual learning tasks. Knowledge acquired was separated into three categories: knowledge of data, knowledge of process, and knowledge of innovation. Each top-level category was further partitioned into productive and nonproductive knowledge depending on whether the knowledge was, or was not used, in the construction of the final product. The event chains were processed to visualize the chronological progression of how knowledge acquired in the separate categories moved between subcategories of productive and nonproductive knowledge as development progressed. Results of this analysis show trends in KA for the case studies investigated, which we plan to use in the design of future work on this topic.

We propose a model that enables software developers to systematically evaluate and compare all possible alternative reuse scenarios. The model supports the clear identification of the basic operations involved and associates a cost component with each basic operation in a focused and precise way. The model is a practical tool that assists developers to weigh and evaluate different reuse scenarios, based on accumulated organizational data, and then to decide which option to select in a given situation. The model is currently being used at six different companies for cost-benefit analysis of alternative reuse scenarios; we give a case study that illustrates how it has been used in practice.

Data coupling between modules, especially common coupling, has long been considered a source of concern in software design, but the issue is somewhat more complicated for products that are comprised of kernel modules together with optional nonkernel modules. This paper presents a refined categorization of common coupling based on definitions and uses between kernel and nonkernel modules and applies the categorization to a case study. Common coupling is usually avoided when possible because of the potential for introducing risky dependencies among software modules. The relative risk of these dependencies is strongly related to the specific definition-use relationships. In a previous paper, we presented results from a longitudinal analysis of multiple versions of the open-source operating system Linux. This paper applies the new common coupling categorization to version 2.4.20 of Linux, counting the number of instances of common coupling between each of the 26 kernel modules and all the other nonkernel modules. We also categorize each coupling in terms of the definition-use relationships. Results show that the Linux kernel contains a large number of common couplings of all types, raising a concern about the long-term maintainability of Linux.

Abstract RTP is a widely used commercial real‐time product that has been maintained over a period of 13 years. We have analyzed multiple versions of RTP, which is written in C and Assembler. We measured increases in dependencies within the code between successive versions and performed statistical analyses on the data. There was no significant difference between the maintenance of Assembler files and C files. Also, there was no significant difference between the versions written by the original developers and those written by maintenance programmers not involved in the original development. The differences between individual programmers were very highly significant. Our interpretation of these results is that the skill of the individual programmer is an important factor in ensuring that a software product remains maintainable over its lifetime and that software engineering education and training are therefore of major importance. Copyright © 2001 John Wiley & Sons, Ltd.

Maintenance is performed not only after a software product has been delivered to the client. On the contrary, the requirements frequently change during development, thereby necessitating reconstruction of the artifacts that have been developed to date. In this paper we present a process for software construction that recognizes maintenance as an essential aspect of the entire life cycle of the software product, considered from the very first steps of the initial development. The process may be used in conjunction with any software development or maintenance methodology. Our process consists of two components: a procedure that is uniformly applied at every step of the chosen methodology, whether development or maintenance; and a data structure, the propagation graph, which is updated at every step. When requirements change, the propagation graph is used to determine which artifacts of the software product are impacted by the change in requirements. From the viewpoint of changes in requirements, the process treats development as a special case of software maintenance. Copyright © 2000 John Wiley & Sons, Ltd.

Results of a case study in maintenance of an object oriented software application are presented. A software engineer replaced a text based user interface with a graphical user interface (GUI) based on the Microsoft Foundation Classes, adapted the application for the Win32 environment, and corrected faults in the original application. About 94.8% of the maintenance effort was perfective (development of the GUI), 3.2% adaptive and 2.0% corrective. Comparisons are drawn to similar maintenance activities in the literature.

The coupling dependency metric (CDM) is a successful design quality metric. Here we apply it to four case studies: run-time failure data for a COBOL registration system; maintenance data for a C text-processing utility; maintenance data for a C++ patient collaborative care system; and maintenance data for a Java electronic file transfer facility. CDM outperformed a wide variety of competing metrics in predicting run-time failures and a number of different maintenance measures. These results imply that coupling metrics may be good predictors of levels of interaction within a software product.

Abstract Software reuse has traditionally been put forward as a mechanism for reducing the cost of developing a product. This paper shows that the overall economic impact of reuse on maintenance is greater than its impact on development. A specific reuse example is worked in detail to illustrate the impact of reuse on the various types of maintenance that are performed on a software product. On average, the cost savings during maintenance as a consequence of reuse are nearly twice the corresponding savings during development. The results are generalized to show that, for an arbitrary product, the cost savings during maintenance as a consequence of software reuse exceed the cost savings during development as a consequence of reuse when more than about 51% of the software budget is devoted to maintenance, and increase rapidly as the proportion of the budget devoted to maintenance becomes large.

Abstract The application of formal verification in software engineering is limited because programs continue to evolve during the maintenance phase, thus rendering the original verification obsolete. Program decomposition schemes can be used to identify the parts of the modified program that need verification. The original program verification can be reused and combined with the verification of the parts of the modified program. Automatic decomposition of programs into independent computational threads called projections can be performed by utilizing program‐dependence relations. These relations represent dependence information among the variables and statements of a program. The individual proofs of each projection can be combined to produce the verification of the entire program. After a modification, many of the original projections may still be present in the new program and they are not re‐verified. Only new projections need verification which is usually easier than re‐verifying the entire program.

The use of program decomposition to assist maintenance programmers in all three phases of maintenance, namely, comprehension, modification and debugging, is discussed. Visibility flow graphs are introduced to represent the information about the static semantics of a program. Using static analysis of programs, it is possible to approximate their dynamic behavior. More precise analysis is possible if the program is monitored during its execution. For dynamic semantics, dependence relations are used that reflect the dependency of statements on the input value of variables and of the output value of variables on the statements. These relations are generated both at static analysis time and during program execution. Some sample sessions with a prototype program analyzer for a subset of Ada are included.>

Abstract VIADUCT is a very high‐level non‐procedural language designed to simplify usage of MDBS, a microcomputer database management system. Users need not have any knowledge of the structure of the database, because no path through the database is specified in a VIADUCT command. Instead, VIADUCT automatically determines which of a number of paths should be traversed in order to process the command. As this choice of path can critically affect the processing time required, VIADUCT chooses that path which is most likely to minimize the number of record occurrences retrieved from the database. But when a command can have more than one valid semantic interpretation, VIADUCT computes and then displays the alternative paths from which the user is required to make a choice. Following a brief description of relevant aspects of MDBS, an overview of VIADUCT is given. The body of the paper describes the algorithms that are used to find paths through the database, as well as the path‐traversal algorithms. An evaluation of VIADUCT is presented and some restrictions noted.

Abstract The package DBDEBUG assits the users of CODASYL (network) database management systems in two ways. It can be used by applications programmers to debug their programs, and by the database administrator to monitor the performance of the database. The user may select the sections (or even individual statements) of his program to be traced and/or monitored. He may list the specific records and items he wishes to be investigated; he may also restrict tracing and monitoring to only certain DML verbs. The user's database schema and subschema are submitted to processors which generate a data dictionary. This data dictionary is then used by DBDEBUG in modifying the user's DML source code in order to obtain the specified tracing or performance statistics. The output is high‐level in that it reflects the high‐level language (DML COBOL) in which the user's source code was written. The package is designed to be portable. All but one of its components are written in standard Pascal or ANSI COBOL; assembler code is restricted to a ten‐line subroutine which obtains L/O and CPU times from the operating system.

A very high-level trace for data structures is one which displays a data structure in the shape in which the user conceptualizes it, be it a tree, an array, or a graph. GRAPHTRACE is a system that facilitates the very high-level graphic display of interrelationships among dynamically allocated Pascal records. It offers the user a wide range of options to enable him to "see" the data structures on a graphics screen in a format as close as possible to that in which he visualizes it, thereby providing a useful display capability when the user's conceptual model is a directed graph or tree.

The problem of finding a mm-max partmon of a weJghted tree T with n veruces into q subtrees by means of k = q -1 cuts is considered.A top-down shifting algorithm for this problem ts presented An outhne is given of an efficJent implementatmn of the algorithm wtth complexity O(k3rd(T) + kn), where rd(T) ts the number of edges m the radius of T Categories and Subject Descriptors F 2 2 [Analysis of Algorithms and Problem Complexity].Nonnumencai Algorithms and Problems; G 2 2 [Discrete Mathematics]' Graph Theory--network problems, trees General Terms.

Abstract An implementation of Concurrent Pascal on a UNIVAC1106 is described. Design decisions include the choice of compiled rather than interpreted code, as well as scheduling strategies. The advantages and disadvantages of a mainframe implementation are discussed.

Abstract The central problem of software engineering, namely an overall strategy for the successful production of large‐scale software, has not yet been solved. Various techniques do exist for separate sections of the production process, but largely owing to the huge costs involved, it is virtually impossible to perform controlled experiments to test their validity, or to compare competing methodologies. One alternative way of deciding which techniques are to be preferred is to set up a science of software management, and to evaluate methodologies within its framework. This paper is a first step towards such a science. It notes similarities between certain techniques for structuring the programming group, the program modules, the testing process and the actual code itself. A theory is then deduced which enables programming managers to choose from among the wide selection of available techniques those which are applicable to the specific system to be written.

The max-rain k-partition algorithm may be formulated as follows: Given a tree T with n edges and a nonnegative weight associated with each vertex, assign a cut to each of k distinct edges of T so as to maximize the weight of the lightest resulting connected subtree.An algorithm for this problem is presented which initially assigns all k cuts to one edge incident with a terminal vertex of T; thereafter the cuts are shifted from edge to adjacent edge on the basis of local information.An efficient implementation with complexity O(k 2. rd(T) + kn), where rd(T) is the number of edges in the radius of T, is described.An algorithm for a simpler problem, namely, the partitioning of Tinto the maximum number of connected components whose weight is bounded below, is then described.Combined with the technique of binary search, it yields an alternative algorithm for the max-rain k-partition problem with complexity dependent on the range of the given weights.

Abstract Debugging aids for high‐level languages supporting structured data types should provide diagnostic information in a form terminologically as close as possible to that of the original source code. In addition, it is desirable that such software be portable. The package HEAPTRACE satisfies both the above criteria. It is a precompiler for Pascal programs which enables the user to trace the heap, selectively dumping dynamically‐created records in a high‐level format. It is portable as it is written entirely in Pascal; furthermore, since it is implemented as additions and modifications to a well‐known compiler, its principles may easily be built into any Pascal compiler or diagnostics system. However, there is a small price to pay for achieving portability in that three possibly desirable features cannot be satisfactorily implemented in a machine‐independent manner.