Effective whole-program analysis in the presence of pointers

ABSTRACT

Understanding large software systems is difficult. Traditionally, automated tools are used to assist program understanding. However, the representations constructed by these tools often require prohibitive time and space. Demand-driven techniques can be used to reduce these requirements. However, the use of pointers in modern languages introduces additional problems that do not integrate well with these techniques. We present new techniques for effectively coping with pointers in large software systems written in the C programming language and use our techniques to implement a program slicing tool.First, we use a fast, flow-insensitive, points-to analysis before traditional data-flow analysis. Second, we allow the user to parameterize the points-to analysis so that the resulting program slices more closely match the actual program behavior. Such information cannot easily be obtained by the tool or might otherwise be deemed unsafe. Finally, we present data-flow equations for dealing with pointers to local variables in recursive programs. These equations allow the user to select an arbitrary amount of calling context in order to better trade performance for precision.To validate our techniques, we present empirical results using our program slicer on large programs. The results indicate that cost-effective analysis of large programs with pointers is feasible using our techniques.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Darren C. Atkinson , William G. Griswold, The design of whole-program analysis tools, Proceedings of the 18th international conference on Software engineering, p.16-27, March 25-29, 1996, Berlin, Germany
• 3: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199461]
• 4: 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
• 5: J. I. Gobat and D. C. Atkinson. The FElt system: User's guide and reference manual. Computer Science Technical Report CS94-376, University of California, San Diego, Department of Computer Science 8s Engineering, 1994.
• 6: William G. Griswold , Darren C. Atkinson, Managing design trade-offs for a program understanding and transformation tool, Journal of Systems and Software, v.30 n.1-2, p.99-116, July/Aug. 1995 [doi>10.1016/0164-1212(94)00119-8]
• 7: Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.104-115, October 12-15, 1995, Washington, D.C., United States
• 8: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 9: Jens Knoop , Bernhard Steffen, The Interprocedural Coincidence Theorem, Proceedings of the 4th International Conference on Compiler Construction, p.125-140, October 05-07, 1992
• 10: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.56-67, June 21-25, 1993, Albuquerque, New Mexico, United States
• 11: M. M. Lehman , L. A. Belady, Program evolution: processes of software change, Academic Press Professional, Inc., San Diego, CA, 1985
• 12: Gleb N. Naumovich , Lori A. Clarke , Leon J. Osterweil, Verification of communication protocols using data flow analysis, Proceedings of the 4th ACM SIGSOFT symposium on Foundations of software engineering, p.93-105, October 16-18, 1996, San Francisco, California, United States
• 13: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 14: Erik Ruf, Context-insensitive alias analysis reconsidered, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.13-22, June 18-21, 1995, La Jolla, California, United States
• 15: Marc Shapiro, II , Susan Horwitz, The Effects of the Presision of Pointer Analysis, Proceedings of the 4th International Symposium on Static Analysis, p.16-34, September 08-10, 1997
• 16: 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]
• 17: Bjarne Steensgaard, Points-to Analysis by Type Inference of Programs with Structures and Unions, Proceedings of the 6th International Conference on Compiler Construction, p.136-150, April 24-26, 1996
• 18: 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]
• 19: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 20: M. Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, July 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

General Terms:
Design, Languages, Measurement, Performance, Theory