TFA: an efficient and precise virtual method call resolution for Java

摘要

The problem of statically resolving virtual method calls in object-oriented (OO) programming languages has been a long standing challenge, often due to the overly complicated class hierarchy structures in modern OO programming languages such as Java, C# and C++. Traditional ways of dealing with this problem include class hierarchy analysis (CHA), variable type analysis (VTA), and retrieval of type information after a sophisticated points-to analysis. In this paper, we tackle this problem by proposing a new approach called type flow analysis (TFA) which propagates type information as well as field access information through the syntactic structure of a program. Our methodology is purely algebraic and there is no need to explicitly construct a heap abstraction. We have assessed our methodology from two perspectives. Regarding its theoretical foundation, we have proved that in the context insensitive setting, our method is as precise as the standard Andersen's subset based points-to analysis regarding the derived types for variables. For an experimental evaluation of TFA, we have implemented the algorithm in the Soot framework and used it to analyze the SPECjvm2008 benchmark suite. During the experiment, we have shown that our method is usually 30-100 times faster than the standard points-to analysis. We further conduct a range of detailed analysis based on the baseline data obtained by running a dynamic profiler, which is also implemented by us, on the SPECjvm2008. The experiment results confirm that TFA can achieve outstanding performance with acceptable accuracy when applied on real-world Java programs.