Efficient field-sensitive pointer analysis of C

ABSTRACT

The subject of this article is flow- and context-insensitive pointer analysis. We present a novel approach for precisely modelling struct variables and indirect function calls. Our method emphasises efficiency and simplicity and is based on a simple language of set constraints. We obtain an O(v⁴) bound on the time needed to solve a set of constraints from this language, where v is the number of constraint variables. This gives, for the first time, some insight into the hardness of performing field-sensitive pointer analysis of C. Furthermore, we experimentally evaluate the time versus precision trade-off for our method by comparing against the field-insensitive equivalent. Our benchmark suite consists of 11 common C programs ranging in size from 15,000 to 200,000 lines of code. Our results indicate the field-sensitive analysis is more expensive to compute, but yields significantly better precision. In addition, our technique has been integrated into the latest release (version 4.1) of the GNU Compiler GCC. Finally, we identify several previously unknown issues with an alternative and less precise approach to modelling struct variables, known as field-based analysis.

REFERENCES

• 1: Alexander Aiken, Set Constraints: Results, Applications, and Future Directions, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.326-335, May 02-04, 1994
• 2: Alexander Aiken, Introduction to set constraint-based program analysis, Science of Computer Programming, v.35 n.2-3, p.79-111, Nov.1.1999 [doi>10.1016/S0167-6423(99)00007-6]
• 3: Aiken, A., and Wimmers, E. L. 1992. Solving systems of set constraints. In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society Press, Los Alamitos, CA, 329--340.
• 4: Alexander Aiken , Edward L. Wimmers, Type inclusion constraints and type inference, Proceedings of the conference on Functional programming languages and computer architecture, p.31-41, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165188]
• 5: Rajeev Alur , Thomas A. Henzinger , Freddy Y. C. Mang , Shaz Qadeer , Sriram K. Rajamani , Serdar Tasiran, MOCHA: Modularity in Model Checking, Proceedings of the 10th International Conference on Computer Aided Verification, p.521-525, June 28-July 02, 1998
• 6: Andersen, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. dissertation. DIKU, University of Copenhagen.
• 7: Thomas Ball , Susan Horwitz, Slicing Programs with Arbitrary Control-flow, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.206-222, May 03-05, 1993
• 8: Berlin, D. 2005. Structure aliasing in GCC. In Proceedings of the GCC Developers Summit. 25--36.
• 9: Marc Berndl , Ondrej Lhoták , Feng Qian , Laurie Hendren , Navindra Umanee, Points-to analysis using BDDs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 10: Binkley, D. 1998. The application of program slicing to regression testing. Inf. Softw. Tech. 40, 11--12, 583--594.
• 11: Bruno Blanchet , Patrick Cousot , Radhia Cousot , Jérôme Feret , Laurent Mauborgne , Antoine Miné , David Monniaux , Xavier Rival, Design and implementation of a special-purpose static program analyzer for safety-critical real-time embedded software, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
• 12: Bruno Blanchet , Patrick Cousot , Radhia Cousot , Jérome Feret , Laurent Mauborgne , Antoine Miné , David Monniaux , Xavier Rival, A static analyzer for large safety-critical software, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 13: François Bourdoncle, Abstract debugging of higher-order imperative languages, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.46-55, June 21-25, 1993, Albuquerque, New Mexico, United States
• 14: Bourdoncle, F. 1993b. Efficient chaotic iteration strategies with widenings. In Proceedings of the Conference on Formal Methods in Programming and Their Applications. Lecture Notes in Computer Science, vol. 735. Springer-Verlag, New York, 128--141.
• 15: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 16: Satish Chandra , Thomas Reps, Physical type checking for C, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-75, September 06-06, 1999, Toulouse, France
• 17: Chandra, S. and Reps, T. 1999b. Physical type checking for C. Technical Report BL0113590-990302-04, Lucent Technologies, Bell Laboratories.
• 18: Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292554]
• 19: Li-Ling Chen , Williams Ludwell Harrison, III, An efficient approach to computing fixpoints for complex program analysis, Proceedings of the 8th international conference on Supercomputing, p.98-106, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181308]
• 20: Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.57-69, June 18-21, 2000, Vancouver, British Columbia, Canada
• 21: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 22: Manuvir Das , Ben Liblit , Manuel Fähndrich , Jakob Rehof, Estimating the Impact of Scalable Pointer Analysis on Optimization, Proceedings of the 8th International Symposium on Static Analysis, p.260-278, July 16-18, 2001
• 23: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.106-117, June 17-19, 1998, Montreal, Quebec, Canada
• 24: Nurit Dor , Michael Rodeh , Mooly Sagiv, CSSV: towards a realistic tool for statically detecting all buffer overflows in C, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 25: Eichin, M. W. and Rochlis, J. A. 1989. With microscope and tweezers: An analysis of the internet virus of November 1988. In Proceedings of the IEEE Symposium on Research in Security and Privacy. IEEE Computer Society Press, Los Alamitos, CA, 326--343.
• 26: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 27: Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su , Alexander Aiken, Partial online cycle elimination in inclusion constraint graphs, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.85-96, June 17-19, 1998, Montreal, Quebec, Canada
• 28: Manuel Fähndrich , Jakob Rehof , Manuvir Das, Scalable context-sensitive flow analysis using instantiation constraints, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.253-263, June 18-21, 2000, Vancouver, British Columbia, Canada
• 29: Christian Fecht , Helmut Seidl, An Even Faster Solver for General Systems of Equations, Proceedings of the Third International Symposium on Static Analysis, p.189-204, September 24-26, 1996
• 30: Christian Fecht , Helmut Seidl, Propagating Differences: An Efficient New Fixpoint Algorithm for Distributive Constraint Systems, Proceedings of the 7th European Symposium on Programming: Programming Languages and Systems, p.90-104, March 28-April 04, 1998
• 31: Flanagan, C. 1997. Effective static debugging via componential set-based analysis. Ph.D. dissertation. Rice University.
• 32: Cormac Flanagan , K. Rustan M. Leino , Mark Lillibridge , Greg Nelson , James B. Saxe , Raymie Stata, Extended static checking for Java, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 33: Jeffrey S. Foster , Manuel Fahndrich , Alexander Aiken, Flow-Insensitive Points-to Analysis with Term and Set Constraints, University of California at Berkeley, Berkeley, CA, 1997
• 34: Jeffrey S. Foster , Manuel Fähndrich , Alexander Aiken, A theory of type qualifiers, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.192-203, May 01-04, 1999, Atlanta, Georgia, United States
• 35: Jeffrey S. Foster , Manuel Fähndrich , Alexander Aiken, Polymorphic versus Monomorphic Flow-Insensitive Points-to Analysis for C, Proceedings of the 7th International Symposium on Static Analysis, p.175-198, June 29-July 01, 2000
• 36: Harold N. Gabow, Path-based depth-first search for strong and biconnected components, Information Processing Letters, v.74 n.3-4, p.107-114, May 2000 [doi>10.1016/S0020-0190(00)00051-X]
• 37: Rakesh Ghiya , Daniel Lavery , David Sehr, On the importance of points-to analysis and other memory disambiguation methods for C programs, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.47-58, June 2001, Snowbird, Utah, United States
• 38: Patrice Godefroid, VeriSoft: A Tool for the Automatic Analysis of Concurrent Reactive Software, Proceedings of the 9th International Conference on Computer Aided Verification, p.476-479, June 22-25, 1997
• 39: Mark Harman , David Binkley , Sebastian Danicic, Amorphous program slicing, Journal of Systems and Software, v.68 n.1, p.45-64, 15 October 2003 [doi>10.1016/S0164-1212(02)00135-8]
• 40: Rebecca Hasti , Susan Horwitz, Using static single assignment form to improve flow-insensitive pointer analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.97-105, June 17-19, 1998, Montreal, Quebec, Canada
• 41: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 42: Nevin Heintze , David McAllester, Linear-time subtransitive control flow analysis, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.261-272, June 16-18, 1997, Las Vegas, Nevada, United States
• 43: Nevin Heintze , David McAllester, On the Cubic Bottleneck in Subtyping and Flow Analysis, Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, p.342, June 29-July 02, 1997
• 44: Nevin Heintze , Olivier Tardieu, Demand-driven pointer analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.24-34, June 2001, Snowbird, Utah, United States
• 45: Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.254-263, June 2001, Snowbird, Utah, United States
• 46: Henzinger, T. A., Jhala, R., Majumdar, R., and Sutre, G. 2003. Software verification with Blast. In Proceedings of the Workshop on Model Checking Software. Lecture Notes in Computer Science, vol. 2648. Springer-Verlag, New York, 235--239.
• 47: 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]
• 48: Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999 [doi>10.1145/325478.325519]
• 49: Michael Hind , Anthony Pioli, Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses, Proceedings of the 5th International Symposium on Static Analysis, p.57-81, September 14-16, 1998
• 50: 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
• 51: Gerard J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, v.23 n.5, p.279-295, May 1997 [doi>10.1109/32.588521]
• 52: Susan Horwitz , Alan Demers , Tim Teitebaum, An efficient general iterative algorithm for dataflow analysis, Acta Informatica, v.24 n.6, p.679-694, November 1, 1987
• 53: ISO90 1990. ISO/IEC. international standard ISO/IEC 9899, programming languages - C.
• 54: Rob Johnson , David Wagner, Finding user/kernel pointer bugs with type inference, Proceedings of the 13th conference on USENIX Security Symposium, p.9-9, August 09-13, 2004, San Diego, CA
• 55: James A. Jones , Mary Jean Harrold , John Stasko, Visualization of test information to assist fault localization, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581397]
• 56: Jones, N. D. and Muchnick, S. S. 1981. Flow analysis and optimization of lisp-like structures. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliff, 102--131.
• 57: Kodumal, J. and Aiken, A. 2005. Banshee: A scalable constraint-based analysis toolkit. In Proceedings of the Static Analysis Symposium, SAS. Lecture Notes in Computer Science, vol. 3672. Springer-Verlag, New York, 218--234.
• 58: William Alexander Landi, Interprocedural aliasing in the presence of pointers, Rutgers University, New Brunswick, NJ, 1992
• 59: William Landi, Undecidability of static analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.323-337, Dec. 1992 [doi>10.1145/161494.161501]
• 60: Lhotak, O. and Hendren, L. J. 2003. Scaling Java points-to analysis using SPARK. In Proceedings of the Conference on Compiler Construction (CC). Lecture Notes in Computer Science, vol. 2622. Springer-Verlag, New York, 153--169.
• 61: Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.199-215, September 06-10, 1999, Toulouse, France
• 62: Donglin Liang , Maikel Pennings , Mary Jean Harrold, Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for Java, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.73-79, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379676]
• 63: Kathryn S. McKinley, Evaluating automatic parallelization for efficient execution on shared-memory multiprocessors, Proceedings of the 8th international conference on Supercomputing, p.54-63, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181265]
• 64: David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.74-89, June 12-13, 1997, Amsterdam, The Netherlands
• 65: 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
• 66: B. A. Myers, Visual programming, programming by example, and program visualization: a taxonomy, Proceedings of the SIGCHI conference on Human factors in computing systems, p.59-66, April 13-17, 1986, Boston, Massachusetts, United States
• 67: Flemming Nielson , Hanne R. Nielson , Chris Hankin, Principles of Program Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 68: Esko Nuutila , Eljas Soisalon-Soininen, On finding the strongly connected components in a directed graph, Information Processing Letters, v.49 n.1, p.9-14, Jan. 14, 1994 [doi>10.1016/0020-0190(94)90047-7]
• 69: Nystrom, E. M., Kim, H.-S., and Hwu, W.-M. W. 2004a. Bottom-up and top-down context-sensitive summary-based pointer analysis. In Proceedings of the Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 3148. Springer-Verlag, New York, 165--180.
• 70: Erik M. Nystrom , Hong-Seok Kim , Wen-mei W. Hwu, Importance of heap specialization in pointer 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.996836]
• 71: D. A. Padua , D. J. Kuck , D. H. Lawrie, High-Speed Multiprocessors and Compilation Techniques, IEEE Transactions on Computers, v.29 n.9, p.763-776, September 1980 [doi>10.1109/TC.1980.1675676]
• 72: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 73: Pearce, D. J. 2005. Some directed graph algorithms and their application to pointer analysis (online version available at http://www.mcs.vuw.ac.nz/djp). Ph.D. dissertation, Imperial College, London, United Kingdom.
• 74: Pearce, D. J. and Kelly, P. H. J. 2004. A dynamic algorithm for topologically sorting directed acyclic graphs. In Proceedings of the Workshop on Efficient and Experimental Algorithms (WEA). Lecture Notes in Computer Science, vol. 3059. Springer-Verlag, New York, 383--398.
• 75: David J. Pearce , Paul H. J. Kelly, A dynamic topological sort algorithm for directed acyclic graphs, Journal of Experimental Algorithmics (JEA), 11, 2006 [doi>10.1145/1187436.1210590]
• 76: Pearce, D. J., Kelly, P. H. J., and Hankin, C. 2003. Online cycle detection and difference propagation for pointer analysis. In Proceedings of the IEEE Workshop on Source Code Analysis and Manipulation (SCAM). IEEE Computer Society Press, Los Alamitos, CA, 3--12.
• 77: David J. Pearce , Paul H. J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis for C, 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.996835]
• 78: David J. Pearce , Paul H. J. Kelly , Chris Hankin, Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis, Software Quality Control, v.12 n.4, p.311-337, December 2004 [doi>10.1023/B:SQJO.0000039791.93071.a2]
• 79: G. Ramalingam, The undecidability of aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1467-1471, Sept. 1994 [doi>10.1145/186025.186041]
• 80: S. P. Reiss, Cacti: a front end for program visualization, Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis '97), p.46, October 18-25, 1997
• 81: Thomas W. Reps , Todd Turnidge, Program Specialization via Program Slicing, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.409-429, February 12-16, 1996
• 82: Reynolds, J. C. 1969. Automatic computation of data set definitions. In Proceedings of the Information Processing Congress (IFIP). Vol. 1. North-Holland, Amsterdam, The Netherlands, 456--461.
• 83: Atanas Rountev , Satish Chandra, Off-line variable substitution for scaling points-to analysis, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.47-56, June 18-21, 2000, Vancouver, British Columbia, Canada
• 84: Atanas Rountev , Ana Milanova , Barbara G. Ryder, Points-to analysis for Java using annotated constraints, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.43-55, October 14-18, 2001, Tampa Bay, FL, USA
• 85: Diptikalyan Saha , C. R. Ramakrishnan, Incremental and demand-driven points-to analysis using logic programming, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.117-128, July 11-13, 2005, Lisbon, Portugal [doi>10.1145/1069774.1069785]
• 86: Erik Schon, On the Computation of Fixpoints in Static Program Analysis with an Application to AKL, European Research Consortium for Informatics and Mathematics at SICS, 1995
• 87: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 88: Shmueli, O. 1983. Dynamic cycle detection. Inf. Proc. Lett. 17, 4 (Nov.), 185--188.
• 89: Byoungro So , Sungdo Moon , Mary W. Hall, Measuring the effectiveness of automatic parallelization in SUIF, Proceedings of the 12th international conference on Supercomputing, p.212-219, July 1998, Melbourne, Australia [doi>10.1145/277830.277876]
• 90: Manu Sridharan , Denis Gopan , Lexin Shan , Rastislav Bodík, Demand-driven points-to analysis for Java, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 91: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 92: Zhendong Su , Manuel Fähndrich , Alexander Aiken, Projection merging: reducing redundancies in inclusion constraint graphs, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-95, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325706]
• 93: SUIF2. The SUIF 2 research compiler Stanford University, Stanford, CA, http://suif.stanford.edu.
• 94: Tarja Systä , Ping Yu , Hausi Müller, Analyzing Java Software by Combining Metrics and Program Visualization, Proceedings of the Conference on Software Maintenance and Reengineering, p.199, February 29-March 03, 2000
• 95: Tarjan, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2, 146--160.
• 96: Robert K. Brayton , Gary D. Hachtel , Alberto L. Sangiovanni-Vincentelli , Fabio Somenzi , Adnan Aziz , Szu-Tsung Cheng , Stephen A. Edwards , Sunil P. Khatri , Yuji Kukimoto , Abelardo Pardo , Shaz Qadeer , Rajeev K. Ranjan , Shaker Sarwary , Thomas R. Shiple , Gitanjali Swamy , Tiziano Villa, VIS: A System for Verification and Synthesis, Proceedings of the 8th International Conference on Computer Aided Verification, p.428-432, August 03, 1996
• 97: Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.35-46, June 2001, Snowbird, Utah, United States
• 98: Wagner, D., Foster, J. S., Brewer, E. A., and Aiken, A. 2000. A first step towards automated detection of buffer overrun vulnerabilities. In Proceedings of the Network and Distributed System Security Symposium (NDSS). The Internet Society, 3--17.
• 99: John Whaley , Monica S. Lam, An Efficient Inclusion-Based Points-To Analysis for Strictly-Typed Languages, Proceedings of the 9th International Symposium on Static Analysis, p.180-195, September 17-20, 2002
• 100: 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
• 101: Robert Paul Wilson , Monica S. Lam, Efficient, context-sensitive pointer analysis for c programs, Stanford University, Stanford, CA, 1998
• 102: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 103: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1982
• 104: Suan Hsi Yong , Susan Horwitz , Thomas Reps, Pointer analysis for programs with structures and casting, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.91-103, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Algorithms, Languages, Theory, Verification

Keywords:
Set-constraints, pointer analysis