Introspective analysis: context-sensitivity, across the board
Introspective analysis: context-sensitivity, across the board
复制标题
DOI：
10.1145/2594291.2594320
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Y. Smaragdakis;George Kastrinis;G. Balatsouras
中科院分区：
文献类型：
--
作者：
Y. Smaragdakis;George Kastrinis;G. Balatsouras
上下文敏感性是在点对点分析中增加精确度的主要方法，同时也希望也保持可扩展性。然而，经常通过上下文敏感分析的问题是它们是双模式的：要么精确地分析，以至于它仅操纵可管理的数据集，因此可以很好地缩放，或者分析很快就会在该分析处迅速脱轨。不精确的第一个迹象，并成为魔力命令的昂贵，鉴于该计划的规模，预期的是预期的。当前，没有任何方法可以在整个级别上以与上下文不敏感的分析相当的水平进行精确的上下文敏感分析（任何风味：呼叫点，对象或类型敏感的）比例。为了解决这个问题，我们提出了内省分析：一种以较小的精确费用消除其性能 - 涉及的行为，用于统一扩展上下文敏感分析的技术。内省分析由一个共同的适应性模式组成：首先执行对上下文不敏感的分析，然后使用结果来选择性地完善（即，分析上下文）的程序元素，不会在运行时间或空间中引起爆炸。技术挑战是适当地确定此类程序要素。我们表明，一种简单但有原则的方法可以非常有效，可用于以前完全无法到达的基准，以实现可扩展性（通常具有巨大的速度），以进行深层上下文敏感的分析。
Context-sensitivity is the primary approach for adding more precision to a points-to analysis, while hopefully also maintaining scalability. An oft-reported problem with context-sensitive analyses, however, is that they are bi-modal: either the analysis is precise enough that it manipulates only manageable sets of data, and thus scales impressively well, or the analysis gets quickly derailed at the first sign of imprecision and becomes orders-of-magnitude more expensive than would be expected given the program's size. There is currently no approach that makes precise context-sensitive analyses (of any flavor: call-site-, object-, or type-sensitive) scale across the board at a level comparable to that of a context-insensitive analysis. To address this issue, we propose introspective analysis: a technique for uniformly scaling context-sensitive analysis by eliminating its performance-detrimental behavior, at a small precision expense. Introspective analysis consists of a common adaptivity pattern: first perform a context-insensitive analysis, then use the results to selectively refine (i.e., analyze context-sensitively) program elements that will not cause explosion in the running time or space. The technical challenge is to appropriately identify such program elements. We show that a simple but principled approach can be remarkably effective, achieving scalability (often with dramatic speedup) for benchmarks previously completely out-of-reach for deep context-sensitive analyses.