ترکیب مفهوم شبکه با نمودار تماس برای آنالیز ضریب تاثیر

Software change impact analysis (CIA) is a key technique to identify unexpected and potential effects caused by software changes. Given a changed entity, most of current CIA techniques compute the change effect composed of some potentially impacted entities. The generated results are often of no help to the maintainers in starting the analysis of impacted entities. In this article, we combine concept lattice with call graph together to obtain a ranked list of potentially impacted methods from the proposed changed methods and/or classes. These impacted methods are ranked based on the hierarchical feature of concept lattice, represented by an impact factor, which can then be used to prioritize these methods to be inspected. Case studies based on four real-world programs show that our approach can improve the precision of the impact result without severely decreasing its recall, when compared with results from either concept lattice or call graph used independently. In addition, the predicted impacted methods with higher impact factor values are also shown to have higher probability to be affected by the changes. Our study also shows that our approach is better than the JRipples CIA approach in removing the false-positives, but at the cost of losing more false-negatives and much more time overhead.

Software change is unavoidable and contributes to the high cost of software maintenance. Lehman and Belady proposed and refined five laws that characterize the dynamics of program evolution, in which the first law is – change is continual [31]. Changes can be stemmed from new requirements, fixing existing faults, change requests, etc. When changes are made to software, they often produce some unexpected and potential ripple effects to other parts of the software. Software change impact analysis (CIA), often simply called impact analysis, is an approach used to identify such potential effects caused by changes made to software [11]. CIA starts with a set of changed elements in a software system, called the change set, and attempts to determine a possibly larger set of elements, called the impact set, which requires attention or maintenance effort due to these changes [11]. The change set is often identified using the feature location technique [40] and [17]. Programmers use feature location to find where in the source code the initial change needs to be made [17]. The full extent of the change is then determined by CIA, which contains a collection of techniques for determining the effects on other parts of the software due to proposed changes [33]. CIA plays an important role in software development, maintenance, and regression testing [11], [12], [42] and [56]. CIA can be used before or after a change implementation. Before making changes, we can employ CIA for program understanding, change impact prediction and cost estimation [11] and [12]. After changes have been implemented, CIA can be applied to trace ripple effects, select test cases, and perform change propagation [42], [56], [9] and [41]. The accuracy of CIA can be determined by its resulting impact set, which often contains some false-positives (i.e., the elements in the estimated impact set are not really impacted) and false-negatives (i.e., some of the real impacted elements are not identified in the impact set). A good CIA should provide an accurate impact set with few false-positives and false-negatives. The commonly used CIA techniques can be categorized into static CIA and dynamic CIA techniques. Static CIA techniques often analyze the dependencies of the program (or its change history repositories), construct an intermediate representation (e.g., call graph), and then conduct analysis based on these representations [52] and [47]. The resulting impact set often has too many false-positives [30]. Thus it is not suitable for practical use [30] and [33]. Whereas dynamic CIA techniques consider part of the inputs, and often rely on the analysis of the information collected during the execution (e.g., execution traces information, coverage information) to calculate the impact set [30], [35] and [5]. The resulting impact set often includes some false-negatives [33]. Given a change set, most of current CIA techniques compute the impact set composed of a set of potentially impacted entities. This presents two challenges to maintainers. First, as all the entities in the impact set are assumed to be equally affected, software maintainers do not know which impacted entities should be inspected first. Second, the impact result may contain many false-positives that will waste the maintainers’ effort in analysis. But in practice, some entities in the impact set are really affected and need corresponding modifications while some others may be false-positives, which are over-estimated by the CIA technique. Hence, a better CIA technique should compute an impact set that includes the probability of being affected associated with each potentially impacted entity and also achieves a higher precision over traditional CIA techniques, that is, the impact set has fewer false-positives. In this article, we propose a new CIA technique to solve these challenges. Our CIA technique combines concept lattice [18] with call graph [32] to compute a ranked list of impact set for method and/or class changes. Given class or method changes, our proposed CIA consists of the following four steps: (1) All proposed changes (method changes or class changes) are mapped to class-level changes to facilitate the class-level impact analysis. (2) Concept lattice is used to predict class-level changes. According to the inherent hierarchical feature of concept lattice, a ranked list of potentially impacted methods are generated. Each method in the generated impact set is assigned an impact factor (IF) value, which represents its probability to be affected by these class changes. (3) Call graph is used to predict the impact set of the method-level changes. This step removes the methods which are not dependent on the changed methods from the impact set obtained in Step 2. (4) The intersection of the two sets obtained from Step 2 and Step 3 gives the final impact set. The methods in this final impact set are also labeled with the IF values. The main contributions of this article are as follows: • We provide a combined approach based on concept lattice and call graph that can remove more false-positives over these two standalone approaches. • From case studies on four real-world programs, it is shown that our CIA approach improves the precision of the impact set without severely decreasing its recall, when compared to other two standalone approaches. • The case studies also show the usefulness of the impact factor metric. Impacted methods with higher impact factor values have a lower probability of belonging to false-positives. • Finally, the accuracy of our CIA approach is empirically compared with the JRipples approach, and the results show that our approach has better precision but a little worse recall and more time overhead. The rest of the article is organized as follows: in the next section, we provide the background of formal concept analysis and call graph, and the precision and recall measure to assess the CIA technique. In Section 3, we present the analysis method of concept lattice and call graph to support CIA. In Section 4, we conduct some case studies to validate the effectiveness of our technique. Then, some related work of CIA techniques and applications of FCA in software maintenance are introduced in Section 5. Finally, we present our conclusion and future work in Section 6.

This article proposes a method to combine formal concept analysis with call graph to support CIA. Concept analysis is used to perform the class-level CIA from a set of class changes, which produces a ranked list of potentially impacted methods. Call graph is used to perform method-level CIA from a set of method changes, giving a set of potentially impacted methods. Finally, the intersection of these two impact sets are computed. Each method in the final impact set is also assigned an impact factor value as that of the class-level impact set. Experimental studies on four real-world programs show that our CIA approach improves the precision of the impact set without severely decreasing its recall when compared to the other two standalone techniques used independently. In addition, the predicted impacted methods with higher impact factor have lower probability to of belonging to false-positives. Finally, we also compare our approach against the JRipples approach in terms of precision and recall, and time overhead. The results show that our approach has better precision but a little worse recall and more time overhead. Although we have shown the effectiveness of our technique through four real-world case studies, we do not know whether it will work as well for other environments. We plan to conduct more experiments with other programs to evaluate the generality of our technique. In addition, we will consider some specular features in object oriented programs, for example, dynamic binding, to more accurately analyze the relation between classes and methods. Then we can predict a more accurate impact set. Finally, given the objective and quantitative result provided by the impact factor, we are planning on investigating how to apply this result to other software maintenance activities, such as comparing various change schemes and selecting regression test cases.