Dynamic inference of abstract types

ABSTRACT

An abstract type groups variables that are used for related purposes in a program. We describe a dynamic unification-based analysis for inferring abstract types. Initially, each run-time value gets a unique abstract type. A run-time interaction among values indicates that they have the same abstract type, so their abstract types are unified. Also at run time, abstract types for variables are accumulated from abstract types for values. The notion of interaction may be customized, permitting the analysis to compute finer or coarser abstract types; these different notions of abstract type are useful for different tasks. We have implemented the analysis for compiled x86 binaries and for Java bytecodes. Our experiments indicate that the inferred abstract types are useful for program comprehension, improve both the results and the run time of a follow-on program analysis, and are more precise than the output of a comparable static analysis, without suffering from overfitting.

REFERENCES

• 1: Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism, Proceedings of the 9th European Conference on Object-Oriented Programming, p.2-26, August 07-11, 1995
• 2: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 3: Eric Allen , David Chase , Victor Luchangco , Jan-Willem Maessen , Guy L. Steele, Jr., Object-oriented units of measurement, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 4: C. C. Chang and C. J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 5: 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
• 6: Thomas Eisenbarth , Rainer Koschke , Daniel Simon, Locating Features in Source Code, IEEE Transactions on Software Engineering, v.29 n.3, p.210-224, March 2003 [doi>10.1109/TSE.2003.1183929 ]
• 7: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957 ]
• 8: Michael D. Ernst , Adam Czeisler , William G. Griswold , David Notkin, Quickly detecting relevant program invariants, Proceedings of the 22nd international conference on Software engineering, p.449-458, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337240]
• 9: Martin Erwig , Margaret M. Burnett, Adding Apples and Oranges, Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages, p.173-191, January 19-20, 2002
• 10: Cormac Flanagan , Matthew Flatt , Shriram Krishnamurthi , Stephanie Weirich , Matthias Felleisen, Catching bugs in the web of program invariants, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.23-32, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 11: Orla Greevy , Stephane Ducasse, Correlating Features and Code Using a Compact Two-Sided Trace Analysis Approach, Proceedings of the Ninth European Conference on Software Maintenance and Reengineering, p.314-323, March 21-23, 2005 [doi>10.1109/CSMR.2005.21]
• 12: Orla Greevy , Stephane Ducasse , Tudor Girba, Analyzing Feature Traces to Incorporate the Semantics of Change in Software Evolution Analysis, Proceedings of the 21st IEEE International Conference on Software Maintenance (ICSM'05), p.347-356, September 25-30, 2005 [doi>10.1109/ICSM.2005.22]
• 13: J. Henkel and A. Diwan. Discovering algebraic specifications from Java classes. In ECOOP, pages 431--456, July 2003.
• 14: I. Hofacker. Vienna RNA package. http://www.tbi.univie.ac.at/~ivo/RNA/.
• 15: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 16: A. Kennedy. Programming Languages and Dimensions. PhD thesis, University of Cambridge, April 1996.
• 17: A. Kuhn, O. Greevy, and T. Gîrba. Applying semantic analysis to feature execution traces. In PCODA, pages 48--53, Nov. 2005.
• 18: J. R. Larus and S. Chandra. Using tracing and dynamic slicing to tune compilers. Technical Report 1174, University of Wisconsin-Madison, Madison, WI, Aug. 26, 1993.
• 19: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 20: R. Milner. A theory of type polymorphism in programming. J. Comp. Syst. Sci., 17(3):348--375, 1978.
• 21: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 22: 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]
• 23: N. Nethercote and J. Seward. Valgrind: A program supervision framework. In RV, July 2003.
• 24: Robert Weeks O'Callahan , Jeannette Wing , Daniel Jackson, Generalized aliasing as a basis for program analysis tools, 2001
• 25: Robert O'Callahan , Daniel Jackson, Lackwit: a program understanding tool based on type inference, Proceedings of the 19th international conference on Software engineering, p.338-348, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253351]
• 26: Jeff H. Perkins , Michael D. Ernst, Efficient incremental algorithms for dynamic detection of likely invariants, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 27: Pascal Rapicault , Mireille Blay-Fornarino , Stephane Ducasse , Anne-Marie Dery, Dynamic Type Inference to Support Object-Oriented Reenginerring in Smalltalk, Workshop ion on Object-Oriented Technology, p.76-77, July 20-24, 1998
• 28: Thomas Reps , Thomas Ball , Manuvir Das , James Larus, The use of program profiling for software maintenance with applications to the year 2000 problem, Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.432-449, September 22-25, 1997, Zurich, Switzerland
• 29: David Saff , Shay Artzi , Jeff H. Perkins , Michael D. Ernst, Automatic test factoring for java, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101927]
• 30: S. A. Spoon and O. Shivers. Demand-driven type inference with subgoal pruning: Trading precision for scalability. In ECOOP, pages 51--74, June 2004.
• 31: 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]
• 32: Frank Tip, A Survey of Program Slicing Techniques., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 33: G. A. Venkatesh, Experimental results from dynamic slicing of C programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.197-216, March 1995 [doi>10.1145/201059.201062]
• 34: M. Weiser. Program slicing. IEEE TSE, SE-10(4):352--357, July 1984.
• 35: 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
• 36: Norman Wilde , Michael C. Scully, Software reconnaissance: mapping program features to code, Journal of Software Maintenance: Research and Practice, v.7 n.1, p.49-62, Jan.-Feb. 1995 [doi>10.1002/smr.4360070105]
• 37: W. Eric Wong , Swapna S. Gokhale , Joseph R. Horgan, Quantifying the closeness between program components and features, Journal of Systems and Software, v.54 n.2, p.87-98, Oct. 15 2000 [doi>10.1016/S0164-1212(00)00029-7 ]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques

General Terms:
Experimentation, Languages

Keywords:
C, C++, Java, abstract types, dynamic analysis, interaction, mixed-level analysis, type inference, units, values and variables