Project topics and materials
Get Complete Project Material File(s) Now! »
Call Graphs
As described in the preceding chapter, Call Graphs (CG) are graphs built from methods and functions calls extracted from the code. These graphs allow to perform impact analysis and some authors in the literature explored this data structure. This section review proposition of Call Graphs approaches listed in Lehnert’s taxonomy.
Chianti
Ryder and Tip [23] created a method of change impact analysis implemented by Chianti [22], an impact analysis tool for Java systems developed by Ren et al. It works as follows. First, given two versions of a program and a set of tests cov-ering a part of the program, it determines which tests have to be re-executed in after the change performed on the software. Ren et al. claim that their method generate an estimated impact set that at least contains the actual impact set (i.e., AIS EIS).
Second, from the impacted tests, the set of affecting changes is computed. These changes are those that may have given rise to a test’s changed behaviour. The authors say their method is conservative because the set of affecting changes computed is guaranteed to contain at least every change that may have caused a change to a test behaviour. Chianti works with model entities at the class, method, variable and test case granularity and works with the following changes: add/delete class, add/delete/ change method and add/delete variable. The results provided by the tool is a set of test cases to be re-executed after a change has been applied.
Change Impact Dependency
Xia and Srikanth [25] proposed a theoretical method for change impact analysis based on a specific metric named the change impact dependency. One of the goals of this metric is to count the direct change impact as well as the indirect change impact (which, according to the authors, is not done by others metrics). The metric assume that there is no information available about the type of change that was performed on the software. The granularity of this technique is at the statement level. The metric allows to select a set of lines of code that are potentially subject to be indirectly impacted by the change.
CCGImpact
Badri et al. [2] proposed an approach that mixes Call Graph (CG) and Control Flow Graph (CFG) approaches. The data structure they proposed is named a Control Call Graph (CCG) and contains more information than a CG. More for-mally, below are presented the definitions of oriented graph, call graph, control flow graph and control call graphs as defined in their article: Oriented Graph: An oriented graph G = (S; A) is composed of a finite set S of vertex and a set of pairs A S S of arcs. Each arc (x; y) 2 A represents an oriented relation between two vertices between x as origin and y as target. Call Graph: A call graph is an oriented graph for which the set S contains vertices representing the methods of the software and the set A contains arcs representing the calls between methods. (x; y) 2 A represents the fact that x is the caller and y is the callee.
Control Flow Graph: A control flow graph is an oriented graph for which the set S contains vertices representing decision points (if-then-else, while, case, etc. . . ), an instruction or a sequential block of instructions (i.e., a suite of instruction for which if the first instruction is executed, all the others instruction of the suite will be executed and always in the same order). An arc between two vertices (x; y) 2 A is present if it is possible to have an execution that leads to have y is executed after x has been executed. Control Call Graph: A control call graph is a control flow graph for which the vertices representing instructions not leading to method calls are elim-inated. The method takes the method that has been changed and propagates the change using the CCG independently of the type of change.
Program Dependency Graphs
Program Dependency Graphs (PDG) are graphs built from the dependencies between program entities. These graphs are built by analysing the source code of a software. This section review proposition of Program Dependency Graphs approaches listed in Lehnert’s taxonomy.
Briand et al.
Briand et al. did an empirical study [7] that investigates the relation between coupling metrics and the ripple effect in object-oriented software. They identi-fied that for two classes C and D the following metrics are relevant to predict the ripple effect:
PIM : The number of method invocations in C of methods in D.
CBO’ : Coupling between object classes when there is no inheritance rela-tions between the two classes. C and D are coupled together, if methods of one class use methods or attributes of the other, or vice versa. CBO is then a binary indicator, yielding 1 if C is coupled to D, else 0.
INAG: Indirect aggregation coupling. Takes the transitive closure of the “C has an attribute of type D” relation into account.
To predict the impact of a change on a class C, the authors rank the classes of the system accord using the average of PIM, CBO’ and INAG values with an equal weight for each metric. The more a class is high in the ranking, the more it is probable that it is impacted by the change. From their impact model, Briand et al. conclude that using the metrics cited before indeed indicates classes with a higher chance to be impacted by a change but also that some aspects of the ripple effect are not taken into account by the model. To have better results, the authors say that future research should try to provide new metrics that are not only based on the source code but also from all kind or requirement and design documentation.
Kung et al.
Kung et al. provide a tool [13] to evaluate the impact of changes in OO libraries. This tool is based on a formal model made for capturing changes and predicting classes affected by these changes. The authors define a specific change model for their tool. This change model is based on the types of entities considered: data change that concerns global variables, local variables and class data members, method change that concerns methods, class change that concerns direct modification on classes and class library change that concerns modification on classes of the package or modifi-cation of the relationships between the classes of the package. Table II.2.2 lists all the changes defined by Kung et al.
Three types of graph are used by Kung et al. formal model: Object Rela-tion Diagram which describes objects of the software and their relations, Block Branch Diagram (BBD) which model methods source code allowing to find which methods were modified by comparing the initial BBD to the BBD of the modified source code and Object State Diagram describing the state behaviour of a class. These are graphs generated from the source code and used to evaluate the impact of a change. In the article, the authors talk about an experience with their tool indicating that it is extremely time consuming and tedious to test and maintain an OO software system. They also claim that they get good feedbacks from the devel-opers that used their tools in the industry. Nevertheless, there is no description of the experimental protocol and there is no details about the experiment’s results.
Table of contents :
Introduction
I Change Impact Analysis
I.1 Motivation
I.2 Definitions
I.3 Taxonomy
I.4 Discussion
II Call Graphs and Program Dependency Graphs
II.1 Call Graphs
II.2 Program Dependency Graphs
II.3 Analysis on Articles Reviewed
II.4 Objectives for the Implementation
III Proposition
III.1 Entities and Relations
III.2 Change Model
III.3 Results Model
III.4 Approach Description
III.5 Implementation
III.6 Discussion
IV Evaluation
IV.1 Complexity Estimation
IV.2 Classification in Lehnert Taxonomy
IV.3 Assessing Precision and Recall
Conclusion
