Learning Minimal Abstractions

• Published in: ACM SIGPLAN notices 2011-01, Vol.46 (1), p.31-42
• Main Authors: LIANG, Percy, TRIPP, Omer, NAIK, Mayur
• Format: Article
• Language: English
• Subjects: Applied sciences; Artificial intelligence; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Computer systems performance. Reliability; Exact sciences and technology; Software
• ISSN: 1523-2867; 0362-1340; 1558-1160
• DOI: 10.1145/1925844.1926391

Static analyses are generally parametrized by an abstraction which is chosen from a family of abstractions. We are interested in flexible families of abstractions with many parameters, as these families can allow one to increase precision in ways tailored to the client without sacrificing scalability. For example, we consider k-limited points-to analyses where each call site and allocation site in a program can have a different k value. We then ask a natural question in this paper: What is the minimal (coarsest) abstraction in a given family which is able to prove a set of queries? In addressing this question, we make the following two contributions: (i) We introduce two machine learning algorithms for efficiently finding a minimal abstraction; and (ii) for a static race detector backed by a k-limited points-to analysis, we show empirically that minimal abstractions are actually quite coarse: It suffices to provide context/object sensitivity to a very small fraction (0.4-2.3%) of the sites to yield equally precise results as providing context/object sensitivity uniformly to all sites.