ROSAEC center Seoul National University
Speaker:ROPAS Members, Research On Program Analysis System
When:2009-01-17 10:00
Place:Room 309-1, Bldg 302, SNU


In objective-oriented programming languages, a virtual function call(or dynamic dispatch) is major resource of ambiguit compile-time control flow information. The class anlysis is technique which allow us to calculate runtime type information without executing program. Inaccurate compile-tile control flow information could be fixed by precalculated runtime type information. Question is, among many dozen of proposed class analysis algorithms, which one is suitable for given problem instance? In this survey, volunteer will present brief historical overview and introduce some papers about class analysis.


Session1 : 10:00~11:00

Introduction and Historical Overview
Wontae Choi [slide]

Session2 : 11:15~13:00

Scalable Propagation-based Call Graph Construction Algorithm
Gaeul Jung [slide]
Interprocedural Class Analysis
Yoonseok Ko [slide]
Refinement-Based Context-Sensitive Points-to Analysisa
Soonho Kong [slide]
Merging Equivalent Contexts
Hakjoo Oh [slide]


  • O. Agsen. “The cartesian product algorithm : Simple and precise type inference of parameteric polymorphis”, In European Conference on Object Oriented Programming, pages 2-26, 1995
  • L. O. Andersen, “Program analysis and specialization for the C programming language”. Ph.D thesis, DIKU, University of Copenhagen, 1994
  • D.Bacon and P. Sweeney, “Fast Static Analysis of C++ Virtual Function Calls”, OOPLSA’96
  • J.Dean, D.Grove, C.Chambers, “Optimization of OO Programs Using Static Class Hierarchy”, ECOOP’95
  • D.Grove and C.Chambers. “A Framework for call graph construction algorithms.” ACM Transactions on Programming Languages and Syatems (TOPLAS), 23(6), 2001
  • A. Milanova, A Rountev, and B.G. Ryder. “Parameterized object-sensitivity for points-to and side-effect analysis for java.” In International Symposium on Software Testing and Analysis, 2002.
  • A. Milanova, Barbara G. Ryder. “Annotated Inclusion Constraints for Precise Flow Analysis”, Proceedings of the 21st IEEE International, 2005
  • A. Milanova. “Light Context-Sensitive Points-to Analysis for Java”, PASTE’07 J. Plevyak and A.Chien.“Precise concrete type inference for object-oriented languages.” OOSPLA’94
  • Ondřej Lhoták  and Laurie Hendren, “Context-Sensitive Points- to Analysis: Is It Worth It?”, LNCS, Springer, 2007
  • Vijay Sundaresn, Laurie Hendren, Chrislain Ranafimahefa, Reja Vallee-Rai, Ptrick Lam, Etenne Gagnon and Charles Godin. “Practical Virtual Method Call Resolution for Java”,Conference on Object Oriented Programming System Languages and Applications, Proceedings of the 15th ACM SIGPLAN conference on Object-orientd programming, systems, languages, and applications, 2000
  • M.Sridharan, R.Bodik, “Refinement-Based Context-Sensitive Analysis for Java”, PLDI’06
  • M.Sharir and A.Pnueli. “Two approaches to interprocedural data-flow analysis”, In S.Muchnick and N.Jones, editors, Program Flow Analysis : Theory and Applications, Prentice Hall, 1981
  • Barbara G.Ryder. “Dimension in Reference Analysis of Object-Oriented Programming Languages”, LNCS Springer, 2003
  • F. Tip and J.Palsberg. “Scalable Propagation-based Call Graph Construcion Algorithm”, OOPSLA’00
  • J.Whaley and M.Lam. “Cloning-Based Context-Sensitive Pointer Analysis Using Binary Decision Diagrams”, PLDI’04
  • Guoqing Xu, Atanas Rountev. “Merging Equivalent Contexts for Scalable Heap-Cloning-Based Context-SEnsitive Points-to Anlyasis”, ISSTA’08

© Copyright 2008-2010 ROSAEC Center, Seoul National University