A Framework for Call Graph Construction

Abstract: In object oriented programming, a Call Graph represents the calling relationships between the program’s methods. To be more precise, a Call Graph is a rooted directed graph where each node of the graph represents a method and each edge (u, v) represents a method call from method u to method v. Focus of this thesis is on building a framework for Call Graph construction algorithms which can be used in program analysis. Our framework is able to be initialized by different front-ends and constructs various Call Graph algorithms. Here, we instantiate framework with two bytecode readers (ASM and Soot) as front-ends and implement three Call Graph construction algorithms (CHA, RTA and CTA). At first, we used two above mentioned bytecode readers to read the bytecode of a specific Java program, then we found reachable methods for each invoked method; meanwhile we kept obtained details on our own data structures.  Creating data structures for storing required information about Classes, Methods, Fields and Statements, gives us a great opportunity to implement an independent framework for applying well known Call Graph algorithms. As a result of these data structures, Call Graph construction will not depend on bytecode readers; since, whenever we read the bytecode of a program, we accumulate all necessary points in pre-defined data structures and implement our Call Graphs based on this accumulated data. Finally, the result is a framework for different Call Graph construction algorithms which is the goal of this thesis. We tested and evaluated the algorithms with a variety of programs as the benchmark and compared the bytecode readers besides the three Call Graph algorithms in different aspects.