| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Searching for Points-To Analysis
October 2003 (vol. 29 no. 10)
pp. 883-897
Abstract—The points-to analysis problem is to find the pointer relationships that could arise during program execution. Many points-to analysis algorithms exist, each making a particular trade off between cost of the analysis and precision of the results. In this paper, we show how points-to analysis algorithms can be defined as transformed versions of an exact algorithm. We present a set of program transformations over a general program model and use them to define some existing points-to analysis algorithms. Doing so makes explicit the approximations involved in these algorithms. We also show how the transformations can be used to define new points-to analysis algorithms. Our transformations are generic and may be useful in the design of other program analysis algorithms.
[1] 883 L. Andersen, Program Analysis and Specialization for the C Programming Language PhD thesis, DIKU, Univ. of Copenhagen, May 1994.[2] S. Bensalem, A. Bouajjani, C. Loiseaux, and J. Sifakis, Property Preserving Simulations Proc. Fourth Int'l Workshop Computer Aided Verification, pp. 260-273, 1992.[3] V. Chakaravarthy, New Results on the Computability and Complexity of Points-to Analysis Proc. 30th Ann. ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, Jan. 2003.[4] D.R. Chase, M. Wegman, and F.K. Zadeck, Analysis of Pointers and Structures Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 296-310, 1990.[5] E.M. Clarke, O. Grumberg, and D.E. Long, Model Checking and Abstraction Proc. 19th Ann. ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, pp. 343-354, 1992.[6] P. Cousot and R. Cousot, Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints Proc. Fourth Ann. ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, pp. 238-252, 1977.[7] M. Das, Unification-Based Pointer Analysis with Directional Assignments Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 35-46, 2000.[8] A. Deutsch, Interprocedural May-Alias Analysis for Pointers: Beyond$k{\hbox{-}}\rm Limiting$ ACM SIGPLAN Notices, vol. 29, no. 6, pp. 230-241, 1994.[9] M. Emami, R. Ghiya, and L.J. Hendren, Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 242-257, 1994.[10] M. Fahndrich, J.S. Foster, Z. Su, and A. Aiken, Partial Online Cycle Elimination in Inclusion Constraint Graphs Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 85-96, 1998.[11] R. Ghiya, D.M. Lavery, and D.C. Sehr, On the Importance of Points-to Analysis and Other Memory Disambiguation Methods for C Programs Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 47-58, 2001.[12] M.S. Hecht, Flow Analysis of Computer Programs. Elsevier North-Holland, 1977.[13] N. Heintze and O. Tardieu, Ultra-Fast Alias Analysis Using CLA Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, 2001.[14] N. Heintze and O. Tardieu, Demand-Driven Pointer Analysis Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 24-34, 2001.[15] M. Hind, M. Burke, P. Carini, and J. Choi, Interprocedural Pointer Alias Analysis ACM Trans. Programming Languages and Systems, vol. 21, no. 4, pp. 848-894, 1999.[16] M. Hind, Pointer Analysis: Haven't We Solved This Problem Yet? 2001 ACM SIGPLAN SIGSOFT Workshop Program Analysis for Software Tools and Eng., pp. 54-61, June 2001.[17] S. Horwitz, Precise Flow-Insensitive May-Alias Analysis is NP-Hard ACM Trans. Programming Languages and Systems, vol. 19, no. 1, pp. 1-6, Jan. 1997.[18] N.D. Jones and F. Nielson, Abstract Interpretation: A Semantics-Based Tool for Program Analysis Handbook of Logic in Computer Science, pp. 527-629, 1994.[19] W. Landi, Interprocedural Aliasing in the Presence of Pointers PhD thesis, Rutgers Univ., Jan. 1992.[20] W. Landi, Undecidability of Static Analysis ACM Letters on Programming Languages and Systems, vol. 1, no. 4, pp. 323-337, Dec. 1992.[21] W. Landi and B.G. Ryder, A Safe Approximate Algorithm for Interprocedural Pointer Aliasing Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 235-248, 1992.[22] W. Landi and B.G. Ryder, Pointer-Induced Aliasing: A Problem Classification Proc. 18th Ann. ACM Symp. Principles of Programming Languages, pp. 93-103, 1991.[23] T.J. Marlowe and B.G. Ryder, Properties of Data Flow Frameworks: A Unified Model Acta Informatica, vol. 28, pp. 121-163, 1990.[24] D. McAllester, On the Complexity Analysis of Static Analyses Proc. Static Analysis Symp., 2001.[25] K.S. Namjoshi and R.P. Kurshan, Syntactic Program Transformations for Automatic Abstraction Proc. 12th Conf. Computer Aided Verification, E.A. Emerson and A.P. Sistla, eds., 2000.[26] F. Nielson, H. Nielson, and C. Hank, Principles of Program Analysis: Flows and Effects. Springer, 1999.[27] T. Reps, Program Analysis via Graph Reachability. Information and Software Technology Information and Software Technology, vol. 40, nos. 11-12, pp. 701-726, 1998.[28] D. Schmidt, Data-Flow Analysis is Model Checking of Abstract Interpretations Proc. 25th ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, 1998.[29] M. Shapiro and S. Horwitz, Fast and Accurate Flow-Insensitive Points-to Analysis Proc. 24th ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, 1997.[30] M. Sharir and A. Pnueli, Two Approaches to Interprocedural Dataflow Analysis Program Flow Analysis: Theory and Applications, S.S. Muchnick and N.D. Jones, eds., 1980.[31] B. Steensgaard, Points-to Analysis in Almost Linear Time Proc. 23th ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, 1996.[32] B. Steffen, Generating Data-Flow Analysis Algorithms for Modal Specification Science of Computer Programming, vol. 21, pp. 115-139, 1993.
Index Terms:
Points-to analysis, program analysis, reachability analysis, model checking.
Citation:
Glenn Bruns, Satish Chandra, "Searching for Points-To Analysis," IEEE Transactions on Software Engineering, vol. 29, no. 10, pp. 883-897, Oct. 2003, doi:10.1109/TSE.2003.1237170
