Comparing call graphs

ABSTRACT

Comparing program analysis results from different static and dynamic analysis tools is difficult and therefore too rare, especially when it comes to qualitative comparison. Analysis results can be strongly affected by specific details of programs being analyzed, so quantitative evaluation should be supplemented by qualitative identification of those details. Our general aim is to develop tools to reduce the difficulty of qualitative comparison. In this paper, we focus on comparison of call graphs in particular. We present two complementary tools for comparing call graphs. Our main contribution is a call graph difference search tool that ranks call graph edges by their likelihood of causing large differences in the call graphs. This is complemented by a simple interactive call graph viewer that highlights specific differences between call graphs, and allows a user to browse through them. In a search for the causes of call graph differences, a user first uses the search tool to identify which of the thousands of spurious edges to look at more closely, and then uses the interactive viewer to determine in detail the root cause of a difference. We present the ranking algorithm used in the difference search tool. We also report on a case study using the comparison tools to determine the most important sources of imprecision in a typical static call graph by comparing it to a dynamic call graph of the same benchmark.

REFERENCES

• 1: Graphviz - graph visualization software. http://www.graphviz.org/.
• 2: *J: A tool for dynamic analysis of java programs.http://www.sable.mcgill.ca/starj/.
• 3: Soot: a Java optimization framework. http://www.sable.mcgill.ca/soot/.
• 4: yEd - Java graph editor. http://www.yworks.com/en/products yed about.htm.
• 5: B. Dufour. Objective quantification of program behaviour using dynamic metrics. Master's thesis, McGill University, June 2004.
• 6: Bruno Dufour , Karel Driesen , Laurie Hendren , Clark Verbrugge, Dynamic metrics for java, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 7: Bruno Dufour , Laurie Hendren , Clark Verbrugge, *J: a tool for dynamic analysis of Java programs, Companion of the 18th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 26-30, 2003, Anaheim, CA, USA [doi>10.1145/949344.949425]
• 8: Michael D. Ernst, Invited Talk Static and dynamic analysis: synergy and duality, Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.35-35, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996823]
• 9: David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001 [doi>10.1145/506315.506316]
• 10: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 11: Michael Hind , Anthony Pioli, Which pointer analysis should I use?, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.113-123, August 21-24, 2000, Portland, Oregon, United States
• 12: O. Lhoták. Spark: A flexible points-to analysis framework for Java. Master's thesis, McGill University, Dec. 2002.
• 13: O. Lhoták. Program Analysis using Binary Decision Diagrams. PhD thesis, McGill University, Jan. 2006.
• 14: O. Lhoták and L. Hendren. Scaling Java points-to analysis using Spark. In G. Hedin, editor, Compiler Construction, 12th International Conference, volume 2622 of LNCS, pages 153--169, Warsaw, Poland, Apr. 2003. Springer.
• 15: O. Lhoták and L. Hendren. Context-sensitive points-to analysis: is it worth it? In A.Mycroft and A. Zeller, editors, Compiler Construction, 15th International Conference, volume 3923 of LNCS, pages 47--64, Vienna, Mar. 2006. Springer.
• 16: Donglin Liang , Maikel Pennings , Mary Jean Harrold, Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 17: Ana Lubenova Milanova , Barbara Gershon Ryder, Precise and practical flow analysis of object-oriented software, Rutgers University, New Brunswick, NJ, 2003
• 18: Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to and side-effect analyses for Java, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 19: Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005 [doi>10.1145/1044834.1044835]
• 20: Markus Mock , Manuvir Das , Craig Chambers , Susan J. Eggers, Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-72, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379671]
• 21: Gail C. Murphy , David Notkin , Erica S.-C. Lan, An empirical study of static call graph extractors, Proceedings of the 18th international conference on Software engineering, p.90-99, March 25-29, 1996, Berlin, Germany
• 22: Atanas Rountev , Scott Kagan , Michael Gibas, Evaluating the imprecision of static analysis, Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996829]
• 23: Atanas Rountev , Scott Kagan , Michael Gibas, Static and dynamic analysis of call chains in java, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 24: B. G. Ryder. Dimensions of precision in reference analysis of objectoriented programming languages. In G. Hedin, editor, Compiler Construction, 12th International Conference, CC 2003, volume 2622 of Lecture Notes in Computer Science, pages 126--137. Springer, 2003.
• 25: Manu Sridharan , Rastislav Bodík, Refinement-based context-sensitive points-to analysis for Java, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 26: Standard Performance Evaluation Corporation. SPEC JVM98 benchmarks. http://www.spec.org/osg/jvm98/.
• 27: Philip A. Stocks , Barbara G. Ryder , William A. Landi , Sean Zhang, Comparing flow and context sensitivity on the modification-side-effects problem, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.21-31, March 02-04, 1998, Clearwater Beach, Florida, United States
• 28: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
• 29: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 30: Jianwen Zhu , Silvian Calman, Symbolic pointer analysis revisited, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

General Terms:
Algorithms, Design, Languages, Measurement

Keywords:
call graph, comparison tools, dynamic analysis, interpreting analysis results, static analysis