Dynamic inference of abstract types

December 12, 2006
Michael D. Ernst | MIT Computer Science and Artificial Intelligence Lab

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.

Speaker Details

Michael D. Ernst is Associate Professor in the MIT Electrical Engineering and Computer Science department and in the MIT Computer Science and Artificial Intelligence Lab. His primary technical interest is programmer productivity, encompassing software engineering, testing, verification, static and dynamic program analysis, compilation, and programming language design. However, he has also published in artificial intelligence, theory, and other areas of computer science. Ernst was previously a researcher at Microsoft Research.