The Research Of Call Graph Construction Based On Static Type Analysis For Java Program

Call graph is a static description of the method calling relationship of the program in compiling time, in which the nodes illustrate methods and the sides indicate the evoking relationship between methods. Call graph has been used widely in software engineering domain, such us compiling optimization, interprocedural data flow analysis, regression test, program understanding and so on. But the polymorphic mechanism of Java and the overridden of the method in the inherited class make the indefiniteness of the actual type of the receiver, the static bonding between the receiver and the target method can not be realized in the complier time. So the call graph of Java program is just an approximation for actual method calling relation during the run time. Therefore, how to advance the efficiency for solving the virtual method call and reduce the number of nodes and edges of the call graph to make the built call graph represent the actual method calling relation during the program running more precisely has been the hot and difficult problem in program analysis domain.First, this dissertation explained three main solutions to the virtual method call problem from an perspective of static class analysis in detail with examples, these three main solutions are Class Hierarchy Analysis, Rapid Type Analysis and XTA. Based on the prototype system for automatically call graph construction we realized, we compared these three solution's analytical precision and analytical efficiency.We proved XTA could get the best analytical precision and Rapid Type analysis could get the best balance between analytical precision and analytical efficiency.Based on the original XTA method, this dissertation presented an improved XTA method using type propagation and type accessibility. This improved method considered the accessibility of method in program incrementally, based on the intraprocedual type propagation and specified a set of accessible variables according to the class of instanced object of every accessible method in order to reduce the possible type of the receiver furtherly. The example represents the improved algorithm can get better analysis precision than the old one.This dissertation also developed and refined the algorithm describing framework based on set presented by F.Tip, and presented the algorithm description of class hierarchy analysis, rapid type analysis, XTA and the improved XTA under this framework, this framework can facilitate to prove that the improved XTA method could get better analytical precision than the original XTA method through the point of set theory view.This dissertation designed and realized a prototype system for automatically call graphcreating. The prototype based on the bytecode anlaysis of Java program and can accomplish the construction of class hierarchical diagram and the automatically creating of call graph based on the class hierarchy analysis, fast type analysis, XTA.